Search tools and guides ⌘K
III · Hashing & lookup

Robin Hood hashing

Steal from the rich, give to the poor.

1985 · Pedro Celis · University of Waterloo
The story

In standard linear probing, lookup time varies wildly — some keys live at their hash, others probe 30 slots. Celis's insight: when inserting, if the slot you want belongs to a key that's "richer" (closer to its home) than you, evict it. The variance in probe distance collapses; max probe length stays under 10 even at 95% load.

How it works

Open addressing with linear probing. Every entry tracks its probe distance. On insert collision, compare distances; the entry with shorter distance "yields" and is reinserted further on. Lookups can stop early when probe distance exceeds the target's.

Where it lives

Rust's default HashMap (since 2016, replaced in 2018 by hashbrown which uses SwissTable). Several JIT compiler hash structures. Mozilla's memory profiler.

The key insight

Robin Hood's low variance lets you run at higher load factors safely — ~90% load with ~6-slot max probe distance. Saves memory in cache-pressured workloads.

More in Hashing & lookup
Hash table O(1), almost always. Cuckoo hashing Two slots, no chains. Consistent hashing Hashing that survives node changes. Perfect hashing Zero collisions, by design.
Across the cabinet
IV Count-Min sketch Approximate frequencies, in tiny memory. IV MinHash Set similarity, in a few hashes. IV t-digest Quantiles, fairly accurate, fully streaming. V Suffix array All suffixes, sorted. V Suffix tree Every substring, in linear space. V Rope A tree of small strings. V Piece table Edit a file without copying it. V Gap buffer A buffer with a hole at the cursor.
← All data structures