Loading video…
hashing and treesdeep

Hash Tables: Collisions, Load Factor, and Resizing

The first hero of this course was a hash set. Lesson 1's GTA story ended with t0st replacing an array scan with a structure where checking "have I seen this?" took the same tiny amount of work whether ten items came before or sixty thousand. I showed you the fix and never explained the machine, and I asked you to file something away: average case O(1), worst case O(n), and an engineering story that is entirely about making the worst case so rare you can price the structure at its average. Eleven lessons later, you own every piece of machinery the explanation needs. Time to cash the file.

Start from what you already trust. The only O(1) lookup in this course so far is array indexing: base + i × size, one multiply, one add, one load (lesson 3). But that trick demands an integer index. Real programs look up usernames, URLs, session tokens, struct keys. So the entire question of this lesson fits in one sentence: how does the string "alice" become an array index?

Manufacturing an index

Take an ordinary array with 8 slots, indexed 0 through 7. Now take a function, hash, that accepts any key (a string, a number, a tuple) and returns a fixed-size integer. Inside it's something like "walk the bytes of the key, mixing each one into a running number"; we'll look at real recipes in a moment. Say hash("alice") comes out to 2347. That's too big for 8 slots, so take the remainder:

insert("alice", value):
    h = hash("alice")          # 2347
    slot = h mod capacity      # 2347 mod 8 = 3
    array[3] = ("alice", value)

The value for "alice" lives in slot 3. The lookup, an hour later, runs the same function on the same bytes: 2347 again, mod 8, slot 3, one array access, there it is.

Notice who is doing the real work. Slot 3 is base + 3 × slot_size, the same O(1) pointer arithmetic from lesson 3. The hash function adds nothing magical; it manufactures the integer index that arrays already knew how to use. A hash table is an array wearing a key-to-index converter. Everything else in this lesson, collisions, load factor, resizing, the 2011 attack, is the engineering required to keep that one-line trick honest.

What makes a good hash function

Three properties make the converter trustworthy:

  1. Determinism. hash("alice") must return the same number every time within a process, or the table breaks: insert under one number, search under another, and the value is simply gone.
  2. Uniformity. Outputs should spread across the integers like rain, no favorite slots. Any bias turns one slot into a crowd, and crowds are the slow case arriving early.
  3. Speed. This function runs on every single operation, so it has to cost a handful of nanoseconds. A few multiplies and XORs per byte, not a ceremony.

Real ones have names. FNV-1a is a few lines: start from a constant, then XOR in each byte and multiply by a prime (it's the hash in this lesson's code section). MurmurHash and its descendants are the workhorses inside a lot of infrastructure. SipHash carries a secret key, and the reason it does is the story near the end of this lesson.

One disambiguation, because the word "hash" is badly overloaded: these are not cryptographic hashes. SHA-256 spends hundreds of cycles per block making its output irreversible and collision-resistant against dedicated attackers with budgets. Table hashes spend a few cycles making output spread. Different jobs, different tools, same unfortunate name.

