Skip to content
../writing

Hashing and the Birthday Paradox

Naseebullah AhmadiSenior Software Engineer, London

A 32-bit hash has 4.3 billion possible values. How many items can you hash before a collision is a coin flip? Not billions: about 77,000.

#hashing
#probability
#math
6 min read
#math

Most people guess billions, because 4.3 billion slots feels like room for billions of items. The same intuition says you'd need a room of about 180 people before two share a birthday. It takes 23.

Count pairs, not people

A collision isn't about any one person. It's about any pair of people matching, and pairs grow much faster than people do:

PeoplePairsChance any pair matches
5103%
2325351%
4078089%
702,41599.9%

With 23 people there are 253 pairs, each a 1-in-365 shot. That's plenty of chances for one to land.

@itsnas chance-of-a-shared-birthday-by-group-size.svg
Chance of a shared birthday by group sizeThe probability that two people share a birthday rises steeply: about 12% at 10 people, 51% at 23, 89% at 40 and nearly certain by 70. A straight line for n divided by 365, what intuition expects, stays below 20% across the whole range.intuitionactual23 people, about 50%0%50%100%0234070People in the roomChance of a match
Intuition grows with people (dashed). The real chance grows with pairs, so it hits 50% at 23 people.

Where the square root comes from

Hashing is the same problem: nn items, mm possible hash values. The cleanest way to count is the chance that nothing goes wrong. The second item must miss 1 taken slot, the third must miss 2, and so on:

P(no collision)=∏i=0n−1(1−im)P(\text{no collision}) = \prod_{i=0}^{n-1}\left(1 - \frac{i}{m}\right)

(1)  Exact chance that every item gets its own slot.

Take logs, use ln⁡(1−x)≈−x\ln(1 - x) \approx -x for small xx, and the sum 0+1+⋯+(n−1)0 + 1 + \dots + (n - 1) is about n2/2n^2/2. Out comes the version worth remembering:

P(collision)≈1−e−n22mP(\text{collision}) \approx 1 - e^{-\frac{n^2}{2m}}

(2)  Collision probability for n items over m slots.

The n2n^2 is the pairs from the table above. Set P=1/2P = 1/2, solve for nn, and you get n≈1.18mn \approx 1.18\sqrt{m}: even odds arrive at the square root of the space, not the space itself.

@itsnas birthday.ts
codebirthday.ts
// Probability of at least one collision when hashing `n` items
// into `m` possible values.
function collisionProbability(n: number, m: number): number {
  return 1 - Math.exp(-(n * n) / (2 * m))
}
 
collisionProbability(77_163, 2 ** 32) // ≈ 0.5006
main
Nas (@itsnas)

What that means for hash width

HashPossible values50% collision at
32-bit4.3 billion77,163 items
64-bit1.8 × 10¹⁹about 5 billion items
128-bit3.4 × 10³⁸about 2.2 × 10¹⁹ items

Doubling the bits squares the safe item count rather than doubling it, which is why 128-bit hashes are treated as collision-free in practice and 32-bit ones are not safe as unique IDs for anything that grows. Once nn gets anywhere near mm, switch back to the exact product: the exponential version only tracks it while nn is small next to mm.

The formula is also a best case. It assumes a perfectly uniform random hash, and real ones fall short: in Daniel Lemire's experiment, a hash that theory said needed 77,000 items to reach 50% collided on every run with just 1,000.

So when someone says a hash space is "huge", take its square root. That's the number of items you can actually afford.