Cuckoo Hashing

Why Cuckoo Hashing Matters

A lookup service needs to answer “is this identifier present?” with a predictable number of table probes. Separate chaining may traverse a long bucket, and linear probing may scan a long cluster. Basic Cuckoo Hashing gives every key exactly two candidate slots: a lookup checks those slots and stops.

The tradeoff appears during insertion. If a candidate slot is occupied, the new key can evict its resident, which moves to its other candidate slot. This displacement can continue through several keys. Sometimes no arrangement exists for the current hash functions, even though most of the table is empty. A robust implementation must bound the insertion walk, preserve every existing key, and rebuild using new hash functions or more capacity.

You will implement a set with lookup, insertion, duplicate detection, and deletion; trace both a successful eviction and an impossible placement; and verify that recovery never silently drops a key. The sample deliberately triggers a rebuild at low overall load, making the distinction between free space and usable candidate locations visible.

Core Concepts and Terminology

Use two arrays $T_0$ and $T_1$, each containing $m$ single-key slots. Two seeded hash functions map a key $x$ to indices $h_0(x)$ and $h_1(x)$ in $[0,m)$. The only legal locations for $x$ are

$$T_0[h_0(x)]\quad\text{and}\quad T_1[h_1(x)].$$

Index $0$ in the first table and index $0$ in the second table are different slots. Every stored key appears exactly once; empty slots have a separate occupancy representation. The implementations use a Python None, a C++ occupancy flag, and Java null, respectively, so the integer $0$ and negative integers remain valid keys.

Let $n$ be the number of distinct stored keys. Define load relative to all available slots:

$$\alpha=\frac{n}{2m}.$$

Thus $n=3$ and $m=4$ means load $3/8$, not $3/4$. The example uses a maximum post-insertion load of $2/5=0.4$. The familiar threshold near $1/2$ concerns the basic two-choice, one-key-per-slot model with suitable random hashing; it is not a guarantee for every particular key set and seed pair, nor the threshold of all bucketed or multi-choice variants.

The graph gives a useful explanation. Assigning a key to a slot means assigning its edge to one endpoint, with at most one assigned edge per vertex. A connected component with more edges than vertices cannot fit its keys. Conversely, in this two-choice model a tree or a component with exactly one cycle can be assigned successfully: trees can be peeled from their leaves, and a remaining cycle can be assigned consistently around the cycle.

Consequently, a legal placement exists exactly when every component has at most one cycle, counting parallel edges appropriately. Two keys sharing the same pair of candidates can occupy the two slots, forming a valid two-edge cycle. Three such keys need three slots but have only two candidates between them; they cannot fit. A cycle by itself is therefore not a sufficient reason to declare the table impossible.

How Cuckoo Hashing Works, Step by Step

Lookup and deletion. Compute both candidates. If either occupied slot contains the requested key, it is present. Deletion clears that slot and decrements the size; no probe chain needs preserving, so this basic scheme does not need tombstones. An absent-key deletion leaves the table unchanged.

Insertion without recovery. First check whether the key already exists. If so, return “not inserted” without changing size or drawing new hash seeds. If adding a new key would exceed the load ceiling, go directly to a larger rebuild. Otherwise start a displacement walk in $T_0$:

1. Compute the pending key's candidate in the current table.
2. Save the slot's old contents in a journal, then write the pending key there.
3. If the old slot was empty, the walk succeeds and insertion is complete.
4. Otherwise the old resident becomes the pending key; switch to the other table and repeat.

During a walk, all residents occupy legal slots, and the residents together with the pending key are exactly the original members plus the new key. Lookup on an externally visible committed state must wait until the walk finishes or is rolled back; the example is a single-threaded structure.

