Cuckoo hashing

Deep dive

How it works

In: a key (and a value on insert) · Out: the value, or none; insert reports success · State: a table of buckets (4 slots each), two seeds · Cost: lookup and delete read exactly 2 buckets; insert O(1) expected

 key k: b1 = h1(k), b2 = h2(k)
 table:  [b0: a b c d] [b1: e f g h] ... [b2: i j k l]
 insert x, both full: evict e from b1, put x there; e goes to its other bucket; repeat.

1. Lookup: compare the key against the 4 slots in b1 and the 4 in b2.
2. Insert: if the key is present, update. Else take any empty slot in b1 or b2.
3. Evict: pick a victim slot in one bucket (random, or BFS for the shortest path), place the new entry, move the victim to its alternate bucket alt = (b == h1(v)) ? h2(v) : h1(v). Repeat with whatever it displaces.
4. After MAX_KICKS (~500) failures, grow (or rehash with new seeds) and reinsert the carried entry.
5. Delete: clear the slot. No tombstones.

Code

// Bucketized cuckoo map u64 -> V: 2 hash choices, 4 slots per bucket (one 64-byte line for (u64,u64) slots).
const SLOTS: usize = 4;
const MAX_KICKS: usize = 500;

fn mix(k: u64, seed: u64) -> u64 { // murmur3 fmix64 of k ^ seed
    let mut x = k ^ seed;
    x = (x ^ (x >> 33)).wrapping_mul(0xFF51_AFD7_ED55_8CCD);
    x = (x ^ (x >> 33)).wrapping_mul(0xC4CE_B9FE_1A85_EC53);
    x ^ (x >> 33)
}

pub struct CuckooMap<V: Copy> { buckets: Vec<[Option<(u64, V)>; SLOTS]>, mask: usize, rng: u64, len: usize }

impl<V: Copy> CuckooMap<V> {
    pub fn new(buckets: usize) -> Self {
        let n = buckets.next_power_of_two().max(2);
        CuckooMap { buckets: vec![[None; SLOTS]; n], mask: n - 1, rng: 0x2545_F491_4F6C_DD1D, len: 0 }
    }
    fn b1(&self, k: u64) -> usize { mix(k, 0x9E37_79B9_7F4A_7C15) as usize & self.mask }
    fn b2(&self, k: u64) -> usize { mix(k, 0xD1B5_4A32_D192_ED03) as usize & self.mask }

    fn slot(&self, k: u64) -> Option<(usize, usize)> {
        for b in [self.b1(k), self.b2(k)] {
            for s in 0..SLOTS {
                if matches!(self.buckets[b][s], Some((key, _)) if key == k) { return Some((b, s)); }
            }
        }
        None
    }
    pub fn get(&self, k: u64) -> Option<V> { self.slot(k).and_then(|(b, s)| self.buckets[b][s].map(|e| e.1)) }
    pub fn remove(&mut self, k: u64) -> Option<V> {
        let (b, s) = self.slot(k)?;
        self.len -= 1;
        self.buckets[b][s].take().map(|e| e.1)
    }

    pub fn insert(&mut self, k: u64, v: V) {
        if let Some((b, s)) = self.slot(k) { self.buckets[b][s] = Some((k, v)); return; }
        let mut cur = (k, v);
        let mut b = self.b1(k);
        for _ in 0..MAX_KICKS {
            for bb in [b, self.alt(b, cur.0)] {
                if let Some(s) = self.buckets[bb].iter().position(|e| e.is_none()) {
                    self.buckets[bb][s] = Some(cur);
                    self.len += 1;
                    return;
                }
            }
            // Both buckets full: random-walk eviction from bucket b.
            self.rng ^= self.rng << 13; self.rng ^= self.rng >> 7; self.rng ^= self.rng << 17;
            let s = (self.rng >> 32) as usize % SLOTS;
            let victim = self.buckets[b][s].replace(cur).unwrap();
            cur = victim;
            b = self.alt(b, cur.0); // the victim's other bucket
        }
        self.grow();
        self.insert(cur.0, cur.1); // cur was displaced and is not in the table
    }
    fn alt(&self, b: usize, k: u64) -> usize { let b1 = self.b1(k); if b == b1 { self.b2(k) } else { b1 } }

    fn grow(&mut self) {
        let old = std::mem::replace(self, Self::new((self.mask + 1) * 2));
        for e in old.buckets.into_iter().flatten().flatten() { self.insert(e.0, e.1); }
    }
}

Complexity and constants

