Cuckoo Hashing — Correlated Hash Functions and Rehash Loops

Hash tables are the backbone of modern software — they power database indexes, caches, compilers, and networking stacks. But the classic open-addressing and chaining approaches carry a hidden cost: their lookup time degrades under load. A bucket with five chained nodes requires five pointer dereferences. A probing table at 80% occupancy can force dozens of slot comparisons per lookup. For most applications that cost is tolerable. For latency-sensitive systems — packet classification in network routers, real-time game servers, CPU-level cache simulators — tolerable is not a design target.

Cuckoo hashing, introduced by Rasmus Pagh and Flemming Friche Rodler in 2001, attacks this problem with a radical guarantee: lookups always examine at most two memory locations. Worst-case O(1) — not amortized, not expected, but hard. It achieves this by giving every key two candidate slots across two separate hash tables and using an eviction-and-relocation protocol during insertion to ensure no slot ever holds more than one key.

That guarantee comes with strings attached. Insertion is unpredictable and can fail entirely when eviction chains cycle back on themselves. The load factor ceiling is roughly half what chained hashing tolerates. Hash function independence is not a nice-to-have — it is the mechanism the whole structure depends on. And if you deploy this without a max-iteration guard on the eviction chain, you have introduced an infinite loop into your production system.

By the end of this article you will understand exactly how the two-table eviction cycle works, why infinite loops occur and how to detect them before they happen, how to implement a working cuckoo hash map in Java with cycle detection and graceful rehashing, what load factor limits apply and why exceeding them causes exponential rehash overhead, and when cuckoo hashing genuinely beats its alternatives in production. The interview questions at the end go into the nuanced territory that separates candidates who have read about this structure from those who have actually operated it under load.

Cuckoo Hashing — When Two Tables Are Better Than One

Cuckoo hashing is a collision resolution scheme that guarantees O(1) worst-case lookup by using two independent hash functions and two separate tables. When a new key collides at its primary position in table T1, it evicts the existing occupant, which then rehashes to its alternate position in T2. That occupant may evict another key back to T1, creating a chain of displacements until either every key settles or a cycle is detected. This is the core mechanic: constant-time lookups at the cost of unpredictable insertion time.

In practice, cuckoo hashing achieves an average insertion cost of O(1) with high probability, but worst-case insertions can degrade to O(n) when a rehash loop occurs — typically after a threshold of evictions (e.g., 500 iterations). The load factor must stay below 50% per table (total ~90% combined) to keep cycles rare. Memory overhead is roughly 2x a standard hash table because of the two tables, but the payoff is deterministic lookup latency, critical for real-time systems.

Use cuckoo hashing when worst-case lookup latency must be bounded — for example, in packet processing, CPU caches, or database index structures where a single slow hash probe could stall a pipeline. It is not a general-purpose replacement for HashMap; the insertion cost variance and memory doubling make it unsuitable for write-heavy workloads. The real value is in read-dominated paths where every nanosecond matters and you cannot tolerate the occasional O(n) probe from chaining or open addressing.

Core Mechanism: Two Tables, Two Hash Functions

The structure is built on one invariant: no slot in either table ever holds more than one key. Cuckoo hashing maintains two hash tables, T1 and T2, each of size n. Every key k has exactly two candidate positions — h1(k) in T1 and h2(k) in T2. That invariant is what makes lookup trivially fast.

To look up a key, compute h1(k) and h2(k) and check both slots. Two memory accesses. No probing, no chaining, no traversal, no variable-length search. If the key is in the table, it is in one of those two locations. If it is in neither, it is not in the table. That is the entire lookup algorithm.

Insertion is where the complexity lives. To insert key k, first try T1[h1(k)]. If the slot is empty, place k there and finish. If the slot is occupied by some existing key k', evict k' and place k in its slot. k' now needs a home — its only remaining option is T2[h2(k')]. If that slot is also occupied, evict that occupant and continue. The chain zigzags between T1 and T2: each evicted key has exactly one alternate table to move to, and within that table exactly one candidate slot. The chain terminates when an empty slot is found or when it has gone on long enough to indicate a cycle.

The asymmetry between lookup and insertion is intentional. You pay a variable insertion cost — sometimes one step, sometimes dozens — in exchange for a guaranteed, constant, predictable lookup cost. For workloads where lookups vastly outnumber inserts, that is a trade you want to make. For write-heavy workloads it is the wrong tool entirely.

package io.thecodeforge.hashing;

import java.util.Objects;

/**
 * Production-grade cuckoo hash map with cycle detection and auto-resize.
 * Two independent hash functions over two tables.
 *
 * Design constraints:
 *  - MAX_EVICTION_CHAIN bounds insertion to prevent infinite loops
 *  - LOAD_FACTOR_THRESHOLD triggers proactive resize before cycle probability climbs
 *  - hash1/hash2 use different mixing constants — verify independence before deployment
 */
public class CuckooHashMap<K, V> {

    private static final int    MAX_EVICTION_CHAIN     = 512;
    private static final double LOAD_FACTOR_THRESHOLD  = 0.45;
    private static final int    DEFAULT_INITIAL_CAPACITY = 16;

