Understanding Cuckoo Hashing for Collision Resolution

A hash table offers fast key-based lookup, but its speed depends on how it handles collisions—when different keys map to the same bucket. The choice of collision resolution affects memory use, insertion latency, deletion behaviour and how gracefully a table grows under load.

Chaining stores colliding records in lists, while open addressing searches elsewhere in an array. Cuckoo hashing uses another strategy: every key has two candidate buckets, and an occupied candidate can be displaced to make room for a newcomer.

The result is a compact table with good expected performance, provided its capacity, hash functions and failure recovery are managed carefully. It is not a universal replacement for Python dictionaries, but it is an instructive technique for caches, indexes and fixed-memory lookup structures.

Why collisions need a different strategy

A collision is not a sign that a hash function has failed. Two distinct keys may share an initial bucket, so the table must preserve both records and still support reliable retrieval. The difficult part is balancing predictable memory use with a lookup path that remains short as the population increases.

Separate chaining handles overflow by attaching a list to each bucket. It is forgiving of high load factors, although pointer-heavy list nodes can become expensive in memory-constrained programs. Linear probing searches adjacent array cells, but a long run of occupied cells creates clustering. Both approaches are established, and neither should be discarded without considering workload requirements.

Cuckoo hashing removes the need for a conventional overflow list. A record may live in either of two candidate buckets, determined by two hash functions. If one bucket is full, its occupant is evicted and moved toward its other candidate. This keeps the occupied space compact while trading the risk of a long probe sequence for the possibility of an eviction cycle.

Choosing buckets, capacity, and hash functions

A common layout contains two arrays of buckets, with each bucket holding several slots. If there are m buckets per array and each bucket has B slots, the table provides 2mB usable positions. A key hashes to one bucket in each array; lookup examines both, while insertion chooses whichever has space or begins a displacement process.

The global load factor is n divided by 2mB, where n is the number of live entries. Keeping some empty slots is essential because a full table cannot absorb evictions. With one slot per bucket and two choices, successful insertion becomes difficult at roughly half full in the large-table limit. Multi-slot buckets tolerate denser occupancy, but their exact threshold depends on bucket size, hash quality and the failure policy, so a universal percentage would be misleading.

The two hash functions should also be independent. A weak second function that is merely the first plus a constant can send keys into the same bucket pairs and undermine the whole design. Universal hashing or two independently keyed hashes are stronger choices, particularly when keys may be chosen by an adversary. Hash outputs should map uniformly onto bucket indexes, and the two candidate buckets for a key should normally be distinct.

Following a cuckoo displacement cycle

An insertion starts with the new key and its two candidate buckets. If one has room, the operation is complete. Otherwise, the algorithm selects an occupied slot, replaces its record with the new one and carries the evicted record toward its alternate bucket. The moving record can trigger another eviction, producing a chain of kicks across the table.

A simplified insertion routine can make the invariant explicit. Here, other_candidate returns the position that is not the current bucket, and a fixed kick limit prevents an unresolved cycle from running forever.

insert(item):
    moving = item
    place = random choice of the two candidate buckets

    for kick in 1..MAX_KICKS:
        if bucket[place] has a free slot:
            store moving in bucket[place]
            return true

        slot = random occupied slot in bucket[place]
        bucket[place][slot], moving = moving, bucket[place][slot]
        place = other_candidate(moving.key, place)

    return false

A false result means that this attempt did not find a legal arrangement; it does not mean the key has been partially inserted. The table can retry with another bucket choice, use a different seed or rebuild with more capacity. Tracking visited buckets can identify an obvious cycle earlier, but a kick cap remains necessary because repeated states need not always appear as a simple visible loop.

Lookup, deletion, and table growth

Lookup is straightforward because the key can only be in one of two candidate buckets. The implementation checks both and compares stored keys, rather than trusting a hash value alone. With a fixed bucket size, the expected cost is constant; a stored fingerprint can speed up comparisons, but it must still be verified against the complete key to avoid a false match.

Deletion requires checking the same two buckets. A physical removal is simplest with lists of records, since cuckoo placement does not create an open-addressing cluster that must be preserved. Fixed-slot implementations may use a tombstone to mark a deleted record, but tombstones still consume space and should not be counted as live entries. Periodic cleanup or a resize returns that capacity to useful work.

