What If a Hash Table Could Check Just Two Positions? Understanding Cuckoo Hashing 🐦

Imagine looking for a name in a directory containing one million entries, but instead of searching through thousands of records, you only need to check two locations.

Sounds interesting, right?

This is one of the fascinating ideas behind a data structure called Cuckoo Hashing.

While studying Algorithms and Complexity, I came across this concept, and I thought it was worth sharing with fellow developers.

Let's break it down, from the problem it solves to how it works, without making the mathematics unnecessarily complicated.

1. First, let's understand the problem

Imagine you're building a university system that stores thousands of student IDs.

Your system needs to perform three operations:

• Insert: Add a student ID.
• Lookup: Check whether a student ID exists.
• Delete: Remove a student ID.

One way of storing these IDs would be to use a linked list.

The problem?

If we have 100,000 student IDs and the one we're searching for happens to be at the end, we might need to examine all 100,000 entries.

That's a worst-case time complexity of O(n).

Can we do better?

Absolutely. Enter hashing.

2. Hashing: Giving every item an address

Instead of searching through every item, what if we could calculate where an item should be stored?

That's what a hash function does.

A hash function takes an item, called a key, and maps it to a position in a table.

For example, suppose we have a table with 10 positions, numbered 0 to 9.

We define:

h(x) = x mod 10

The mod operator returns the remainder after division.

Consider these student IDs:

Notice something?

Both 123 and 133 map to position 3.

This is called a hash collision.

Two different keys want to occupy the same location.

So how do we solve this?

3. Traditional solution: Hashing with chaining

A common solution is chaining.

Instead of storing only one item at a table position, we attach a linked list to that position.

For example:

Position 3 → 123 → 133 → 253

All three IDs have the same hash value, so they share a bucket.

This works, but it introduces a problem.

When searching for an item, we might need to traverse the linked list.

Under suitable assumptions, hashing with chaining achieves O(1) expected lookup time.

However, in the worst case, if many items collide, a search can still take O(n) time.

Now imagine a different approach.

What if we eliminated those linked lists and allowed every item only two possible positions?

That's where things become interesting.

4. Meet Cuckoo Hashing 🐦

Cuckoo hashing was introduced by researchers Rasmus Pagh and Flemming Friche Rodler in 2001.

The name comes from the behaviour of cuckoo birds, which are known for laying their eggs in other birds' nests. In some species, the cuckoo chick pushes other eggs out.

Cuckoo hashing uses a similar idea: when a new item needs an occupied position, it can displace the item already there.

But the displaced item isn't discarded.

Instead, it moves to its alternative position.

Here's the key difference.

Traditional hashing normally assigns each key one hash location.

Cuckoo hashing gives each key two possible locations, calculated using two hash functions:

• h1(x) — First possible position
• h2(x) — Second possible position

Each position can hold at most one item.

This gives us a powerful property:

To find an item, we only need to check two positions.

Regardless of whether our table contains 100 items or one million, the number of candidate positions checked remains at most two.

That's the foundation of worst-case O(1) lookup time, assuming hash calculations and key comparisons take constant time.

5. Let's see how cuckoo hashing works

Suppose we have these items and their two possible positions:

Initially, our table looks like this:

Now, let's insert a new item: X.

Its first choice is position 1.

But position 1 already contains A.

What happens next?

Step 1: X displaces A

X moves into position 1, pushing A out.

Position 1 now contains X.

But where should A go?

Step 2: A moves to its alternative position

A has two possible positions: 1 and 3.

Since X now occupies position 1, A attempts to move to position 3.

Unfortunately, position 3 already contains B!

So A displaces B.

Step 3: B searches for its alternative position

B can occupy position 3 or position 5.

Since A now occupies position 3, B moves to position 5.

Luckily, position 5 is empty.

The insertion succeeds!

Our table now looks like this:

Notice what happened.

We inserted X without creating any linked lists. Every position still contains at most one item.

And each item remains in one of its two valid locations.

One small detail: position 7 was also available for X. The particular insertion algorithm we are illustrating starts at the first hash location and performs displacement. An optimised implementation could check both positions first and avoid unnecessary displacement.

6. What happens when displacement never ends?

You might have spotted a potential problem.

What if every displaced item tries to move somewhere that is already occupied?

Suppose three items can only occupy the same two positions.

There is simply not enough space for all three.

The algorithm could repeatedly displace items without finding an empty position.

This leads us to an important concept: cycles.