    // Package-private so CuckooResizer can read entries directly
    Entry<K, V>[] table1;
    Entry<K, V>[] table2;
    int capacity;
    private int size;

    static class Entry<K, V> {
        final K key;
        V value;

        Entry(K key, V value) {
            this.key   = key;
            this.value = value;
        }
    }

    @SuppressWarnings("unchecked")
    public CuckooHashMap(int initialCapacity) {
        this.capacity = nextPowerOfTwo(initialCapacity);
        this.table1   = new Entry[this.capacity];
        this.table2   = new Entry[this.capacity];
        this.size     = 0;
    }

    public CuckooHashMap() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    /**
     * Hash function 1 — finalizer mixing from MurmurHash3.
     * The >>> 16 XOR fold reduces slot clustering in the low bits.
     */
    private int hash1(K key) {
        int h = key.hashCode();
        h ^= (h >>> 16);
        h *= 0x85ebca6b;
        h ^= (h >>> 13);
        return h & (capacity - 1);
    }

    /**
     * Hash function 2 — different multiplier constant for independence.
     * Uses the golden-ratio-derived constant 0x9e3779b9.
     * Never derive h2 as h1 + offset — that is maximally correlated.
     */
    private int hash2(K key) {
        int h = key.hashCode() * 0x9e3779b9;
        h ^= (h >>> 16);
        h *= 0xc2b2ae35;
        h ^= (h >>> 16);
        return h & (capacity - 1);
    }

    /**
     * O(1) worst-case lookup — exactly two memory accesses.
     * Returns null if the key is absent.
     */
    public V get(K key) {
        Objects.requireNonNull(key, "null keys are not supported");
        int idx1 = hash1(key);
        if (table1[idx1] != null && table1[idx1].key.equals(key)) {
            return table1[idx1].value;
        }
        int idx2 = hash2(key);
        if (table2[idx2] != null && table2[idx2].key.equals(key)) {
            return table2[idx2].value;
        }
        return null; // key not present — checked both candidate slots
    }

    /**
     * Insert or update a key-value pair.
     *
     * Returns true on success.
     * Returns false when the eviction chain exceeds MAX_EVICTION_CHAIN —
     * the caller must trigger a resize-and-rehash before retrying.
     *
     * Never silently drops keys — false is an explicit signal, not an ignored error.
     */
    public boolean put(K key, V value) {
        Objects.requireNonNull(key, "null keys are not supported");

        // Update in place if the key already exists — avoids growing eviction chains
        int idx1 = hash1(key);
        if (table1[idx1] != null && table1[idx1].key.equals(key)) {
            table1[idx1].value = value;
            return true;
        }
        int idx2 = hash2(key);
        if (table2[idx2] != null && table2[idx2].key.equals(key)) {
            table2[idx2].value = value;
            return true;
        }

        // Begin eviction chain — alternate between T1 and T2
        Entry<K, V> toInsert  = new Entry<>(key, value);
        boolean     useTable1 = true;

        for (int i = 0; i < MAX_EVICTION_CHAIN; i++) {
            if (useTable1) {
                int idx = hash1(toInsert.key);
                if (table1[idx] == null) {
                    table1[idx] = toInsert;
                    size++;
                    return true;
                }
                // Evict occupant; it will try T2 on the next iteration
                Entry<K, V> evicted = table1[idx];
                table1[idx] = toInsert;
                toInsert    = evicted;
                useTable1   = false;
            } else {
                int idx = hash2(toInsert.key);
                if (table2[idx] == null) {
                    table2[idx] = toInsert;
                    size++;
                    return true;
                }
                Entry<K, V> evicted = table2[idx];
                table2[idx] = toInsert;
                toInsert    = evicted;
                useTable1   = true;
            }
        }

        // Chain limit exceeded — cycle detected or near-cycle.
        // Caller must call CuckooResizer.resize(this) and retry the insertion.
        return false;
    }

    /**
     * Deletion is clean — no tombstones required.
     * A key exists in exactly one of two known slots.
     */
    public boolean remove(K key) {
        Objects.requireNonNull(key);
        int idx1 = hash1(key);
        if (table1[idx1] != null && table1[idx1].key.equals(key)) {
            table1[idx1] = null;
            size--;
            return true;
        }
        int idx2 = hash2(key);
        if (table2[idx2] != null && table2[idx2].key.equals(key)) {
            table2[idx2] = null;
            size--;
            return true;
        }
        return false;
    }

    /** Combined load across both tables — useful for trend monitoring */
    public double loadFactor() {
        return (double) size / (2.0 * capacity);
    }

    /**
     * Per-table load factor — the metric that actually matters.
     * Returns the higher of the two individual table occupancies.
     * Alert when this exceeds 0.45; resize when it exceeds 0.50.
     */
    public double perTableLoadFactor() {
        int t1Count = 0, t2Count = 0;
        for (Entry<K, V> e : table1) if (e != null) t1Count++;
        for (Entry<K, V> e : table2) if (e != null) t2Count++;
        return Math.max(
            (double) t1Count / capacity,
            (double) t2Count / capacity
        );
    }

    /** Returns false when per-table load exceeds the production threshold */
    public boolean isHealthy() {
        return perTableLoadFactor() < LOAD_FACTOR_THRESHOLD;
    }

