# Probability of hash collision in the case of two parallel hashes

I understand how to calculate the probability of a hash collision.

I am designing a DB and have a potential case where a record could have the inherited hash of its parent plus its own hash, meaning I could potentially query two hashes to determine probable record matches.

If I have 1 billion records, a 64-bit hash will have $\sim 1:32.5$ collisions. If I have two by 64-bit hashes, how many effective bits will I have?

65-bits seems pessimistic, 128-bits seems optimistic. $\sim 32.5^2$ results in a fraction over 69 bits hash resolution.

How do I calculate this?

ILLUSTRATION

Parent Table

parent id, $\{$ field $1$, field $2$, ... field $n \}\implies$ parent hash

Child Table

child id, parent id, parent hash, $\{$ field $1$, field $2$, ... field $n \}\implies$ child hash

As illustrated, the child table has both parent hash and child hash. Two by 64-bit hashes.

• If you have two 64-bit independent hashes, then you have a 128-bit hash. – Yuval Filmus Dec 30 '17 at 8:52
• I still don't understand what you do. For each element, you compute two hashes, and then a collision occurs when both hashes agree? If so, then unless you're trying to foil this scheme on purpose, it's like using a hash which is double the size. – Yuval Filmus Dec 30 '17 at 9:26
• If $h$ is an $n$-bit hash and $x \neq y$, then $\Pr[h(x) = h(y)] = 2^{-n}$. – Yuval Filmus Dec 30 '17 at 9:34
• I strongly suggest that you forget about the formula and instead focus on how to obtain this formula yourself. Plugging values into a formula you don't understand is the best way to make errors. – Yuval Filmus Dec 30 '17 at 9:53
• Comments are not for extended discussion; this conversation has been moved to chat. – D.W. Dec 30 '17 at 20:32

You can think of concatenating the two hash values and treating the result as a single hash. Then you have $n$ records, each of which has a single hash. The probability of a collision among $n$ hashes is roughly $n^2/2^{b+1}$, if the hash outputs a $b$-bit value. In your case if each of the two individual hashes is 64 bits long, after concatenation you have a 128-bit hash for the record, so $b=128$.

How did I obtain the formula $n^2/2^{b+1}$? It's an application of the birthday paradox, with $n$ people born on a planet that has $2^b$ days in the year (instead of 365 days). Or, if you prefer an intuitive argument: think of all ways to pick a pair of $b$-bit hashes. There are about $n^2/2$ pairs of hashes. For each one, there's a $1/2^b$ probability that those pair of hashes are equal (that they collide). So the total probability that at least one of these collide is about $n^2/2$ times $1/2^b$. This is a crude estimate that isn't totally accurate, but it turns out to be a reasonable approximation as long as $n^2/2$ is fairly small compared to $2^b$.

The distribution of hash collision lengths is binomial, but for a large enough problem, it's easier to use a Poisson distribution.

Suppose you are inserting $m$ pigeons into $n$ pigeonholes. Denote the load factor $\lambda = \frac{m}{n}$. Then for large enough $n$, the expected proportion of pigeonholes which receive $k$ pigeons is roughly:

$$\textit{Poiss}(\lambda; k) = \frac{e^{-\lambda} \lambda^k} {k!}$$

The expected number of pigeons which get their own pigeonhole is:

$$n \, \textit{Poiss}(\lambda; 1) = m e^{-\frac{m}{n}}$$

And so the expected number of pigeons who have to share a pigeonhole is:

$$m (1 - e^{-\frac{m}{n}})$$

Plugging in your numbers, for $m = 10^9$ and $n = 2^{64}$, you would expect roughly $0.05$ items to be involved in a collision. For $m = 10^9$ and $n = 2^{128}$, the expected number of items to be involved in a collision is $3 \times 10^{-21}$.

One useful rule of thumb comes from the observation that there is a 50% chance of one or more collisions when $m (1 - e^{-\frac{m}{n}}) = 1$. (Remember, you need two items for an actual collision, so setting the expected number of items involved to 1 gives you half a collision.)

Using the approximation $e^{-x} \approx 1 - x$, we find $m \approx \sqrt{n}$. So if you have $n$ possible hash values, you have a 50% probability of one or more collisions after hashing $\sqrt{n}$ items.

This estimate is reasonably accurate for $n>10$ or so. In your case, there are $2^{64}$ possible hash values, so there will be a 50% probability of one or more collisions after inserting around $2^{32}$ items.