Cuckoo hashing can be analysed using a graph where:

• Every table position is a vertex.
• Every item is an edge connecting its two possible positions.

Displacement follows connections in this graph.

Cycles can create insertion difficulties. More precisely, a cycle does not automatically mean insertion must fail, but certain graph structures make it impossible to place every item.

The solution: Rehashing

If the insertion algorithm exceeds its allowed number of displacement attempts, it can rebuild the table using newly selected hash functions.

This process is called rehashing.

The new hash functions give items different candidate positions, potentially resolving the problem.

Rehashing is expensive because multiple items may need to be repositioned.

Fortunately, when the table has sufficient spare capacity and the hash functions satisfy suitable randomness assumptions, rehashing happens infrequently enough to preserve efficient expected performance.

7. The mathematics: How fast is cuckoo hashing?

This is arguably the most interesting part.

Let's examine its performance.

Let's understand these claims.

Lookup: O(1) worst-case

We compute two hash values and inspect at most two locations.

The number of checks doesn't grow with the number of stored items.

Deletion: O(1) worst-case

We check the same two positions. If the item exists, we remove it.

No linked-list traversal is required.

Insertion: O(1) expected, amortised

Insertion is more complicated because displacement may involve several items.

Occasionally, rehashing might require O(n) work.

However, under the theoretical model used in the analysis, the expected total insertion cost over a sequence of operations is proportional to the number of operations.

That gives us constant expected amortised insertion time.

The distinction matters:

Expected O(1) does not mean every insertion completes in O(1).

The guarantee concerns the expected cost averaged over the random choices and amortised across operations.

There is another important condition: spare space.

The basic theoretical construction can use approximately 2(1 + ε)n table slots for at most n items, where ε is any fixed positive constant.

In other words, efficient cuckoo hashing doesn't come for free. It trades extra storage capacity for predictable lookup performance.

8. A clever improvement: The stash

There is one more interesting improvement I learned about.

What if, instead of rebuilding the entire table every time an insertion encounters a problematic structure, we provide a small extra storage area?

This is called a stash.

Items that cannot be placed in their normal candidate positions can temporarily be stored there.

Researchers Kirsch, Mitzenmacher and Wieder showed that, under fully random hash-function assumptions, a stash of size s can reduce the failure probability from:

O(1/n)

to:

O(1/n^(s+1))

That's a powerful improvement from adding only a small, constant-sized amount of auxiliary storage.

It does mean a lookup must also check the stash, but if its capacity is constant, lookup still takes O(1) worst-case time.

9. When is cuckoo hashing useful?

Cuckoo hashing is especially interesting in systems where predictable lookup performance matters.

Potential applications include:

• High-performance networking and routing tables
• Hash-based indexes
• In-memory dictionaries
• Systems with latency-sensitive membership checks

Of course, it isn't automatically the best choice for every application.

Insertions can be more complicated than in ordinary hash tables, and the structure requires careful hash-function design and capacity management.

The best data structure always depends on the workload and the performance guarantees we need.

10. What I learned

The biggest lesson for me wasn't simply that cuckoo hashing can achieve constant-time lookups.

It was understanding how changing the rules of where data can be stored changes the guarantees we can provide.

Traditional chaining says:

"If two items collide, keep them together in a bucket."

Cuckoo hashing says:

"Give each item an alternative location. If necessary, move the existing occupant."

That small change leads to a completely different way of managing collisions.

It also introduces a deeper lesson in algorithms: sometimes we deliberately accept unpredictable work in one operation to obtain stronger guarantees for another.

Cuckoo hashing is a beautiful example of the relationship between data structures, randomness, probability and algorithmic performance.

I'm currently exploring these concepts as part of my Algorithms and Complexity studies, and I've decided to share more of what I'm learning as I go.

Because one of the best ways to understand something deeply is to try teaching it to someone else.

Over to you 👇

If you were building a system where lookup speed was critical, would you choose cuckoo hashing over traditional hashing with chaining?

What trade-offs would influence your decision?

I'd love to hear your thoughts.

Further reading

• Pagh, R., & Rodler, F. F. (2001). Cuckoo Hashing. European Symposium on Algorithms.
• Mitzenmacher, M., & Upfal, E. Probability and Computing.
• COMP53215 Algorithms and Complexity — Data Structures lecture notes, Tom Friedetzky.

Suggested DEV tags: #algorithms #datastructures #computerscience #beginners