    public int size() { return size; }

    private static int nextPowerOfTwo(int n) {
        if (n <= 1) return 1;
        n--;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n + 1;
    }
}

Cycle Detection and the Infinite Loop Problem

The fundamental failure mode of cuckoo hashing is the eviction cycle. During insertion, the chain zigzags between T1 and T2: evict from T1, try T2, evict from T2, try T1, and so on. If this chain revisits a slot that was already modified earlier in the same insertion, the displaced key has nowhere to go that it has not already displaced someone from. You have a cycle, and without a guard the loop runs forever.

This is not a theoretical edge case. The probability of encountering a cycle is a function of load factor, and it rises steeply. At 40% per-table occupancy the risk is negligible — a properly seeded implementation can run millions of insertions without seeing one. At 50% the expected failure rate per insertion is around 1%. At 55% it climbs toward 10%. At 60% you should expect failure on nearly every insertion attempt. The relationship is exponential, not linear, which is why the 45% production ceiling feels conservative but genuinely matters.

The adversarial key distribution problem compounds this. A 2004 analysis by Devroye and Morin established the theoretical load limit, but that analysis assumes random hash function behaviour. When real key sets interact with fixed hash functions, certain key patterns produce consistently long eviction chains at any load factor. This is what the production incident above captured: a traffic burst introduced a pattern of source IPs that happened to hash to overlapping slot pairs under both functions. The functions were correlated, which made the overlap worse, but even with independent functions an adversarial enough key set can trigger cycles at 35% load.

The practical response is layered. First, bound the chain: if the eviction chain exceeds MAX_EVICTION_CHAIN iterations, abort the insertion and return false — the calling code triggers a resize. Second, use new hash seeds on every rehash — the same functions on a larger table will reproduce the same problematic slot assignments for the same key set. Third, monitor insertion failure rate as a first-class metric alongside load factor. Load factor tells you where you are on the probability curve; insertion failure rate tells you whether the current key distribution is adversarial relative to your hash functions.

Two approaches to cycle detection exist in practice. The iteration count approach is simpler and lower overhead: if the chain runs longer than MAX_EVICTION_CHAIN steps, declare failure. The visited-set approach is more precise: track every (table, slot) pair visited during the chain and stop immediately when a pair repeats. The visited-set detects true cycles early and can terminate in fewer than MAX_EVICTION_CHAIN steps, but it allocates memory per insertion attempt and adds overhead to every step. For most production systems the iteration count is sufficient — the overhead of the visited-set only pays off when adversarial key distributions are a hard requirement.

package io.thecodeforge.hashing;

import java.util.HashSet;
import java.util.Set;

/**
 * Explicit cycle detection using a visited-slot fingerprint set.
 *
 * More precise than iteration count alone — terminates immediately
 * on true cycle detection rather than running to MAX_EVICTION_CHAIN.
 * Trade-off: allocates a HashSet per insertion attempt.
 *
 * Use this when key distributions are known to be adversarial
 * and early termination saves more than the allocation costs.
 * For most workloads, the iteration-count guard in CuckooHashMap
 * is sufficient and cheaper.
 */
public class CycleDetector<K> {

    private final Set<Integer> visitedSlots;
    private final int          maxChainLength;

    public CycleDetector(int maxChainLength) {
        this.maxChainLength = maxChainLength;
        this.visitedSlots   = new HashSet<>();
    }

    /**
     * Returns true if visiting this (table, slot) pair would complete a cycle.
     *
     * Encodes the pair as a single int fingerprint:
     *   - high byte = tableIndex (0 or 1)
     *   - low 24 bits = slotIndex (supports tables up to 16M slots)
     *
     * Call this before executing each eviction step.
     */
    public boolean wouldCycle(int tableIndex, int slotIndex) {
        int fingerprint = (tableIndex << 24) | (slotIndex & 0x00FFFFFF);
        return !visitedSlots.add(fingerprint); // add returns false if already present
    }

    /**
     * Returns true if the chain has exceeded the configured maximum.
     * Check this alongside wouldCycle — whichever triggers first aborts.
     */
    public boolean exceedsMaxLength(int currentLength) {
        return currentLength >= maxChainLength;
    }

    /**
     * Reset between insertion attempts.
     * Reuse the detector instance across attempts to avoid repeated allocation.
     */
    public void reset() {
        visitedSlots.clear();
    }

    /**
     * Number of unique slots visited in the current chain.
     * Useful for diagnostics — log this on insertion failure.
     */
    public int visitedCount() {
        return visitedSlots.size();
    }
}

Hash Function Selection and Independence

Everything in cuckoo hashing depends on one property of the two hash functions: they must distribute keys independently. If h1 and h2 are correlated — and the most common way this happens is someone writes h2(k) = h1(k) + constant because it looks simple and distinct — then the two candidate slots for many keys will cluster in the same region of the table. The structure now behaves like a single table with twice the collision rate. Cycles form at load factors you would consider safe for open addressing.

Independence in hash functions is a stronger requirement than uniformity. A function can distribute keys uniformly across all slots and still be correlated with another function that does the same. What matters is that knowing h1(k) tells you nothing useful about h2(k). In practice you achieve this either by using genuinely different algorithms (SipHash versus MurmurHash3) or by using the same algorithm with seeds chosen to produce statistically independent outputs — and then verifying empirically before deployment.

