Robin Hood Hashing

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.

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">{{btn_insert}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

How good is Robin Hood hashing, mathematically?

• Expected lookup is $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)$. This is the key theoretical win: with high probability, no key ever sits more than $O(\log n)$ steps from its home. Classic linear probing can produce clusters where the worst key needs $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)$ 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)$ 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.

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.

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)$ to $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.