← Explainer Library

Interactive Explainer

Hash Tables, Collision by Collision

Hash tables look magical from outside: average $O(1)$ lookup, no ordering, used in every dictionary and cache. Inside, the magic is collision resolution. Insert keys into a small table and watch them collide; switch between chaining and three open-addressing strategies; watch the load factor creep up and the lookups slow down.

~15 min Data structures · Hashing · Cache
Prelude

The pigeonhole problem

A hash table maps a key — any key — to a slot in a fixed array. The mapping is a hash function $h(\text{key}) \mod m$ for table size $m$. The whole machine depends on this mapping being approximately uniform.

It can't be uniform and injective: there are infinitely many possible keys and only $m$ slots. So two different keys will eventually hash to the same slot. The question is what you do when they do.

Two big families of answers:

Below: a small 16-slot table you can insert into. Switch between strategies and watch the same insertion produce very different layouts.

Step 1

Insert, watch, probe

empty occupied probing just inserted tombstone robin-hood evict
size m 16
load factor α 0.00
avg probe length 0.0
n keys 0
enter a key and press add.

Things to try:

Step 2

What makes a hash function good

Two properties matter:

For non-cryptographic hashes — FNV-1a, Murmur — the attacker model is "no attacker, just uniform-ish inputs". Fast, good enough. For inputs an attacker controls (HTTP headers, JSON keys, network payloads), you need a keyed hash with a random secret: SipHash is the standard. Without it, an attacker who knows your hash function can synthesise keys that all map to one slot, turning your $O(1)$ table into an $O(n^2)$ DoS.

Hash flooding. The "first-letter" bad hash above is a toy version of a real 2003 attack on PHP, Perl, ASP.NET and the JVM. The fix every language eventually adopted is process-random hash seeding (so two runs of the same program see different hash values) and SipHash for user-controlled input. If you're writing a server in 2026, your runtime probably already does this.
Step 3

Separate chaining — the simple one

Each slot points to a linked list (or small array) of all keys hashing there. Insert: prepend to the list. Lookup: walk the list.

With a uniform hash, the expected chain length is $\alpha = n/m$ — the load factor. Lookup is $O(1 + \alpha)$ on average. Even at $\alpha = 5$ (a heavily loaded table), you're walking lists of about 5 nodes — far from $O(n)$.

What chaining gives up: cache locality. Each list node is a heap allocation; walking it is a cache miss. On modern hardware where main-memory latency is 100× L1, this is the difference between a fast hash table and a slow one.

Step 4

Open addressing — the fast one

Store every key directly in the array. On collision, probe along a sequence of slots until you find empty space. The whole table fits in contiguous memory; lookups touch one cache line.

Three classic probe sequences:

All open-addressing strategies break down before $\alpha = 1$ (you cannot insert into a full table — there's literally no empty slot). They typically resize when $\alpha$ crosses a threshold (0.5, 0.75, or 0.9 depending on the variant). Resize means: allocate a 2× table, rehash every key, free the old one. Amortised $O(1)$ per insert; a single slow insert when the resize fires.

Step 5

Robin Hood hashing — take from the rich

Linear probing with one twist: when a new key probes past an existing one, compare their displacement (probe count). If the incumbent's displacement is shorter than the newcomer's would be at this slot, swap them — kick the incumbent out and continue probing with it. Hence the name: take from the rich (low-displacement keys) and give to the poor (high-displacement keys).

The point: it equalises probe distances. After many inserts, every key's probe distance is within a constant factor of the average. Variance shrinks dramatically. Worst-case lookup time becomes proportional to the maximum displacement, which under uniform hashing is $O(\log n)$ rather than the $O(\sqrt n)$ of plain linear probing at high load factors.

Robin-hood hashing is the default in modern fast-hash-table libraries (Rust's HashMap via hashbrown until recently; Boost's flat_map; Google's absl::flat_hash_map) precisely because it makes high load factors viable.

Step 6

The cheat sheet

strategy avg lookup worst lookup memory cache delete typical $\alpha_\text{max}$
chaining $O(1 + \alpha)$ $O(n)$ (degenerate) $m + n$ + node ptrs poor easy (unlink) $\alpha$ unbounded
linear probing $\frac{1}{1 - \alpha}$ $O(\sqrt n)$ at high $\alpha$ $m$ excellent tombstones $\sim 0.7$
quadratic probing $-\frac{\ln(1-\alpha)}{\alpha}$ $O(\log n)$ $m$ good tombstones $\sim 0.5$
robin hood $\frac{1}{1 - \alpha}$ $O(\log n)$ $m$ + 1 byte/slot excellent backshift $\sim 0.9$
cuckoo (2 tables) $O(1)$ worst $O(1)$ worst $2m$ good easy $\sim 0.5$
Step 7

The advanced wing

Step 8

Sharp edges

Step 9

Reading list