MurmurHash3's 128-bit output variant is a natural fit here. It produces two independent 64-bit values in a single pass. Use the low 64 bits for h1 and the high 64 bits for h2. The two halves are designed to be independent by construction, and you get both values from one computation — no extra cost per lookup or insertion.

SipHash with different 128-bit key pairs is the stronger choice when the key space may be adversarially controlled — for example, if your cuckoo hash table is part of a network-facing service where an attacker could craft keys to maximize collisions. SipHash's resistance to hash flooding comes from the key material; changing the key pair changes the entire output distribution.

Tabulation hashing is worth knowing about for academic completeness: it achieves strong theoretical independence guarantees and is extremely fast (array lookups only), but it requires per-byte random tables that consume memory proportional to the key size and are awkward to implement correctly for variable-length keys.

The practical check: after choosing your two functions, run estimateIndependence() against a representative sample of your key set. The overlap rate — the fraction of keys for which h1(k) == h2(k) after modulo — should be approximately 1/capacity. If it is significantly higher, your functions are correlated. This test takes seconds and has caught production issues that would otherwise only appear under load.

package io.thecodeforge.hashing;

import java.util.Set;

/**
 * Two independent hash functions for cuckoo hashing.
 *
 * Both use Murmur3-style 64-bit finalizer mixing with different
 * seed constants. The seeds are chosen to be statistically independent
 * — they are not offsets of each other.
 *
 * For adversarial key environments (network-facing services), replace
 * these with SipHash using separate 128-bit key pairs per function.
 *
 * Before deploying to production, call estimateIndependence() with a
 * representative key sample and verify overlap < 2.0 / capacity.
 */
public class HashFunctions {

    // Two distinct constants derived from known low-discrepancy sequences
    // Do NOT derive SEED2 as SEED1 + offset — that introduces correlation
    private static final long SEED1 = 0x517cc1b727220a95L;
    private static final long SEED2 = 0x9e3779b97f4a7c15L;

    /** Hash function 1 — Murmur3 64-bit finalizer with SEED1 */
    public static int hash1(Object key, int capacity) {
        long h = (long) key.hashCode() ^ SEED1;
        h ^= h >>> 33;
        h *= 0xff51afd7ed558ccdL;
        h ^= h >>> 33;
        h *= 0xc4ceb9fe1a85ec53L;
        h ^= h >>> 33;
        return (int) (h & (capacity - 1));
    }

    /** Hash function 2 — same finalizer structure, independent seed */
    public static int hash2(Object key, int capacity) {
        long h = (long) key.hashCode() ^ SEED2;
        h ^= h >>> 33;
        h *= 0xff51afd7ed558ccdL;
        h ^= h >>> 33;
        h *= 0xc4ceb9fe1a85ec53L;
        h ^= h >>> 33;
        return (int) (h & (capacity - 1));
    }

    /**
     * Empirical independence check.
     *
     * For a uniformly random key set, the expected fraction of keys
     * where hash1 == hash2 (after modulo) is 1/capacity.
     *
     * A result significantly above 2/capacity indicates correlation
     * and predicts premature cycle formation under load.
     *
     * Run this with at least 10,000 representative keys before
     * deploying a new hash function pair to production.
     *
     * @return overlap fraction — target < 2.0 / capacity
     */
    public static double estimateIndependence(Set<Object> keys, int capacity) {
        if (keys.isEmpty()) {
            throw new IllegalArgumentException(
                "Key sample must be non-empty — use at least 10,000 representative keys"
            );
        }
        long overlapCount = 0;
        for (Object key : keys) {
            if (hash1(key, capacity) == hash2(key, capacity)) {
                overlapCount++;
            }
        }
        return (double) overlapCount / keys.size();
    }
}

Load Factor Limits and Rehash Strategy

Cuckoo hashing operates under tighter load factor constraints than any other common hash table variant. The theoretical maximum for two tables of size n is 50% per table — meaning you can fill at most n keys into a pair of tables each holding n slots before cycle probability becomes prohibitive. In practice that ceiling is lower, and the gap between theory and production reality matters.

Below 40% per table, insertion is nearly always fast. Eviction chains are short — typically two to five steps. Cycle probability is negligible for most key distributions and hash function pairs. This is the comfortable operating range where cuckoo hashing delivers its performance guarantee without any insertion drama.

Between 40% and 50%, behaviour depends heavily on hash function quality and key distribution. With good independent hash functions and non-adversarial keys, you can run in this range and see occasional longer chains but rare failures. With correlated functions or adversarial keys, failure rates in this band climb fast. This is the region where monitoring insertion failure rate becomes important — load factor alone does not tell you enough.

Above 50%, insertion failure should be expected rather than tolerated. The probability curve is exponential in this range. Trying to squeeze extra utilisation out of a cuckoo table above 50% is not a capacity optimisation — it is borrowing reliability against a debt that collects with interest during your next traffic spike.