flowchart TD
    A["Insert key"] --> B{"Already present?"}
    B -->|Yes| C["Return false"]
    B -->|No| D{"New load at most 0.4?"}
    D -->|Yes| E["Bounded eviction walk; journal each write"]
    E --> F{"Reached an empty slot?"}
    F -->|Yes| G["Increase size; return true"]
    F -->|No| H["Undo writes in reverse; keep old table"]
    H --> I["Build trial tables with fresh seeds"]
    D -->|No| J["Choose doubled trial capacity"]
    J --> I
    I --> K{"All old keys and new key placed?"}
    K -->|Yes| L["Commit trial tables and seeds"]
    K -->|No| M{"More attempts and capacity available?"}
    M -->|Yes| I
    M -->|No| N["Report failure; preserve old members"]

Safe recovery. If the walk exhausts its budget, restore the journal in reverse order. Reversing matters because the same slot may have been overwritten more than once. Now scan the restored tables in a fixed order, collect all old members, and append the new key. Build separate trial tables with a fresh seed pair. Commit their arrays, seeds, capacity, and size only after every key has been placed.

The code allows at most $12$ trial builds, with up to four seed pairs at each trial capacity. It doubles the trial capacity after every four failed builds and stops before exceeding the configured maximum. A load-triggered rebuild starts at twice the current capacity; an eviction-budget rebuild starts at the current capacity. If no trial succeeds, the operation raises a reported rebuild failure and preserves the old members, layout, capacity, and active hash seeds. Diagnostic counters and the generator stream still record the attempted work.

The budget is a termination policy, not an exact graph feasibility test. A short budget can reject a walk that would eventually reach a free slot. More elaborate implementations can search for an augmenting displacement path, use a stash, or spread rebuild work across later operations.

Worked Example with a Full Trace

Start with $m=4$, generator seed $6$, and walk budget $K=16$. The first two generator outputs are salts $100842$ and $1694851494$. Under the code's specified integer mixer, keys $0$, $16$, and $20$ all have the initial candidate pair $(0,0)$: slot $0$ of each table.

Insert $0$: write it into empty $T_0[0]$. Insert $16$: write $16$ into $T_0[0]$, carry the evicted $0$ into empty $T_1[0]$, and stop. The committed size is now $2$, with $T_0[0]=16$ and $T_1[0]=0$. The first two insertions used $3$ placements and $1$ eviction in total.

Inserting $20$ is allowed by the global load test because $3/(2\cdot4)=3/8\le0.4$, but no arrangement exists with these seeds. The table below records every attempted write in its $16$-step walk. All other slots remain empty. “Pending next” is the resident just evicted, and the next table alternates.

After write $6$, the complete walk state repeats its starting state: both occupied slots and the pending key match. The code does not need explicit cycle detection; it stops after write $16$, restores all journaled slot versions in reverse order, and recovers exactly the prior set $\{0,16\}$. It then adds $20$ to the separate list of keys to rebuild. No displaced key is discarded.

The next two salts are $1145965850$ and $1614694654$. At the same capacity $m=4$, the candidates become:

All three trial placements reach empty first-table slots. Commit $T_0=[16,0,\mathrm{empty},20]$ and an empty $T_1$. Capacity did not grow; changing the candidate graph was sufficient.

The totals are $22$ placements: $3$ before the failed walk, $16$ in that walk, and $3$ in the successful rebuild. There are $17$ evictions: the initial eviction of $0$ plus all $16$ failed-walk writes. There is $1$ failed walk, $1$ trial rebuild, $0$ committed growth events, and $4$ hash-seed draws. Undo writes are not counted as new placement attempts.

Implementation in Python, C++, and Java

Each panel is a standalone, exact-membership integer set. add returns true only for a new member, false for a duplicate, and raises an exception if its bounded recovery cannot finish. contains performs at most two slot checks; remove returns whether a member was deleted. The code uses no auxiliary built-in set to hide a failed Cuckoo placement.

The shared generator updates $s\leftarrow16807s\bmod2147483647$. Its seed is an integer from $1$ through $2147483646$. Two consecutive outputs initialize a hash pair, and two more are consumed for each attempted rebuild. The generator is deterministic for replay; successive salts are not a proof of independent universal hashing.

