Cuckoo Hashing: Two Homes per Key, and Whoever Is There Gets Kicked Out

Hash tables are designed around a simple objective: given a key, find its associated value, or determine that the key is absent, without scanning every stored item. A hash function turns the key into one or more candidate locations. A collision-resolution strategy decides what happens when two keys want the same location.

Cuckoo hashing takes a particularly strict approach to collisions. Every key has two candidate homes. If one home is free, the key goes there. If both homes are occupied, inserting the new key may evict an existing key, which then moves to its other home and may evict another key. The chain continues until it reaches an empty slot—or cycles.

The payoff is a very simple lookup rule: in the two-home design, a lookup checks no more than two locations. If neither candidate slot contains the key, the key is absent. The supplied model uses two four-slot tables to show the complete pattern: a chain of kicks, a lookup that reads at most two slots, and a rebuild when an eviction cycle occurs.

This article explains that model, places it in the broader family of hash tables, and connects it to common uses such as frequency counting, deduplication, two-sum lookups, grouping, caching, and prefix-sum maps.

1. From a key to a bucket or slot​

A hash function maps a key to an integer. A table then converts that integer into a valid bucket or slot index. If a table has $m$ positions, a common conceptual rule is:

Suppose a hash calculation produces $29$ and the table has four slots. Using zero-based indexes, the selected position is:

The key is directed to slot $1$.

A collision occurs when different keys produce the same position. For example, if cat produces $9$ and dog produces $13$, both choose slot $1$ in a four-slot table:

cat:  9  mod 4 = 1
dog: 13  mod 4 = 1

The hash function has not failed. It has reduced a large key space to a small set of positions, so collisions are unavoidable in general. The data structure needs a policy for storing both keys.

A hash map stores key-value pairs, such as an item and its count. A hash set stores keys and usually answers only whether a key is present. Both can use the same basic hashing machinery. The difference is what is associated with each key after the key has been found.

The familiar average $O(1)$ claim for hash-table lookup, insertion, and deletion depends on assumptions. The hash functions should distribute keys reasonably, and the table should not become too full. Under those conditions, an operation examines only a small amount of information instead of scanning all $n$ entries. The word average is important: poor distribution, an overly full table, or a collision-resolution failure can produce much more work.

2. Hashing versus sorting and balanced trees​

Hashing is especially useful when the application needs exact-key operations:

• Does this key exist?
• What value is associated with this exact key?
• How many times has this key appeared?
• Have we already processed this item?

A hash table computes candidate locations directly. It does not normally maintain all keys in sorted order.

Sorting provides a different benefit. Once values are sorted, an array can support binary search in $O(\log n)$ time. Sorted data is also useful for ordered output, range processing, and algorithms that depend on neighboring values. The trade-off is that inserting into the middle of a plain sorted array may require shifting many elements.

A balanced search tree maintains order while supporting search, insertion, and deletion in $O(\log n)$ time under the usual balancing assumptions. Its worst-case behavior is more predictable than the typical hash-table target, and it naturally supports predecessor, successor, and range queries.

Hash tables generally target average $O(1)$ exact lookup, insertion, and deletion, but their worst case can be $O(n)$. A large collision chain, a long probe sequence, or a rebuild can involve many entries. Cuckoo hashing changes the balance: it makes the lookup path extremely short while allowing insertion to perform a sequence of evictions.

Use hashing when exact membership or retrieval dominates. Use sorting or a balanced tree when ordered traversal and range queries are central. Cuckoo hashing is most distinctive when a small, fixed number of lookup locations is valuable.

3. Ordinary collision handling​

Cuckoo hashing is easier to understand after comparing it with common collision strategies.

Chaining​

With chaining, each bucket contains a collection of entries. If several keys map to bucket $1$, all of them can be stored in that bucket's chain.

key       hash result       bucket
cat       9                 9 mod 4 = 1
dog       13                13 mod 4 = 1
owl       5                 5 mod 4 = 1

Bucket $1$ now contains cat, dog, and owl. A lookup computes bucket $1$ and searches that bucket's entries until it finds the key or reaches the end.

When keys are distributed well and the load factor is controlled, chains are short on average, so operations are often treated as average $O(1)$. If many keys land in one bucket, a lookup can degrade toward $O(n)$. Chaining can tolerate a load factor greater than one because a bucket can hold multiple entries. Its representation, however, needs extra storage for the bucket collections and may involve pointer-heavy memory accesses.

Open addressing​