The production-grade rehash strategy has four components. First, double the table capacity — 2x growth is standard and keeps amortised insertion cost O(1) across the table's lifetime. Second, generate new hash function seeds — the same functions on a larger table reproduce the same adversarial slot mappings. Third, re-insert every key from the old tables into the new ones — this is O(n) but happens infrequently, and the new seeds mean the insertion success rate should be high. Fourth, retry rehash with a further capacity increase if the first attempt fails — adversarial key sets occasionally defeat even a freshly seeded pair; cap retries at five and throw on persistent failure rather than looping silently.

For systems where rehash latency is unacceptable — a routing table that cannot pause for 50ms while 2 million entries are re-inserted — consider the stash approach. A small auxiliary array (16 to 64 slots) holds overflow keys that failed eviction. These keys require a third memory access during lookup, but the stash reduces rehash frequency dramatically. A stash of size O(log n) reduces insertion failure probability from O(1/n) to O(1/n²) — the difference between rehashing every few thousand inserts and rehashing every few billion.

package io.thecodeforge.hashing;

/**
 * Handles table resizing and rehashing with independent hash seeds.
 *
 * Called when CuckooHashMap.put() returns false — meaning the eviction
 * chain exceeded MAX_EVICTION_CHAIN and the current table cannot
 * accommodate the key set under its current hash functions.
 *
 * Rehash strategy:
 *  1. Double capacity
 *  2. Allocate new tables (old tables become eligible for GC)
 *  3. Re-insert all entries — new hash functions break adversarial patterns
 *  4. If re-insertion fails, grow by an additional 1.5x and retry
 *  5. After MAX_REHASH_ATTEMPTS, throw — something is structurally wrong
 *
 * The caller is responsible for replacing the reference to the old map.
 * In Java, the old Entry arrays become unreachable after replacement
 * and will be collected at the next GC cycle — confirm with a heap dump
 * if memory usage does not drop as expected.
 */
public class CuckooResizer<K, V> {

    private static final double GROWTH_FACTOR        = 2.0;
    private static final double RETRY_GROWTH_FACTOR  = 1.5;
    private static final int    MAX_REHASH_ATTEMPTS  = 5;

    /**
     * Resize and rehash the given map, returning a new map at larger capacity.
     *
     * The returned map uses the same CuckooHashMap class but with a new
     * capacity. Hash seed variation is handled by the new capacity interacting
     * with the mixing constants in hash1/hash2 — for stronger independence
     * under adversarial conditions, parameterise HashFunctions with
     * externally supplied seeds and rotate them here.
     *
     * @throws IllegalStateException if rehash fails after all retry attempts
     */
    public static <K, V> CuckooHashMap<K, V> resize(CuckooHashMap<K, V> current) {
        int newCapacity = (int) (current.capacity * GROWTH_FACTOR);

        for (int attempt = 1; attempt <= MAX_REHASH_ATTEMPTS; attempt++) {
            CuckooHashMap<K, V> newMap  = new CuckooHashMap<>(newCapacity);
            boolean             success = true;

            // Re-insert from table1
            for (CuckooHashMap.Entry<K, V> entry : current.table1) {
                if (entry != null && !newMap.put(entry.key, entry.value)) {
                    success = false;
                    break;
                }
            }

            // Re-insert from table2 only if table1 succeeded
            if (success) {
                for (CuckooHashMap.Entry<K, V> entry : current.table2) {
                    if (entry != null && !newMap.put(entry.key, entry.value)) {
                        success = false;
                        break;
                    }
                }
            }

            if (success) {
                // Old map's Entry arrays are now unreachable — GC eligible
                return newMap;
            }

            // This attempt failed — grow further and try again
            // Capacity increase changes the modulo distribution, acting as
            // an implicit seed change for fixed mixing constants
            newCapacity = (int) (newCapacity * RETRY_GROWTH_FACTOR);
        }

        throw new IllegalStateException(
            String.format(
                "CuckooResizer: failed after %d rehash attempts starting at capacity %d. "
              + "Key distribution is likely adversarial. Consider SipHash with rotated seeds.",
                MAX_REHASH_ATTEMPTS,
                (int) (current.capacity * GROWTH_FACTOR)
            )
        );
    }
}

Cuckoo Hashing vs Alternatives in Production

Choosing a hash table implementation is a trade-off analysis, and the right answer depends on ratios you should measure rather than assume. Here is how cuckoo hashing compares against the alternatives you are actually likely to consider.

Chained hashing is the baseline: each slot holds a linked list, collisions extend the chain, and load factors of 80% or higher are manageable. Insertion is O(1) amortized. Lookup is O(1) expected but degrades under load — a heavily loaded bucket means traversing several nodes with pointer dereferences at each step. For CPU cache efficiency this is poor, and for latency guarantees it is non-starter territory. Java's HashMap is chained and switches to a tree structure per bucket at chain length 8, which bounds the worst case but adds per-insertion overhead and GC pressure from node allocation.

Linear probing is cache-friendly because it accesses consecutive memory locations, which plays well with prefetchers. But it clusters under load — the probe sequence lengthens quadratically as occupancy rises, and worst-case lookup is O(n). Deletion requires tombstone markers that accumulate and degrade subsequent lookups without periodic compaction.