To make the integer hash identical across languages, interpret the key as $32$ unsigned bits, XOR with the salt, then apply the same xor-shifts and multiplications. Both multiplications wrap modulo $2^{32}$. Python masks explicitly, C++ uses uint32_t, and Java uses defined wrapping int arithmetic and unsigned right shifts. The final unsigned value is reduced modulo the capacity. C++ and Java use $64$-bit arithmetic for generator multiplication and load checks.

The mixer is an educational deterministic hash family, not an analyzed independent universal family. Its output distribution and correlations do not establish the classic expected-time theorem. Lookup correctness, legal slot placement, rollback, and recovery behavior can still be checked directly for every operation.

Capacity is per table and must be at least $2$, no larger than the configured maximum, and at most $1048576$ in this bounded example. The default walk budget is $16$ writes. Public operations validate keys through the lookup path in Python; C++ and Java accept their signed integer type. Treat the lower-level walk and rebuild helpers as implementation internals, and do not call a walk to insert a duplicate directly.

class RNG:
    def __init__(self, seed):
        if not isinstance(seed, int) or not 1 <= seed < 2147483647:
            raise ValueError("invalid seed")
        self.state, self.draws = seed, 0

    def next(self):
        self.state = (16807 * self.state) % 2147483647
        self.draws += 1
        return self.state


def index(key, salt, capacity):
    z = (key & 0xffffffff) ^ salt
    z ^= z >> 16
    z = (z * 0x7feb352d) & 0xffffffff
    z ^= z >> 15
    z = (z * 0x846ca68b) & 0xffffffff
    z ^= z >> 16
    return z % capacity


class Stats:
    def __init__(self):
        self.placements = self.evictions = self.failed_walks = self.rebuilds = self.grows = 0


class CuckooSet:
    def __init__(self, capacity=4, seed=6, kick_limit=16, max_capacity=1048576):
        if not 2 <= capacity <= max_capacity <= 1048576 or kick_limit < 1:
            raise ValueError("invalid capacity or kick limit")
        self.rng = RNG(seed)
        self.salts = [self.rng.next(), self.rng.next()]
        self.m, self.size = capacity, 0
        self.kick_limit, self.max_capacity = kick_limit, max_capacity
        self.tables = [[None] * capacity for _ in range(2)]
        self.stats = Stats()

    def location(self, key):
        if not isinstance(key, int) or not -2147483648 <= key <= 2147483647:
            raise ValueError("key must be a signed 32-bit integer")
        for table in range(2):
            j = index(key, self.salts[table], self.m)
            if self.tables[table][j] == key:
                return table, j
        return None

    def contains(self, key):
        return self.location(key) is not None

    def remove(self, key):
        found = self.location(key)
        if found is None:
            return False
        table, j = found
        self.tables[table][j] = None
        self.size -= 1
        return True

    def walk(self, tables, salts, capacity, key):
        journal, table = [], 0
        for _ in range(self.kick_limit):
            j = index(key, salts[table], capacity)
            old = tables[table][j]
            journal.append((table, j, old))
            tables[table][j] = key
            self.stats.placements += 1
            if old is None:
                return True
            self.stats.evictions += 1
            key, table = old, 1 - table
        for table, j, old in reversed(journal):
            tables[table][j] = old
        self.stats.failed_walks += 1
        return False

    def rebuild(self, new_key, capacity):
        keys = [key for table in self.tables for key in table if key is not None]
        keys.append(new_key)
        for attempt in range(12):
            if attempt and attempt % 4 == 0:
                capacity *= 2
            if capacity > self.max_capacity:
                break
            trial = [[None] * capacity for _ in range(2)]
            salts = [self.rng.next(), self.rng.next()]
            self.stats.rebuilds += 1
            if all(self.walk(trial, salts, capacity, key) for key in keys):
                if capacity > self.m:
                    self.stats.grows += 1
                self.tables, self.salts, self.m, self.size = trial, salts, capacity, len(keys)
                return
        raise RuntimeError("rebuild limit reached; set unchanged")

    def add(self, key):
        if self.contains(key):
            return False
        if 5 * (self.size + 1) <= 4 * self.m:
            if self.walk(self.tables, self.salts, self.m, key):
                self.size += 1
                return True
            self.rebuild(key, self.m)
        else:
            self.rebuild(key, 2 * self.m)
        return True