Open addressing stores entries directly in the table. If the preferred slot is occupied, the algorithm follows a probe sequence to inspect another slot. An empty location is significant: under the correct search rules, it can prove that a key is absent.

Open addressing needs spare capacity. As the table becomes full, finding an empty slot becomes harder and probe sequences become longer. The usual measure is the load factor:

Here, $n$ is the number of stored entries and $m$ is the number of available slots. With three entries in eight slots:

A low load factor uses more empty space but leaves more room for collision resolution. A high load factor uses memory more efficiently but generally increases the work required to insert and find keys.

Linear probing​

Linear probing checks consecutive positions after a collision. Its probe sequence can be written as:

For a four-slot table, suppose red and blue both hash to slot $2$. Insert red at slot $2$. When inserting blue, inspect slot $2$, find it occupied, and inspect slot $3$. If slot $3$ is empty, place blue there.

slot:  0     1     2     3
       .     .    red  blue

Linear probing is compact and often benefits from nearby memory accesses. Its principal weakness is clustering. Once a consecutive run of occupied slots forms, later collisions are likely to join that run. Deletion also requires care: simply clearing a slot can cause a later lookup to stop too early. Implementations commonly use tombstones or another repair strategy.

Double hashing​

Double hashing uses a second hash function to choose the step size:

The first hash chooses the starting location. The second determines how far the next probe moves. For example, if the initial position is $2$, the table has four slots, and the step is $3$, successive positions are generated by repeatedly adding $3$ modulo $4$.

Double hashing generally spreads probes more broadly than linear probing, reducing the specific clustering pattern caused by consecutive positions. It still has a variable-length lookup path, needs capacity management, and requires careful deletion rules. The step function must also be chosen so that the probe sequence can reach the necessary table positions.

4. Cuckoo hashing gives every key two homes​

Cuckoo hashing uses two hash functions. For a key $k$, let its candidate locations be:

The key may live in either location, but not somewhere else. In the two-table model, $h_1(k)$ identifies a slot in the first table and $h_2(k)$ identifies a slot in the second table. The two physical tables each have four slots in the supplied example.

Table A: [A0] [A1] [A2] [A3]
Table B: [B0] [B1] [B2] [B3]

A key might have homes A1 and B3. Another key might have homes A1 and B0. Both keys compete for A1, but each also has an alternative location.

For example:

key       first home       second home
K         A1                B3
L         A1                B0
M         A2                B3

K can be stored at A1 or B3. L can be stored at A1 or B0. M can be stored at A2 or B3.

The lookup rule follows directly from the placement rule. To search for M, compute its two homes and inspect A2 and B3. There is no need to scan a chain, follow a long probe sequence, or search other slots. If neither location contains M, the key is absent.

Thus, in this two-home design, a lookup reads at most two candidate slots. That is the central attraction of cuckoo hashing. The bounded lookup does not mean collisions disappear; it means insertion handles collisions by rearranging occupants so that every stored key remains in one of its known homes.

5. Insertion: place, evict, and move​

If one of a new key's homes is empty, insertion is simple. Place the key there. If both homes are occupied, the algorithm chooses one home, places the new key there, and evicts the occupant.

The evicted key is not discarded. It moves to its other home. If that home is occupied, the displaced key moves again. This is the kick chain.

Consider this abstract state:

Table A: [ . ] [P ] [ . ] [ . ]
Table B: [ . ] [ . ] [ . ] [Q ]

Suppose the candidate homes are:

key       first home       second home
R         A1                B2
P         A1                B3
Q         A2                B2

Insert R. Its first home, A1, contains P. Put R in A1 and evict P:

Table A: [ . ] [R ] [ . ] [ . ]
Table B: [ . ] [ . ] [ . ] [Q ]

P now moves to its alternate home, B3. That slot contains Q, so P evicts Q:

Table A: [ . ] [R ] [ . ] [ . ]
Table B: [ . ] [ . ] [ . ] [P ]

Q moves to its alternate home, A2, which is empty:

Table A: [ . ] [R ] [Q ] [ . ]
Table B: [ . ] [ . ] [ . ] [P ]

The insertion succeeds. The new key was inserted, two existing keys moved, and every key still occupies one of its two permitted homes. A later lookup for any of these keys still examines only its own two homes; it does not need to replay the eviction chain.

An implementation must decide which home to try first and how to track the displaced key. Those choices affect the insertion path, but not the essential invariant: after successful insertion, every stored key must be in one of its candidate locations.

6. The two four-slot tables​

The four-slot model makes the process easy to visualize. Start with two empty tables:

