Introduction

Hash tables are everywhere — behind every dictionary, cache, and database index you have ever used. The idea is deceptively simple: run a key through a hash function, land on a slot, and the lookup is done in constant time. Most of the time, at least.

The trouble is collisions. Two keys can hash to the same slot, or a whole cluster of keys can pile up in adjacent slots. One key might reach its home slot in a single step while another must probe ten slots before it finds a free one. That imbalance slows lookups for the unlucky keys and, at high load factors, makes the table uncomfortably slow.

Robin Hood hashing, introduced by Pedro Celis in his 1986 doctoral thesis, fixes this with a single elegant rule added to ordinary linear probing: during insertion, if the incoming key has traveled farther from its home than the key currently sitting in the candidate slot, swap them. The newcomer — the "poor" key — takes the slot; the displaced key — the "rich" one — continues probing.

The name is deliberate. The algorithm steals slots from keys that got lucky (short probe distances) and gives them to keys that got unlucky (long probe distances). The result is a dramatically flatter distribution of probe lengths, with a provably small maximum probe length. Unlike the average case (which ordinary probing already keeps reasonable), Robin Hood cares about the worst individual key — and it wins there too.

Try It

Insert keys into the hash table below. Each slot shows the key it holds and its probe length — how many steps it took from its home slot to land here. Click Insert random key to add a new key and watch the Robin Hood rule displace shorter-probing keys to make room.

<div class="controls">
  <button id="btn-insert" type="button">Insert random key</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
  <span class="stat">Max probe: <b id="max-probe">0</b> &nbsp;|&nbsp; Keys: <b id="key-count">0</b> / <b id="table-size">0</b></span>
</div>
<div id="table-wrap">
  <div id="hash-table"></div>
