What Is Cuckoo Hashing and How Does It Work?

Cuckoo Hashing is a hashing technique designed to resolve collisions in a hash table while keeping lookup operations extremely fast.

Traditional hash tables must handle situations where multiple keys map to the same position. Common solutions include Separate Chaining and Open Addressing. Cuckoo Hashing takes a different approach: each key has multiple possible positions, and a newly inserted key can evict an existing key from its position.

The name comes from the behavior associated with the cuckoo bird. Some cuckoo species place their eggs in other birds' nests. In a similar way, a new key in Cuckoo Hashing may take an occupied position and force the previous key to move elsewhere.

The Collision Problem

A traditional hash table calculates a position using a hash function:

index = hash(key)

Two different keys may produce the same index:

hash(20) = 3
hash(45) = 3

This creates a collision.

Cuckoo Hashing commonly uses two hash functions:

h1(key)
h2(key)

Therefore, every key has two possible locations.

The Main Idea

Suppose we want to insert key A.

We first calculate:

h1(A)

If the position is empty, A is stored there. If the position already contains B, then A can replace B.

The displaced key B must then move to its alternative position:

h2(B)

If that location is also occupied, another displacement occurs.

Conceptually:

Insert A
   ↓
Position contains B
   ↓
A replaces B
   ↓
B moves to its alternative position
   ↓
Repeat when necessary

Why Lookup Is Fast

Lookup is one of the strongest properties of Cuckoo Hashing.

To find a key x, we only need to check its possible positions:

h1(x)
h2(x)

With two hash functions, only two locations need to be inspected. Lookup therefore runs in constant time:

O(1)

This makes the technique particularly attractive for lookup-heavy workloads.

Insertion

A simplified insertion procedure is:

1. Calculate h1(key)
2. Insert the key if the position is empty
3. Otherwise evict the existing key
4. Store the new key
5. Move the evicted key to its alternative location
6. Repeat until an empty location is found

However, repeated displacement introduces an important problem: cycles.

The Cycle Problem

A sequence of displacements can potentially repeat forever:

A → B → C → A → B → C → ...

Implementations therefore normally limit the number of displacement attempts.

For example:

MAX_KICKS = 50

If insertion still fails, the table can be rehashed.

Rehashing

Rehashing may involve:

• selecting new hash functions,
• increasing the table size,
• rebuilding the table,
• reinserting existing keys.

An individual rehash operation is relatively expensive, but it occurs occasionally rather than for every insertion.

A Simple JavaScript Implementation

class CuckooHashTable {
  constructor(size = 11) {
    this.size = size;
    this.table1 = new Array(size).fill(null);
    this.table2 = new Array(size).fill(null);
  }

  hash1(key) {
    return key % this.size;
  }

  hash2(key) {
    return Math.floor(key / this.size) % this.size;
  }

  search(key) {
    const i1 = this.hash1(key);
    const i2 = this.hash2(key);

    return this.table1[i1] === key || this.table2[i2] === key;
  }

  insert(key) {
    let current = key;
    let table = 1;
    const maxKicks = this.size * 2;

    for (let i = 0; i < maxKicks; i++) {
      if (table === 1) {
        const index = this.hash1(current);

        if (this.table1[index] === null) {
          this.table1[index] = current;
          return true;
        }

        [current, this.table1[index]] = [this.table1[index], current];
        table = 2;
      } else {
        const index = this.hash2(current);

        if (this.table2[index] === null) {
          this.table2[index] = current;
          return true;
        }

        [current, this.table2[index]] = [this.table2[index], current];
        table = 1;
      }
    }

    return false;
  }
}

This implementation is intentionally simplified. A production implementation should also handle resizing, rehashing, load factors, robust hash functions, duplicate keys, and generic key types.

Time Complexity

Typical behavior can be summarized as follows:

| Operation | Typical Complexity | |---|---| | Search | O(1) | | Delete | O(1) | | Insert | Expected O(1) | | Rehash | O(n) |

The key advantage is that lookup checks only a small fixed number of possible positions.

Cuckoo Hashing vs. Chaining

Separate Chaining stores multiple elements in a bucket, often through a list or another container:

index → A → B → C → D

Cuckoo Hashing instead restricts a key to a small set of candidate positions:

h1(key) OR h2(key)

This makes lookup behavior particularly predictable.

Advantages

Important advantages include:

• very fast lookup,
• constant-time lookup,
• a bounded number of locations to inspect,
• no linked list required for each bucket,
• good performance for lookup-heavy workloads.

Limitations

Cuckoo Hashing also has several trade-offs:

• insertion is more complicated than lookup,
• displacement cycles can occur,
• rehashing may occasionally be required,
• performance depends on good hash functions,
• high load factors can make insertion difficult.

Where Is Cuckoo Hashing Used?

The technique is useful when fast membership or key lookup is important. Related ideas can appear in:

• caching systems,
• in-memory data structures,
• networking systems,
• high-performance lookup structures,
• storage and database-related structures.

The same core idea also inspired another important probabilistic data structure: the Cuckoo Filter.

Cuckoo Filter

A Cuckoo Filter is a probabilistic membership data structure based partly on Cuckoo Hashing concepts. It is often compared with the Bloom Filter and can provide useful properties such as efficient membership queries and deletion support.

Conclusion

Cuckoo Hashing provides an unusual solution to hash collisions: instead of building long chains or probing many positions, each key has a small number of candidate locations. When a collision occurs, an existing key can be displaced to its alternative location.

The result is extremely efficient and predictable lookup behavior. The trade-off is a more complicated insertion process that must handle displacement cycles, table load, and occasional rehashing.

For developers studying hash tables and data structures, Cuckoo Hashing is an excellent next step after learning basic hashing, Separate Chaining, and Open Addressing.