The Birthday Problem and Hash Collisions

In a room of just 23 people, two probably share a birthday. The same math says a hash with N possible values starts colliding after only about √N items, far sooner than intuition expects, and the pigeonhole principle guarantees a collision once there are more items than values.

How it works

The product rule and the pigeonhole principle

In one sentence

For $n$ items placed independently and uniformly into $N$ bins, $P(\text{all distinct}) = \prod_{k=0}^{n-1}(1 - k/N) \approx e^{-n(n-1)/(2N)}$ , so the collision probability reaches $\tfrac12$ near $n \approx \sqrt{2N\ln 2} \approx 1.18\sqrt N$ . For $n > N$ a collision is certain (pigeonhole principle).

General formula

{\htmlData{sym=0}{P(\text{no collision})}} = \prod_{{\htmlData{sym=3}{k}}=0}^{{\htmlData{sym=1}{n}}-1}\left(1 - \frac{\htmlData{sym=3}{{k}}}{\htmlData{sym=2}{{N}}}\right) \approx e^{-{\htmlData{sym=1}{n}}^2/(2{\htmlData{sym=2}{N}})}

Collisions come from pairs, not individuals, and the number of pairs grows like n². Twenty-three people already make 253 pairs.

What the symbols mean

$P(\text{no collision})$
Chance of no collision
The probability that all n items land on different values.
$n$
Items
People in the room, or keys being hashed.
$N$
Possible values
365 birthdays, or 2³² hash values for a 32-bit hash.
$k$
Index
How many items are already placed when the next one arrives.

Line people up one at a time. The second avoids the first one's birthday with probability 364/365, the third avoids both with 363/365, and so on; by the product rule, multiply.
So the chance that $n$ items all land in different slots is $\prod_{k=0}^{n-1}(1 - k/N)$ , and the chance of a collision is 1 minus that.
There are $\binom{n}{2} \approx n^2/2$ pairs, each colliding with chance $1/N$ , which is why collisions become likely once $n$ is around $\sqrt N$ : 23 people for 365 days, about 77,000 items for a 32-bit hash.
With $n > N$ items a collision is certain, by the pigeonhole principle.

Learn the math

Functions: One-to-One and OntoDiscrete · Lesson 11, Sets, Functions and Relations The Pigeonhole PrincipleDiscrete · Lesson 19, Counting Error Detection: Parity, Checksums and CRCsDiscrete · Lesson 33, The Math Inside Computers