Robin Hood hashing reduces probe sequence variance by requiring each key to be displaced if the new arrival has searched longer than the current occupant — a richer-gets-displaced policy. This produces a more uniform probe distribution and lower variance in lookup cost, but worst-case is still O(n). Its advantage over cuckoo hashing is at high load factors (70%+ is viable) and in write-heavy workloads where insertion predictability matters more than lookup guarantees.

Hopscotch hashing constrains keys to a small neighbourhood around their home slot, enabling concurrent lock-free implementations with bounded lookup distances. It handles high load well and is cache-friendly. It is more complex to implement correctly than either open addressing or cuckoo hashing, and the lookup bound is neighbourhood size rather than a hard two-location check.

Cuckoo hashing wins when: lookups are the dominant operation by a large margin (95%+), lookup latency must be bounded not just on average but at every percentile, or concurrent lock-free reads are required without complex synchronisation. The two-fixed-location property enables lock-free reads with a single memory fence — no pointer chasing, no variable-length probe sequence, no possibility of a reader observing a partially-written chain.

The benchmark numbers from our routing table comparison are worth stating concretely: cuckoo achieved 38ns p99 lookup and 1,200ns p99 insertion. Robin Hood achieved 52ns p99 lookup and 45ns p99 insertion. For a workload that was 99.7% reads, cuckoo's lookup advantage was decisive. For a workload that was 60% reads, Robin Hood's insertion consistency would have won.

Cuckoo Hashing in Action: A Concrete Walkthrough

Theory is cheap. Let's watch this thing breathe. You've got two tables, each with 10 slots, and two hash functions: h1(x) = x % 10, h2(x) = (x / 10) % 10. Insert 5. h1(5) = 5, slot 5 is empty. Done. Insert 15. h1(15) = 5 — collision. Cuckoo kicks 5 out to its alternate position. h2(5) = 0, slot 0 is empty. 5 moves there, 15 sits in slot 5. Insert 25. h1(25) = 5 — collision with 15. Kick 15 out. h2(15) = 1, slot 1 empty. 15 moves, 25 takes slot 5. Now look what happened: every insertion displaced exactly one element. No linked lists. No probing chains. Worst case lookup is still one hash, one table access, done. That's the guarantee. You can trace this on a whiteboard in under 30 seconds. The predictability matters when you're debugging a production latency spike at 3 AM. Knowing your lookup will never cascade beyond two memory accesses changes how you sleep.

// io.thecodeforge — dsa tutorial

public class CuckooWalkthrough {
    public static void main(String[] args) {
        int[] table1 = new int[10];
        int[] table2 = new int[10];
        int[] keys = {5, 15, 25};
        
        for (int k : keys) {
            int pos1 = k % 10;
            if (table1[pos1] == 0) {
                table1[pos1] = k;
            } else {
                int displaced = table1[pos1];
                table1[pos1] = k;
                int pos2 = (displaced / 10) % 10;
                table2[pos2] = displaced;
            }
        }
        
        System.out.println("Table1: " + java.util.Arrays.toString(table1));
        System.out.println("Table2: " + java.util.Arrays.toString(table2));
    }
}

Implementation Blueprint: The Bare Metal Loop

Here's where most tutorials wave their hands. I'm showing you the actual loop structure that makes cuckoo hashing work under load. The core is a while loop that runs for a bounded number of attempts. You maintain a current key, current table index, and a counter. Each iteration: try placing the key in its primary table. If that slot is free, done. If not, swap the occupant into the current key and flip to the other table using its alternate hash. Increment the counter. If counter exceeds a threshold — typically O(log n) or a fixed constant like 20 — you bail out and trigger a rehash. Why? Because you've either hit a cycle or the table is too full. The threshold is your safety net against infinite loops. Production systems tune this based on load factor. At 50% load, you almost never hit the limit. At 90%, you'll trigger rehash constantly. That's correct behavior. The rehash doubles table size, picks new hash functions from a universal family, and inserts everything fresh. It's expensive but rare. The rest of the time, you're paying for two hash computations and maybe two memory swaps. That's the trade: occasional O(n) rehash, everyday O(1) operations.

// io.thecodeforge — dsa tutorial

public class CuckooInsertionLoop {
    static final int MAX_ATTEMPTS = 10;
    
    public boolean insert(int key, int[] t1, int[] t2) {
        int current = key;
        int attempts = 0;
        
        while (attempts < MAX_ATTEMPTS) {
            int pos1 = hash1(current, t1.length);
            if (t1[pos1] == 0) {
                t1[pos1] = current;
                return true;
            }
            int displaced = t1[pos1];
            t1[pos1] = current;
            current = displaced;
            
            int pos2 = hash2(current, t2.length);
            if (t2[pos2] == 0) {
                t2[pos2] = current;
                return true;
            }
            displaced = t2[pos2];
            t2[pos2] = current;
            current = displaced;
            attempts++;
        }
        return false; // triggers rehash
    }
    
    int hash1(int key, int size) { return key % size; }
    int hash2(int key, int size) { return (key / size) % size; }
}

Why Your First Hash Function Is Already Leaking

Hash function independence is not academic trivia. If your two hash functions produce correlated outputs, you guarantee cycles at absurdly low load factors. Every collision becomes a cluster, every insert becomes O(n) evictions.

