Robin Hood Hashing: Variance-Minimizing Open Addressing

The problem: linear probing's fat tail

Open addressing stores every entry directly in one array. When a key hashes to an occupied slot, the table probes forward for the next free cell. The number of steps from a key's ideal ('home') slot to where it actually lives is its probe sequence length (PSL), also called displacement or distance-from-home.

Plain linear probing has a nasty property called primary clustering: runs of occupied slots merge into ever-longer contiguous clusters, and any key hashing anywhere into a cluster must traverse the whole run. At load factor α = 0.9 the average successful search is modest, but the distribution is heavy-tailed — a few unlucky keys sit 40, 60, even 100 probes deep. That variance is what hurts: it blows cache-line budgets, wrecks tail latency, and makes lookups unpredictable.

• Average cost is fine; the maximum and the variance are the problem.
• Robin Hood keeps the same set of occupied slots but redistributes which key sits where, so no key is dramatically more displaced than its neighbors.

How it works: rob the rich, pay the poor

The whole scheme is one rule applied during insertion. Track each entry's PSL. While probing forward to insert a new key x, at each occupied slot compare PSLs:

• If the existing entry has a PSL greater than or equal to x's current PSL, leave it — x keeps probing.
• If x's PSL is now greater (it has traveled farther, so it is 'poorer'), evict the existing entry: x takes the slot, and the evicted entry becomes the new element being inserted, continuing to probe from there.

insert(key):
  slot = hash(key) % N;  psl = 0
  loop:
    if table[slot] is empty:
        table[slot] = (key, psl); return
    if table[slot].psl < psl:        # existing is 'richer'
        swap((key,psl), table[slot])  # rob it; carry evicted on
    slot = (slot + 1) % N
    psl += 1

The resulting invariant: within any probe run, PSLs are (weakly) sorted — a key is never found before one that is closer to home. This bounds how unequal displacements can get.

Complexity and a worked trace

Robin Hood does not change the mean successful-search cost — it is provably the same as linear probing, about ½(1 + 1/(1−α)). What it changes is the tail. Celis proved the variance of PSL is O(1) (bounded independent of table size), and the expected longest probe length is Θ(log n) at constant α, versus Θ(log n / log log n)-and-worse clustering for naive linear probing whose variance grows badly.

• Insert / lookup / delete: O(1) expected, O(max PSL) worst-case.
• A powerful optimization: because PSLs are sorted along a run, a lookup can stop early — if you reach a slot whose stored PSL is smaller than the distance you've traveled, the key cannot be present.

Insert order a,b,c,d, all hashing to slot 3 (N=8):
after a: [.. a@3(psl0) ..]
insert b: 3 taken, b.psl(0)==a.psl(0) -> move on;
          slot4 empty -> b@4(psl1)
insert c: 3,4 taken (psl 0,1 >= c's 0,1) -> c@5(psl2)
insert d: at slot3 d.psl0 not > a.psl0; slot4 not>; 
          slot5 c.psl2 == d.psl2 -> slot6 empty -> d@6(psl3)

Where it is used in real systems

Robin Hood hashing is a workhorse behind several high-performance hash-map implementations where predictable tail latency matters:

• Rust — the standard library's HashMap used a Robin Hood table for years (pre-2018) before switching to SwissTable/hashbrown; the technique is still widely used in the Rust ecosystem.
• Emmanuel Goossaert / Malte Skarupke's C++ maps — tsl::robin_map and Skarupke's flat_hash_map family are popular open-source Robin Hood tables praised for speed at high load factors.
• Databases and analytics engines use Robin Hood or Robin-Hood-inspired open addressing for in-memory join and group-by hash tables, where cache locality and bounded probe length beat pointer-chasing chains.
• Game engines and allocators favor it because a single flat array is cache-friendly and has no per-node allocation.

Its cousin, the SwissTable design (Google Abseil), shares the flat-array, metadata-byte philosophy and largely superseded pure Robin Hood in the highest-tier libraries — but the variance-minimizing insight remains foundational.

Compared to the alternatives

The right mental model is a spectrum of collision-resolution tradeoffs:

• vs. separate chaining: Robin Hood keeps everything in one contiguous array — far better cache behavior and no per-element allocation — but degrades toward higher load factors more gracefully only because of its variance control. Chaining tolerates α > 1 trivially; open addressing needs α < 1 and usually resizes near 0.7–0.9.
• vs. plain linear probing: identical memory layout and average cost, but Robin Hood adds a per-slot PSL (often 1 byte) and swap logic to buy dramatically lower variance and early-exit lookups. Almost strictly better at high α.
• vs. cuckoo hashing: cuckoo gives a hard O(1) worst-case lookup (≤2 probes) but needs two tables, two hash functions, and can fail insertion, forcing a full rehash. Robin Hood never fails an insert (until resize) and has better average cache locality, at the cost of a probabilistic rather than guaranteed worst case.

Pitfalls, deletion, and significance

Deletion is the subtle part. You cannot just blank a slot — that would break probe runs. Robin Hood's elegant answer is backward-shift deletion: after removing an entry, walk forward shifting each subsequent element back one slot (decrementing its PSL) until you hit an empty slot or an element already at PSL 0. This restores the invariant and, unlike tombstones, leaves no dead cells to bloat future probes.

• High-load-factor cliff: like all open addressing, performance falls off sharply as α → 1; resize before ~0.9.
• Insertion is costlier: the swap/carry chain means inserts touch more slots than a naive linear probe, trading write cost for read predictability.
• Needs good hashing: a weak hash concentrates keys and no reordering can fully rescue it.

Its lasting significance: Robin Hood proved you can keep the cache-friendly flat-array layout of open addressing while taming the tail latency that had made it risky at high occupancy — a lesson carried directly into modern SwissTable-style maps.

Robin Hood hashing versus other collision-resolution schemes at high load factor

Scheme	Avg probe (successful)	Worst-case tail	Deletion	Memory overhead
Separate chaining	1 + α/2	O(log n / log log n) longest chain	Trivial (unlink node)	1 pointer per element + node headers
Linear probing	~½(1 + 1/(1-α))	Very long clusters (high variance)	Tombstones or backward shift	None (bit array)
Robin Hood (linear)	Same mean as linear probing	Low variance; expected max ~Θ(log n)	Backward-shift (no tombstones)	~1 byte/slot for stored distance
Cuckoo hashing	≤ 2 (guaranteed)	O(1) worst-case lookup	Trivial	2 tables; insert can fail/rebuild