Hashing Internals: Collisions & Load Factor

The 10-second versionCopy Anchor Link

A hash function maps a huge key space into a small number of buckets, so collisions are a mathematical certainty — not a bug to fix, but a fact to design around. Two families handle them. Separate chaining keeps a list per bucket and just adds to it. Open addressing keeps everything inside the array and, on a collision, probes ahead — linearly, quadratically, by eviction (Robin Hood), or by bouncing keys between two tables (cuckoo). What keeps either fast is the load factor α = keys / buckets: cross a threshold and you rehash into a bigger table. Below the threshold, lookups are O(1) on average — but a bad hash or a fully loaded table collapses them to O(n).

Why this existedCopy Anchor Link

The instant Luhn reached for a fixed number of buckets, a wall appeared: pigeonhole. If you have more possible keys than buckets, some keys must share a bucket. You cannot avoid it. So the real question shifted from "how do we prevent collisions?" to "what do we do when they happen, and how do we keep them rare?"

• 1953 — Luhn's hash coding accepts collisions and stores the sharing keys together.
• 1954 — Gene Amdahl introduces open addressing with linear probing: on a collision, take the next free slot. Same array, no chains.
• 1963 — Donald Knuth publishes the first rigorous analysis of hashing — how long probes and chains get as a function of load factor.
• 1985 — Robin Hood hashing (Celis and others) evens out probe lengths by stealing from the rich.
• 2001 — cuckoo hashing (Pagh and Rodler) gives worst-case O(1) lookups by letting keys kick each other between two tables.

Why it mattered: the collision strategy — not the hash function alone — decides whether your map is a dependable O(1) or a hidden O(n). That's the difference between a fast cache and a production incident.

Inside the inventor's headCopy Anchor Link

You've got your buckets. Two different keys just hashed to slot 7. Now what?

The first attempt is a trap worth naming: just overwrite. If the slot is taken, clobber it. You get O(1) lookups and lose data silently — the worst kind of bug. Every real strategy is a way to keep both keys and still find them fast.

// Naive: a collision silently overwrites the earlier entry. Data vanishes.function putNaive(slots, key, val) {  slots[key % CAP] = val;              // second key wins; first is gone}

// Keep both keys: on a collision, scan forward for the next empty slot.function putProbing(keys, vals, key, val) {  let i = key % CAP;  while (keys[i] !== EMPTY && keys[i] !== key)    i = (i + 1) % CAP;                 // wrap around and keep probing  keys[i] = key;  vals[i] = val;}

Both keys survive, both stay findable, and no extra memory was allocated. Now the only question is how far the probing has to walk — which depends entirely on how full the table is.

The final approachCopy Anchor Link

Two families of collision handlingCopy Anchor Link

Separate chaining pushes new entries into a list at the bucket. It never runs "full" in the probing sense — load factor can even exceed 1 — but every entry costs a pointer and lookups chase pointers all over memory.

Open addressing keeps everything in the bucket array itself. The probe sequence defines the flavor:

• Linear probing (b, b+1, b+2, …): simplest and the most cache-friendly, but collisions cluster — a run of full slots grows at both ends.
• Quadratic probing (b, b+1, b+4, b+9, …): jumps away from clusters, at the cost of possibly not visiting every slot.
• Robin Hood: on insert, if the entry you're displacing has probed less than you have, swap — the rich give to the poor, and probe lengths equalize.
• Cuckoo hashing: two hash functions, two tables; a new key evicts the occupant, which bounces to its other position, kicking the next key, and so on — guaranteeing O(1) lookups.

Load factor and rehashingCopy Anchor Link

Define α = n / m — stored keys over bucket count. It's the single number that governs everything. As α rises, chains lengthen and probe runs grow, and performance slides from O(1) toward O(n). The fix is boring and effective: when α crosses a threshold (often 0.7), allocate a bigger table and rehash every key into it — recomputing each hash(key) mod m for the new size. Amortized over the inserts, this is O(1) per insert.

The invariantsCopy Anchor Link

