Cuckoo Hashing
Elegant hash table variant guaranteeing O(1) worst-case lookup time. Named after the cuckoo bird (which lays eggs in other birds' nests), it uses two hash functions and two tables. Each key has two possible locations; on collision, the existing key is 'kicked out' to its alternate location, potentially triggering a chain of displacements. Invented by Rasmus Pagh and Flemming Rodler in 2001, it's used in network routers and high-performance systems requiring predictable lookup times.
Visualization
Interactive visualization for Cuckoo Hashing
Table 1:
Table 2:
Cuckoo Hashing:
- • Two tables, two hash functions
- • Displaced keys kicked to alternate table
- • O(1) worst-case lookup
Interactive visualization with step-by-step execution
Implementation
1class CuckooHash {
2 private tab:(Array<string|number|null>)[]; private n=0; constructor(private capacity=16){ this.tab=[Array(capacity).fill(null), Array(capacity).fill(null)]; }
3 private h(k:any,i:number){ const s=String(k); let h= i?0:0; for(let c of s){ h=((h* (i?131:31)) + c.charCodeAt(0))|0; } return (h>>>0)%this.capacity; }
4 put(k:any){ if(this.n/this.capacity>0.5) this.resize(this.capacity*2); let cur=k; let i=0; for(let kick=0;kick<2*this.capacity;kick++){ const idx=this.h(cur,i); if(this.tab[i][idx]==null){ this.tab[i][idx]=cur; this.n++; return true; } [cur, this.tab[i][idx]] = [this.tab[i][idx]!, cur]; i^=1; } this.resize(this.capacity*2); return this.put(cur); }
5 has(k:any){ return this.tab[0][this.h(k,0)]===k || this.tab[1][this.h(k,1)]===k; }
6 private resize(nc:number){ const old=[...this.tab[0]], old2=[...this.tab[1]]; this.capacity=nc; this.tab=[Array(nc).fill(null), Array(nc).fill(null)]; this.n=0; for(const v of [...old,...old2]) if(v!=null) this.put(v); }
7}Deep Dive
Theoretical Foundation
Cuckoo hashing maintains two tables T0 and T1 with hash functions h0 and h1. Key k can be at T0[h0(k)] or T1[h1(k)]. **Insertion**: try T0[h0(k)]; if occupied, evict existing key and place it in its alternate location. Continue displacement chain with limit (typically 2n). If chain exceeds limit (cycle detected), rebuild with new hash functions or larger tables. **Lookup**: check both locations - O(1) worst case, just 2 memory accesses! **Load factor**: typically keep α < 0.5 for good performance. Variants use 3+ hash functions or d-ary cuckoo for higher load factors (~0.9). Mathematical analysis shows expected O(1) insertion amortized.
Complexity
Time
O(1)
O(1)
O(1) lookup, rehash occasionally
Space
O(n)
Applications
Industry Use
Network routers (IP lookup tables with strict latency)
Hardware switches (TCAM alternatives)
Real-time systems requiring predictable lookup
High-frequency trading systems
Compiler symbol tables
Bloom filter alternatives
Graphics processing (GPU hash tables)
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.