Table 1: [ . ] [ . ] [ . ] [ . ]
Table 2: [ . ] [ . ] [ . ] [ . ]

Assume the candidate homes are:

key       home 1       home 2
A         1             2
B         1             3
C         0             2
D         3             0

The first home belongs to Table 1 and the second home belongs to Table 2.

Insert A into its first home, Table 1 slot $1$:

Table 1: [ . ] [ A ] [ . ] [ . ]
Table 2: [ . ] [ . ] [ . ] [ . ]

Insert B. Its first home is also Table 1 slot $1$. Put B there and move A to its second home, Table 2 slot $2$:

Table 1: [ . ] [ B ] [ . ] [ . ]
Table 2: [ . ] [ . ] [ A ] [ . ]

Insert C. Its first home, Table 1 slot $0$, is empty:

Table 1: [ C ] [ B ] [ . ] [ . ]
Table 2: [ . ] [ . ] [ A ] [ . ]

Insert D. Its first home, Table 1 slot $3$, is also empty:

Table 1: [ C ] [ B ] [ . ] [ D ]
Table 2: [ . ] [ . ] [ A ] [ . ]

A lookup for A computes its two homes and checks Table 1 slot $1$ and Table 2 slot $2$. It finds A in the second location. A lookup for C checks its two locations and finds it in Table 1 slot $0$. A missing key is absent if neither of its two candidate slots contains it.

The example is intentionally small. The point is not the particular labels or slot numbers; it is the invariant that lets the lookup stop after two reads.

7. Cycles and rebuilds​

An eviction chain does not always reach an empty slot. It can return to a slot or arrangement that it has already visited. Continuing would repeat the same displacements indefinitely.

Here is a simplified pattern:

key       first home       second home
X         A0                B1
Y         A0                B2
Z         A2                B1

Imagine that inserting X displaces Y. Y moves toward B2, where another occupant may be displaced. That occupant can move to B1, and the chain may eventually return to a location involved earlier in the process. No empty slot is reached by continuing the same sequence.

A cuckoo implementation must detect or limit this behavior. It can track displaced keys, stop after a displacement limit, or use another method to recognize that the current attempt is cycling. Once a cycle is detected, the current arrangement is abandoned and the table is rebuilt.

A rebuild, or rehash, places the keys again using different hash functions, a changed table arrangement, a larger capacity, or some combination of these changes. The supplied description specifically emphasizes that a cycle forces a rebuild. This is not an error outside the design; it is the recovery mechanism for an arrangement that cannot be completed through the current kick sequence.

If a rebuild processes $n$ stored keys, it can require $O(n)$ work. That cost is much larger than the usual local insertion, but it is occasional rather than part of every lookup. Dynamic hash-table implementations often spread exceptional rebuilding costs across many operations; the exact amortized guarantee depends on the resizing and rebuild policy.

The important correctness condition is that normal operations resume only after every key has been placed in one of its two new homes. Lookup must use the same hash functions that were used during the rebuild.

8. Load factor, capacity, and rehashing​

The load factor measures how much table capacity is occupied:

With two tables of four slots each, the total capacity is eight. If five keys are stored, then:

A higher load factor leaves fewer empty locations for kick chains to reach. It also makes it more likely that both homes of a new key are occupied and that the resulting displacement path becomes long or cyclic. For that reason, a cuckoo table may rebuild or resize before every slot is filled.

Resizing changes capacity. For example, the implementation may create larger tables and then insert all existing keys into the new space. Rehashing means recomputing candidate locations, often with different hash functions or a different table configuration. A cycle can force rehashing even when the nominal capacity has not changed, because the current pair of hash functions may produce an arrangement that cannot place the present keys successfully.

A conceptual rebuild looks like this:

choose new hash functions or a new capacity
create empty table storage
for each existing key:
    compute its two new homes
    place it, evicting occupants when necessary
if another cycle occurs:
    try another arrangement

The precise implementation is not the important part. The key invariant is that a successful table has a valid home for every key, and lookup knows exactly which two locations to inspect.

The load factor is therefore both a memory and performance consideration. More unused space consumes more capacity, but it gives insertion more opportunities to finish without a cycle. Less unused space saves capacity but increases pressure on the placement process.

9. Complexity and worst-case behavior​

In a two-home cuckoo table, lookup examines at most two candidate slots. Treating the hash computations and key comparisons as constant-time operations, lookup is $O(1)$ relative to the number of stored keys. This applies to both successful and unsuccessful lookups: at most two homes are checked.