</div>
<div id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stat { font-size: .85rem; color: #555; margin-left: .3rem; }
#table-wrap { overflow-x: auto; }
#hash-table { display: flex; gap: 3px; min-width: max-content; margin-bottom: .6rem; }
.slot { width: 44px; min-height: 56px; border-radius: 7px; border: 1.5px solid #cdd9e3;
        background: #f0f4f7; display: flex; flex-direction: column;
        align-items: center; justify-content: center; font-size: 11px; transition: background .25s; }
.slot .idx { color: #8a9db5; font-size: 9px; margin-bottom: 2px; }
.slot .key { font: 700 12px ui-monospace, monospace; color: #1d3557; }
.slot .probe { font-size: 10px; color: #666; }
.slot.empty { background: #eef1f4; border-color: #e0e5ea; }
.slot.filled { background: #dce8f3; border-color: #b0c8e0; }
.slot.just-inserted { background: #c6e0b8; border-color: #7db86a; }
.slot.displaced { background: #fde9c5; border-color: #e8a43a; }
.slot.probe-0 { border-color: #7db86a; }
.slot.probe-high { border-color: #e8703a; }
#log { font-size: .8rem; color: #444; min-height: 2.4em; line-height: 1.5; }
.log-ins { color: #0a7d33; }
.log-disp { color: #b85e00; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Robin Hood Hashing — open addressing with linear probing + displacement swap.
// Rule: when inserting key K at slot s, if the current occupant C has a SHORTER
// probe length than K (C is "richer"), swap K and C; C continues probing.
// This keeps the variance of probe lengths minimal (Celis 1986).

const SIZE = 13; // prime table size
let table = new Array(SIZE).fill(null); // null = empty; {key, home, probe}
let keyCounter = 0;

// Simple hash: djb2-style on the string, mod SIZE
function hash(key) {
  let h = 5381;
  for (let i = 0; i < key.length; i++) h = ((h << 5) + h + key.charCodeAt(i)) >>> 0;
  return h % SIZE;
}

function probeLen(slot, home) {
  return (slot - home + SIZE) % SIZE;
}

// Insert key using Robin Hood hashing. Returns {inserted, steps, log}.
function rhInsert(key) {
  const home = hash(key);
  let slot = home;
  let currentKey = key;
  let currentHome = home;
  let steps = 0;
  const events = [];

  for (let i = 0; i < SIZE; i++) {
    const pos = (home + i) % SIZE;
    steps++;
    if (table[pos] === null) {
      // Empty slot — place it
      table[pos] = { key: currentKey, home: currentHome, probe: probeLen(pos, currentHome) };
      events.push({ type: 'insert', pos, key: currentKey, probe: probeLen(pos, currentHome) });
      return { inserted: true, steps, events };
    }
    const resident = table[pos];
    const residentProbe = probeLen(pos, resident.home);
    const currentProbe = probeLen(pos, currentHome);
    if (currentProbe > residentProbe) {
      // Robin Hood: steal the slot from the richer resident
      events.push({ type: 'displace', pos, evicted: resident.key, placed: currentKey, probe: currentProbe });
      table[pos] = { key: currentKey, home: currentHome, probe: currentProbe };
      // Continue inserting the displaced resident
      currentKey = resident.key;
      currentHome = resident.home;
    }
    // else: current probe <= resident probe, keep probing
  }
  return { inserted: false, steps, events }; // table full
}

function maxProbe() {
  return table.reduce((m, s) => s ? Math.max(m, s.probe) : m, 0);
}

function keyCount() {
  return table.filter(Boolean).length;
}

function render(highlightPos, displaced) {
  const el = document.getElementById('hash-table');
  el.innerHTML = '';
  table.forEach((slot, i) => {
    const div = document.createElement('div');
    let cls = 'slot';
    if (!slot) {
      cls += ' empty';
    } else {
      cls += ' filled';
      if (slot.probe === 0) cls += ' probe-0';
      if (slot.probe >= 3) cls += ' probe-high';
    }
    if (i === highlightPos && slot && !displaced) cls += ' just-inserted';
    if (displaced && displaced.includes(i)) cls += ' displaced';
    div.className = cls;
    const idxDiv = document.createElement('div');
    idxDiv.className = 'idx'; idxDiv.textContent = i;
    div.appendChild(idxDiv);
    if (slot) {
      const keyDiv = document.createElement('div');
      keyDiv.className = 'key'; keyDiv.textContent = slot.key;
      const probeDiv = document.createElement('div');
      probeDiv.className = 'probe'; probeDiv.textContent = fmt('p=%probe%', { probe: slot.probe });
      div.appendChild(keyDiv); div.appendChild(probeDiv);
    }
    el.appendChild(div);
  });
  document.getElementById('max-probe').textContent = maxProbe();
  document.getElementById('key-count').textContent = keyCount();
  document.getElementById('table-size').textContent = SIZE;
}

function setLog(html) {
  document.getElementById('log').innerHTML = html;
}

const WORDS = ['alpha','beta','gamma','delta','epsilon','zeta','eta','theta',
               'iota','kappa','lambda','mu','nu','xi','omicron','pi','rho',
               'sigma','tau','upsilon'];

document.getElementById('btn-insert').addEventListener('click', () => {
  if (keyCount() >= SIZE - 1) { setLog('Table is nearly full — reset to continue.'); return; }
  const key = WORDS[keyCounter % WORDS.length];
  keyCounter++;
  const { inserted, events } = rhInsert(key);
  if (!inserted) { setLog('Table full.'); return; }
  const lastEvent = events[events.length - 1];
  const displacedPositions = events.filter(e => e.type === 'displace').map(e => e.pos);
  render(lastEvent.pos, displacedPositions.length ? displacedPositions : null);
  let logParts = [fmt('<span class="log-ins">Inserted <b>%key%</b> (home=%hash%, probe=%probe%)</span>', { key: key, hash: hash(key), probe: lastEvent.probe })];
  const displacedEvents = events.filter(e => e.type === 'displace');
  if (displacedEvents.length) {
    logParts.push(...displacedEvents.map(e =>
      fmt('<span class="log-disp"> ↳ displaced <b>%evicted%</b> from slot %pos%</span>', { evicted: e.evicted, pos: e.pos })));
  }
  setLog(logParts.join('<br>'));

  // Verify Robin Hood invariant: for every filled slot s,
  // no filled slot t just before s (in probe order from t's home) has a longer probe.
  // Simplified check: for each slot s with probe p>0, the slot at (s-1+SIZE)%SIZE
  let invariantOk = true;
  for (let i = 0; i < SIZE; i++) {
    if (!table[i]) continue;
    const p = table[i].probe;
    if (p === 0) continue;
    const prev = (i - 1 + SIZE) % SIZE;
    if (!table[prev]) { invariantOk = false; break; } // gap before a displaced key is impossible
    if (table[prev].probe < p - 1) { invariantOk = false; break; }
  }
  console.assert(invariantOk, 'Robin Hood invariant violated!');
});

document.getElementById('btn-reset').addEventListener('click', () => {
  table = new Array(SIZE).fill(null);
  keyCounter = 0;
  render(null, null);
  setLog('');
});

render(null, null);
Result
Console

Notice how the probe lengths stay tightly clustered. In a plain linear-probing table the unluckiest key would sit far from its home while others stay close — Robin Hood constantly re-balances, stealing from the short-probers and giving to the long ones. The max probe length shown at the top is always small even as the table fills up.

The Real Complexity

How good is Robin Hood hashing, mathematically?

  • Expected lookup is O(1)O(1). At a load factor α < 1, the average probe length for a successful search is roughly 1/(1 − α) — the same as classic linear probing. Robin Hood does not improve the average; it improves the distribution.
  • Maximum probe length is O(log⁡n)O(\log n). This is the key theoretical win: with high probability, no key ever sits more than O(log⁡n)O(\log n) steps from its home. Classic linear probing can produce clusters where the worst key needs O(n)O(n) probes.
  • Variance drops dramatically. Pedro Celis proved in 1986 that the variance of probe lengths under Robin Hood hashing is asymptotically constant as n grows — for ordinary linear probing it grows without bound. A constant variance means all keys are treated nearly equally, regardless of how unlucky their hash was.
  • Insertion is still O(1)O(1) expected. The displacement swaps add work, but each insertion still runs in expected constant time at typical load factors.
  • Backward-shift deletion is clean. Removing a key from a Robin Hood table can be done by backward-shifting subsequent keys rather than leaving a tombstone, keeping the invariant intact without a full rebuild.

The technique is solved in the sense that its asymptotic properties are fully understood and it is provably better than naive open addressing in the worst case. It was introduced by Pedro Celis (1986) and later refined by Pagh, Rodler, and others who showed related techniques (like cuckoo hashing) can achieve O(1)O(1) worst-case lookup — but Robin Hood hashing remains popular in practice for its simplicity and cache friendliness. See also hash tables and P vs NP for the broader context of what "efficient" really means.

Where It Matters

The tight worst-case guarantee and cache-friendly layout make Robin Hood hashing a go-to choice wherever hash tables face high load or latency requirements:

  • Programming language runtimes. Rust's standard HashMap used Robin Hood hashing until version 1.36, when it switched to Swiss Tables (a SIMD-accelerated variant). Many high-performance C++ and Java implementations use it internally.
  • Database indexes. In-memory hash indexes in databases like DuckDB and RocksDB rely on open-addressing schemes with Robin Hood-style displacement to stay fast as the table fills.
  • Caches and key-value stores. A flat probe-length distribution means lookup latency is predictable — vital for caches where a single slow lookup defeats the purpose. Redis and similar stores use related open-addressing ideas.
  • Compiler symbol tables. Compilers resolve thousands of identifiers per second; a flat worst case keeps compilation times predictable.
  • Network routing tables. Packet-forwarding hardware uses tiny, extremely fast hash tables; Robin Hood hashing keeps the miss penalty bounded.

The deeper lesson connects to algorithm design: often the interesting question is not just the average case but the worst case for any individual input. Robin Hood hashing is a beautiful example of engineering that targets exactly that worry — and succeeds.

Conclusion

Robin Hood hashing is a reminder that small algorithmic ideas can have large practical payoffs. One rule — swap if the incoming key has traveled farther — turns an unequal probe distribution into a nearly flat one, cutting the worst-case lookup from O(n)O(n) to O(log⁡n)O(\log n) and reducing variance to a constant.

Pedro Celis solved the theory in 1986, and the idea spent decades quietly powering databases and runtimes before landing in Rust's standard library and making headlines. It is now a textbook technique, but the insight behind it — steal from the lucky to help the unlucky — remains one of the cleanest examples of how fairness and efficiency can be the same thing.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/robin-hood-hashing/Content licensed under CC BY-NC 4.0.