Robin Hood hashing

Deep dive

How it works

In: a key (and a value on insert) · Out: the value or absent; insert reports update or new · State: one array of entries plus each entry's distance from its home slot (DIB) · Cost: expected O(1); at load 0.9 a hit probes about 5.5 slots, a miss stops about as early

slot:   0     1     2     3     4
key:    a     b     c     .     .
home:   0     0     1
dib:    0     1     1      insert x (home 1, dib 0 at slot 1)

At slot 1, b has DIB 1 > x's 0: move on. Slot 2: c has DIB 1, equal to x's: move on. Slot 3 empty: place x with DIB 2.

1. Lookup: start at home = h & mask, d = 0. At each slot: empty or dib[slot] < d → absent. Key match → found. Else d += 1, next slot.
2. Insert: same walk; before the first swap compare keys (update if equal). When dib[slot] < d, swap the walker with the resident and continue with the evicted one.
3. Delete (backward shift): remove entry at i; while the next slot holds an entry with dib > 0, move it back one slot and decrement its DIB. Stop at an empty slot or an entry at home.

Code

// Robin Hood map u64 -> V. dist[i]: 0 = empty, else DIB + 1. Max stored DIB 253; larger triggers growth.
fn hash(k: u64) -> u64 { let x = k.wrapping_mul(0x9E37_79B9_7F4A_7C15); x ^ (x >> 32) }

pub struct RhMap<V: Copy + Default> { dist: Vec<u8>, keys: Vec<u64>, vals: Vec<V>, mask: usize, len: usize }

impl<V: Copy + Default> RhMap<V> {
    pub fn new(cap: usize) -> Self {
        let n = cap.next_power_of_two().max(8);
        RhMap { dist: vec![0; n], keys: vec![0; n], vals: vec![V::default(); n], mask: n - 1, len: 0 }
    }
    fn home(&self, k: u64) -> usize { (hash(k) >> 7) as usize & self.mask }

    fn find(&self, k: u64) -> Option<usize> {
        let (mut i, mut d) = (self.home(k), 1u8);
        loop {
            if self.dist[i] < d { return None; } // empty (0) or a richer entry: k cannot be further on
            if self.keys[i] == k { return Some(i); }
            i = (i + 1) & self.mask;
            d += 1; // cannot overflow: stored dist <= 254 forces an earlier return
        }
    }
    pub fn get(&self, k: u64) -> Option<V> { self.find(k).map(|i| self.vals[i]) }

    pub fn insert(&mut self, k: u64, v: V) {
        if let Some(i) = self.find(k) { self.vals[i] = v; return; }
        if (self.len + 1) * 10 > (self.mask + 1) * 9 { self.grow(); } // max load 0.9
        let (mut k, mut v, mut d) = (k, v, 1u8);
        let mut i = self.home(k);
        loop {
            if d == u8::MAX { self.grow(); return self.insert(k, v); } // carried entry is not in the table
            if self.dist[i] == 0 {
                self.dist[i] = d; self.keys[i] = k; self.vals[i] = v;
                self.len += 1;
                return;
            }
            if self.dist[i] < d { // resident is richer: take its slot, carry it onward
                std::mem::swap(&mut self.dist[i], &mut d);
                std::mem::swap(&mut self.keys[i], &mut k);
                std::mem::swap(&mut self.vals[i], &mut v);
            }
            i = (i + 1) & self.mask;
            d += 1;
        }
    }

    pub fn remove(&mut self, k: u64) -> Option<V> {
        let mut i = self.find(k)?;
        let out = self.vals[i];
        loop { // backward shift: pull the rest of the run one slot toward home
            let j = (i + 1) & self.mask;
            if self.dist[j] <= 1 { self.dist[i] = 0; break; } // empty or already at home
            self.dist[i] = self.dist[j] - 1;
            self.keys[i] = self.keys[j];
            self.vals[i] = self.vals[j];
            i = j;
        }
        self.len -= 1;
        Some(out)
    }

    fn grow(&mut self) {
        let old = std::mem::replace(self, Self::new((self.mask + 1) * 2));
        for i in 0..old.dist.len() {
            if old.dist[i] != 0 { self.insert(old.keys[i], old.vals[i]); }
        }
    }
}