Deletion first locates the key using those same two homes and then clears the occupied location. In the basic two-home model, it does not need to repair a long probe sequence. The exact representation can affect implementation details, but the central deletion search remains bounded by the two candidate locations.

Routine insertion is expected to be $O(1)$ when the table is appropriately sized, the hash functions distribute keys well, and eviction chains remain short. However, a single insertion can perform many displacements, and a cycle can trigger an $O(n)$ rebuild. Therefore, insertion is not universally $O(1)$ in the worst case.

The same distinction applies to hashing more generally. Average-case performance depends on distribution and load management. A poor hash distribution or a deliberately difficult set of keys can make ordinary collision handling approach $O(n)$ for an operation. Cuckoo hashing gives a particularly strong lookup bound, but it does not eliminate the possibility of expensive insertion or rebuilding.

A table holding $n$ entries uses $O(n)$ space, including the capacity reserved for empty slots. The two-home design may use two physical arrays, as in the two four-slot-table model, or an equivalent combined representation. Either way, the data structure needs enough total capacity to preserve efficient placement.

10. Hash maps and frequency counting​

A frequency counter maps each distinct item to the number of times it appears. For example:

apple, pear, apple, plum, pear, apple

produces:

apple -> 3
pear  -> 2
plum  -> 1

For every input item, the algorithm looks up its key, reads the existing count or a default value, increments the count, and stores it again. A hash map is a natural fit because the operation concerns exact keys, not sorted order.

Under average constant-time hash operations, processing $n$ items takes expected $O(n)$ time. With cuckoo hashing, the map's membership and retrieval path checks the key's two candidate homes. The counting algorithm itself does not need to know which home currently contains the key; the table handles that detail.

11. Hash sets and deduplication​

A hash set records whether a key has appeared. To deduplicate a sequence, scan from left to right. If an item is not in the set, emit it and insert it. If it is already present, skip it.

The set stores only membership information, so the value associated with a key is usually unnecessary. In a two-home cuckoo set, membership checks the two candidate slots. If neither contains an equal key, the item is new.

If the surrounding algorithm emits items when first encountered, the output can preserve first-seen order. That behavior comes from the scan and output logic, not from hashing itself. A hash table should not be assumed to preserve sorted order.

12. Two-sum style lookups​

In a two-sum style problem, the algorithm examines each current value $x$ and asks whether a previously seen value equals the complement of $x$ with respect to the target. The required key is:

The algorithm checks whether needed is in a hash set or map. If it is present, a matching pair has been found. If not, the algorithm records $x$ and continues.

With $n$ values and average $O(1)$ hash operations, the complete scan takes expected $O(n)$ time. A direct comparison of every pair can take $O(n^2)$ time. The improvement comes from storing previously seen values so that the complement test does not scan all earlier values.

Cuckoo hashing fits the membership test naturally: compute the two homes of needed and inspect them. The application sees a fast exact-key query; the collision-resolution details remain inside the data structure.

13. Grouping by a key​

Grouping uses a map from a group key to a collection of members. The group key might be a category, a first letter, or another computed identifier. For each record, the algorithm looks up the group, creates it if necessary, and adds the record to that group's collection.

Hashing makes the map lookup expected $O(1)$, so creating or finding a group does not require scanning all existing groups. The values stored in the map may be arrays, sets, trees, or other collections. Their behavior is separate from the map's key lookup.

This distinction matters when analyzing complexity. Hashing locates the group. Adding an item to the group's value collection may have its own cost, depending on the collection and operation.

14. Caching​

A cache maps a request key to a stored result. On a request, the system hashes the key and checks whether the result exists. A hit returns the cached value. A miss computes or retrieves the result and stores it under the key.

Exact-key lookup is usually more important to a cache than sorted order. A two-home cuckoo table offers a bounded lookup path: the cache checks the two candidate locations for the request key.

Collision eviction and cache eviction are different ideas. In cuckoo insertion, a key is kicked out of a slot because another key needs that slot, and the displaced key moves to its alternate home. In cache management, an entry may be removed because the cache has reached its capacity or because a separate policy prefers other entries. The first is collision resolution; the second is application-level capacity management.

Keeping these operations separate makes the design easier to reason about. Cuckoo hashing preserves the two-home invariant, while the cache policy decides which stored results should remain available.

15. Prefix-sum maps​

Prefix sums provide another useful example of a map keyed by computed values. Let the running prefix sum after position $i$ be:

Suppose a later prefix sum and an earlier prefix sum satisfy:

