Ever heard of a bird inspiring a computer science algorithm? Yep, you read that right. Today we’re diving into Cuckoo Hashing, a powerful hashing technique that takes its inspiration straight from nature.
???? A Quick Story About Cuckoo Birds
Cuckoo birds are… jerks. Instead of building their own nests, they sneak their eggs into other birds’ nests. When the chick hatches, it kicks the others out and claims the nest all to itself. Bold move, right?
That same “move in and push the other out” trick is exactly how cuckoo hashing handles collisions in hash tables. It’s nature + computer science = genius.
???? First, What’s a Hash Table Again?
A hash table is like a super-fast digital filing cabinet where you drop data in and retrieve it in almost constant time. If you’re new to hash tables, check out my earlier breakdown ???? What is a Hash Table?
Hash tables are amazing, but they have one problem: collisions. That’s when two keys end up mapped to the same slot. Normally, we fix this with chaining or linear probing… but those methods can get messy.
Enter cuckoo hashing. ????✨
???????? What Makes Cuckoo Hashing So Special?
Instead of giving each key just one slot, cuckoo hashing uses two different hash functions. That means each key has two possible homes.
Here’s the magic:
- If one spot is full, the new key boots out the old resident (just like a cuckoo chick).
- The displaced key then moves to its other possible home.
- If that’s also full, the cycle repeats until everything finds a nest.
???? Want to see cuckoo hashing in action? Play around with this awesome app, I made using AI Cuckoo Hashing Visualizer.
???????? Pseudo Code: Cuckoo Hashing in Action
Here’s a simple version of the insert logic, written in easy-to-read pseudo code:
// Insert a key into the cuckoo hash table
function insert(key):
for i = 1 to MaxAttempts:
// Try first home
if table1[h1(key)] is empty:
place key in table1[h1(key)]
return success
// If not empty, evict the old resident
swap key with table1[h1(key)]
// Try second home
if table2[h2(key)] is empty:
place key in table2[h2(key)]
return success
// If not empty, evict the old resident again
swap key with table2[h2(key)]
// and repeat the loop with the evicted key
// If we’ve tried too many times, the table is probably too full
resize_and_rehash()
???? Key things to notice:
- Each key has two homes.
- If both are busy, one of the current residents gets kicked out.
- After too many kicks, the table needs to resize and rehashed.
This simple loop is the heart of cuckoo hashing.
⏱️ Time Complexity: How Fast Is It Really?
- Lookup → O(1). You only check up to 2 spots.
- Insert → O(1) on average, though sometimes you shuffle a few items.
- Delete → O(1). Just clear the spot.
Worst case? A cycle forms (items keep kicking each other around endlessly). That’s when you resize and rehash the whole table.
???? A Little History: The Creators of Cuckoo Hashing
Cuckoo hashing was introduced in 2001 by Rasmus Pagh and Flemming Friche Rodler. Their goal? A hash table with constant-time lookups and clean structure — no messy chains or long probing sequences.
Whenever you need predictable O(1) lookups and can afford a little shuffle during insertions, cuckoo hashing is your friend.