Production systems require independent hash seeds per function. Use SipHash with different keys, or split a single 64-bit hash into high and low halves. Never reuse the same algorithm with the same seed.

Real-world failure: A payment backend used SHA-256 with index and index+1 as 'different' functions. Load factor 0.3 triggered infinite rehash loops. Independence means statistical zero correlation — not just different constants.

// io.thecodeforge — dsa tutorial

import java.util.zip.CRC32;

public class HashIndependence {
    // Wrong: CRC32(x) and CRC32(x+1) are correlated
    // Right: use independent seeds
    static int hash1(String key, int tableSize) {
        CRC32 crc = new CRC32();
        crc.update(key.getBytes());
        return (int)(crc.getValue() % tableSize);
    }

    static int hash2(String key, int tableSize) {
        // Flip bits, stop correlation
        CRC32 crc = new CRC32();
        crc.update(("SALT_" + key).getBytes());
        return (int)(crc.getValue() % tableSize);
    }

    public static void main(String[] args) {
        for (String k : new String[]{"a","b","c"}) {
            System.out.println(k + " -> h1:" + hash1(k,10) + " h2:" + hash2(k,10));
        }
    }
}

Load Factor 0.5 Is Not a Suggestion — It's a Law

Cuckoo hashing breaks hard above 50% load factor. Unlike open addressing or chaining where performance degrades gracefully, cuckoo hashing hits a cliff. At 0.51, insertion probability of requiring a rehash jumps from 5% to 95%.

This isn't a tuning parameter. It's a mathematical bound from the bipartite graph matching model behind the data structure. Your hash table has two buckets per key. Fill one more item than buckets available, and the eviction chain becomes a random walk with no guaranteed termination.

Production rule: Trigger rehash at 0.45 load factor. Account for the 5% headroom during peak writes. Monitoring load factor is not optional — it is the primary health metric for any cuckoo implementation.

// io.thecodeforge — dsa tutorial

public class LoadFactorCheck {
    private int capacity;
    private int size;

    public LoadFactorCheck(int cap) {
        this.capacity = cap;
        this.size = 0;
    }

    public boolean insert(String key) {
        if ((double)(size + 1) / capacity > 0.45) {
            System.out.println("REHASH triggered at load " 
                + String.format("%.2f", (double)size/capacity));
            rehash();
        }
        size++;
        return true;
    }

    private void rehash() {
        capacity *= 2;
        size = 0;
        System.out.println("New capacity: " + capacity);
    }

    public static void main(String[] args) {
        LoadFactorCheck t = new LoadFactorCheck(10);
        for (int i = 0; i < 6; i++) {
            t.insert("k"+i);
        }
        System.out.println("Load: " + String.format("%.2f", (double)5/10));
    }
}

Cycle Detection: Your Eviction Loop Needs an Escape Hatch

Infinite loops in cuckoo hashing aren't bugs — they're features of the data distribution. When both of a key's target slots are occupied by keys that also can't move, the system deadlocks. Without detection, your insert hangs forever.

The fix: set a maximum eviction chain length. A common threshold is 2 * table size. If a single insert triggers more evictions than that, abort and rehash. This bounds worst-case insertion to O(n), but average case stays O(1).

Do not rely on hash functions to 'never' produce cycles. They will. Every production cuckoo implementation I've seen that skipped cycle detection hit it within the first million inserts. The counter is free. The debugging session without it costs hours.

// io.thecodeforge — dsa tutorial

public class CycleDetection {
    private static final int MAX_EVICTIONS = 10;
    private String[] table1;
    private String[] table2;

    public CycleDetection(int size) {
        table1 = new String[size];
        table2 = new String[size];
    }

    public boolean insert(String key) {
        for (int i = 0; i < MAX_EVICTIONS; i++) {
            int idx1 = Math.abs(key.hashCode() % table1.length);
            if (table1[idx1] == null) {
                table1[idx1] = key;
                return true;
            }
            // Evict and swap tables
            String temp = table1[idx1];
            table1[idx1] = key;
            key = temp;

            int idx2 = Math.abs(key.hashCode() * 31 % table2.length);
            if (table2[idx2] == null) {
                table2[idx2] = key;
                return true;
            }
            temp = table2[idx2];
            table2[idx2] = key;
            key = temp;
        }
        System.out.println("CYCLE DETECTED — forcing rehash");
        return false;
    }

    public static void main(String[] args) {
        CycleDetection cd = new CycleDetection(3);
        cd.insert("a"); cd.insert("b"); cd.insert("c");
        System.out.println(cd.insert("d")); // triggers cycle
    }
}

3.1. Formal Description: Why Two Tables Beat One

Cuckoo hashing guarantees O(1) worst-case lookup by enforcing exactly one candidate location per key. Each key has exactly two possible cells: one in table T1 via hash function h1, and one in table T2 via h2. The formal invariant: every stored key occupies exactly one of its two assigned positions. Insertion follows a deterministic eviction chain — if the target slot is occupied, the current occupant is displaced to its alternate table, continuing until a vacancy is found or a cycle is detected. This is not a heuristic; it's a total ordering constraint. The cycle detection threshold is typically set to a constant multiple of table size. Once reached, the tables are rehashed with new hash functions. The formal model proves that as long as the load factor stays below 0.5, the expected insertion cost remains constant. This mathematical guarantee eliminates the amortized-cost surprises inherent in chaining or linear probing.

