Cairn
guides · comparison, not a new algorithm

↩ back to Guides

Choosing a Hash Table Collision Strategy

This site's Hash-Based category holds fourteen entries, but only four answer the same question: given a fixed number of slots and two keys that hash to the same one, how do you resolve the collision while building a hash table from scratch. Hash Table (separate chaining), Cuckoo Hashing, Robin Hood Hashing, and Hopscotch Hashing all answer it as four different collision-resolution strategies for the same put/get/delete contract. The other ten entries set aside, each for a different reason: Linear Probing answers the identical question but is set aside anyway — it's the same one-table, one-hash-function contract Robin Hood Hashing uses, minus the swap rule, and Robin Hood Hashing's own Pitfalls section already showed that rule never raises the total probe-step cost across a batch of inserts, only redistributes it. There is no input on which plain linear probing beats Robin Hood hashing at this exact contract, so it isn't an additional branch of this decision, just the baseline the "hard bound" and "variance" questions below are asking about. Double Hashing answers the same question with a different per-key step instead of linear probing's fixed one, but its own Complexity section makes the identical "not a real branch" case against Robin Hood hashing for a second, independent reason on top of the first: it introduces a step function that has to satisfy a global coprime-with-the-table-size property no individual test case makes obvious, a correctness-critical parameter Robin Hood hashing simply doesn't need. Extendible Hashing answers a question one level up from any of the four — not how to resolve a collision inside a fixed-size table, but how the table grows without a full rehash once it's out of room — a directory of bucket pointers that splits one overflowing bucket at a time, covered on its own page rather than folded into this one's four-way comparison since none of the four below face that question the same way (fixed tables that simply rehash everything on resize). Consistent Hashing answers a different question entirely — which server owns a key, not which slot inside one fixed array — needed once, as hash-table.html's own Complexity section puts it, "the servers themselves can come and go," which needs the buckets to be far more stable than a fixed array's % numBuckets allows. Virtual Nodes is set aside for the identical reason — it's a refinement of Consistent Hashing's own ring, not a new answer to this page's collision question. Bloom Filter never stores a key at all, only a fixed number of bits per possible member, so there's no collision to resolve in the sense this page means — two keys setting the same bit isn't a conflict that needs breaking, it's the entire mechanism. LRU Cache and LFU Cache are both policies built on top of a hash table (each paired with its own flavor of doubly linked list for eviction order) rather than another way to resolve a collision inside one. Perfect Hashing doesn't have a live put/delete at all — its own page's whole point is that the key set is fixed and known before the table is built, so there's no "while building a hash table from scratch, two keys just collided" moment this page's four-way comparison is about; it trades that flexibility away entirely for a stronger guarantee than any of the four below offer. Minimal Perfect Hashing is set aside for the identical reason — the same fixed-key-set, no-live-put contract as Perfect Hashing, just a tighter space bound.

Two questions, asked in order

First: does get need a hard worst-case bound — a fixed, small number of probes no matter what the table has been through — or is a good average with an occasional slow lookup acceptable? If a good average is enough, skip straight to the variance question below — only two of the four strategies here offer a real worst-case guarantee, and neither gives it away for free. If a hard bound is required, a second question decides which of the two: is a second table and a second hash function available? Cuckoo hashing buys its bound with exactly that. Hopscotch hashing buys the identical bound with neither — one table, one hash function, and a per-slot bitmap that caps how far any key can live from its own home instead.

A hard bound, two tables allowed: cuckoo hashing

Cuckoo Hashing gives every key exactly two candidate slots, one in each of two separate tables, and get checks both and stops — O(1) worst case, "two fixed slot checks, full stop, regardless of how the table was built," as its own page states. That guarantee is exactly what a hardware lookup table or a latency-sensitive path needs, where an occasional slow chain is an unacceptable spike rather than an averaged-out cost — its own "Where cuckoo hashing shows up" section names network switches doing forwarding-table lookups in silicon as the canonical case, plus the site's own Cuckoo Filter, built directly on this page's displacement idea.