def show(table):
    return "[" + ", ".join("_" if key is None else str(key) for key in table) + "]"


def main():
    s = CuckooSet()
    keys = [0, 16, 20]
    for key in keys:
        s.add(key)
    print("T0 = " + show(s.tables[0]))
    print("T1 = " + show(s.tables[1]))
    print(f"size={s.size}, capacity per table={s.m}")
    t = s.stats
    print(f"placements={t.placements}, evictions={t.evictions}, failed walks={t.failed_walks}, rebuilds={t.rebuilds}, grows={t.grows}")
    print(f"hash draws = {s.rng.draws}")
    duplicate = not s.add(keys[0])
    ok = all(s.contains(key) for key in keys) and not s.contains(999) and duplicate
    ok = s.remove(keys[1]) and not s.contains(keys[1]) and s.size == 2 and ok
    print("membership and deletion = " + ("PASS" if ok else "FAIL"))


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <utility>
#include <vector>

struct RNG {
    std::int64_t state, draws = 0;
    explicit RNG(std::int64_t seed) : state(seed) {
        if (seed < 1 || seed >= 2147483647) throw std::invalid_argument("invalid seed");
    }
    std::uint32_t next() {
        state = (16807 * state) % 2147483647; ++draws;
        return static_cast<std::uint32_t>(state);
    }
};
int index(int key, std::uint32_t salt, int capacity) {
    std::uint32_t z = static_cast<std::uint32_t>(key) ^ salt;
    z ^= z >> 16; z *= 0x7feb352dU;
    z ^= z >> 15; z *= 0x846ca68bU;
    z ^= z >> 16;
    return static_cast<int>(z % static_cast<std::uint32_t>(capacity));
}
struct Slot { bool used = false; int key = 0; };
using Tables = std::vector<std::vector<Slot>>;
struct Stats {
    std::int64_t placements = 0, evictions = 0, failed_walks = 0, rebuilds = 0, grows = 0;
};
struct Change { int table, j; Slot old; };

