We use essential cookies to run the site (session, security, and your theme/language preferences). With your permission we also load embedded third-party content, such as YouTube videos. Cookie Policy
Why collisions arrive at the square root of the space
Author(s):Elier Rodríguez García
Index
Introduction
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×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.
Watch the First Collision
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 N marker.
<p class="hint">Each item gets hashed into one of <b id="nlabel">365</b> buckets. Add items one by one, or let it run, and watch when the <b>first collision</b> happens. It almost always lands near <b>√N</b> — far below N.</p>
<div class="controls">
<label>Buckets N:
<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">√N</span><span id="nend">N</span></div>
</div>
<div class="status" id="status">No items yet. Press Add item.</div>
<div class="grid" id="grid"></div>
<div class="btns">
<button id="add" type="button">Add item</button>
<button id="run" type="button">Run to collision</button>
<button id="reset" type="button" class="ghost">Reset</button>
</div>
const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Birthday paradox / hash collisions: hash random items into N buckets and
// watch the FIRST collision. Theory: the expected first collision lands after
// about sqrt(pi*N/2) ~ 1.25*sqrt(N) items -- the square root of the space,
// NOT N. For N=365 that's ~24, matching the classic "23 people" birthday fact.
let N = 365;
const seen = new Set(); // bucket indices already used
const items = []; // history of bucket indices, in order
let done = false; // collision reached?
const $ = id => document.getElementById(id);
function reset(){
seen.clear(); items.length = 0; done = false;
$('add').disabled = false; $('run').disabled = false;
render(); setStatus('No items yet. Press Add item.', '');
}
// Drop one item; returns true if it collided with an existing bucket.
function addItem(){
if(done) return false;
const b = Math.floor(Math.random() * N);
const collided = seen.has(b);
items.push(b);
if(collided){
done = true;
$('add').disabled = true; $('run').disabled = true;
const sqrtN = Math.sqrt(N).toFixed(1);
setStatus(fmt('Collision at item #%length%! (√N ≈ %sqrtN%, N = %N%)', { length: items.length, sqrtN: sqrtN, N: N }), 'hit');
} else {
seen.add(b);
setStatus(fmt('%length% %v%, no collision yet. √N ≈ %sqrt%.', { length: items.length, v: items.length===1?'item':'items', sqrt: Math.sqrt(N).toFixed(1) }), 'ok');
}
render();
return collided;
}
function setStatus(t, cls){ const s = $('status'); s.textContent = t; s.className = 'status ' + cls; }
function render(){
// progress bar: items placed vs N, with the sqrt(N) marker
const frac = Math.min(items.length / N, 1);
$('fill').style.width = (frac * 100) + '%';
const sqrtFrac = Math.sqrt(N) / N; // sqrt(N)/N = 1/sqrt(N)
$('sqrt').style.left = (sqrtFrac * 100) + '%';
$('sqrtlbl').style.left = (sqrtFrac * 100) + '%';
$('nlabel').textContent = N;
$('nend').textContent = 'N=' + N;
// chips: show each item's bucket; the last one is red if it was the duplicate
const g = $('grid'); g.innerHTML = '';
items.forEach((b, i) => {
const c = document.createElement('span');
const isDup = done && i === items.length - 1;
c.className = 'chip' + (isDup ? ' dup' : '');
c.textContent = b;
g.appendChild(c);
});
}
function run(){
// Drop items until the first collision (capped so the loop is always finite).
let guard = 0;
while(!done && guard < N + 5){ addItem(); guard++; }
}
$('add').addEventListener('click', addItem);
$('run').addEventListener('click', run);
$('reset').addEventListener('click', reset);
$('nsel').addEventListener('change', e => { N = parseInt(e.target.value, 10); reset(); });
reset();
Result
Console
Run it a few times. The first collision almost always lands close to 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× (2), not 2×.
The Real Complexity
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
(1−N1)(1−N2)⋯(1−Nk−1)
It crosses 50% when k≈1.18N.
The expected first collision lands after about $πN/2≈1.25N$ 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 k2/2. To make that comparable to N, you need k near 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=2n possible values, so a birthday attack finds a collision in about 2n/2 tries, not 2n. 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.
Where It Matters
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 2n/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.
Conclusion
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 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.
Comments
Loading comments...