Why is it called cuckoo hashing?

The name evokes an incoming occupant displacing another from its location.

Can a key have more than two choices?

Yes. Generalizations use more hash locations or buckets, with different trade-offs.

Does rehashing mean changing the keys?

No. It changes the mapping or table arrangement while preserving the stored keys and associated values.

AI Glossary / Graphs and symbolic AI / Intermediate

Cuckoo hashing

Definition

Cuckoo hashing is a hash-table technique that gives each key a small number of possible storage locations. In the classic two-table scheme, a key occupies one of two hash-selected cells; insertion can displace an existing key to its alternative location.

What it means

Ordinary hashing maps a key to a location, but different keys can collide. Cuckoo hashing resolves collisions by moving occupants among their permitted locations instead of building an unbounded lookup chain.

The classic lookup is simple: calculate the key's two candidate positions and compare the stored keys there. If neither matches, the key is absent, provided the table invariants hold. This gives a worst-case constant number of table probes for lookup in the basic model.

Insertion is less predictable. One displacement can trigger another, and a chain can cycle. The implementation needs a limit and a recovery mechanism such as rebuilding with new hash functions, resizing or a variant-specific overflow arrangement.

This is an exact dictionary technique when full keys are retained and compared. A cuckoo filter is a related approximate membership structure using fingerprints; its false-positive behavior should not be attributed to an ordinary cuckoo hash table.

How it works

Let h1 and h2 map a key to cells in tables T1 and T2. Maintain the invariant that every stored key is in T1[h1(key)] or T2[h2(key)]. It is unnecessary to search other cells for that key.

To insert a new key, first check whether it already exists according to the dictionary's duplicate-key policy. If a permitted cell is empty, place it there. Otherwise replace an occupant and attempt to move that displaced key to its other permitted cell. Continue until an empty cell is reached or the displacement limit is exceeded.

A failed placement must not lose the currently displaced key. Rehashing must include every existing key and the pending insertion. Deletion can clear the matching cell in the basic scheme, although resizing and concurrent access add implementation concerns.

The original analysis uses assumptions about hash-function selection and spare capacity. Expected amortized insertion bounds are not a promise that each insertion finishes in constant time. Bucketed and multi-choice variants change capacity behavior and probe patterns.

Key hashing and comparison also have costs. A constant number of table accesses does not make reading an arbitrarily long string constant time, nor does it guarantee a fixed wall-clock latency under every memory workload.

Three practical examples

An in-memory dictionary uses bounded candidate locations for predictable key lookup while accepting occasional rebuilding work.
A network-processing prototype evaluates cuckoo hashing for exact identifiers, measuring insertion spikes separately from lookup throughput.
A data-structure lesson visualizes displaced keys moving between two possible cells to explain collision handling.

Think of it this way

Think of assigning each person two possible lockers. A new arrival can take one locker and ask its occupant to move to their other permitted locker, potentially causing a chain of moves.

The analogy highlights both convenience and risk. Finding someone requires checking only their two lockers, but fitting a new person can take several moves or fail under the current assignment. Real implementations must preserve all displaced records during recovery.

Worked example

Following a displacement chain

Use two tables, each with cells numbered 0, 1 and 2. Let key A have candidates T1[0] and T2[1]. Let B have candidates T1[0] and T2[2]. Let C have candidates T1[2] and T2[1].

Initially A occupies T1[0], C occupies T2[1], and the other cells are empty. Insert B by placing it in T1[0], displacing A. Move A to its alternative T2[1], displacing C. Move C to its alternative T1[2], which is empty.

The final placement is B in T1[0], A in T2[1] and C in T1[2]. Every key remains in one of its own permitted cells. Looking up A checks T1[0] and T2[1], even though insertion involved three placements.

For an impossible configuration, imagine three distinct keys whose only candidates are the same two cells. All three cannot be stored in those two cells under the basic one-key-per-cell rules. Repeated displacement cannot create capacity; a recovery mechanism must change the situation.

Illustrative case study

Fictional case: Cedar Index benchmarks a cuckoo dictionary using mostly successful lookups and reports consistently short probe sequences. A later ingestion test encounters long displacement chains and rebuilds.

The team separates lookup latency from insertion latency, includes failed and duplicate-key operations, and tests the configured load range. It also verifies that interrupted rebuilding cannot drop the key currently being displaced.

The lesson is that the attractive lookup property does not describe every operation's cost.

Common misconceptions and mistakes

Every operation always takes the same constant time. Insertions can trigger displacement chains and rehashing.
Two candidate locations mean a key is stored twice. The classic scheme stores it in one of them.
An empty cell anywhere guarantees insertion succeeds. The key-location structure can prevent a valid placement.
Cuckoo hashing inherently returns false positives. An exact table compares keys; approximate filters are different structures.
All variants have the same load threshold. Buckets, choices and implementation policies affect capacity.

Business use

Cuckoo hashing can be useful when bounded lookup work is valuable and insertion variability can be managed. The decision should be based on the actual read-write mix and memory constraints.

Measure successful and unsuccessful lookups, insertion tails, rebuild frequency and space overhead. Validate hash quality for the expected key distribution and define behavior when insertion cannot complete. For concurrent systems, relocation needs appropriate coordination so readers do not mistake a temporarily moving key for an absent one.

Check your understanding

Three keys share exactly two possible single-entry cells. Can more displacement attempts alone fit all three?

Answer: No. That candidate-location configuration has insufficient capacity. The table must use an appropriate recovery or variant-specific mechanism.

Related terms

Hash function
Dictionary
Hash table
collision
rehashing
load factor
amortized analysis
cuckoo filter

Learn next

Trace the worked chain and verify each final key against both of its hash locations. Add a fourth key with specified candidates and try insertion. Record both the number of lookup probes and the number of moves, explaining why they measure different operations.

Sources

Rasmus Pagh and Flemming Friche Rodler, Cuckoo Hashing, original author-hosted paper, especially the two-table invariant and bounded displacement procedure: https://www.rasmuspagh.net/papers/cuckoo.pdf

The three-key placement and fictional benchmark are original illustrations. No historical experimental speedup is assumed to hold for a new workload.

Previous: Cuboid (computer vision) Next: Cumulative distribution