class CuckooSet {
public:
    RNG rng;
    std::vector<std::uint32_t> salts;
    int m, size = 0, kick_limit, max_capacity;
    Tables tables;
    Stats stats;
    explicit CuckooSet(int capacity = 4, std::int64_t seed = 6, int kicks = 16, int maximum = 1048576)
        : rng(seed), m(capacity), kick_limit(kicks), max_capacity(maximum) {
        if (capacity < 2 || capacity > maximum || maximum > 1048576 || kicks < 1)
            throw std::invalid_argument("invalid capacity or kick limit");
        salts = {rng.next(), rng.next()};
        tables = Tables(2, std::vector<Slot>(capacity));
    }
    std::pair<int, int> location(int key) const {
        for (int t = 0; t < 2; ++t) {
            int j = index(key, salts[t], m);
            if (tables[t][j].used && tables[t][j].key == key) return {t, j};
        }
        return {-1, -1};
    }
    bool contains(int key) const { return location(key).first != -1; }
    bool remove(int key) {
        auto found = location(key);
        if (found.first == -1) return false;
        tables[found.first][found.second].used = false; --size; return true;
    }
    bool walk(Tables& target, const std::vector<std::uint32_t>& hashes, int capacity, int key) {
        std::vector<Change> journal; int t = 0;
        for (int step = 0; step < kick_limit; ++step) {
            int j = index(key, hashes[t], capacity); Slot old = target[t][j];
            journal.push_back({t, j, old});
            target[t][j].used = true; target[t][j].key = key; ++stats.placements;
            if (!old.used) return true;
            ++stats.evictions; key = old.key; t = 1 - t;
        }
        for (auto it = journal.rbegin(); it != journal.rend(); ++it) target[it->table][it->j] = it->old;
        ++stats.failed_walks; return false;
    }
    void rebuild(int new_key, int capacity) {
        std::vector<int> keys;
        for (const auto& table : tables) for (const auto& slot : table) if (slot.used) keys.push_back(slot.key);
        keys.push_back(new_key);
        for (int attempt = 0; attempt < 12; ++attempt) {
            if (attempt && attempt % 4 == 0) capacity *= 2;
            if (capacity > max_capacity) break;
            Tables trial(2, std::vector<Slot>(capacity));
            std::vector<std::uint32_t> hashes = {rng.next(), rng.next()}; ++stats.rebuilds;
            bool ok = true;
            for (int key : keys) if (!walk(trial, hashes, capacity, key)) { ok = false; break; }
            if (ok) {
                if (capacity > m) ++stats.grows;
                tables = std::move(trial); salts = std::move(hashes); m = capacity;
                size = static_cast<int>(keys.size()); return;
            }
        }
        throw std::runtime_error("rebuild limit reached; set unchanged");
    }
    bool add(int key) {
        if (contains(key)) return false;
        if (5LL * (size + 1) <= 4LL * m) {
            if (walk(tables, salts, m, key)) { ++size; return true; }
            rebuild(key, m);
        } else rebuild(key, 2 * m);
        return true;
    }
};
void show(const std::vector<Slot>& table) {
    std::cout << '[';
    for (std::size_t i = 0; i < table.size(); ++i) {
        if (i) std::cout << ", ";
        if (table[i].used) std::cout << table[i].key; else std::cout << '_';
    }
    std::cout << "]\n";
}
int main() {
    CuckooSet s; std::vector<int> keys = {0, 16, 20};
    for (int key : keys) s.add(key);
    std::cout << "T0 = "; show(s.tables[0]); std::cout << "T1 = "; show(s.tables[1]);
    std::cout << "size=" << s.size << ", capacity per table=" << s.m << '\n';
    const Stats& t = s.stats;
    std::cout << "placements=" << t.placements << ", evictions=" << t.evictions
              << ", failed walks=" << t.failed_walks << ", rebuilds=" << t.rebuilds << ", grows=" << t.grows << '\n';
    std::cout << "hash draws = " << s.rng.draws << '\n';
    bool duplicate = !s.add(keys[0]), ok = !s.contains(999) && duplicate;
    for (int key : keys) ok = s.contains(key) && ok;
    ok = s.remove(keys[1]) && !s.contains(keys[1]) && s.size == 2 && ok;
    std::cout << "membership and deletion = " << (ok ? "PASS" : "FAIL") << '\n';
    return 0;
}

import java.util.ArrayList;

