Cuckoo Hashing: O(1) Worst-Case Lookup
Standard hash table implementations promise O(1) average-case lookup, but that 'average' hides significant variance. With chaining, a pathological hash function or adversarial input can degrade a...
Key Insights
- Cuckoo hashing guarantees O(1) worst-case lookup time by checking exactly two locations, making it ideal for real-time systems where predictable latency matters more than average-case performance.
- The trade-off is insertion complexity: elements may trigger a chain of displacements, and cycles require a full rehash with new hash functions.
- Practical implementations cap load factor around 50%, but variants like bucketized cuckoo hashing push this to 95%+ while maintaining constant-time lookups.
The Problem with Traditional Hash Tables
Standard hash table implementations promise O(1) average-case lookup, but that “average” hides significant variance. With chaining, a pathological hash function or adversarial input can degrade a single bucket to O(n). Open addressing with linear probing suffers from clustering—a long probe sequence on one lookup means unpredictable latency.
For most applications, this doesn’t matter. Your web application’s user session cache can tolerate occasional slow lookups. But consider a network router processing millions of packets per second, or a trading system where microseconds translate to dollars. These systems need guarantees, not averages.
Cuckoo hashing, introduced by Pagh and Rodler in 2001, provides exactly that: O(1) worst-case lookup with a simple, elegant mechanism. You check two locations. The element is in one of them, or it doesn’t exist. No chains to traverse, no probe sequences to follow.
How Cuckoo Hashing Works
The core insight is deceptively simple: maintain two hash tables (or two regions of one table), each with its own hash function. Every key has exactly two possible locations—one in each table.
When you insert a key, you try the first location. If it’s empty, you’re done. If it’s occupied, you evict the existing element and place your new key there. The evicted element then tries its alternate location in the other table. This process continues until an element finds an empty slot or you detect a cycle.
The name comes from the cuckoo bird, which lays eggs in other birds’ nests, evicting the original eggs. Your new key does the same—it kicks out the incumbent and forces it to find somewhere else to live.
Here’s the basic structure:
class CuckooHashTable:
def __init__(self, capacity: int = 16):
self.capacity = capacity
self.table1 = [None] * capacity
self.table2 = [None] * capacity
self.size = 0
# Use different seeds for independent hash functions
self.seed1 = 0x9e3779b9
self.seed2 = 0x85ebca6b
def _hash1(self, key) -> int:
h = hash(key) ^ self.seed1
return h % self.capacity
def _hash2(self, key) -> int:
h = hash(key) ^ self.seed2
return h % self.capacity
The two hash functions must be independent. In practice, you can use a single strong hash function with different seeds, or apply different mixing operations to the same base hash.
Insertion Algorithm
Insertion is where cuckoo hashing earns its complexity budget. The displacement chain can theoretically grow long, though in practice it’s usually short.
The algorithm works as follows:
- Compute both hash positions for the new key
- If either position is empty, insert there
- Otherwise, evict the element at position 1 and insert the new key
- The evicted element now tries its alternate position
- Repeat until finding an empty slot or hitting the maximum displacement threshold
The maximum displacement threshold is critical. Without it, a cycle in the displacement graph causes an infinite loop. When you hit this threshold, you must rehash the entire table with new hash functions.
def insert(self, key, value) -> bool:
# Check if key already exists
if self.lookup(key) is not None:
return self._update(key, value)
# Maximum displacements before declaring a cycle
max_displacements = int(3 * math.log2(self.capacity + 1))
current_key, current_value = key, value
use_table1 = True
for _ in range(max_displacements):
if use_table1:
pos = self._hash1(current_key)
table = self.table1
else:
pos = self._hash2(current_key)
table = self.table2
if table[pos] is None:
table[pos] = (current_key, current_value)
self.size += 1
return True
# Evict existing element
evicted = table[pos]
table[pos] = (current_key, current_value)
current_key, current_value = evicted
# Evicted element tries its alternate table
use_table1 = not use_table1
# Cycle detected - need to rehash
self._rehash()
return self.insert(current_key, current_value)
def _update(self, key, value) -> bool:
pos1 = self._hash1(key)
if self.table1[pos1] is not None and self.table1[pos1][0] == key:
self.table1[pos1] = (key, value)
return True
pos2 = self._hash2(key)
if self.table2[pos2] is not None and self.table2[pos2][0] == key:
self.table2[pos2] = (key, value)
return True
return False
The displacement threshold of 3 * log2(n) comes from theoretical analysis. With good hash functions, the probability of exceeding this threshold is vanishingly small—roughly 1/n³.
Lookup and Deletion
Here’s where cuckoo hashing shines. Lookup is trivially simple and provably O(1):
def lookup(self, key):
pos1 = self._hash1(key)
if self.table1[pos1] is not None and self.table1[pos1][0] == key:
return self.table1[pos1][1]
pos2 = self._hash2(key)
if self.table2[pos2] is not None and self.table2[pos2][0] == key:
return self.table2[pos2][1]
return None
def delete(self, key) -> bool:
pos1 = self._hash1(key)
if self.table1[pos1] is not None and self.table1[pos1][0] == key:
self.table1[pos1] = None
self.size -= 1
return True
pos2 = self._hash2(key)
if self.table2[pos2] is not None and self.table2[pos2][0] == key:
self.table2[pos2] = None
self.size -= 1
return True
return False
Two memory accesses. Two comparisons. That’s it. No loops, no chains, no variable-length probe sequences. This predictability is why cuckoo hashing appears in hardware implementations—you can pipeline the two lookups and guarantee completion within a fixed number of cycles.
Rehashing and Table Growth
When insertion detects a cycle, the only recourse is rehashing with new hash functions. This is expensive—O(n) to reinsert all elements—but happens rarely enough that amortized insertion cost remains O(1).
def _rehash(self):
old_table1 = self.table1
old_table2 = self.table2
# Generate new hash function seeds
self.seed1 = random.getrandbits(32)
self.seed2 = random.getrandbits(32)
# Optionally grow tables if load factor is high
if self.size > self.capacity * 0.5:
self.capacity *= 2
self.table1 = [None] * self.capacity
self.table2 = [None] * self.capacity
self.size = 0
# Reinsert all elements
for entry in old_table1:
if entry is not None:
self.insert(entry[0], entry[1])
for entry in old_table2:
if entry is not None:
self.insert(entry[0], entry[1])
Load factor is the key constraint. Standard cuckoo hashing with two tables maxes out around 50% before cycles become frequent. Push beyond this, and you’ll spend more time rehashing than doing useful work.
This 50% space efficiency seems wasteful compared to chaining (which can exceed 100% load factor) or linear probing (which works well up to 70-80%). The trade-off is explicit: you’re paying with memory to buy guaranteed lookup time.
Variants and Optimizations
The basic two-table scheme has spawned numerous improvements:
Bucketized Cuckoo Hashing stores multiple elements per bucket (typically 4-8). This dramatically improves space efficiency—load factors of 95%+ are achievable—while maintaining O(1) lookup (you scan a small, fixed-size bucket). This variant powers production systems like MemC3, a high-performance memcached implementation.
D-ary Cuckoo Hashing uses d > 2 hash functions, giving each element d possible locations. More choices mean better load factors and fewer rehashes, at the cost of slightly more complex lookups (still O(1), but with a larger constant).
Cuckoo Filters apply the displacement principle to approximate set membership, competing with Bloom filters. They offer better space efficiency than Bloom filters for false positive rates below 3%, plus they support deletion—something standard Bloom filters cannot do.
When to Use Cuckoo Hashing
Cuckoo hashing excels in specific scenarios:
Real-time systems where worst-case latency matters more than average-case. If your SLA specifies p99.9 latency, a hash table with O(n) worst-case is a liability.
Network hardware like routers and switches, where lookups must complete in a fixed number of clock cycles. The two-location guarantee maps cleanly to parallel memory accesses.
Read-heavy workloads where lookup performance dominates. The complex insertion logic matters less when you’re doing 1000 reads per write.
Memory-constrained environments using bucketized variants. When you need 95% space efficiency and guaranteed lookup time, bucketized cuckoo hashing is hard to beat.
Avoid cuckoo hashing when:
- Write performance is critical and you can’t tolerate occasional rehashes
- You need load factors above 50% without implementing bucketization
- Your keys have poor hash distribution (garbage in, garbage out)
In benchmarks against other schemes, cuckoo hashing typically shows 10-30% slower average-case lookup than optimized linear probing (due to accessing two cache lines instead of one), but dramatically better tail latency. For insertion-heavy workloads, the gap widens—Robin Hood hashing or Swiss tables often win on throughput.
The right choice depends on your constraints. If you’re building a general-purpose hash table, linear probing with good collision handling is probably fine. If you’re building a packet classifier that must respond within 50 nanoseconds, every time, cuckoo hashing deserves serious consideration.