The Birthday Paradox and Hash Collisions

This post is the formal companion to the hash table discussion in my data structures course. In the course notes, we say that collisions are unavoidable and that a hash table must have a collision-resolution strategy, such as chaining or probing. Here we work out why collisions appear so early, even when the table is mostly empty.

The prerequisites are modest. You should know what a hash table slot is, what a collision is, and what it means for a hash function to spread keys evenly. You should also be comfortable with fractions, percentages, and the basic idea of probability. You do not need a discrete mathematics course. When we use notation such as $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ or expected value, I will explain what it means.

We will use a simplified model called uniform hashing. The table has $m$ slots, numbered $0$ through $m-1$, and each key is equally likely to land in any one of those slots. Real hash functions are not perfectly random, but this model is the right starting point: it tells us what happens when the hash function is doing its job well.

A collision happens when two different keys receive the same slot number. You might expect collisions to become likely only when the table is close to full, with nearly $m$ keys competing for $m$ slots. They start much sooner than that. A table with thousands of empty slots can already be likely to contain at least one collision.

A warm-up: shared birthdays

Set hash tables aside for a moment and think about birthdays. There are 365 possible birthdays, ignoring leap years. Put some people in a room and ask whether two of them share a birthday. How many people do you need before a shared birthday is more likely than not?

The common guess is around 180, about half of 365. The real answer is 23. With 23 people, the chance that two of them share a birthday is already about 51%. With 50 people, it is about 97%. Shared birthdays appear far sooner than intuition expects, and this is known as the birthday paradox.

The reason is that a shared birthday is not about one particular pair of people. It is about any pair among all of them.

With 23 people, there are 253 different pairs of people. The notation for this is

$$\left(\genfrac{}{}{0ex}{}{23}{2}\right)=253.$$

The symbol $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ means "the number of ways to choose 2 things from $n$ things." In this setting, it counts pairs. The formula is

$$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}.$$

Why divide by 2? Because $A$ paired with $B$ and $B$ paired with $A$ are the same pair. The product $n(n-1)$ counts both orders, so we divide by 2 to remove the duplicate counting.

With 23 people, every one of the 253 pairs is a chance for a birthday match. That is a lot of chances, and they add up quickly.

Hashing is the same situation with different labels. The people are the keys, and the 365 birthdays are the $m$ slots. Two people sharing a birthday is two keys sharing a slot, which is a collision. So the birthday paradox tells us that collisions appear far sooner than the table filling up would suggest.

Counting the chance of no collision

Here is the calculation behind that number 23, and it works for any number of slots.

Place keys into $m$ slots one at a time, and assume each key is equally likely to land in any slot. Follow the probability that no collision has happened yet, meaning every key so far sits in a slot of its own.

• The first key lands in some slot. There is nothing to collide with, so this step is certain. Its probability is $1$.
• The second key collides only if it hits the one occupied slot. It avoids that slot with probability $1-\frac{1}{m}$.
• The third key must avoid the two occupied slots, which happens with probability $1-\frac{2}{m}$.
• In general, the $i$-th key must avoid the $i-1$ slots already taken, with probability $1-\frac{i-1}{m}$.

For all $k$ keys to land in separate slots, every one of these steps has to succeed. We multiply the probabilities because each line is asking for the next key to avoid the slots already occupied, assuming all previous keys have avoided collisions.

So the exact probability of no collision among $k$ keys is

$$P(\text{no collision})=\left(1-\frac{1}{m}\right)\left(1-\frac{2}{m}\right)\cdots \left(1-\frac{k-1}{m}\right).$$

The first key's probability of $1$ is not written because multiplying by $1$ does not change the product.

The chance of at least one collision is whatever is left:

$$P(\text{collision})=1-P(\text{no collision}).$$

Each factor is a little less than $1$, and multiplying many numbers that are each a little less than $1$ pulls the product down quickly. That is why the no-collision probability drops so fast as $k$ grows.

If $k>m$, then a collision is guaranteed: there are more keys than slots. The surprising part is what happens much earlier, when $k$ is still much smaller than $m$.

Putting numbers in

With $m=365$, the product gives these chances of a collision for a few values of $k$:

By 23 keys, the odds have already crossed one half. At least 342 of the 365 possible birthdays are still unused, and possibly more if a collision has already happened. The table is only about 6% full, yet a collision is already about as likely as not.

The square-root rule

There is a useful shortcut for where the halfway point lands, and it works for any $m$.

The exact no-collision probability is