public class Main {
    static class RNG {
        long state, draws;
        RNG(long seed) {
            if (seed < 1 || seed >= 2147483647L) throw new IllegalArgumentException("invalid seed");
            state = seed;
        }
        int next() { state = (16807L * state) % 2147483647L; ++draws; return (int)state; }
    }
    static int index(int key, int salt, int capacity) {
        int z = key ^ salt;
        z ^= z >>> 16; z *= 0x7feb352d;
        z ^= z >>> 15; z *= 0x846ca68b;
        z ^= z >>> 16;
        return (int)(Integer.toUnsignedLong(z) % capacity);
    }
    static class Stats { long placements, evictions, failedWalks, rebuilds, grows; }
    static class Change {
        final int table, j; final Integer old;
        Change(int table, int j, Integer old) { this.table = table; this.j = j; this.old = old; }
    }
    static class CuckooSet {
        final RNG rng;
        int[] salts;
        int m, size, kickLimit, maxCapacity;
        Integer[][] tables;
        final Stats stats = new Stats();
        CuckooSet(int capacity, long seed, int kicks, int maximum) {
            if (capacity < 2 || capacity > maximum || maximum > 1048576 || kicks < 1)
                throw new IllegalArgumentException("invalid capacity or kick limit");
            rng = new RNG(seed); salts = new int[] {rng.next(), rng.next()};
            m = capacity; kickLimit = kicks; maxCapacity = maximum;
            tables = new Integer[2][capacity];
        }
        int[] location(int key) {
            for (int t = 0; t < 2; ++t) {
                int j = index(key, salts[t], m);
                if (tables[t][j] != null && tables[t][j] == key) return new int[] {t, j};
            }
            return null;
        }
        boolean contains(int key) { return location(key) != null; }
        boolean remove(int key) {
            int[] found = location(key);
            if (found == null) return false;
            tables[found[0]][found[1]] = null; --size; return true;
        }
        boolean walk(Integer[][] target, int[] hashes, int capacity, int key) {
            ArrayList<Change> journal = new ArrayList<>(); int t = 0;
            for (int step = 0; step < kickLimit; ++step) {
                int j = index(key, hashes[t], capacity); Integer old = target[t][j];
                journal.add(new Change(t, j, old));
                target[t][j] = key; ++stats.placements;
                if (old == null) return true;
                ++stats.evictions; key = old; t = 1 - t;
            }
            for (int i = journal.size() - 1; i >= 0; --i) {
                Change c = journal.get(i); target[c.table][c.j] = c.old;
            }
            ++stats.failedWalks; return false;
        }
        void rebuild(int newKey, int capacity) {
            ArrayList<Integer> keys = new ArrayList<>();
            for (Integer[] table : tables) for (Integer key : table) if (key != null) keys.add(key);
            keys.add(newKey);
            for (int attempt = 0; attempt < 12; ++attempt) {
                if (attempt != 0 && attempt % 4 == 0) capacity *= 2;
                if (capacity > maxCapacity) break;
                Integer[][] trial = new Integer[2][capacity];
                int[] hashes = {rng.next(), rng.next()}; ++stats.rebuilds;
                boolean ok = true;
                for (int key : keys) if (!walk(trial, hashes, capacity, key)) { ok = false; break; }
                if (ok) {
                    if (capacity > m) ++stats.grows;
                    tables = trial; salts = hashes; m = capacity; size = keys.size(); return;
                }
            }
            throw new IllegalStateException("rebuild limit reached; set unchanged");
        }
        boolean add(int key) {
            if (contains(key)) return false;
            if (5L * (size + 1) <= 4L * m) {
                if (walk(tables, salts, m, key)) { ++size; return true; }
                rebuild(key, m);
            } else rebuild(key, 2 * m);
            return true;
        }
    }
    static String show(Integer[] table) {
        StringBuilder out = new StringBuilder("[");
        for (int i = 0; i < table.length; ++i) {
            if (i != 0) out.append(", ");
            if (table[i] == null) out.append('_'); else out.append(table[i]);
        }
        return out.append(']').toString();
    }
    public static void main(String[] args) {
        CuckooSet s = new CuckooSet(4, 6, 16, 1048576); int[] keys = {0, 16, 20};
        for (int key : keys) s.add(key);
        System.out.println("T0 = " + show(s.tables[0])); System.out.println("T1 = " + show(s.tables[1]));
        System.out.println("size=" + s.size + ", capacity per table=" + s.m);
        Stats t = s.stats;
        System.out.println("placements=" + t.placements + ", evictions=" + t.evictions + ", failed walks="
            + t.failedWalks + ", rebuilds=" + t.rebuilds + ", grows=" + t.grows);
        System.out.println("hash draws = " + s.rng.draws);
        boolean duplicate = !s.add(keys[0]), ok = !s.contains(999) && duplicate;
        for (int key : keys) ok = s.contains(key) && ok;
        ok = s.remove(keys[1]) && !s.contains(keys[1]) && s.size == 2 && ok;
        System.out.println("membership and deletion = " + (ok ? "PASS" : "FAIL"));
    }
}

