Questions tagged [hash]
Mathematical function that maps arbitrarily-sized data to fixed-size integers, often used as keys in hash tables or to help ensure data integrity
325
questions
0
votes
0
answers
21
views
If the data that I input for locality sensitive hashing is sensitive, should its resulting hash also be considered sensitive?
Is it correct to assume that if the input that I hash is sensitive, that I should also consider the locality-sensitive hash generated for that input to be sensitive? I presume that, if an attacker has ...
- 121
0
votes
0
answers
13
views
Universal hash functions and prime number modulus scheme
Definition of a universal hashing function $h: U \rightarrow[m]$ (where $[m]=\{0, \ldots, m-1\}$) is that for any given distinct keys $x,y \in U$, when $h$ is picked at random (independently of $x$ ...
- 101
0
votes
1
answer
13
views
Reversible computing as a path to a useful PRNG or hash function?
There's a question I've long had about reversible computing: do non-trivial algorithms usually end up generating strongly pseudorandom data as an artifact of the computation?
The most straightforward ...
- 284
4
votes
1
answer
65
views
Self referential hash function possible?
Is there a hashing function $f$ that for each input $x$ if $f(x) = y$, then $f(x \, || \, y) = y$? In other words, if we concatenate its output with the input, the result will not change.
Furthermore, ...
- 93
1
vote
2
answers
89
views
Perfect ordered hash function on ordered sequence
I have a sequence of integer tuples $t_1, t_2,..., t_N$ of different sizes in lexicographic order, e.g.:
$(1, 1), (1, 2), (1, 3, 5), (1, 3, 6), (1, 5), (3), (3, 2, 3), (3, 7), (3, 8, 1), ...$
...
- 287
1
vote
0
answers
20
views
How to properly save Zobrist Keys?
In a project of mine, I want to represent states as efficiently as possible. Initially, I went ahead with a BitBoard representation and some clever tricks to speed up the evaluation of the game tree. ...
- 111
0
votes
0
answers
32
views
In the complexity of open addressing, why it is necessary take the sum to $\infty$?
When estimating the average calculation complexity of open addressing,
I found following explanation:
Let $B$ be the number of backets and $N$ be the number of elements already in the hash table.
The ...
- 1
1
vote
1
answer
71
views
Perfect hash function that weakly preserves leading zeros
I need a perfect hash function that maps 2 integers into one integer twice the size (i.e. $(Int64, Int64) \rightarrow Int128$).
The function preserves sum of leading zero bits:
$(0, 0) \rightarrow 0$ ...
- 287
0
votes
1
answer
104
views
Simple Uniform hashing with chances of no collision
I know that if I have $n$ different values in an array of size $m$ (where $m>n$) under simple uniform hashing, the average probability of the total number of collisions is:
$$\sum_{i=1}^{n-1}\frac{...
- 33
1
vote
2
answers
92
views
Order-preserving hashtable for integer tuples
There are integer tuples which index cells of a sparse multi-dimensional array (points inside n-parallelepiped), $n \le 32$.
The array itself is a BST with keys formed as $key = (...((a_0 * S_1 + a_1) ...
- 287
1
vote
2
answers
86
views
How to use a worst case scenario in Rolling Hash: Rabin Karp Algorithm when the given string only contains the occurrences of "a and b?"
Issue: I am having a hard time figuring out how to use the worst case for Rolling Hash, especially if the occurrences are only "a and b" for the string. Not only that but it is a bit of a ...
- 13
0
votes
0
answers
9
views
How to locate the element with universal hash after inserction
I'm new to algorithm and recently finish a coursera video about universal hash. But I'm a little confused here.
(1)If the hash function is chosen randomly from a universe, how could we locate the ...
0
votes
0
answers
47
views
Why using nC2*1/365 to calculate the birthday paradox is incorrect
The birthday paradox is basically that assume there are 365 days in a year(ignore the effect of Febuary 29th), each person's birthday is uniformly random in these 365 days and independent with others. ...
0
votes
2
answers
50
views
Is there any algorithm to find all unique pairs of People with age equal to a given number in less than O(n²)
I have a problem where I have to find all the pairs of a list of People where the sum of their age is equal to a given number under time complexity less than
O(N²)
...
1
vote
1
answer
29
views
Sampling unique records from a large dataframe
Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe?
Some sort of sampling algorithm?
- 11
0
votes
1
answer
51
views
Universal family of hash functions — dependent on table size?
Given the following family of hash functions:
$$
\mathbb{H} = \{h_c(x) = (12x + c) \bmod
m \mid c \in \mathbb{N} \},
$$
where $m$ is the key size.
Prove that $\mathbb{H}$ is not a universal ...
- 1
-5
votes
1
answer
379
views
Implementing Flajolet–Martin algorithm in Python
I am stuck on what to do.
I am trying to create a simple implementation of the Flajolet–Martin algorithm using Python. The stream will be the contents of a text file and you will produce an ...
0
votes
2
answers
144
views
the load factor in hash table
What is numerically the best value or range of values used as a reference for the load factor used in the hash table?
What is the pseudo-code of the “rehashing” method, which is applied when many ...
- 9
1
vote
1
answer
223
views
Hash / Compression algorithm to shorten text?
I desperately need a hash / compression function that is suited to shorten text.
The context is this: I want to bring order and sort my box with hundreds of charging adapters (duh). After I determined ...
- 31
0
votes
1
answer
112
views
Consistent Hashing Algorithm Without Distribution / Load Balancing
I need some help finding or creating a consistent hashing algorithm with the following properties:
Given N buckets, only distributes keys to bucket N.
When number of buckets are increased from N to N+...
- 61
1
vote
2
answers
481
views
Averege time complexity of open addressing
I get that it depends from the number of probes, so by how many times the hash code has to be recalculeted, and that in the best case there will only be one computation of the hash code and the ...
- 115
1
vote
0
answers
37
views
Where does 2^32 come from with bitcoin?
Several months ago I was doing research into calculating mining revenue for several crypto currencies. When trying to calculate BTC revenue I found this value 1/2^32 which was described somewhere ...
- 51
2
votes
1
answer
54
views
How do these Crypto terms relate to each other and what do they all mean?
Alright this is another day of my pursuit to learn about how crypto works. I have several terms that I have found linked together. I was trying to do research on how the Target Hash is determined and ...
- 51
0
votes
2
answers
41
views
What happens in the event of a collision in a crypto hash function?
I was reading about hash functions in crypto and a website had mentioned that they were collision free, which obviously isn't possible if there are infinite input values that are mapped to outputs of ...
- 51
1
vote
0
answers
21
views
Algorithm Complexity Question
this is my first question on this site and I would like to preface this by saying I am not very savvy when it comes to Computer Science. So, I will try to ask this the best I can.
I was doing some ...
- 51
1
vote
1
answer
37
views
Locality Sensitive Hashing for Sets
Are there locality sensitive hashes that work nicely with sets? Each set would get a hash, the order of the elements in the set does not change the hash, and sets that share more elements are closer ...
2
votes
1
answer
61
views
Splitting the output of a wide hash in lieu of multiple independent hashes
Certain algorithms require two independent hash functions. An optimization I've seen is to split the output of a wide hash function and use the parts instead of the two independent hash functions of ...
- 21
1
vote
1
answer
143
views
Optimal parameters for a Bloom filter
My first question here. Please do not judge me much if this is a too simple.
Some text consists of $n=12\,500$ distinct words. I would like to construct a Bloom filter with $\epsilon=10^{-2}$ ...
- 125
0
votes
1
answer
26
views
Confused about the appropriate slot in linear probing
The following paragraph is from the book CLRS:
Given an ordinary hash function $h' : U \rightarrow \{0, 1, ..., m - 1\}$, which we refer to as an auxiliary hash function, the method of linear probing ...
- 411
1
vote
1
answer
37
views
Fingerprint functions for set equality checks?
Given I have two sets of objects $A =\{a, b, c\}$ and $B = \{a, b, c, a\}$
Based on the set equality, I want the fingerprint of these sets to be the same $F(A) = F(B)$.
Additionally I want to be able ...
- 123
2
votes
1
answer
100
views
Analysis of a calculation of expected number of collisions in hashing
For a formal problem statement, I quote from the text Introduction to Algorithms by Cormen et. al
Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. ...
- 1,042
0
votes
1
answer
62
views
Finding a hash function, so that the set of hash functions is universal
Problem:
Let $U = \{0,1,2,3,4,5\}$ be a universe of keys and $T = \{0,1,2\}$ we observe follwing 5 hash functions which map from $U$ to $T$ :
$$h_1(x) = (x+1) \mod{3} \hspace{5mm} h_2(x) = (x+2) \mod{...
- 25
0
votes
3
answers
132
views
How do i delete one single unequal element from an array of equal elements without using hashing?
The rules of the question state that:
Only one element is different.
Rest are all same.
Array A size is 8.
I need to find the different element and remove it (Hashing cannot be used).
I have not ...
1
vote
1
answer
53
views
How to efficiently see if a value is in a set
I was curious is there a really efficient way to see if a value is in a set? This question comes from me thinking about youtube views. As far as I understand youtube view count goes up for every ...
- 113
3
votes
1
answer
160
views
A question about hash problems in CLRS book
Consider the following problem 11.2-6 from CLRS book:
Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, ...
- 323
1
vote
1
answer
142
views
A hash function for a 2D hash table with a scattering property?
I have an $n\times n$ matrix, and want to find a bijective function $h:[n^2] \to [n]\times [n]$ that can act as a hash function to map the numbers 1 through $n^2$ to row/column indices in my matrix. ...
- 11
1
vote
0
answers
47
views
Check if string contains pattern (with respect to one-to-one symbols mapping) [closed]
I'm trying to solve following problem:
Check, if the string contains substring, that can be obtained from pattern using one to one lower case symbols replacement (using bijection between original ...
1
vote
1
answer
84
views
Expected Lookup Length in Open Addressing Hash Table with Simple Uniform Hashing
In several proofs of the expected lookup length in an open addressing hash table, an assumption is made (which is said to follow from the "simple uniform hashing assumption":
Given a hash ...
- 113
0
votes
1
answer
53
views
What are the chances of hash collision given large input and small hash?
I have an input of 128 bits (binary, 0s and 1s) and want to hash this input with 32 bit CRC. But I am not sure if collision rate is moderate or too high ?
Is it 2^128/2^32 = 2^98.
And does that ...
- 35
1
vote
0
answers
44
views
Finding a full collision within a large array
I apologize for the vagueness of the title, but this question is quite difficult for me to describe.
For that reason, I'm unable to directly convey my problem.
In an effort to circumvent this, I've ...
- 11
0
votes
1
answer
385
views
hash-tables - Expected-time for an unsuccessful search
The following question is from MIT-OCW 6.006, Spring-2008, Problem-Set 2, Q-3.c.
Suppose you have a hash table where the load-factor $\alpha$ is related to the number $n$ of elements in the table by ...
- 101
1
vote
0
answers
33
views
Average-case retrieval time
The book CLRS claims these statements before introducing the topic of universal hashing:
If a malicious adversary chooses the keys to be hashed by some fixed hash function,
then the adversary can ...
- 411
2
votes
1
answer
204
views
Quadratic probing variant scheme
Suppose that we are given a key $k$ to search for in a hash table with positions $0, 1, \dots , m-1$, and suppose that we have a hash function $h$ mapping the key space into the set $\{0, 1, \dots , m-...
- 481
1
vote
1
answer
248
views
If $(h_2(k),m) = 1$ then $h_1(k)+ih_2(k) \bmod{m}$ is a permutation of $0,\ldots,m-1$
The following question appears in Introduction to Algorithms (CLRS):
Suppose that we use double hashing to resolve collisions; that is, we use the hash function $ h(k, i) = (h_1(k) + ih_2(k)) \bmod{m}...
- 481
0
votes
1
answer
28
views
Can possiblity of hash collision be "zero" when we hash same file in different formats?
Let's say I have a file A, which is any normal file (pdf, jpeg, mp3 etc.)
Now I get the binary dump of file, say another file B{A}.
And the hexdump of file say, file H{A}.
Now I hash all the three ...
- 35
1
vote
1
answer
397
views
Number of probes in a unsuccessful search in open address hashing
Theorem: Given an open-address hash table with load factor $α = n/m < 1$, the expected number of probes in an unsuccessful search is at most $1/(1−α)$, assuming uniform
hashing.
Let us define the ...
- 481
1
vote
1
answer
83
views
Can one brute force entries to create the whole file?
I want to know if one can brute-force a large list of entries (>10,00,000) in linear time to form a whole file.
For example:
I have an ebook and i extract all the words and symbols from that ebook....
- 35
1
vote
1
answer
70
views
Prove that the expected length $E [n_{h(k)}]$ of the list containing key $k $ is at most $1 + \alpha$
Theorem: Suppose that a hash function $h$ is chosen from a universal collection of hash functions and is used to hash n keys into a table $ T$ of size $m$, using chaining to resolve collisions. If key ...
- 481
0
votes
2
answers
93
views
Can 2 files have "same" "many" "different" types of hash?
I know that hash collision is possible with large number of files. But i want to know if 2 files can share "many , different" types of hash. I have 2 hashes SHA256 and BLAKE256 (Both will ...
- 35
2
votes
0
answers
205
views
Proving that a successful search of hash function is $\Theta(1+\alpha)$
Question: Prove that successful search of hash function with chaining (list at each slot) takes $\Theta(1+\alpha)$.
Given a dictionary or hash table that has a chain at each slot in case we have a ...
- 481