Probability of hash collision

Let’s imagine we have a truly random hash function that hashes from strings to n-bit numbers. This means that there are 2ⁿ possible hash codes, and each string’s hash code is chosen uniformly at random from all of those possibilities.

The birthday paradox specifically says that once you’ve seen roughly √(2k) items, there’s a 50% chance of a collision, where k is the number of distinct possible outputs. In the case where the hash function hashes to an n-bit output, this means that you’ll need roughly 2^n/2 hashes before you get a collision. This is why we typically pick hashes that output 256 bits; it means that we’d need a staggering 2¹²⁸ ≈10³⁸ items hashed before there’s a “reasonable” chance of a collision. With a 512-bit hash, you’d need about 2²⁵⁶ to get a 50% chance of a collision, and 2²⁵⁶ is approximately the number of protons in the known universe.

The exact formula for the probability of getting a collision with an n-bit hash function and k strings hashed is

1 – 2ⁿ! / (2^kn (2ⁿ – k)!)

This is a fairly tricky quantity to work with directly, but we can get a decent approximation of this quantity using the expression

1 – e^-k2/2n+1

So, to get (roughly) a probability p chance of a collision, we can solve to get

p ≈ 1 – e^-k2/2n+1

1 – p ≈ e^-k2/2n+1

ln(1 – p) ≈ -k²/2ⁿ⁺¹

-ln(1 – p) ≈ k²/2ⁿ⁺¹

-2ⁿ⁺¹ ln(1 – p) ≈ k²

2^(n+1)/2 √(-ln(1 – p)) ≈ k

As one last approximation, assume we’re dealing with very small choices of p. Then ln(1 – p) ≈ -p, so we can rewrite this as

k ≈ 2^(n+1)/2 √p

Notice that there’s still a monster 2^(n+1)/2 term here, so for a 256-bit hash that leading term is 2^128.5, which is just enormous. For example, how many items must we see to get a 2^-50 chance of a collision with a 256-bit hash? That would be approximately

2^(256+1)/2 √2^-50

= 2^257/2 2^-50/2

= 2^207/2

= 2^153.5.

So you’d need a staggeringly huge number of hashes to have a vanishingly small chance of getting a collision. Figure that 2^153.5 is about 10⁴⁵, which at one nanosecond per hash computed would take you longer than the length of the universe to compute. And after all that, you’d get a success probability of 2^-50, which is about 10^-15.

In fact, this precisely why we pick such large numbers of bits for our hashes! It makes it extremely unlikely for a collision to occur by chance.

(Note that the hash functions we have today aren’t actually truly random functions, which is why people advise against using MD5, SHA1, and others that have had security weaknesses exposed.)

Hope this helps!