The site's chaining hash table handles a collision by growing a list at the colliding bucket. Its cuckoo hashing neighbor handles one by evicting whoever's there into a second table via a second hash function. Robin Hood hashing is open addressing like cuckoo hashing — no lists, every key lives directly in one array slot — but with only one table and one hash function. A key's probe sequence length (PSL) is how many slots past its own computed home it actually had to travel before finding a free one. Plain open addressing (linear probing with no further rule) just lets PSLs pile up wherever collisions happen to land. Robin Hood hashing adds exactly one rule on top: while inserting, if the slot in front of you is held by a key with a smaller PSL than yours, that key has had an easier time so far than you have — evict it, take its slot, and go find the evicted key a new home the same way, continuing to carry whichever entry currently has the largest claim to being "poor."
The name is the obvious one: take from the slot that's closer to its own home (the "rich" key, lucky enough to have a short probe distance) and give it to the one that's traveled further (the "poor" key). No key ever gets stuck with an enormous PSL just because it happened to arrive after its neighbors — the demo below inserts the same six keys with the rule on and off and the difference is dramatic, not subtle.
Put a key/value pair, get one back, or delete it. The log traces every slot the operation
touches: whether it was empty, held a match, or (on insert) held a "richer" key worth evicting.
The sample loads six keys — hen, fox, doe,
hog, ram, pig — into an 8-slot table in that order, chosen
because ram and pig both hash to slot 6, and by the time
pig arrives, slots 6 and 7 are already both occupied. With Robin Hood
swap unchecked, click "Reload sample": pig ends up dragged all the way
around the table to a PSL of 5, the single worst-off key by a wide margin. Check the box and
reload the identical sequence: the same six keys land with a maximum PSL of 1 — the total number
of probe steps taken across all six keys is identical either way (5), only how unevenly that cost
is spread out changes. Then try deleting ram and getting pig back with
Backward-shift delete unchecked, to see a key the table still holds get reported
as missing.
O(k) for a key
of length k.hash(key), comparing keys.
Stop and return the value on a match, stop and report "not found" the instant an empty slot
turns up — a match can never sit past a gap in its own probe sequence, as long as delete
maintains that invariant (see Pitfalls). O(1) average.hash(key), tracking the
arriving key's own PSL as it goes. An empty slot: place it, done. A slot already holding that
key: overwrite the value, done. A slot held by a different key with a smaller PSL than
the arriving key's current PSL: swap — the arriving key takes the slot, and the evicted key
becomes the new "arriving key," continuing the same walk one slot further with its own PSL one
higher than it was. O(1) average, resizing (doubling past a 0.75 load factor,
reinserting everything, same threshold as the chaining hash table) amortizes to O(1)
per put over a run of inserts.get to find the slot, then
clear it and pull the run of following occupied slots back one position each, decrementing each
one's PSL by one, stopping the moment a slot is empty or already sitting at its own home (PSL
0) — backward-shift deletion. This keeps every remaining key's probe sequence
gap-free without needing a tombstone marker.class RobinHoodHashTable {
#size;
#table;
#count = 0;
constructor(size = 8) {
this.#size = size;
this.#table = new Array(size).fill(null);
}
#hash(key, size = this.#size) {
let h = 0;
const s = String(key);
for (let i = 0; i < s.length; i++) h = (h * 31 + s.charCodeAt(i)) >>> 0;
return h % size;
}
get(key) {
let i = this.#hash(key);
for (let step = 0; step < this.#size; step++) {
const slot = this.#table[i];
if (!slot) return undefined;
if (slot.key === key) return slot.value;
i = (i + 1) % this.#size;
}
return undefined;
}
has(key) { return this.get(key) !== undefined; }
put(key, value, robinHood = true) {
let i = this.#hash(key);
let cur = { key, value, psl: 0 };
for (let step = 0; step < this.#size; step++) {
const slot = this.#table[i];
if (!slot) { this.#table[i] = cur; this.#count++; this.#maybeResize(robinHood); return; }
if (slot.key === cur.key) { slot.value = cur.value; return; }
if (robinHood && cur.psl > slot.psl) {
this.#table[i] = cur;
cur = slot;
}
i = (i + 1) % this.#size;
cur.psl++;
}
throw new Error('table full');
}
#maybeResize(robinHood) {
if (this.#count / this.#size <= 0.75) return;
const old = this.#table.filter(Boolean);
this.#size *= 2;
this.#table = new Array(this.#size).fill(null);
this.#count = 0;
for (const slot of old) this.put(slot.key, slot.value, robinHood);
}
delete(key, backwardShift = true) {
let i = this.#hash(key);
let found = -1;
for (let step = 0; step < this.#size; step++) {
const slot = this.#table[i];
if (!slot) return false;
if (slot.key === key) { found = i; break; }
i = (i + 1) % this.#size;
}
if (found === -1) return false;
this.#table[found] = null;
this.#count--;
if (!backwardShift) return true;
let empty = found;
let next = (found + 1) % this.#size;
for (let step = 0; step < this.#size - 1; step++) {
const slot = this.#table[next];
if (!slot || slot.psl === 0) break;
this.#table[empty] = slot;
slot.psl--;
this.#table[next] = null;
empty = next;
next = (next + 1) % this.#size;
}
return true;
}
}Every index step uses % this.#size, including inside put's main
loop — dropping that modulo is the third Pitfall below. #maybeResize only fires
after a genuinely new key is placed (not a value-only overwrite), matching the chaining hash
table's own 0.75 threshold so the two structures are directly comparable. Verified against a
plain-Map reference model over 4,000 randomized trials (300-800 interleaved
put/get/delete calls each, key spaces from 5 to 20 across table sizes that force both frequent
collisions and repeated resizes), checking every get/delete result
against the model after every call, plus that the live entry count always matches the model's
size and no two occupied slots ever hold the same key — see /tmp/robinhood_ref2.js,
scratch, not committed. Separately confirmed the page's own six-key walkthrough by hand against
this exact class: robinHood=false and robinHood=true produce the two
tables described above and in the Pitfalls section, byte for byte.
Skipping the swap doesn't just make things "a bit less even" — it can wreck one key's
probe length while barely touching the total. Inserting hen,
fox, doe, hog, ram, pig into an
empty 8-slot table with the Robin Hood rule off lands pig at index 3 with a
PSL of 5 — dragged past five already-occupied slots it has no other reason to sit near — while
every other key sits at PSL 0. Total probe steps across all six keys: 5. Rerunning the identical
sequence with the rule on lands every displaced key at PSL 1 (only ram,
never displaced, stays at PSL 0) — maximum PSL 1 instead of 5. Total probe steps across all six
keys: still 5, unchanged. Both numbers came from actually running the reference implementation
above, not from reasoning about it — Robin Hood hashing doesn't reduce the average work a lookup
does, it reduces how badly any single key can get unlucky, which is exactly the variance-not-mean
distinction the demo's own stats line makes visible.
Deleting without backward-shift leaves a key the table still holds unreachable.
In the same loaded sample (robinHood on), ram sits at slot 6 (PSL 0) and
pig sits at slot 7 (PSL 1) — pig's probe sequence runs straight through
ram's slot. Delete ram by simply nulling slot 6 and leaving everything
else where it is, then call get("pig"): the walk starts at pig's home
(slot 6), finds it empty, and stops immediately — reporting "not found" even though
pig is still sitting at slot 7, one step further on. The real reference
implementation's backward-shift step instead pulls pig back into slot 6 (and, in this
example, several more keys cascade back one slot behind it) the moment ram is
removed, so every remaining key's probe sequence stays gap-free and get keeps working
without needing a tombstone marker at all. Verified against the exact shipped
delete/get pair with backwardShift forced to
false: get("pig") genuinely returns undefined, not just a
slower correct answer.
Forgetting the modulo on the probe index during insert loses a key silently, not
loudly. JavaScript arrays grow to fit whatever index gets assigned, so replacing
i = (i + 1) % this.#size with plain i = i + 1 inside put's
loop doesn't throw — it just writes past the intended 8 slots. Rerunning the same six-key sequence
against that broken version lands fox at index 8, outside the table entirely, while
the array silently reports a length of 9. A correctly written
get — one that does wrap its own probe index with % size, exactly as the
reference implementation above does — starts at fox's real home, walks slots 7, 0, 1,
2, hits the empty slot 3, and reports "not found." The insert believed it succeeded; the key is
gone. Checked by running the broken insert loop against every key in the sample and confirming
which ones a correct get can no longer find — fox is the only casualty
in this particular sequence, but which key gets lost depends entirely on insertion order and hash
values, not on anything visible at insert time.
HashMap. Before the switch
to the SwissTable-derived hashbrown implementation, Rust's std::collections::
HashMap used Robin Hood hashing specifically for the guarantee this page's demo makes
visible: bounded, predictable worst-case lookup times instead of an occasional very long
chain.robin_hood::unordered_map C++ library — a drop-in
replacement for std::unordered_map named directly after this algorithm, popular in
performance-sensitive C++ code specifically for the same low-variance property.get a genuine worst-case bound of two probes, no matter
what, at the cost of needing two tables and tolerating a lower load factor before eviction
cycles get likely. Robin Hood hashing doesn't offer that hard bound — a pathological input can
still build a long chain — but it keeps everyday probe lengths tightly clustered near the
average using one table, one hash function, and a real load factor a chaining table would
consider comfortable.Time: get, put, and delete are all
O(1) average, same headline as the site's
chaining hash table — Robin Hood hashing doesn't
change that average, only the spread around it, exactly as the first Pitfall's matched 5-vs-5
total-probe-count demonstrates. Worst case is still O(n): a pathological key set can
still build one long run, just as it can for plain
linear probing or chaining, and this page makes
no stronger guarantee than that — the site's cuckoo
hashing page is the one that trades this away for a hard O(1) worst case on
lookups specifically. Space: O(n), with the same
0.75-load-factor-then-double policy as the chaining hash table — a single table, so no second
array's worth of near-empty overhead the way cuckoo hashing's two tables carry.
This is one of four collision-resolution strategies the site covers for the same put/get/delete
contract — the site's chaining hash table, cuckoo hashing, and hopscotch hashing are the other three. Hopscotch
hashing keeps this page's single table and one hash function but trades away the low-variance,
unbounded-worst-case tradeoff this page makes for a hard worst-case bound on get,
using a per-slot bitmap instead of the unbounded probe walk this page relies on. See Choosing a Hash Table Collision Strategy
for the full four-way comparison.