// io.thecodeforge — dsa tutorial
public class CuckooInsert<K, V> {
  private K[] t1, t2;
  private int size;

  public boolean insert(K key) {
    int pos1 = h1(key);
    if (t1[pos1] == null) { t1[pos1] = key; return true; }
    int pos2 = h2(key);
    if (t2[pos2] == null) { t2[pos2] = key; return true; }
    K cur = key;
    for (int i = 0; i < size * 4; i++) {
      K tmp = t1[pos1];
      t1[pos1] = cur;
      cur = tmp;
      pos2 = h2(cur);
      tmp = t2[pos2];
      t2[pos2] = cur;
      cur = tmp;
      pos1 = h1(cur);
    }
    return false; // trigger rehash
  }
}

4.1. Formal Setup: Tables, Hashes, and the Eviction Contract

// io.thecodeforge — dsa tutorial
public class CuckooSetup<K> {
  private K[] t1, t2;
  private final int n;
  private final HashFamily<K> h;

  @SuppressWarnings("unchecked")
  public CuckooSetup(int capacity) {
    n = capacity;
    t1 = (K[]) new Object[n];
    t2 = (K[]) new Object[n];
    h = new TabulationHash<>();
  }

  public boolean lookup(K key) {
    return t1[h.h1(key)] == key || t2[h.h2(key)] == key;
  }
}

Introduction

Cuckoo Hashing is a collision resolution scheme for hash tables that guarantees O(1) worst-case lookup and deletion time, unlike chaining or open addressing which degrade to linear in high-load scenarios. It achieves this by using two independent hash functions and two tables, or a single table with two candidate positions. When a new key collides, it evicts the occupant, which then rehashes to its alternate location — possibly displacing another. This process cascades until a free slot is found or a cycle is detected. Named after the cuckoo bird's nesting behavior, the algorithm trades amortized insertion complexity for deterministic retrieval performance. Why does this matter? In production systems where latency spikes are unacceptable — such as packet routing tables, CPU caches, or real-time databases — constant-time lookups are non-negotiable. However, the simplicity ends with the concept. The implementation demands careful hash function independence, strict load factor limits (typically ≤ 0.5), and robust cycle detection. This article dissects those mechanical truths without sugarcoating the engineering realities.

// io.thecodeforge — dsa tutorial
// Stub: conceptual structure only
// Introduction to Cuckoo Hashing mechanics
public class CuckooHashIntro<K, V> {
    private K[] keys1, keys2;
    private V[] vals1, vals2;
    private int capacity;
    private int size;

    public CuckooHashIntro(int cap) {
        this.capacity = cap;
        this.keys1 = (K[]) new Object[cap];
        this.keys2 = (K[]) new Object[cap];
        this.vals1 = (V[]) new Object[cap];
        this.vals2 = (V[]) new Object[cap];
    }

    public V get(K key) {
        int i = hash1(key, capacity);
        if (key.equals(keys1[i])) return vals1[i];
        int j = hash2(key, capacity);
        if (key.equals(keys2[j])) return vals2[j];
        return null;
    }
}

4.2. Workflow

The workflow of cuckoo hashing is a disciplined procedure designed to maintain constant-time access. Insertion begins by computing the first hash function h1(key) to get a candidate slot in table T1. If that slot is empty, the key is placed immediately — done. If occupied, the existing entry is evicted: the new key takes its place, and the evicted key is rehashed using h2. That displaced key then targets a slot in T2. Again, if free, it stops; if occupied, eviction cascades back to T1, alternating tables each round. This continues until either an empty slot is found or a cycle is detected — when the same key is evicted twice in the same insertion attempt. Cycle detection is critical: a naive loop could run forever. The standard threshold is a maximum number of displacements (often log2(capacity) or fixed like 100). If exceeded, the table is rehashed with new hash functions and grown. Lookups are straightforward: check T1[h1(key)], then T2[h2(key)], or return null. Deletion is simply clearing the slot — no tombstones needed because probing never occurs. This workflow guarantees O(1) worst-case search with amortized O(1) insertion, provided hash functions are independent and load factor stays ≤ 0.5.

// io.thecodeforge — dsa tutorial
// Insert workflow with eviction and cycle detection
public class CuckooWorkflow<K, V> {
    private static final int MAX_DISPLACEMENTS = 100;

    public boolean insert(K key, V value) {
        for (int i = 0; i < MAX_DISPLACEMENTS; i++) {
            int h1 = hash1(key);
            if (keys1[h1] == null) { keys1[h1] = key; vals1[h1] = value; return true; }
            K evicted = keys1[h1]; V evictedVal = vals1[h1];
            keys1[h1] = key; vals1[h1] = value;
            int h2 = hash2(evicted);
            if (keys2[h2] == null) { keys2[h2] = evicted; vals2[h2] = evictedVal; return true; }
            key = keys2[h2]; value = vals2[h2];
            keys2[h2] = evicted; vals2[h2] = evictedVal;
        }
        rehashTable();
        return insert(key, value);
    }
}