The guarantee is bought on the put side, not given away for free. Insert is only O(1) expected — most inserts resolve within one or two evictions, but a displacement chain has no small worst-case bound and can run all the way to a kick cap before forcing a full O(n) rehash. The page's own Pitfalls section shows this isn't hypothetical: removing the kick cap from the reference implementation and rerunning its own sample sequence makes the eviction chain cycle through the same six keys for over 1,000 kicks with no sign of stopping — a genuine cycle in the eviction graph, not merely a long chain that would eventually resolve. And the guarantee needs headroom the other three strategies don't: the same worked example hits a cycle at just 7 of 16 slots filled — 44%, nowhere near the 0.75 the chaining hash table tolerates comfortably. Production cuckoo tables generally keep load under roughly 50%, trading memory for the worst-case bound on top of the trickier insert. Reach for cuckoo hashing specifically when get's worst case has to be bounded no matter what and a second table and hash function are genuinely available; if not, the next section covers the alternative that gets the same bound without them.

A hard bound, only one table: hopscotch hashing

Hopscotch Hashing gives get the same shape of guarantee cuckoo hashing does — a fixed, small number of slots checked, always — using the same single table and single hash function robin hood hashing and chaining use instead of a second one. Every key is guaranteed to live within a fixed neighborhood of its own home slot, and a per-home hop-info bitmap tells get exactly which of that neighborhood's offsets to check: O(1) worst case, checked against a fixed constant rather than an average. Reach for it over cuckoo hashing specifically when a second table and hash function aren't available or worth the memory, and over robin hood hashing when even a rare, occasional long probe chain — which robin hood hashing's own page admits it cannot rule out — is genuinely unacceptable.

The cost moves entirely onto put. An insert landing too far from home doesn't fail or fall back to scanning; it repeatedly displaces a neighbor that can legally move closer, "hopping" the empty slot backward until it's within reach. Its own Pitfalls section shows skipping that step doesn't corrupt anything loudly — it just makes a physically-present key permanently unreachable to a correct, bitmap-bound get, the same shape of failure as robin hood hashing's own skipped-backward-shift-delete pitfall. And the resize trigger isn't only the usual load factor: a neighborhood that fills up entirely with same-home keys can force a resize well under 0.75 even though the table as a whole is nowhere near full — its own worked example resizes an 8-slot table at just 5 entries, 62.5% full, for exactly this reason. Neither cuckoo hashing's ~50% practical ceiling nor robin hood hashing's plain 0.75 shares that particular failure mode. Reach for hopscotch hashing when the hard bound cuckoo hashing offers is required but a second table and hash function aren't an option worth taking.

No hard bound needed, but variance still matters: robin hood hashing

Robin Hood Hashing makes no stronger worst-case promise than plain chaining — a pathological key set can still build one long probe run, and its own Complexity section says so directly: "Worst case is still O(n)... just as it can for plain linear probing or chaining." What it changes is the spread around the average, not the average itself. Its own Pitfalls section measured this precisely rather than just asserting it: inserting the same six-key sample with the Robin Hood rule off lands one key at probe sequence length 5 while every other key sits at 0 — total probe steps across all six keys: 5. With the rule on, every displaced key lands at PSL 1 instead — maximum PSL 1, not 5 — and the total probe-step count across all six keys is still 5, unchanged. Robin Hood hashing doesn't reduce the average work a lookup does; it reduces how badly any single key can get unlucky, using one table and one hash function, at the same 0.75 load factor the chaining table tolerates — no second table's worth of headroom to sacrifice the way cuckoo hashing needs. The cost of that low-variance property is a stricter deletion rule: skipping the backward-shift step on delete doesn't just slow a later lookup, it can make a key the table still holds permanently unreachable, as the page's own worked example shows a live get silently returning "not found" for a key still sitting one slot further on. Reach for Robin Hood hashing when everyday probe lengths tightly clustered near the average is worth more than plain chaining's simplicity, but a hard worst-case bound isn't worth cuckoo hashing's headroom and eviction-cycle risk.

Neither of the above: hash table (chaining)