$$\left(1-\frac{1}{m}\right)\left(1-\frac{2}{m}\right)\cdots \left(1-\frac{k-1}{m}\right).$$

When $i$ is small compared with $m$, the number $i/m$ is small, and

$$1-\frac{i}{m}$$

is close to

$$e^{-i/m}.$$

This is a standard approximation: for small $x$, $1-x$ is close to $e^{-x}$. You do not need the proof here; the point is that it turns a product into something easier to simplify.

Using that approximation,

$$P(\text{no collision})\approx e^{-(1+2+\cdots +(k-1))/m}=e^{-k(k-1)/(2m)}.$$

The exponent contains

$$1+2+\cdots +(k-1).$$

That sum is

$$\frac{k(k-1)}{2}.$$

One way to remember this formula is to use "number of terms times average term." There are $k-1$ terms, from $1$ through $k-1$. Their average is halfway between the first and last term:

$$\frac{1+(k-1)}{2}=\frac{k}{2}.$$

So the sum is

$$(k-1)\frac{k}{2}=\frac{k(k-1)}{2}.$$

Now ask when a collision becomes about as likely as not. That happens when the no-collision probability is about $1/2$:

$$e^{-k(k-1)/(2m)}\approx \frac{1}{2}.$$

Take natural logs of both sides:

$$-\frac{k(k-1)}{2m}\approx \ln \left(\frac{1}{2}\right).$$

Since $\ln (1/2)=-\ln 2$, this becomes

$$\frac{k(k-1)}{2m}\approx \ln 2.$$

So

$$k(k-1)\approx 2m\ln 2.$$

For large $k$, $k(k-1)$ is close to $k^2$, so

$$k\approx \sqrt{2m\ln 2}.$$

Because $\sqrt{2\ln 2}\approx 1.18$, this is often written as

$$k\approx 1.2\sqrt{m}.$$

That is the square-root rule: a collision becomes likely after roughly $\sqrt{m}$ keys, not $m$ keys. For $m=365$, this gives

$$1.2\sqrt{365}\approx 23,$$

which matches the birthday table. For a table with one million slots, the halfway point is only about

$$1.2\sqrt{1,000,000}=1200$$

keys.

Load factor and keeping collisions rare

The birthday calculation explains when the first collision becomes likely. Hash table performance is a slightly different question. A real hash table does not need zero collisions. It needs collisions to stay controlled.

To see what "controlled" means, count colliding pairs. Among $n$ keys, there are

$$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$$

pairs of keys. For any one pair, the probability that both keys land in the same slot is $1/m$.

The expected value of a random quantity is its long-run average: if you built many hash tables under the same assumptions and averaged the number of colliding pairs, that average would approach the expected value. Since each pair has probability $1/m$ of colliding, adding those probabilities over all pairs gives the expected number of colliding pairs:

$$\frac{n(n-1)}{2m}\approx \frac{n^2}{2m}.$$

This number grows quickly if $m$ is fixed and $n$ keeps increasing. But hash tables do not keep $m$ fixed forever. They grow the array as more keys are inserted.

The quantity that controls the average crowding is the ratio of keys to slots, called the load factor:

$$\alpha =\frac{n}{m}.$$

The load factor is the average number of keys per slot. If $\alpha$ is a small constant, each slot holds only a constant number of keys on average. In a chaining hash table, that means a lookup goes to one slot and checks a short list on average. In an open-addressing hash table, the details are different, but the same principle remains: performance depends strongly on keeping the table from becoming too crowded.

If $\alpha$ is allowed to grow with $n$, slots get crowded and lookups slow down. If $\alpha$ is kept below a fixed bound, such as $0.75$, the average amount of crowding stays bounded. That is what supports average-case $O(1)$ lookup under the uniform hashing assumption.

So a hash table watches its load factor. When $n$ grows and $\alpha$ passes the chosen bound, the table allocates a larger array and re-inserts every key, which drops $\alpha$ back down.

This does not mean the total number of collisions in a large table is constant. If the table stores many keys, there may be many colliding pairs overall. The important point is local: the average amount of work per operation stays small because each key only has to deal with a bounded amount of crowding on average.

What this means for a hash table

Collisions are not a rare accident to be handled as an afterthought. The birthday paradox shows that the first collision appears while the table is still mostly empty. The pair count shows why crowding grows quickly if the table size is fixed. Load factor explains why resizing works: as the number of keys grows, the table grows too, keeping the average crowding per slot under control.

A working hash table needs both pieces. It needs a way to resolve collisions when they happen, and it needs a resizing rule that keeps the load factor bounded. Neither one alone is enough.