This site's Hash-Based category holds eleven 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 seven
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. 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 is a policy built on top
of a hash table (paired with a 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.
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.
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.
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.
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.
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.
| Entry | get guarantee | Load factor before resize | Reach 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 |