Complexity and constants

• Expected probes (linear probing, uniform hash, load α): hit ≈ (1 + 1/(1-α))/2, classic miss ≈ (1 + 1/(1-α)²)/2. Robin Hood keeps the hit mean, but misses stop at the first richer entry, so they cost about the same as hits.
• At α = 0.9: hit ≈ 5.5 slots; 16-byte entries put that within 1-2 cache lines. One cache miss per lookup in large tables, order of 80-150 ns; cache-resident lookups order of 5-15 ns.
• Insert can shift a run: average a few slots, worst case O(max DIB).
• Bytes per entry: sizeof(K)+sizeof(V)+1 divided by load factor.

Efficiency

• Cost: one cache miss per lookup in large tables, order of 80-150 ns, then 1-2 cache lines of linear scan; cache-resident lookups order of 5-15 ns. At load 0.9 a hit probes about 5.5 slots. Memory is sizeof(K)+sizeof(V)+1 per slot divided by the load factor. Bound: memory latency.
• Levers:
  • backward-shift delete — no tombstones, so lookup cost stays flat under churn (Celis; tsl::robin_map) — tables with deletes
  • shift the run with one memmove instead of swapping per step — faster inserts (Ankerl, tsl::robin_map) — small entries
  • hash bits next to the DIB byte — fewer key compares (as in Implementation notes) — string keys
  • indices into a dense array — cheap shifts, fast iteration (unordered_dense) — large values
  • DIB cap that triggers growth — bounds the worst probe and flags bad hashes — untrusted or weak hashes
• Naive → standard → state of the art:
  • chained table · pointer chase per probe, one allocation per entry
  • linear probing with tombstones · short but uneven runs, tombstones accumulate
  • Robin Hood with backward shift · same mean probes, low variance at 0.9 load; SIMD tag tables (Swiss table) win on long runs

Implementation notes

• Store DIB in a byte array (as here) or pack 7 bits of hash + DIB into one metadata word; matching hash bits before comparing keys saves work for string keys.
• "Shift" implementation (Ankerl, tsl::robin_map): instead of swapping at every step, find the first empty slot and memmove the run right by one; faster for cheap-to-move entries.
• Cap DIB (e.g. 127 or 255) and grow when exceeded; this also protects against bad hashes and acts as a DoS tripwire.
• Use hash >> k for the home slot if the low bits are weak; with a multiplicative hash the high bits are the good ones.
• Backward shift deletion keeps the table tombstone-free, so lookup cost does not degrade under churn.

Pitfalls

• Comparing keys after the first swap is wasted work and wrong if you "update" a carried key; check membership first (as find does).
• Forgetting to grow on DIB overflow lets a u8 distance wrap, silently corrupting the run order.
• Hashing integers with identity: sequential keys form one giant run. Always mix.
• Rust's old HashMap (Robin Hood + SipHash) suffered quadratic behaviour when iterating one map and inserting into another of the same capacity: iteration order equals hash order, which builds a single cluster. Seed per map or iterate in random order.
• Large values: each displacement copies the entry; keep entries ≤ 16-32 bytes or store an index.

Variants and alternatives

In production

• Language runtimes: Rust std::HashMap before 1.36 (2019).
• C++ libraries: tsl::robin_map, Martin Ankerl's robin_hood::unordered_map and its successor ankerl::unordered_dense, ska::flat_hash_map (Robin Hood with a probe limit).
• Only language-runtime and library uses are sourced; no verified use in other fields was found.

Implementations

Sources

• Pedro Celis, Robin Hood Hashing, PhD thesis, University of Waterloo, 1986. pdf
• Pedro Celis, Per-Åke Larson, J. Ian Munro, Robin Hood Hashing, FOCS 1985.
• Donald Knuth, The Art of Computer Programming, Vol. 3, section 6.4 (linear probing analysis).
• Maurice Herlihy, Nir Shavit, Moran Tzafrir, Hopscotch Hashing, DISC 2008. paper
• Martin Ankerl, unordered_dense README. code