Skip to content
Published on

The Birthday Paradox and Hash Collisions — Why 23 People Means a 50% Match

🇰🇷KO🇺🇸EN🇯🇵JA
Split View필사 모드
Authors

Introduction — A Probability Story That Starts at a Party

Say 23 people are in a room. What are the odds that two of them share a birthday? Most people answer something like, "365 days, 23 people... maybe 6%?" The actual answer is 50.7%. More than half.

The result is so counterintuitive that it earned the name "the birthday paradox." It is not really a paradox, though — it is an illusion that arises because our intuition is answering the wrong question. And once you understand the illusion properly, a set of seemingly unrelated problems all thread together: why UUIDs never collide, how many bits a hash needs to be safe, when a hash table should grow, and why git abandoned SHA-1.

This post starts from the party problem and follows how far that math reaches. If you want to build hashes yourself and get a feel for it, keep this site's Hash Generator open alongside.

Why 23 People Gives You 50%

The key is what we are actually counting. The question our intuition reaches for is: "Is there someone with the same birthday as me?" But the real question is different: "Do any two people share a birthday?"

How many pairs of people can you form from 23? It is a combination.

number of pairs = C(23, 2) = 23 × 22 / 2 = 253 pairs

253 pairs. Each pair has a 1/365 chance of sharing a birthday, and with 253 pairs, the room for one of them to match is larger than it feels. As the crowd grows, the number of people grows linearly (23, 24, 25...), but the number of pairs grows almost quadratically (roughly n²/2). Our intuition looks only at the number of people and misses what actually matters: the number of pairs.

The exact probability is computed through the complement. Find the probability of "no pair matches," then subtract from 1.

P(all different) = 365/365 × 364/365 × 363/365 × ... × 343/365
P(at least one match) = 1 − P(all different)

Computing this for n people gives:

PeopleProbability at least one pair matches
10~11.7%
20~41.1%
23~50.7%
30~70.6%
50~97.0%
70~99.9%

At 23 you already cross half, and at 70 it is practically certain. You can verify it directly in Python.

def birthday_prob(n, days=365):
    p_all_different = 1.0
    for i in range(n):
        p_all_different *= (days - i) / days
    return 1 - p_all_different

for n in (10, 20, 23, 30, 50, 70):
    print(n, round(birthday_prob(n) * 100, 1))

The √N Intuition — the Real Star of This Post

Far more important than the specific numbers of the birthday problem is the rule hiding behind them. When you draw at random from N possible values, once you have drawn roughly √N of them, collisions (two identical values) start to appear.

Birthdays have N = 365, and √365 ≈ 19.1. The point where the probability crosses 50%, at 23 people, sits right near this √N. That is no coincidence.

Here is why it is √N, roughly. Draw n items and you get about n²/2 pairs, each colliding with probability 1/N. The expected number of colliding pairs is about n²/(2N), and the point where this reaches about 1 — the point where "a collision is now plausible" — is n ≈ √N. Written more precisely against the 50% threshold:

samples needed for a 50% collision: n ≈ 1.1774 × √N

This single approximation governs the entire rest of this post. There is only one thing to remember: collisions start at √N, not N. A large space is no reason to relax; what matters is what its square root is.

Moving on to UUIDs and Hashes

Now we leave the party and go to computers. In software we constantly mint "identifiers that must be unique": UUIDs, hash values, tokens. These are effectively values drawn at random from a very large box. So the birthday math applies unchanged.

UUID version 4 carries 122 random bits (a few of the 128 bits go to version and variant markers). The number of possible values N is 2¹²², roughly 5.3 × 10³⁶. For a collision to be a realistic worry in a space this large, you would need to generate about √N of them — around 2.3 × 10¹⁸ UUIDs.

Let us get a feel for how big that is. Even generating a billion (10⁹) UUIDs per second nonstop, reaching a 50% collision probability would take centuries. That is why in practice we use UUIDv4 with the comfortable assumption that it "never collides." Strictly, a collision is possible; the probability is just negligibly small.

Here the power of the √N intuition shows itself. The safety of a 122-bit space is not 122 bits but half of it — about 61 bits. When judging collision resistance, you must always fold the bit count in half.

Estimating Hash Collision Probability

Cryptographic hash functions are the same story. A hash function maps an input of arbitrary length to a fixed-length output. If the output is b bits, there are 2ᵇ possible hash values. When two different inputs produce the same hash value, that is a collision.

Applying the birthday approximation directly, the collision probability becomes meaningful once you have hashed about 2^(b/2) distinct inputs. In summary:

Hash output sizeFull space NWhere collisions worry you (~√N)
32 bits2³² ≈ 4.3 billion~2¹⁶ = 65,536
64 bits2⁶⁴~2³² ≈ 4.3 billion
128 bits2¹²⁸~2⁶⁴
256 bits2²⁵⁶~2¹²⁸

A 32-bit hash reaches a 50% collision probability at just ~65,536 values. This is exactly why you must not be fooled by the space size of 4.3 billion; the real safety margin is its square root, a mere 65,536.

There is also a handy formula for estimating very small collision probabilities. When N is large and the sample count n is far below √N, the collision probability is roughly:

P(collision) ≈ n² / (2N)

For example, feeding a billion values (n = 10⁹ ≈ 2³⁰) into a 128-bit hash (N = 2¹²⁸) gives a collision probability of about (2³⁰)² / (2 × 2¹²⁸) = 2⁶⁰ / 2¹²⁹ = 2⁻⁶⁹. Effectively zero.

Why 128 Bits Is Enough

Now we can answer "why 128 bits." The collision resistance of a 128-bit hash or identifier is on the order of √N — that is, 2⁶⁴ attempts. And 2⁶⁴ is about 1.8 × 10¹⁹.