• Deterministic mapping: the same key always hashes to the same bucket for a given table size. Rehashing changes the size, so every key must be re-inserted — you can't keep the old positions.
• α stays under the threshold (or performance quietly degrades). This is the invariant that separates an O(1) table from a disguised linked list.
• The probe sequence reaches a free slot (given an appropriate table size and step), so insertions and lookups terminate.

It in codeCopy Anchor Link

const CAP = 16;const EMPTY = -1;class Map {  keys = new Array(CAP).fill(EMPTY);  vals = new Array(CAP).fill(0);  size = 0;  #hash(key) { return (Math.imul(key, 2654435761) >>> 0) % this.keys.length; }  put(key, val) {    let i = this.#hash(key);    while (this.keys[i] !== EMPTY && this.keys[i] !== key)      i = (i + 1) % this.keys.length;         // linear probe    if (this.keys[i] === EMPTY) this.size++;    this.keys[i] = key;    this.vals[i] = val;  }  get(key) {    let i = this.#hash(key);    while (this.keys[i] !== EMPTY) {          // stop at first empty slot      if (this.keys[i] === key) return this.vals[i];      i = (i + 1) % this.keys.length;    }    return undefined;  }}

A worked trace: clustering in actionCopy Anchor Link

A 7-slot table using hash(key) = key mod 7, inserting 1, 8, 15, 22. All four hash to bucket 1, so watch them pile up:

That run 1, 8, 15, 22 is a cluster. Worse, any key that merely hashes near the cluster (like 2) now has to skip past it too. Clustering is why real systems rehash long before the table is full: keeping α low keeps clusters short, and short clusters keep lookups near O(1).

Knuth's analysis, and the O(n) worst caseCopy Anchor Link

Knuth (1963) showed that under uniform hashing — keys spread evenly, independent of each other — the expected cost is a clean function of α:

• Separate chaining: successful lookup ≈ 1 + α/2 probes; unsuccessful ≈ α.
• Linear probing: successful lookup ≈ ½ (1 + 1/(1-α)); unsuccessful ≈ ½ (1 + 1/(1-α)²).

Read that last one carefully: as α → 1, the cost blows up — α = 0.9 is already over 50 probes for a miss. Keeping α ≤ 0.7 keeps everything comfortably small. And the worst case is O(n) for a blunt reason: a deterministic hash can be attacked or simply unlucky. Feed keys that all collide and every lookup walks the entire bucket — the map is a linked list in a trench coat. That's why some systems salt their hash or cap chain length (Java turns long chains into balanced trees), and why "hash flooding" is a real denial-of-service attack.

ComplexityCopy Anchor Link

Space is O(n) for all of them — the difference is pointers (chaining) versus unused slots (open addressing).

Where you meet it todayCopy Anchor Link

• Real maps, real strategies. Java's HashMap uses chaining and grows a chain into a balanced tree past 8 entries. Python's dict is open addressing with perturbed probing. Rust's HashMap (via hashbrown) uses a SIMD "Swiss table". C++'s unordered_map chains.
• Caches. Every bounded cache (LRU, TTL) sits on a hash table and must tune its load factor — a rehash that doubles memory mid-request is a latency spike you can feel.
• Security. Hash flooding attacks exploit collision collapse; randomized seeds and keyed hashing exist specifically to keep the worst case from being reachable by an attacker.

maybeGrow() {  if (this.size * 4 >= this.keys.length * 3) {  // load factor α ≥ 0.75    this.rehash(this.keys.length * 2);          // double, then re-insert all  }}

RecapCopy Anchor Link

• Collisions are guaranteed (pigeonhole), so a design must handle them — never overwrite.
• Separate chaining keeps a list per bucket; open addressing probes for the next slot (linear, quadratic, Robin Hood, cuckoo).
• The load factor α = n/m controls cost; cross the threshold and you rehash into a bigger table, amortized O(1).
• Knuth's analysis pins the average cost to α; the worst case is O(n) because a bad or adversarial hash can collapse every key into one bucket.

Next up: Linear & Binary Search — where we leave the hash behind and go back to sorted order, and the log n that comes with it.