And one piece of honest fine print on "O(1)". Hashing an integer is near-free, often just a couple of mixing steps on the value itself. Hashing a string walks its bytes, so a string-keyed lookup is really O(key length) for the hash plus O(1) for the table. For "alice" that's five bytes of nothing; for ten-kilobyte keys it's the dominant cost. The O(1) quote prices the table, not the key. (Lesson 4's fact that immutable strings can cache their hash is one reason languages love immutable keys; Python hashes a string once and remembers the answer.)

Collisions are arithmetic, not bad luck

Two keys can land in the same slot. Say hash("bob") is 9011: mod 8 is 3, the same slot as "alice". That's a collision, and the pigeonhole principle says they are unavoidable: infinitely many possible keys, finitely many slots, so some keys must share. No cleverer hash function escapes that.

What intuition gets wrong is how fast they show up. You may know the birthday paradox: 23 people in a room and it's a coin flip that two share a birthday, with 365 days to spread across. Tables are worse. Three keys into 8 slots already carry about a 34% chance that two share a slot. A table with a million slots reaches coin-flip collision odds at roughly 1,200 keys. Twelve hundred, into a million. Collisions are not a failure mode to be engineered away; they are line one of the design brief. There are exactly two classic answers.

Resolution one: separate chaining

Let every slot hold not a value but a pointer to a linked list of entries, lesson 5's structure back on payroll. Insert "alice": slot 3, new node, a list of one. Insert "bob": slot 3 again, prepend, a chain of two. Lookup "bob": hash, mod, slot 3, then walk the chain comparing actual keys: first node "alice", no; second node "bob", yes. Two comparisons. Collisions just add a short walk.

And now lesson 1's worst case is visible to the naked eye: if the hash is terrible, or someone forces every key into one slot, the hash table quietly becomes a linked list, and lookup is O(n). The whole game is keeping chains short, and the average chain length is simply items ÷ slots. Hold onto that ratio; it gets a name shortly.

Resolution two: open addressing

The second answer throws the lists away. In open addressing, every entry lives in the array itself, and a collision means: walk forward. Insert "alice" at slot 3, fine. Insert "bob": slot 3 occupied, try slot 4, empty, "bob" lives at 4. The walk is called probing; trying the very next slot is linear probing. (Fancier footwork exists: quadratic probing jumps by growing gaps, double hashing uses a second hash to pick the step size. Same idea.)

A lookup probes the same path and ends in one of two ways: it finds the key, or it hits an empty slot, which is proof the key was never inserted, because the insert would have stopped there.

That proof is exactly what makes deletion subtle. Delete "alice" from slot 3 and leave a hole, and a lookup for "bob" now hits empty at 3 and declares him missing, while he sits right there in slot 4. So open addressing can't just erase; it plants a tombstone, a marker meaning "dead, but keep walking". Lookups step over tombstones, inserts may reclaim them, and a table that accumulates too many rebuilds itself clean during the next resize.

The cache vote

Which resolution wins? Chaining is simpler and tolerates crowding gracefully. But lesson 2 already told you the deeper story. Walking a chain means each node is a separately allocated object somewhere in the heap: every step is a pointer chase, a potential ~100ns trip to RAM. Chains commute. Linear probing checks slots 3, 4, 5: adjacent entries on the same cache line or the next one, which the prefetcher is already hauling. Probes stream. The two collision strategies are the two memory access patterns of lesson 2 wearing hash-table costumes.

Modern engineering voted with the hardware. Python's dict is open addressing. Google's Abseil flat_hash_map introduced the Swiss table design; Rust's standard HashMap adopted it (via hashbrown), and Go's built-in map moved to a Swiss-table design in Go 1.24. The Swiss trick, kept to one honest teaser: store one metadata byte per slot in a separate contiguous block, so a single wide SIMD instruction can check sixteen slots' worth of "maybe" at once, touching the real entries only on a likely hit. The internals are a rewarding rabbit hole; the headline is lesson 2's thread paying off. Hardware likes neighbors.

Load factor: the dial

The ratio from the chaining section, items ÷ slots, is the load factor (written α), and it's the dial every hash table lives by. Eight slots, six entries: α = 0.75. It reads as "how full is the table", and it trades memory for speed: low α wastes slots to keep operations near O(1); high α saves memory and pays in probes.

The two resolutions feel α very differently. For chaining, α = 1.0 means chains average one node: comfortable, degrading gently beyond. Open addressing degrades hard as α approaches 1, because probes need empty slots to stop, and clustering snowballs. Picture slots 3 through 9 all full, one long run. A new key that hashes anywhere in that run (3, 5, 8, anywhere) walks to the end and parks at slot 10, so the run grows, so it catches even more future keys, so it grows faster. Clusters feed themselves. Back-of-the-envelope (under idealized uniform-hash assumptions): at α = 0.5 an unsuccessful lookup probes about 2.5 slots on average; at α = 0.9, about 50.

So real tables never let it get there. CPython resizes its dict around 2/3 full; Java's HashMap defaults to 0.75 (it switched to chaining-with-treeification, a different lesson); Swiss tables run to about 7/8 because the metadata scan keeps probing cheap. The numbers differ by design; the policy is identical: cross a threshold, rebuild.

Resizing: the renumbered street

The rebuild is the moment lesson 11's bridge promised: every hash table you've ever used occasionally stops to remake itself. Here's why it can't cheat. Allocate a bigger array, 16 slots instead of 8, and every home address changes, because the home was hash mod capacity. "alice": 2347 mod 8 = 3, but 2347 mod 16 = 11. The keys didn't move; the street got renumbered. So a resize must allocate the new array and rehash every key into its new slot. O(n), no way around it.

You already own the defense: lesson 3's doubling argument, verbatim. Double the capacity each time, and the rebuilds land exponentially far apart, so the total work of all rebuilds ever stays proportional to n. Amortized O(1) per insert, same bank-balance arithmetic as the dynamic array, plus a hash per element moved.

But remember what amortized analysis does not promise: that no single operation is slow. One unlucky insert pays for the entire rebuild, all at once. For most programs that pause is invisible. For some it's a production incident: a table holding fifty million entries in a hot service crosses the threshold, one innocent insert rehashes fifty million keys before returning, and every request queued behind it waits. On a latency graph it's a spike with no visible cause, because the triggering code did nothing unusual; it was just the unlucky one.

Redis, the in-memory database that is one giant hash table at heart, refuses to take that pause. Its dictionaries do incremental rehashing: when a resize begins, Redis keeps both arrays, old and new. Reads check both. Writes go to the new one. And every operation that touches the dictionary migrates a small batch of old entries on its way through, with a background task nibbling at the rest, until the old table drains and is freed. No operation ever pays for the whole move. The cost is bookkeeping and a window where two tables coexist; the prize is no spike. Same amortized total, spread fine instead of lumped.

The worst case, weaponized

Now the worst case stops being theoretical. December 2011, the 28C3 conference in Berlin: Alexander Klink and Julian Wälde present "Efficient Denial of Service Attacks on Web Application Platforms". Their observation: web frameworks parse every incoming form field into a hash table, the field names are chosen by the client, and the languages' string hashes were public, deterministic, and unkeyed. So an attacker can precompute thousands of strings that all hash to the same slot, send them as one POST request, and the server's table degenerates into one long chain. Every insert walks it; inserting n keys costs O(n²). A single request of a few hundred kilobytes pinned a CPU core for minutes. PHP, Java, Python, Ruby and more were vulnerable the same week.

Recall lesson 1's exact phrasing: engineering a hash table is "the art of making the worst case so rare you can price them at their average". This attack is why rare isn't enough. Against an adversary, the worst case must be unguessable. The fix is keyed hashing: in 2012 Jean-Philippe Aumasson and Daniel J. Bernstein designed SipHash, a fast hash that mixes a secret 128-bit key chosen randomly at process start. Same table, same slots, but an attacker can no longer predict where any key lands, so they can no longer manufacture collisions. Python (default since 3.4), Ruby, and Rust's default hasher all adopted it. That's why SipHash carries a key, and why it appeared in the "good hash functions" list earlier.

The randomness has a visible side effect, and Go turned it into a design statement. Hash order was never meaningful (it's whatever the hash scattered), but programmers kept shipping code that accidentally depended on iteration order, code that broke whenever a seed or implementation changed. So Go seeds each process's map hashing randomly and deliberately randomizes map iteration order on every loop, so the dependency can't even form. The API lesson: never depend on hash order; if you need order, sort the keys. (Python dicts have preserved insertion order since 3.7, but that's extra bookkeeping layered on top of the table, not hash order leaking through.)

The key contract

Two clauses, both load-bearing.

Keys must hold still. Lesson 4 told you immutable strings cache their hash and that dict keys must not mutate; here is the full mechanism. Insert a key object, and its hash decides slot 3. Now mutate the object: its bytes changed, so its hash changed, so every future lookup probes slot 6. Nobody moved the entry. It still sits in slot 3, unreachable: lost without being deleted. This is exactly why Python refuses a list as a dict key and accepts a tuple, and why "hashable" and "immutable" travel together.

Equal keys must hash equal. If two keys compare equal but hash differently, the table stores them in different slots and treats them as strangers. Java spells this rule out as the equals/hashCode contract: override both or neither. Break either clause and the table doesn't crash; it quietly loses things, which is worse.

The real code

The videos stay in pseudocode; here is a minimal but honest hash map, chaining plus threshold resize, in the three languages this course carries. The hash is real FNV-1a.

function fnv1a(key: string): number {
  let hash = 0x811c9dc5 // FNV offset basis
  for (let i = 0; i < key.length; i++) {
    hash ^= key.charCodeAt(i) // mix in one byte
    hash = Math.imul(hash, 0x01000193) // multiply by FNV prime, mod 2^32
  }
  return hash >>> 0 // force unsigned
}
 
interface Entry {
  key: string
  value: number
  next: Entry | null
}
 
class HashMap {
  private buckets: (Entry | null)[] = new Array(8).fill(null)
  private count = 0
 
  get(key: string): number | undefined {
    const slot = fnv1a(key) % this.buckets.length
    for (let e = this.buckets[slot]; e !== null; e = e.next) {
      if (e.key === key) return e.value
    }
    return undefined // hit the end of the chain: not present
  }
 
  set(key: string, value: number): void {
    if (this.count / this.buckets.length > 0.75) this.resize()
    const slot = fnv1a(key) % this.buckets.length
    for (let e = this.buckets[slot]; e !== null; e = e.next) {
      if (e.key === key) {
        e.value = value // existing key: overwrite
        return
      }
    }
    this.buckets[slot] = { key, value, next: this.buckets[slot] } // prepend
    this.count++
  }
 
  private resize(): void {
    const old = this.buckets
    this.buckets = new Array(old.length * 2).fill(null)
    this.count = 0
    for (let head of old)
      for (let e = head; e !== null; e = e.next) this.set(e.key, e.value)
  }
}

Read the TypeScript against the lesson. fnv1a is the byte walk: XOR a byte in, multiply by the prime, 32-bit wrap (Math.imul keeps the multiply in 32 bits, >>> 0 makes it unsigned). Both get and set open with the same two-step ritual, hash then mod, manufacturing the index. get walks the chain comparing actual keys, because the slot only says "maybe". set checks the load factor before inserting: cross 0.75 and resize doubles the bucket array and re-inserts every entry, which re-runs hash-mod against the new length, the renumbered street in code. The whole worst-case story lives in those for loops over chains: their length is what the load factor cap is bounding.

The Go version is the same skeleton, two Go notes. Unsigned arithmetic comes free: uint32 multiplication wraps by definition, so fnv1a needs no masking tricks. And Get returns the idiomatic (value, ok) pair, the same shape as Go's own v, ok := m[k], because "absent" and "stored zero" are different answers.

The C++ resize does something the other two don't: it relinks the existing nodes into the new bucket array instead of re-inserting copies. The entries never move in memory, only the pointers between them change, which is cheaper, and it demonstrates a guarantee real C++ tables make: std::unordered_map promises that rehashing never invalidates pointers or references to elements, which is precisely why the standard's requirements effectively mandate a chaining design. (A production version would also need a destructor and copy/move rules for those newed nodes; omitted to keep the structure visible.)

What the standard libraries actually are, one honest line each: Python's dict is open addressing with a compact two-array layout (that's where the 3.7 insertion-order guarantee comes from). Go's map is a Swiss-table design as of Go 1.24, metadata bytes and group probing included. C++'s std::unordered_map is chaining, locked in by the pointer-stability and bucket-API guarantees above, which is also why C++ performance circles reach for Abseil or other open-addressing maps when those guarantees aren't needed.

