126
votes
Accepted
Why is it best to use a prime number as a mod in a hashing function?
Consider the set of keys $K=\{0,1,...,100\}$ and a hash table where the number of buckets is $m=12$. Since $3$ is a factor of $12$, the keys that are multiples of $3$ will be hashed to buckets that ...
- 3,674
24
votes
Accepted
Why is a (collision-less) hashtable lookup really O(1)?
The hash function doesn't return some string such as mkwer. It directly returns the position of the item in the array. If, for example, your hash table has ten ...
- 81.4k
22
votes
Do passwords need a max length?
No. There is no* limit on the length of the input to for most* good cryptographic hash functions. As a result, password hashing can support passwords of unlimited length and do not need to impose a ...
D.W.♦
- 156k
13
votes
Accepted
What is the point in hashing a value?
The purpose of a hash in this scenario to be able to uniquely identify an entity. It's not strictly unique, only probabilistically unique.
Hashes are not reversible functions, so your client can't ...
- 653
10
votes
Accepted
1-to-1 cryptographically secure bit shuffling
This is known as a one-way permutation. The "permutation" refers to the first of your two requirements; the "one-way" refers to the second of your two requirements. There are various candidate ...
D.W.♦
- 156k
9
votes
Accepted
Hashing using Horner’s Rule
Let's prove by induction that after $i$ iterations,
$$
r = \sum_{j=1}^i 256^{i-j} c[j] \bmod m,
$$
where $m$ is the size of the table.
The base case is $i = 0$, where $r = 0 = 0 \bmod m$. Now suppose ...
- 275k
9
votes
Do passwords need a max length?
Yes, passwords need maximum length, but not because of collision risk (see other answers regarding collisions).
Reason for setting maximum length - possibility of denial of service attack.
Someone ...
- 191
9
votes
Accepted
Are there associative cryptographic / collision resistant hashes?
There is a plausible construction of such a hash. At design time, randomly choose two $2\times 2$ matrices with entries in $\mathbb{F}_{2^n}$ that have determinant 1, fix them, and call them $h(0),h(...
D.W.♦
- 156k
8
votes
Do passwords need a max length?
As hashes are fixed length, does that mean that even if not specified when creating the password, all login systems would need to have some sort of maximum input length (although probably very high)?
...
- 191
7
votes
Why is a (collision-less) hashtable lookup really O(1)?
Hash function calculates array position from given string. If this is perfect hash it means that there are for sure no collisions, the most probably array is at least twice bigger than number of ...
- 9,425
7
votes
Accepted
Building static hash table with particular collisions
The easiest way is to construct a static hash table $T$ containing all the collisions, in the following form: for each set of keys $S$ which are supposed to map to the same value, single out some $x \...
- 275k
7
votes
Accepted
Hash-Table in Practice
SHA1 or SHA256, whichever you use, is for any practical purpose a random function. What you are observing is that random allocation is not as good as deterministic allocation. If you knew all the ...
- 275k
7
votes
Accepted
Does this problem offer any insight into $P$ vs $NP$
It depends what your hash function is. If your hash function is the identity function, it's trivial to invert without constructing the hash table.
Your question seems to be essentially reinventing ...
- 81.4k
6
votes
Accepted
Is the following intuition valid for understanding $k$-wise independent hash functions?
Your intuition is exactly right. Yes, that's equivalent to choosing a random polynomial over $\mathbb{F}_p$. The reason why it works is exactly the interpolation theorem for finite fields.
$k$-wise ...
D.W.♦
- 156k
6
votes
Accepted
What is the reasoning behind magic constancs in hash code calculations found in programming practice?
XOR is not a good method, because then the hash of $(a,b)$ will be equal to the hash of $(b,a)$. Also, the hash of $(a,a,c)$ will be equal to the hash of $(b,b,c)$ and to the hash of just $c$. That'...
D.W.♦
- 156k
6
votes
Why is Big O not defined here for a hash table?
The chart is underspecified. I assume they mean by "Access" to "retrieve the $i$-th element¹.
In hashtables, there is no notion of order. While you could pick the $i$-th element in the underlying ...
- 72k
5
votes
Why is it best to use a prime number as a mod in a hashing function?
First of all, the question is phrased incorrectly. The following are equivalent and correct expressions of the intended question:
why must we use a prime number as the modulo of the hash value (not "...
- 51
5
votes
Accepted
What is an example of a weakly universal hash function that is not pairwise independent?
Let $U = [m]$, and let $h$ be the identity function.
If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by
$$
h_i(x) = \begin{...
- 275k
5
votes
How do you find a hash function that respects a custom equality function?
The way I can think of to do this is by some sort of normalization: that is, you need to find a function $f$ such that, if $\equiv$ is your custom equality and $==$ is the normal C++ (or whatever ...
- 29.7k
4
votes
Accepted
Understanding Murmur3
You have asked two questions. I will answer them one by one.
Choosing the seed. The usual approach here is to choose the seeds randomly once and for all, and to hard-code them. If the hash family is ...
- 275k
4
votes
Why is a (collision-less) hashtable lookup really O(1)?
To expand on David Richerby's answer, the term "hash function" is a little overloaded. Often, when we talk about a hash function we think of MD5, SHA-1, or something like Java's ...
- 173
4
votes
Accepted
Two definitions of universal hash functions
The two definitions are not equivalent. The second definition does not imply the first. You can take $\mathcal{H}$ to be the collection of all functions $h$ such that $h(1) = 1$.
- 275k
4
votes
What Exactly Does the Term "Key" Mean with Regards to a Hash Table?
A hash table is an implementation of a more general principle: A key/value table. In a key/value table you can insert values according to a key, you cannot add two values under the same key. You can ...
- 28.4k
4
votes
Accepted
Embedding high dimensional vectors into low dimensional space preserving similarity
Locality-sensitive hashing is one reasonable approach for this. I suggest reading standard resources on locality-sensitive hashing (LSH). In your case, a locality-sensitive hash is a hash function ...
D.W.♦
- 156k
4
votes
Accepted
Hash multiple integers directly using FNV-1a
It's not equivalent, and I suspect there will be a loss of statistical randomization/mixing.
The core step that offers mixing of the bits is multiplication by ...
D.W.♦
- 156k
4
votes
"Hash" Probing?
Your scheme is very similar to Cuckoo Hashing. In Cuckoo Hashing you have two (or, in variations, more) independent hash functions $h,g$. To insert an item $x$ you check at location $h(x)$. If that ...
- 5,931
4
votes
Accepted
How similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work?
I can see some similarity too, but only in a loose sense; there are also some significant differences.
Here's the similarity. Define $H_2(x)$ to be the first $d$ bits of $H(x||D)$. Then you can ...
D.W.♦
- 156k
4
votes
Accepted
Knuth's proof of O(1) for linear probing
Let $p_i$ be the probability that position $i$ is empty. A simple coupling (detailed below) shows that $p_i = p_j$ for all $i,j$, and so $Mp_0 = p_0 + \cdots + p_{M-1}$. Now let $X_i$ be the indicator ...
- 275k
4
votes
Accepted
range / interval query algorithm
Use an interval tree. It is designed to support exactly this. In particular, the query "find all ranges that contain this value" is known as a stabbing query, and it can be answered in essentially $O(...
D.W.♦
- 156k
4
votes
Accepted
Surprisingly high collision rates when hashing a short list with few buckets
Depending on how you count collisions, we can expect either about 2000 collisions, or about 1472 collisions. The latter is in close agreement with what you observe, so yes, 1500 collisions looks ...
D.W.♦
- 156k
Only top scored, non community-wiki answers of a minimum length are eligible