Run Python 3 directly, compile C++ with g++ -std=c++14 -O2 main.cpp -o cuckoo, or use Java 17 or later with javac Main.java followed by java Main. All three print exactly these six lines; _ denotes an empty slot, never a special integer key:

• T0 = [16, 0, _, 20]
• T1 = [_, _, _, _]
• size=3, capacity per table=4
• placements=22, evictions=17, failed walks=1, rebuilds=1, grows=0
• hash draws = 4
• membership and deletion = PASS

The first five describe the state before the final membership/deletion checks; deleting $16$ changes the live set afterward. The check verifies all inserted keys, an absent key, duplicate detection, and successful deletion. Rebuild attempts scan the old tables in table order and increasing slot order, append the new key last, and always start each insertion walk in $T_0$; these rules make exact arrangements and counters reproducible.

The statistics include attempted work later rolled back or discarded: placements counts target-slot writes, evictions counts writes replacing an occupied slot, failed_walks counts exhausted walk budgets, and rebuilds counts trial seed pairs actually attempted. grows counts successful commits with a larger capacity, not every abandoned size increase. The reported-failure preservation contract concerns budget and capacity failures; generator state and diagnostic counters intentionally advance while trying recovery.

Complexity, Correctness, and Invariants

For fixed-size integer keys and constant-cost hash evaluation, membership takes $O(1)$ time in the best, average, and worst case: at most two candidate slots are checked. Duplicate detection and deletion have the same bound. Initializing two tables costs $\Theta(m)$ time and storage. The resident table space is $\Theta(m)$; deletion does not shrink the arrays, so storage is not necessarily proportional to the current size after many deletions.

An insertion that reaches an empty slot immediately takes constant time. A walk has at most $K$ placement attempts, uses $O(K)$ journal space, and costs $O(K)$ including rollback if necessary. With the default fixed $K=16$, the unrecovered insertion path has a constant bound, but a rebuild can do much more work.

For the actual bounded implementation, let $R\le12$ be the number of trial builds and $M$ the largest trial capacity. Scanning the restored old tables costs $O(m)$; collecting the old members plus the new key takes $O(n)$ storage; each trial initializes $2M$ slots in the upper bound and attempts at most $n+1$ walks of length at most $K$. A recovery insertion therefore has upper bound

$$O\bigl(m+K+R(M+(n+1)K)\bigr)$$

time and $O(m+M+n+K)$ live space including the old committed tables, a current trial, the key list, and a walk journal. Earlier discarded trials may await garbage collection in managed runtimes; the bound describes logically live storage. An operation that exhausts its allowed recovery raises an error rather than claiming that insertion succeeded.

The classic theoretical result is different: with an appropriate random hash family, load bounded below the two-choice threshold, and a suitable displacement cutoff and resampling/growth policy, insertion has expected amortized $O(1)$ cost. This includes accounting for rare whole-table rehashes and geometric growth over a sequence. It does not give worst-case constant insertion, and it does not automatically apply to a small fixed generator, arbitrary hash mixer, or arbitrary fixed walk budget.

The correctness argument separates the committed state from an insertion walk. In a committed state, every member appears once in a legal slot. A successful lookup is therefore sound, and an unsuccessful check of both candidates proves absence. Removing a member cannot make another member unreachable because no other member's lookup depends on traversing the cleared slot.

During a displacement, the pending key is placed in its designated slot. If the slot was occupied, exactly one resident becomes pending, so no key is lost or duplicated in the combined table-plus-pending collection. If the old slot was empty, all old keys and the new key are resident exactly once, and the size can increase. If the walk stops without an empty slot, undoing every recorded version in reverse restores the prior resident collection and layout exactly.