A rebuild rehashes every live record into a larger or freshly allocated table. Resizing after an insertion failure is essential, but proactive resizing at a measured occupancy threshold is usually more predictable. When the required operation is a range sum rather than equality lookup, a dedicated ordered index is preferable; this Fenwick tree implementation illustrates that alternative. A cuckoo table should be chosen because direct lookup fits the problem, not because every indexing task needs the same structure.

Failure modes and probabilistic guarantees

Cuckoo hashing has expected constant-time lookup and usually fast insertion, yet it does not guarantee that every insertion will succeed. Two records may need to occupy the same candidate bucket, or a cycle may require a record to return to a bucket already visited. The bounded kick routine detects that practical failure, after which the program must resize, rebuild or reject the insertion without losing existing data.

The guarantees depend on random or universal hash choices and on occupancy below an appropriate threshold. Near the critical load, successful insertion probability can fall sharply rather than degrade smoothly, making monitoring important. Increasing bucket capacity can raise the usable load, yet it also enlarges the number of entries that must be examined during lookup and eviction. These trade-offs are why an implementation should report both live-entry count and physical slot occupancy.

A fixed, predictable hash mapping can also create pathological inputs, particularly when an external party controls the keys. Seeded hashing reduces that exposure, although it does not turn the structure into a universal worst-case data structure. The path-like nature of evictions has a loose analogy with route selection in graph algorithms: the Johnson algorithm guide shows how repeated edge decisions are handled when calculating shortest paths, though cuckoo hashing uses a far smaller and different state space.

Building and testing the implementation

Python is well suited to a prototype because lists can represent buckets and functions can express the candidate calculations cleanly. A practical class should store the two bucket indexes for each entry, the live count, physical occupancy and the maximum kick limit. It should also expose an explicit rebuild operation rather than silently changing capacity during a failed insert. Similar exercises in the problem-solving collection can help readers practise choosing between a dictionary, a tree and a specialised hash table.

Australian use cases add useful constraints. Sydney and Melbourne commuters commonly check public-transport and journey-planning apps on mobile devices, and this mobile-first habit is also common in Brisbane and Perth. Compact tables can suit handsets and embedded tools where memory is limited. In the local market, retailers such as Coles and Woolworths operate catalogue, stock and online-fulfilment systems, while Australian banks and fintech businesses support everyday payments through mobile apps; fast, stable lookups matter across both settings.

Privacy and security rules require equal care. Under the Privacy Act 1988 and the Australian Privacy Principles, a hashed customer or staff identifier may still count as personal information when it can reasonably be linked to a person. Security safeguards such as access controls and appropriate key management are therefore part of a sound design, alongside obligations surrounding the Notifiable Data Breaches scheme. A keyed hash is preferable to a plain digest for unguessable identifiers, but pseudonymisation should not be mistaken for automatic de-identification.

Testing should cover ordinary inserts, duplicate handling, deletions, high load, rebuilds and deliberately unhelpful key patterns. Property-based tests can generate random key sets, compare lookups against a reference dictionary and verify that every successful insertion leaves its key in one of its two legal buckets. Benchmarks should measure lookup, insertion and rebuild time separately, because improving one operation can quietly damage another.

Recommendations for dependable implementations

Cuckoo hashing works best as a deliberately sized, self-monitoring index. The following practices keep its probabilistic strengths while making rare insertion failures visible and recoverable.

• Use two independently keyed hash functions, and verify complete keys during lookup instead of trusting fingerprints alone.
• Keep bucket capacity small and defined, then monitor the live load factor and physical slot occupancy as separate measures.
• Set a finite kick limit and give every failed insertion a defined path to retry or rebuild with additional capacity.
• Remove deleted records cleanly, expire tombstones during maintenance and never count them as usable live entries.
• Test duplicate keys, collisions, deletions, full buckets, forced kick chains and rebuilds with reproducible seeds.
• Benchmark against realistic dictionaries and alternative indexes, recording the occupancy at which insertion latency becomes unacceptable.

Together, these measures make the table’s behaviour understandable rather than mysterious. The defining operational property is not constant-time insertion under every circumstance, but controlled failure followed by deterministic recovery.