0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ If you have two 64-bit independent hashes, then you have a 128-bit hash. $\endgroup$ – Yuval Filmus Dec 30 '17 at 8:52
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 30 '17 at 9:26
  • 1
    $\begingroup$ If $h$ is an $n$-bit hash and $x \neq y$, then $\Pr[h(x) = h(y)] = 2^{-n}$. $\endgroup$ – Yuval Filmus Dec 30 '17 at 9:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 30 '17 at 9:53
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Dec 30 '17 at 20:32
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.