Where this shows up in production

  • Your language runtime, constantly. Python objects, modules, and keyword arguments are dicts; JavaScript engines back object property storage with hash-based structures when objects get irregular; every symbol table in every compiler is a hash map. A meaningful slice of all CPU time everywhere is hashing keys.
  • Databases. A hash join builds a hash table over the smaller side of a join and probes it with the larger: O(n + m) instead of O(n × m), the GTA fix at table scale. Postgres also offers hash indexes alongside B-trees for pure equality lookups.
  • Caches. Redis and memcached are, at heart, one big hash table with a network port, and Redis's incremental rehash exists because that table must never stop to rebuild.
  • The deduplication move. t0st's fix, "replace the scan with a set", is the single most reusable optimization in this course, and now you know its full price sheet: O(1) average, O(key length) fine print, a resize pause unless engineered away.
  • One nod across the course boundary: spreading keys across servers instead of slots, so that adding a machine doesn't renumber every key's home, is consistent hashing, and it belongs to the distributed systems course.

No order: the price, and the bridge

Cash the promise out. A hash table is an array plus an index factory. Average O(1) because a decent hash spreads keys and a load-factor cap keeps crowds small. Worst case O(n), real enough that attackers weaponized it, now made not just rare but unguessable with keyed hashing. The occasional rebuild, amortized away by doubling, or spread thin when latency budgets demand it. That is the structure t0st reached for, fully explained.

But look at what the hash function destroyed to buy that speed: it scattered the keys on purpose. Ask the table for "alice", instant. Ask for all users between "alice" and "bob" alphabetically, and it has no idea. Smallest key? No idea. Everything near a key? Gone, scattered, by design. O(1) lookup, at the price of all order. The next structures pay the opposite way: they keep every key sorted, answer range queries and nearest-neighbor and smallest-key, and still run in logarithmic time, by borrowing the one move you already trust completely: halving. Binary trees, and the four ways to walk them, are next.

Command Palette

Search for a command to run...