47
votes
Accepted
What exactly (and precisely) is "hash?"
The Wikipedia article on hash functions is very good,
but I will here give my take.
What is a hash?
"Hash" is really a broad term
with different formal meanings in different contexts.
There ...
- 4,099
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
11
votes
What exactly (and precisely) is "hash?"
A hash function is a function that takes an input and produces a value of fixed size. For example you might have a hash function stringHash that accepts a ...
- 301
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
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
Accepted
Two-way Hash Functions
Yes, this is possible. Here are two examples of such a function.
One function is $f(x)=x$. This has no collisions, and the function is easy to invert.
Here is another function: define $f(x) = x$ ...
D.W.♦
- 156k
6
votes
Accepted
Hash functions and pathological data sets
An easy way to visualize this is to imagine a hash table of size $n$ (implemented with chaining) that contains all of the elements of $U$ (even though this is unrealistic in practice because $U$ ...
- 3,674
6
votes
Accepted
Understanding hashtable performance in the worst-case
The load factor denotes the average expected length of a chain, therefore it is interesting for an average case analysis, not the worst case analysis. That's why on average you expect needing constant ...
6
votes
Can we remove duplicates faster than we can sort?
It is a classical result that the element distinctness problem requires $\Omega(n\log n)$ comparisons in the comparison model (the one used to analyze sorting algorithms); in fact, it also requires $\...
- 275k
5
votes
simple uniform hashing: unclear definition of probability
First, the outcome of a situation being deterministic doesn't mean we will necessarily assign a probability of $1$ or $0$ to it. If I say I'm going to flip a coin, but it is actually a double-sided ...
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
Difference between properties of good hash function: uniformity and randomness
Uniformity is about potential values, while randomness is about actual values.
For example, suppose you make a very simple hash function that takes the first byte of a string, resulting in 256 ...
4
votes
Merkle tree collision probability
Yes, the root has a higher probability of collision.
Take, for example, simple trees with two leaves. Label tree 1's leaves $A$ and $B$, and tree 2's leaves $X$ and $Y$.
The probability that the ...
- 3,310
4
votes
Finding a (minimal?) program that maps $M$ items to indices $[0,M)$
There is a deterministic algorithm for constructing a perfect hash, if you don't care about efficiency. For instance, you can enumerate all programs (in order of increasing size) and test each one to ...
D.W.♦
- 156k
4
votes
Accepted
Why Bloom filter needs $\frac{m}{n}\ln{2}$ hash functions?
This is explained in Wikipedia. Given $n,m$, the false positive probability is
$$
\left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k.
$$
This is the quantity we want to minimize. While the exact ...
- 275k
4
votes
Fast comparison with a tolerance
If for all $|r - s| < 1$ it is the case that $K(r) = K(s)$ then $K$ is constant (exercise).
What you are asking is impossible.
One thing which is possible is to compare keys with three rather ...
- 275k
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
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
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
Hash functions and pathological data sets
Assume there is no such bucket. Then each bucket has at most $|U|/n - 1$ items. There are $n$ buckets, so the total number of items is at most $n*(|U|/n - 1) = |U| - n$. This is less than $|U|$, which ...
- 3,310
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
Ketama hash explanation
This is simply a way to generate 32-bit hash for the string.
Assuming that MD5 is a good cryptographic hash function, it doesn't matter which bits you take from the hash and in which order you ...
- 1,028
4
votes
is modulo of hash function is evenly distributed?
if I take the result of a 32bit hash function(the param is random string) and apply module N on the result - will the values be evenly distributed?
It depends on the hash function. For a good hash ...
- 13.2k
3
votes
Accepted
Locality-sensitive hashing random projection
No. The statement you're reading is correct. Try working through an example (in 2 dimensions, i.e., $d=2$); pick specific values of $v$ and $r$, draw them on the picture, and see what happens. The ...
D.W.♦
- 156k
3
votes
Hash function to hash 6-digit positive integers
A hash function cannot avoid collisions when the size $M$ of the hash table is smaller than the size of the universal set $U$ that you are hashing. This is a consequence of the compression step. In ...
- 3,674
3
votes
Hash function to hash 6-digit positive integers
A hash table usually uses two different things: One, a hash function that maps an item to a hash code (with the requirement that equal items are mapped to equal hash codes), and two, a function that ...
- 28.4k
3
votes
What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$
The mean chain length is the sum of the chain lengths divided by the number of chains. The sum of the chain lengths is, by definition $n$ and the number of chains is $m$. This is by far the easiest ...
- 21.7k
3
votes
Hash function to hash 6-digit positive integers
I think you've missed the point of hash tables. Hash tables are used to give array-like access to a dataset that's too big and sparse to store in an array. So, for example, it sounds like you're ...
- 81.4k
3
votes
Accepted
Given a string, is it possible to determine which hashing algorithm has produced it, if any?
You will first need to define what you mean by a hashing algorithm. For example, my favorite hashing algorithm is simple: check whether the input is "string", and if so, output "...
- 4,282
3
votes
Given a string, is it possible to determine which hashing algorithm has produced it, if any?
No it is not possible to determine that is produced by a hashing algo, or which one that produced it -- at least not from a single sample.
Good hashing algo will produce a uniform set of values ...
- 209
Only top scored, non community-wiki answers of a minimum length are eligible