Consider what that scale means physically. Even marshaling the fastest supercomputers on Earth to compute trillions of hashes per second (about 2⁴⁰), reaching 2⁶⁴ attempts would take hundreds of thousands of years. The chance of stumbling onto a random collision is effectively zero.

Here we must distinguish two kinds of "resistance."

  • Collision resistance: an attacker finds any two inputs whose hashes are equal. The birthday attack applies, so the difficulty is 2^(b/2). For 128 bits, that is 2⁶⁴.
  • Preimage resistance: finding an input that maps to a given specific hash value. The birthday trick does not apply here, so the difficulty is 2ᵇ. For 128 bits, that is 2¹²⁸.

So even for the same 128 bits, "breaking a specific value" is far harder at 2¹²⁸, while "finding any collision" is relatively easier at 2⁶⁴. That is why, where strong collision resistance is required, 128 bits is considered insufficient and 256 bits is used. SHA-256 uses 256 bits precisely to secure this headroom — a collision resistance of 2¹²⁸.

Hash Tables — Where Collisions Are Embraced Instead

So far collisions have been bad. But in a hash table, collisions are an unavoidable daily fact, and the design assumes them from the start. Here the hash space is small on purpose.

A hash table hashes the key, then takes the remainder modulo the number of buckets m as the index.

index = hash(key) % num_buckets

With only m buckets, N = m is very small. By the birthday problem, inserting just √m keys is enough to start colliding. With 100 buckets, collisions become common at barely a dozen keys. So a hash table does not try to eliminate collisions; it focuses on handling them gracefully when they occur. The two classic approaches are chaining (hanging entries off the same bucket in a linked list) and open addressing (probing for the next empty slot).

Load Factor and Resizing

The value that governs hash table performance is the load factor.

load factor α = number of stored items n / number of buckets m

A low load factor means collisions are rare and lookups stay near an average of O(1). But as the load factor rises, entries pile up per bucket, collisions become frequent, and lookups slow down as they scan those chains. So most hash table implementations, once the load factor crosses a threshold, increase the bucket count and reposition every entry. This is resizing, or rehashing.

  • Java's HashMap has a default load factor threshold of 0.75. When the item count exceeds 75% of the bucket count, it doubles the buckets.
  • Python's dict grows once it exceeds roughly 2/3 (about 0.66).
  • Go's map grows at a similar threshold.

Resizing costs O(n) because every entry must be reinserted into the new buckets. It looks expensive, but thanks to the doubling strategy (amortized doubling), the average cost of adding a single item stays O(1). It is the same principle by which a dynamic array grows by doubling. Occasionally one operation is expensive, but spread that cost across the cheap operations in between and the average is constant time.

There is an interesting contrast here. In cryptography, collisions starting at √N is a threat, so we make the space huge to avoid them. In a hash table, we accept the very same √N phenomenon, keep the space small, and manage performance through collision handling and resizing. Same math, opposite strategies.

When Collisions Truly Matter — git's Move from SHA-1 to SHA-256

The definitive case where collision probability stopped being theory and became a real event is git.

Git identifies every object (commit, tree, blob) by the hash of its content. For a long time that hash was SHA-1, which outputs 160 bits. By the birthday rule, SHA-1's collision resistance is 2^(160/2) = 2⁸⁰ attempts. For years, that was considered plenty safe.

Two problems emerged. First, 2⁸⁰ is not infinite, and as computing power advanced it crept into reach. Second, and more decisively, SHA-1 was not a pure random function. Weaknesses in its internal structure meant a collision could be produced with far less effort than the 2⁸⁰ of brute force.

In 2017, Google and CWI actually succeeded in making two different PDF files share the same SHA-1 hash. This "SHAttered" attack produced a collision at roughly 2⁶³ computation — well below the theoretical safety line of 2⁸⁰. That was a direct threat to git, a content-addressed store: if two maliciously crafted objects share a hash, there is room to quietly swap one for the other.

So git responded in two directions.

  • Short-term defense: it adopted a hardened SHA-1 (a variant with collision detection) that filters out SHAttered-style collisions by catching the known attack pattern.
  • Root fix: it undertook the transition to SHA-256 for the hash function itself. SHA-256 outputs 256 bits, so its collision resistance jumps to 2¹²⁸, making not only random collisions but also structural attacks effectively impossible for the foreseeable future.

The lesson from git is clear. "Enough bits today" is not enough forever. When advances in computing power coincide with the discovery of weaknesses in the hash function itself, yesterday's safety line becomes today's vulnerability. That is why security systems are always designed with generous headroom, like SHA-256's 2¹²⁸.

Summary — One Piece of Math, Many Faces

The birthday paradox looks like an amusing party trick, but it is really a fundamental principle running through all of computing.

  • The core rule: in a space of N, collisions start at √N, not N.
  • UUIDs and hashes: so the collision resistance of b bits is effectively b/2 bits. 128 bits is safe because the wall at 2⁶⁴ is physically hard to climb.
  • Hash tables: the same √N phenomenon makes collisions inevitable, so you manage the load factor and double the table at a threshold.
  • git: when SHA-1's 2⁸⁰ resistance fell to SHAttered, it moved to SHA-256's 2¹²⁸. Today's "enough" can become tomorrow's "not enough."

All of this flows from one simple observation: the number of pairs grows as the square of the number of people. Next time you mint a UUID or pick a hash size, think not of the size of the space but of its square root. The real safety margin is always there.

If you want to generate outputs from various hash algorithms yourself and compare their sizes, experiment in the Hash Generator.

References

Discuss on Twitter • View on GitHub