Hashing and the Birthday Paradox

In one line

Hash $n$ items into $m$ possible values and collisions become likely far sooner than intuition suggests, once $n$ passes roughly $\sqrt {m}$ , not $m$ .

What it says

This formula answers one specific question. If you hash $n$ items into $m$ possible slots, uniformly and independently at random, what is the chance that at least two of them land on the same slot?

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

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

It's the same question as the classic birthday paradox: put 23 people in a room ( $n = 23$ ) against 365 possible birthdays ( $m = 365$ ). The odds two of them share a birthday are already better than even, even though 23 is nowhere near 365. Hashing falls into the same trap: a hash space that looks astronomically large can still produce collisions with a surprisingly small number of items.

Breaking it down

$P(\text{collision})$ : the probability that at least two of the $n$ items land on the same hash value.
$n$ : the number of items being hashed.
$m$ : the size of the hash space, the number of distinct possible output values (for example $2^{32}$ for a 32-bit hash).

It is easier to count the ways nothing goes wrong. The chance that all $n$ items land in distinct slots is a product of shrinking survival terms. The second item must avoid 1 slot, the third must avoid 2, and so on.

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

(2) Exact probability that every item lands in its own slot.

Where it comes from

Take logs of equation (2) and apply $\ln(1 - x) \approx -x$ for small $x$ . The sum $\sum_{i=0}^{n-1} i$ collapses to $n(n-1)/2 \approx n^2/2$ . That gives the exponential form in equation (1).

Seeing it work

Setting $P = 1/2$ in equation (1) and solving for $n$ gives $n \approx 1.1774\sqrt{m}$ : even odds arrive at the square root of the output space, not the space itself.

A 32-bit hash has $m = 2^{32}$ , about 4.3 billion possible values, so intuition says you would need billions of items before collisions become a real concern. The formula says otherwise: at $n = 77{,}163$ items, the collision probability is already at 50%.

@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)

// Probability of at least one collision when hashing `n` items
// into `m` possible values.
fn collision_probability(n: f64, m: f64) -> f64 {
    1.0 - (-(n * n) / (2.0 * m)).exp()
}
 
collision_probability(77_163.0, 2f64.powi(32)); // ≈ 0.5006

main

Nas (@itsnas)

// Probability of at least one collision when hashing `n` items
// into `m` possible values.
double collisionProbability(double n, double m) {
  return 1 - std::exp(-(n * n) / (2 * m));
}
 
collisionProbability(77163, std::pow(2, 32)); // ≈ 0.5006

main

Nas (@itsnas)

// Probability of at least one collision when hashing n items
// into m possible values.
func collisionProbability(n, m float64) float64 {
	return 1 - math.Exp(-(n*n)/(2*m))
}
 
collisionProbability(77163, math.Pow(2, 32)) // ≈ 0.5006

main

Nas (@itsnas)

# Probability of at least one collision when hashing `n` items
# into `m` possible values.
def collision_probability(n: float, m: float) -> float:
    return 1 - math.exp(-(n * n) / (2 * m))
 
collision_probability(77_163, 2**32)  # ≈ 0.5006

main

Nas (@itsnas)

A 128-bit hash pushes $m$ up to $2^{128}$ , and the same formula puts the 50% mark at roughly $1.1774 \times 2^{64} \approx 21.7$ quintillion items. That's why 128-bit hashes are treated as "collision-free" for essentially any practical dataset size.

Common misreadings

1
Assuming safety scales with m, not √m
A hash space of size $m$ does not buy you $m$ safe items: it buys you roughly $\sqrt{m}$ . Doubling the hash width doesn't double the safe item count, it roughly squares it.
2
Trusting the formula more than the hash function
This approximation assumes a perfectly uniform, independent random hash. Real hash functions can fall well short of that: in Daniel Lemire's own experiment, 1,000 items reached a 100% collision rate with a hash function that theory predicted would need over 77,000 items to hit 50%. The formula is a best case, not a guarantee.
3
Applying it past n ≈ m
The $e^{-n^2/2m}$ approximation holds while $n \ll m$ . As $n$ approaches $m$ , use the exact product $\prod_{i=0}^{n-1}(1 - i/m)$ instead: the exponential approximation stops tracking it closely.