Hash Collisions

Put 23 strangers in a room and the odds that two of them share a birthday are already better than even — about 50.7%. Most people guess you'd need closer to 183, half of 365. The gap between that guess and reality is the famous birthday paradox, and it is not a trick of wording. It is a deep fact about how pairs grow.

You are not looking for someone with your birthday. You are looking for any matching pair, and the number of pairs among 23 people is $23 \times 22 / 2 = 253$ — already more than the 365 days. Pairs, not people, drive the collision.

Replace "birthday" with "hash value" and "person" with "item," and you have one of the most important rules in computing: collisions in a space of size N start appearing not near N, but near the square root of N.

Below are N buckets. Press Add item to hash a random item into one of them, or Run to drop items automatically until two land in the same bucket. Watch the counter against the dashed $\sqrt{N}$ marker.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{label_buckets}}
    <select id="nsel">
      <option value="100">100</option>
      <option value="365" selected>365</option>
      <option value="1000">1000</option>
    </select>
  </label>
</div>
<div class="meter">
  <div class="bar"><div id="fill" class="fill"></div><div id="sqrt" class="sqrt"></div></div>
  <div class="ticks"><span>0</span><span id="sqrtlbl" class="sqrtt">&radic;N</span><span id="nend">N</span></div>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="grid" id="grid"></div>
<div class="btns">
  <button id="add" type="button">{{btn_add}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { margin: .2rem 0 .6rem; font-size: .9rem; }
select { font: inherit; padding: .15rem .3rem; border-radius: 6px; border: 1px solid #adb1b8; }
.meter { margin: .4rem 0 .2rem; }
.bar { position: relative; height: 14px; background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 7px; overflow: hidden; }
.fill { height: 100%; width: 0; background: #1d3557; transition: width .15s; }
.sqrt { position: absolute; top: -3px; bottom: -3px; width: 0; border-left: 2px dashed #e63946; }
.ticks { position: relative; font-size: .72rem; color: #555; height: 1.1em; }
.ticks span { position: absolute; }
.ticks span:first-child { left: 0; }
.ticks .sqrtt { color: #c92f3c; font-weight: 700; transform: translateX(-50%); }
.ticks #nend { right: 0; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0 .4rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.hit { color: #c92f3c; }
.grid { display: flex; flex-wrap: wrap; gap: 3px; margin: .3rem 0 .6rem; max-height: 120px; overflow: auto; }
.chip { font: 700 12px ui-monospace, monospace; padding: 2px 6px; border-radius: 6px;
        background: #c9ccd1; border: 1px solid #adb1b8; }
.chip.dup { background: #e63946; border-color: #c92f3c; color: #fff; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Run it a few times. The first collision almost always lands close to $\sqrt{N}$, not anywhere near N. With 365 buckets the average first collision shows up around 24 items — uncannily close to the 23 of the birthday paradox. Double the buckets and the collision point grows only by about $1.41\times$ ($\sqrt{2}$), not 2×.

This is not an open question or a hard problem — it is solved exactly, and the answer is clean.

• The probability of no collision after k items in N buckets is the product

  $$\left(1-\tfrac{1}{N}\right)\left(1-\tfrac{2}{N}\right)\cdots\left(1-\tfrac{k-1}{N}\right)$$

  It crosses 50% when $k \approx 1.18\sqrt{N}$.

• The expected first collision lands after about $$\sqrt{\pi N/2} \approx 1.25\sqrt{N}$$ items. For N = 365 that is ≈ 24; the simulation above confirms it.

• Why the square root? The chance of no match among k items depends on the number of pairs, roughly $k^2/2$. To make that comparable to N, you need k near $\sqrt{N}$ — so collisions arrive at the square root of the space, every time.

The punchline for security: a hash with an n-bit output has $N = 2^{n}$ possible values, so a birthday attack finds a collision in about $2^{n/2}$ tries, not $2^{n}$. A 128-bit hash gives only ~64 bits of collision resistance — which is exactly why modern hashes are 256 bits. This same counting argument underlies why brute force is unavoidable for problems like those behind P vs NP.

The square-root rule is one of those facts that, once you see it, you notice everywhere:

• Hash tables: this is why a table starts colliding (and slowing down) long before it is full, and why engineers resize at a load factor well below 100%.
• Cryptographic hashes: the birthday attack sets the real security level — output sizes are doubled precisely to keep $2^{n/2}$ infeasible. Related to hashing in general.
• Load balancing & sharding: random assignment to servers or shards collides sooner than expected, so naive "just hash it" schemes get lumpy.
• Bioinformatics & deduplication: matching reads or detecting duplicate files relies on the same pair-counting, where collisions are sometimes the goal.

Whenever you scatter items into a finite space and ask "when do two coincide?", the answer is the square root — a tiny formula with enormous reach.

The birthday paradox feels like a paradox only because we instinctively count people instead of pairs. Once you count pairs, the magic vanishes and a precise law appears: scatter items into a space of size N and the first collision shows up near $\sqrt{N}$, every single time.

That same square root quietly sizes your hash tables, sets the strength of cryptographic hashes, and explains why brute-force search blows up so fast. Twenty-three people in a room are not a curiosity — they are a window into the deep arithmetic of hashing and the limits of computation.