If no per-lookup guarantee is needed and probe-length variance isn't a concern worth managing, plain separate chaining is the simplest of the four to build and reason about: each bucket just grows a list, so a bad hash function or an unlucky cluster of collisions degrades a lookup's speed, never its correctness — "collisions aren't a bug to eliminate... a good hash function just spreads them thin instead of piling them into a few buckets," as its own page puts it. It tolerates as high a load factor as any of the four before needing to resize (0.75, the same baseline threshold Robin Hood hashing and hopscotch hashing reuse, well above cuckoo hashing's practical ~50% ceiling), and it carries none of cuckoo hashing's eviction-cycle risk, Robin Hood hashing's backward-shift-on-delete requirement, or hopscotch hashing's neighborhood-exhaustion resize trigger — a bucket is just a list; removing from it is just removing from a list. The cost is the one the other three entries exist to close: get and put are only O(1) average, and one badly-behaved chain can still degrade a lookup to a full linear scan with no guardrail against it. That's the right trade whenever "average is fine, worst case is rare and tolerable" actually describes the workload — which, for most general-purpose uses, it does; chaining is why this is the site's default hash table implementation, not an inferior option.

Side by side

Entryget guaranteeLoad factor before resizeReach for it when
Cuckoo Hashing O(1) worst case, always two probes ~50% practical ceiling, two tables a hard bound on lookup latency is required, no exceptions
Hopscotch Hashing O(1) worst case, checks a fixed neighborhood 0.75, or earlier if a neighborhood fills; one table a hard bound is required but a second table/hash function isn't an option
Robin Hood Hashing O(1) average, low variance, O(n) worst case 0.75, one table tightly clustered probe lengths matter, hard bound isn't required
Hash Table (chaining) O(1) average, O(n) worst case 0.75, one table simplicity is the priority, average-case speed is enough

Race them yourself

Every claim above about worst-case bounds and variance comes from each page's own small worked example — worth watching hold (or not) over many random keys instead of just the one sample each page already walks through. This runs the exact reference implementation from Hash Table, Cuckoo Hashing, Robin Hood Hashing, and Hopscotch Hashing, unmodified, in your own browser: the same random keys go into all four, then every key gets looked up (a guaranteed hit) and an equal number of fresh random keys get looked up too (a guaranteed miss). These are all too fast for performance.now() to time meaningfully at realistic sizes, the same reason the Searching guide's own race counts instead of timing — so this counts distinct slots touched per lookup via a Proxy on each table's backing array, the same technique, with one wrinkle: cuckoo hashing's own get re-indexes the same slot up to three times for one logical check (if (t[i] && t[i][0]===key) return t[i][1]), so counting raw reads instead of distinct indices would triple-count a single real probe and make cuckoo hashing look far worse than its own documented "exactly one or two" bound.

Looking up a key that's there (hit)

Looking up a key that's not there (miss)

Press "Run race" to insert the same random keys into all four tables and measure real probes.

Cuckoo hashing's hit and miss bars barely move no matter the key count: get checks at most one slot in each of its two tables, full stop, so both average and worst case sit at or near that fixed ceiling every run — the live version of the "exactly one or two" guarantee stated above. Hopscotch hashing's bars stay just as flat, bounded by its own fixed neighborhood window instead of a second table. Robin Hood hashing's hit bars land close to chaining's, which looks at first like it undercuts the variance story above — but that story was always about PSL spread, not raw hit cost, and the real surprising result shows up on the miss side instead: this page's reference get has no early-exit once the current probe's PSL would already be impossible to beat, so a miss keeps scanning all the way to the next empty slot — at 1,600 keys, Robin Hood hashing's worst observed miss reliably reaches double digits across repeated runs, well above plain chaining's worst miss at the same key count (single digits every run) — a real cost Robin Hood hashing's own Pitfalls section now measures directly: its shipped get has no early-exit once the current probe's resident PSL would already be impossible to beat, so a miss keeps scanning all the way to the next empty slot when one extra comparison per probe would let it stop early instead — a measured 3×-plus average-case cut on that page's own benchmark.