• Lookup: exactly 2 bucket reads. With 64-byte buckets that is 2 cache misses on large tables, but independent, so out-of-order CPUs overlap them: order of 1.2-1.5× one miss, not 2×.
• Expected insert cost is O(1) below the threshold load; near 95 % the average eviction path grows to tens of kicks.
• Classic 2-choice, 1-slot cuckoo below 50 % load: building a table of n keys needs a rehash with probability O(1/n), which is why a rehash fallback suffices.
• Memory: sizeof(slot) / load; at 95 % load overhead is about 5 %, far better than linear probing at 70-80 %.

Efficiency

• Cost: a lookup reads 2 buckets (64 bytes each): two independent cache misses that the CPU overlaps, order of 1.2-1.5× one miss, order of 100 ns from DRAM. Memory is slot size divided by load: about 5 % overhead at 95 % load. Insert near full load takes tens of kicks. Bound: memory latency.
• Levers:
  • 4-slot (or 8-slot) buckets — load rises from 50 % to 95 % and one bucket is one cache line (MemC3, DPDK rte_hash) — always
  • 1-byte tags per slot, SIMD compare — fewer full key compares per bucket (MemC3, libcuckoo) — keys longer than 8 bytes
  • BFS for the shortest eviction path — shorter, fewer critical sections (Li et al. 2014) — concurrent writers
  • version counter per lock stripe — readers take no lock (MemC3) — many readers, few writers
  • batched lookups with prefetch of both buckets — overlaps the misses of many keys (CuckooSwitch) — packet forwarding tables
• Naive → standard → state of the art:
  • chained hash table · pointer chase per probe, 70-80 % load for open addressing
  • 2-choice, 4-slot cuckoo · 2 bucket reads worst case, 95 % load
  • tagged buckets, BFS eviction, optimistic readers, batch prefetch · same 2 reads, concurrent and lock-free for readers

Implementation notes

• Bucketization is what makes cuckoo practical: 4 slots of 16 bytes fit one cache line; scan them with SIMD or unrolled compares. Store 1-byte tags per slot to avoid key compares (MemC3, libcuckoo).
• Partial-key cuckoo (cuckoo filters, MemC3): b2 = b1 ^ hash(tag). The alternate bucket is computable from the tag alone, so evictions need no full key. Requires a power-of-two table.
• BFS eviction (libcuckoo): search for the shortest path to an empty slot first (depth ≤ 5 covers thousands of slots), then move entries backwards along the path. Shorter paths mean fewer, shorter critical sections.
• Concurrent reads (MemC3 "optimistic cuckoo"): a version counter per lock stripe; writers bump it (odd = in progress) while moving an entry; readers retry if the version changed, a seqlock per stripe. Moving along the path backwards ensures a key is always findable in at least one bucket.
• Use two independent hash outputs (two halves of a 128-bit hash, or two seeds).

Pitfalls

• Same bucket for both choices (b1 == b2): halves capacity for that key; fine, but don't count it as two choices in analysis.
• Infinite eviction cycles: always bound kicks and rehash/grow.
• Forgetting that the carried entry after a failed walk is a different key than the one being inserted (handled above by reinserting cur).
• Inserting duplicates in a cuckoo filter more than 2 × SLOTS times makes inserts fail.
• With 1-slot buckets, staying under 50 % load is mandatory; past it, failure probability jumps.

Variants and alternatives

In production

• Caches: MemC3 (memcached variant), RocksDB's cuckoo table format.
• Networking: CuckooSwitch (software switch forwarding table), DPDK rte_hash (cuckoo with 8-slot buckets and signatures; DPDK guide).
• Concurrent in-memory maps: libcuckoo (C++); cuckoo filters in several databases and networking stacks.

Implementations

Sources

• Rasmus Pagh, Flemming Friche Rodler, Cuckoo Hashing, ESA 2001; Journal of Algorithms 51(2), 2004. paper
• Bin Fan, David G. Andersen, Michael Kaminsky, MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing, NSDI 2013. pdf
• Xiaozhou Li, David G. Andersen, Michael Kaminsky, Michael J. Freedman, Algorithmic Improvements for Fast Concurrent Cuckoo Hashing, EuroSys 2014. paper · code
• Bin Fan, David G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher, Cuckoo Filter: Practically Better Than Bloom, CoNEXT 2014. paper · pdf · code
• Dong Zhou, Bin Fan, Hyeontaek Lim, Michael Kaminsky, David G. Andersen, Scalable, High Performance Ethernet Forwarding with CuckooSwitch, CoNEXT 2013. paper
• Martin Dietzfelbinger, Christoph Weidling, Balanced allocation and dictionaries with tightly packed constant size bins, Theoretical Computer Science, 2007.