Then the elements after position $i$ through position $j$ have sum $T$. Rearranging gives the lookup key:

As the algorithm scans the input and computes $P_j$, it checks whether $P_j-T$ appeared earlier. A hash map can store a prefix sum and its first index, allowing the scan to run in expected $O(n)$ time.

The prefix-sum technique and cuckoo placement are separate layers. The algorithm decides which mathematical key to query. The hash table decides which two physical locations can contain that key.

16. The invariants behind two-read lookup​

Cuckoo hashing's lookup guarantee depends on several invariants.

First, every stored key must occupy one of its two candidate homes. If a key were placed in an overflow position, a lookup that checks only the two homes would miss it.

Second, each slot can contain at most one occupant. If a preferred location is occupied, insertion must use the alternate home or displace the current occupant.

Third, insertion and lookup must use the same hash functions and table dimensions. If a rebuild changes the hash functions, all existing keys must be placed according to the new functions before normal lookup resumes.

Fourth, a failed displacement chain must terminate. The implementation must detect a cycle or stop after a suitable limit and then rebuild. Allowing the chain to continue forever would make insertion incorrect and prevent the data structure from making progress.

These invariants explain the trade-off. Lookup is simple because insertion does the difficult work of arranging keys. Every successful insertion leaves behind a state that can be searched through exactly two candidate locations.

17. Strengths and trade-offs​

The strongest feature of two-home cuckoo hashing is its fixed lookup bound. A successful or unsuccessful lookup reads at most two candidate slots. This can be easier to reason about than a variable-length chain or probe sequence.

The cost is more complicated insertion. One insertion can displace several existing keys, and a cycle can force a rebuild involving many entries. The structure also needs sufficient unused capacity so that kick chains are likely to reach empty slots.

Chaining is flexible because a bucket can hold several entries and can tolerate a load factor above one, but a lookup may search a chain. Linear probing is compact and often cache-friendly, but clustering and deletion handling complicate it. Double hashing generally spreads probes better than linear probing, but lookup still examines a variable number of locations. Balanced trees provide ordered operations and $O(\log n)$ worst-case search, but they do not provide the same average exact-lookup target as hashing.

There is no universally best collision strategy. The choice depends on the workload:

• Choose hashing for exact membership, counting, grouping, and key-value retrieval.
• Choose cuckoo hashing when a very small number of lookup reads is especially valuable.
• Choose chaining when flexible bucket occupancy and straightforward collision handling matter.
• Choose probing when compact table storage and locality are priorities.
• Choose sorting or balanced trees when ordered output, range queries, or predictable logarithmic behavior matter.

18. A practical checklist​

When designing or evaluating a hash-based structure, ask:

1. What is the key, and what equality rule determines whether two keys are the same?
2. How many candidate locations does each key have?
3. What happens when all candidate locations are occupied?
4. What load factor is expected?
5. When does the structure resize or rehash?
6. How are cycles or excessively long insertion chains detected?
7. What is the average operation cost?
8. What is the worst-case operation cost?
9. Does the application require sorted order or range queries?
10. How does deletion affect the collision-resolution rules?

For cuckoo hashing, the rebuild policy deserves special attention. A two-read lookup guarantee is useful only if insertion has a reliable way to recover when the current pair of hash functions cannot place every key. The rebuild is part of the design, not an afterthought.

Conclusion​

Hash functions map keys to candidate storage locations. Hash tables, hash maps, and hash sets use those locations to make exact lookup, insertion, and deletion average $O(1)$ under suitable distribution and load assumptions. Their worst case can still be $O(n)$ when collisions become severe or when a global rebuild is required.

Cuckoo hashing makes the lookup rule unusually clear: every key has two homes, and a lookup reads no more than those two slots. When insertion finds an occupied home, it places the new key there and kicks out the occupant. That displaced key moves to its other home and may kick out another key. If the chain reaches an empty slot, insertion succeeds. If the chain cycles, the table rebuilds with a new arrangement.

The central trade-off is therefore easy to remember: cuckoo hashing moves complexity from lookup into insertion and occasional rebuilding. The two four-slot-table model makes that exchange visible. Keys remain in one of two known locations, lookups perform at most two reads, and cycles trigger the rebuild needed to restore the invariant.

For frequency counting, deduplication, two-sum lookups, grouping, caching, and prefix-sum maps, that invariant provides a fast exact-key foundation. The practical disciplines are to monitor load factor, use consistent hash functions, preserve the two-home rule, and treat cycle-triggered rebuilding as a normal part of cuckoo hashing.