Graph feasibility explains failures without assuming that every encountered loop is fatal. For a connected component with $v$ vertices, a tree has $v-1$ edges and one free slot after assignment; a unicyclic component has $v$ edges and can still fit exactly. A component with more than $v$ edges cannot assign every key to a different endpoint. The sample's three parallel edges have $v=2$ and $e=3$, so reordering alone cannot solve it. A placement budget can also expire in a feasible graph, so reported budget exhaustion is deliberately weaker than a mathematical impossibility certificate.

Variants, Pitfalls, and Optimizations

The most damaging implementation error is losing the pending key when a walk is abandoned. After the sample's sixteenth failed write, the resident slots contain $0$ and $20$, while $16$ is pending. Rebuilding only those resident keys would silently drop the previously stored member $16$. The code first restores the original table and then rebuilds from every old member plus the requested new key.

Several related choices affect performance and guarantees:

• Refresh the hash graph when retrying. Rebuilding the same keys at the same capacity with the same hashes cannot repair an impossible candidate graph. Resampling seeds changes edges; increasing capacity also changes the available index range. Commit capacity and seeds together with the successfully built arrays.
• Do not equate repetition with infeasibility. A feasible one-cycle component is allowed. A bounded walk is a practical trigger for recovery, not a complete cycle-counting algorithm. Searching for an augmenting path can find a placement without a blind long walk.
• Handle duplicates before displacement. A set stores one copy. Size increases only after a genuinely new key is committed, and a failed rebuild leaves the old size intact. A map version must move each key together with its associated value and define duplicate-key updates.
• Use explicit occupancy. Zero, negative values, and the minimum signed integer are valid sample-domain keys. A sentinel drawn from the same unrestricted key domain would make at least one key unrepresentable.
• Account for load in the correct denominator. The two arrays contain $2m$ slots, while the per-table key-to-slot ratio is $n/m$. Low global load reduces random failure probability but does not exclude a small overfull component.
• Consider buckets and stashes separately. Several cells per bucket, additional hash choices, or a small stash can improve utilization or reduce rebuild frequency. A stash must be included in every relevant lookup, deletion, size, and recovery rule. Those variants require their own analysis.
• Control latency and concurrency explicitly. Incremental rebuilding or de-amortized variants can spread expensive work across operations. Concurrent readers need synchronization or a relocation protocol; the single pending key during a walk makes the unsynchronized code unsuitable for concurrent access.

For variable-length strings, hashing and equality are not automatically constant-time in the number of characters. For adversarial inputs, a fixed public mixer and seed should not be treated as a randomized performance guarantee. Choose a hash family, seed policy, and retry strategy that match the required model, and keep membership correctness independent of performance optimism.

A Cuckoo filter is a different structure that stores fingerprints and may return false positives. The exact-key set here is not a probabilistic membership filter: a successful lookup compares the full integer key. Similarly, high load figures for a bucketed implementation should not be applied to this one-key-per-slot demonstration.

Practice Problems and Real-World Use

Test each public operation against an independent reference set. After every completed operation, scan all occupied slots: the number must equal the stored size, every key must be in a legal candidate slot, no key may appear twice, and the collection must match the reference. Include lookups for absent keys and repeated insertion/deletion of the same key.

Recovery needs targeted tests. Snapshot the prior arrays, active salts, capacity, and size; force a small walk budget or an exhausted capacity limit; then verify that a reported failure preserves that entire committed snapshot. Counters and generator state may advance as documented. Also test growth, repeated candidate pairs, negative and extreme integers, and same-seed replay of layouts and statistics.

For small candidate graphs, an independent bipartite matching solver can check whether a placement exists. This distinguishes graph infeasibility from a budget-limited insertion failure and verifies the tree/unicyclic explanation without relying on the implementation's own displacement logic.

For the theoretical foundation, see Pagh and Rodler's Cuckoo Hashing paper. Kirsch, Mitzenmacher, and Wieder's work on a stash discusses the candidate graph, rare insertion failures, and how extra overflow storage changes robustness. The runnable code emphasizes explicit invariants, reproducible integer arithmetic, and safe bounded recovery; its small deterministic hash generator is not a substitute for those papers' probabilistic assumptions.