Cairn
data structures · open addressing, one table, one hash function · O(1) average get/put/delete

↩ back to Hash-Based

Robin Hood Hashing

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.

Try it

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.

Loaded a sample table (8 slots). Try deleting "ram" then getting "pig" with backward-shift delete unchecked.

Core operations

Reference implementation

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.

Pitfalls

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.

No early-exit means a guaranteed miss pays the full variance Robin Hood was supposed to tame. The reference get above stops at a match or an empty slot — nothing else. But the Robin Hood insert invariant guarantees something stronger: at probe step s into a search (0 for the home slot, 1 for the next, and so on), if the key occupying that slot has a PSL less than s, the key being searched for cannot be anywhere further along this probe sequence. If it were, it would have arrived with PSL s at this very slot during its own insert and evicted the lower-PSL resident right here, per the swap rule above — so a resident with a smaller PSL than the searcher's current step count is proof of absence, not just a bad sign. A correct get can stop the instant that happens, without walking on to the next empty slot. The shipped version above never checks for it, so a guaranteed miss keeps walking anyway. Measured against the exact reference implementation, 2,000 random string keys, right up against this page's own 0.75 load-factor resize threshold: shipped get averages 10.43 probes per miss (worst single miss: 116); adding the one extra comparison drops that to 3.19 average (worst: 16) — a 3.3× average, 7× worst-case cut, for free, with zero effect on hits (every present key still resolves in the same number of probes either way, confirmed across the same run). This is exactly the gap Choosing a Hash Table Collision Strategy's own live race surfaces on the miss side while this page's other three Pitfalls above only ever test keys already in the table.

Pick a key count and click Measure — builds a fresh table right up against this page's own 0.75 load factor, then counts the real probes every guaranteed-miss lookup takes two ways: exactly as the shipped get above runs today, and with the one-line early-exit check added.

Where Robin Hood hashing shows up

Complexity

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.