Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing

1 Introduction

• O(log ε^-1) worst-case updates improve on the prior O(ε^-1) expected bound, which had been conjectured near-optimal up to polylogarithmic factors [BKZ24].The conjecture stated that worst-case query time times expected update time must be Ω(ε^-1) for open-addressed tables [BKZ24].Source: §1 · pp. 1–2
• For n^-1/4 ≤ ε ≤ 1/2, all operations take worst-case O(log ε^-1) time with high probability using (1+ε)n slots, for oblivious polynomial-length update sequences.The theorem also uses O(log n) machine words of metadata and guarantees every operation succeeds.Source: §1 · p. 2
• When ε = n^-Θ(1), each key hashes to two Θ(log n)-sized bins, while conditioning on h1(x) leaves only O(1) choices for h2(x).This contrasts with traditional bucketized cuckoo hashing, whose bins are independent or close to independent.Source: §1 · p. 2
• The braided relationships among bins preserve a power-of-two-choice phenomenon despite h2 adding barely any entropy over h1.This global structure is the paper’s main technical insight.Source: §1 · pp. 2–3
• Pullback chains move elements from other bins into free slots, concentrating most free slots in a small bottom layer that insertions can target.Braiding limits the possible source bins for a vacancy to O(1), making these deletion-driven chains possible.Source: §1 · p. 2
• Static placement analysis uses sub-Gaussian properties of the braided balls-and-bins process, while the basic construction is history independent to avoid problematic dependencies.History independence means the table state depends only on the current element set, not the insertion/deletion history.Source: §1 · pp. 2–3
• For larger ε, a backyard secondary table absorbs elements with no other placement option when certain failure events occur.The backyard provides backup placement options beyond the simplest ε = n^-Θ(1) regime.Source: §1 · p. 3
• A one-way communication argument gives an Ω((log ε^-1)/log log ε^-1) expected update-time lower bound for open-addressed tables with O(log ε^-1)-time queries.This leaves the upper bound tight up to an O(log log ε^-1) factor.Source: §1 · p. 3

2 Preliminaries

• An open-addressed query visits a predetermined sequence h1(x),...,hd(x) of positions in an array; n is the maximum live-key count and m the slot count.The constructions target m = (1 + O(ε))n.Source: §2 · p. 4
• High probability in n means probability at least 1 − O(1/n^γ) for any constant γ > 0, given sufficiently large constant algorithm parameters..Source: §2 · p. 4
• The analysis assumes fully random hash functions and uses Chernoff bounds and McDiarmid’s inequality for independent inputs and bounded differences.The paper notes explicit hash-function implementations as a straightforward alternative using n^Ω(1)-independence and the splitting trick.Source: §2 · p. 4

3 Paper Outline

• Sections 4–6 construct Θ(log n)-time queries, insertions, and deletions under the High-Load and Divisibility Assumptions.The high-load regime is ε = Θ(n^-0.25).Source: §3 · pp. 4–5
• Sections 7–9 remove the divisibility assumption, extend to ε ≥ Ω(n^-1/4), then deamortize updates to worst-case O(log ε^-1) time.Before deamortization, updates are amortized O(log ε^-1) and queries are worst-case O(log ε^-1).Source: §3 · p. 5
• The technically involved static-placement proof is deferred largely to Section 11.Source: §3 · p. 5
• Any open-addressed table with worst-case O(log ε^-1)-time queries requires expected updates of Ω((log ε^-1)/log log ε^-1); whether the log log factor belongs in either bound remains open..Source: §3 · p. 5

4.1 The Divisibility Assumption

• The Divisibility Assumption makes layer sizes exact powers of two; Section 7 later removes it.Source: §4.1 · p. 6

4 The Basic Hash-Table Layout

• The table has layers of power-of-two bin counts, with B = ⌈c log n⌉ slots per bin; ℓ counts layers and the smallest layer has 2K bins.Source: §4 · p. 5, §4.2 · p. 6

4.2 Braided Cuckoo Hashing

• m = n + Θ(n^3/4) slots, giving ε = Θ(n^-0.25) in this construction.The final layer serves as slack: with n elements, earlier layers are full and the final layer is half full with high probability.Source: §4.2 · pp. 6–7
• Conditioned on h1 selecting a bin in layer Li, h2 selects one of three bins in Li+1 by deleting the final address bit and changing a specified bit-pair.The first hash selects a layer and then a uniformly random bin within it.Source: §4.2 · pp. 7–8
• The braided graph has O(n/B) possible hash-pair edges and maximum node degree nine, a sparsity the authors identify as critical for efficient updates.Edges connect legal first- and second-choice bins in adjacent layers.Source: §4.2 · p. 8

5 Static Placement

• Each phase fills available slots in a layer using h1 choices, then forwards overflow to h2 choices without conditioning on those second hashes.Conditioned on forwarding, second hashes remain independent and uniform over three allowed destinations.Source: §5 · p. 9
• With high probability, static placement forwards no element into a full bin, and after placing n elements all remaining free slots are in the final layer.The theorem assumes the construction constant c is sufficiently large.Source: §5 · p. 9
• For n′ ≤ n keys in a table built for n, with high probability every forwarded element is placed, each final-layer bin has a free slot, and each other bin is free or receives Θ(B) forwarded elements from each predecessor.The per-bin forwarded load is at most 3B.Source: §5 · p. 10
• The proof controls per-bin overflow variance: inherited variance is damped between layers, while newly introduced variance is O(B).The analysis uses the braided predecessor structure to treat the six predecessor overflows as independent for the load calculation.Source: §5 · pp. 10–11
• Because B is a large multiple of log n, poor overflow behavior has probability 1/poly(n) per bin, permitting a union bound over all bins.Overflow is concentrated around its intended mean B/4.Source: §5 · pp. 10–11

6 Dynamic Placement

• History independence prevents reappearance dependencies that could bias evictions and overload bins, keeping the dynamic table analyzable using the Static Placement Theorem.The section considers both strong and weak history-independence guarantees for its constructions.Source: §6 · p. 12
• Insertions use forward eviction chains and deletions use pullback chains, each of length at most ℓ = O(log n).An insertion forwards an evicted key from a full first-choice bin; a deletion pulls an overflowed key back to fill the resulting hole.Source: §6 · pp. 12–13

6.1 An O(log2 n)-time Strongly History-Independent Warmup

• The strongly history-independent warmup uses m = n + O(n^0.75) slots, supports queries in O(log n), and completes insertions and deletions in O(log^2 n) time without failure with high probability.A priority hash function canonically selects overflow keys, making the state depend only on the current key set and fixed hash functions.Source: §6.1 · pp. 13, 15

6.2 An O(log n)-time Solution via Weak History Independence

• Weak history independence enables O(log n)-time operations: rejection-sampling trials succeed with probability Ω(1), giving expected O(1) time per chain step and high-probability O(log n) total time.Uniformly random overflow subsets preserve the Uniform Overflow Invariant, which allows analysis through the Static Placement Theorem.Source: §6.2 · p. 16
• Insertions use forward eviction chains, while deletions use pullback chains that stop after deletion from a nonfull bin or pull back a uniformly random overflowed key to fill a hole.After the first insertion step, the forwarded key is replaced by a uniformly sampled resident first-choice key; pullback begins only when the deleted-from bin has overflowed keys.Source: §6.2 · pp. 18–20
• The algorithm preserves the Uniform Overflow Invariant: each bin’s overflowed keys form a uniformly random subset of its first-choice keys, and keys occupy a uniformly random order in a prefix of the bin.The prefix-order invariant is not needed for correctness or running time, but is required for weak history independence.Source: §6.2 · pp. 19–20
• With the stated divisibility and sequence assumptions, the algorithm uses m = n + O(n^0.75) slots and supports each insertion or deletion in O(log n) time with high probability, and queries in O(log n) worst-case time.The sequence is oblivious, has T = n^O(1) operations, never exceeds n live keys, and uses a sufficiently large constant c as a function of log_n T; the sequence succeeds without failure with high probability in n.Source: §6.2 · p. 20
• With high probability, every bin receives at most 3B/4 keys forwarded from the previous layer, and a bin without a free slot has at least ηB keys from each predecessor, preventing operation failure.These conditions hold before and after every operation with high probability across the polynomial-length sequence.Source: §6.2 · pp. 20–21
• Each nonfinal sampling trial succeeds with probability Ω(1), so chains of length at most ℓ take O(log n) sampling time with high probability; the final pullback scan costs O(B) = O(log n).The final scan occurs only when every successor is nonfull, making it the last pullback step.Source: §6.2 · p. 21

7 Removing the Divisibility Assumption

• The Divisibility Assumption lets each layer have an exactly power-of-two number of bins, and the block reduction removes that assumption from the preceding results.The assumption concerns the number n being expressible in the specified form.Source: §7 · pp. 21–22
• For load factors at most 1 − Ω(n^-1/5), arbitrary capacities can be divided into blocks that satisfy the arithmetic assumptions.Each block is treated as a separate hash table after keys are hashed to blocks and a Chernoff bound controls their key counts.Source: §7 · pp. 21–22
• For sufficiently large n, arbitrary capacities admit the same guarantees as Theorem 6.2 or Theorem 6.1 using m = n + O(n^0.8) slots.The theorem gives α = 1/5 in m = n + O(n^(1−α)).Source: §7 · p. 22

8 Supporting Arbitrary Load Factors

• With probability at least 1 −1/poly(n), operations succeed; queries take worst-case O(log ε−1) time, while insertions and deletions take expected amortized O(log ε−1) time.The table uses n + O(εn) slots and supports oblivious polynomial-length update sequences with at most n live keys.Source: §8 · p. 22
• A direct reduction to bins of size Θ(log ε−1) fails with substantial probability because many compatible bin pairs can be overloaded.A fixed pair has Θ(B) expected keys and overload probability ε^Θ(1), with Θ(n/B) possible pairs.Source: §8 · p. 22

8.1 Data Structure Description

• The frontyard assigns keys to independent mini-structures; operations that fail or exceed the time threshold are completed in a backyard, and periodic rebuilds clear it.The frontyard uses copies of the earlier construction, and rebuilds occur every n updates.Source: §8 · pp. 22–23, §8.1 · pp. 23–24

8.2 Bounding the Number of “Bad” Mini-Structures

• With high probability, at most 4n/N^3 mini-structures are bad during an epoch, and every key sent to the backyard belongs to a bad mini-structure.Badness includes excessive traffic, excess assigned live keys, or a local insertion or deletion timeout.Source: §8.2 · pp. 24–26

8.3 Bounding the Number of Backyard Keys

• With high probability, the backyard contains at most O(n/N^2) keys at any time.This bound follows by bounding the keys assigned to the bad mini-structures.Source: §8.3 · p. 27

8.4 Proof of Theorem 8.1

• Queries take worst-case O(log ε−1) time, and insertions and deletions take expected amortized O(log ε−1) time.Frontyard work per non-rebuild update is capped at O(log ε−1); rebuilds every n updates add O(log ε−1) amortized time per update.Source: §8.4 · p. 27
• With high probability, the backyard stays below εn/3 keys, so the deamortized cuckoo-hashing backyard succeeds throughout the polynomial-length update sequence.The section’s stated success guarantee follows because the overall structure can fail only if the backyard fails.Source: §8.1 · p. 23, §8.4 · p. 27

9 Deamortizing the Rebuilds

• With high probability in n, every operation succeeds and queries, insertions, and deletions each take worst-case O(log ε−1) time.The guarantee applies to oblivious polynomial-length update sequences with at most n live keys and ε ≥ n^-1/4.Source: §9 · p. 28
• Rebuilds use a mirror workspace to reconstruct affected mini-structures in place while preserving correct queries.A second backyard receives elements that fail during a rebuild; these additions use O(εn) slots.Source: §9 · p. 28
• Strongly history-independent insertions keep a rebuilt mini-structure within worst-case O(log^2 ε−1) time per operation despite the insertion order.If no failure occurs, rebuilding a mini-structure takes O(N log^2 ε−1) time and restores its Uniform Overflow Invariant.Source: §9 · p. 29
• The construction divides the structure into chunks of size Θ(n^1/3) and schedules one rebuild every Θ(n^1/3) global operations, so each chunk is rebuilt every O(n) operations.The rebuild is budgeted O(log N) time per operation and must finish within its scheduled window.Source: §9 · p. 29
• The many backyard dictionaries collectively use O(log n) machine words of metadata, including their stash elements.The total number of stash elements is O(log n) with high probability in n.Source: §9 · p. 30
• With high probability, a chunk has at most O(R/N^2) backyard keys, enough for its rebuild to finish within the scheduled O(R) window.The analysis bounds bad mini-structures using heavy and light hitters, and separately bounds data-race-bad mini-structures by O(1).Source: §9 · pp. 30–31

10 A Lower Bound on Insertion/Deletion Time

• For tables with O(log ε−1) worst-case query time, the expected average number of moved keys per update is ˜Ω(log ε−1) in the analyzed delete-and-reinsert sequence.The sequence deletes r = 10εm uniformly random stored keys and inserts r new keys.Source: §10 · pp. 31–32
• A one-way communication argument encodes displacement paths so a decoder can recover members of the deletion set.The transcript records each path step using the final cell’s index within that key’s probe set and a stop bit.Source: §10 · pp. 32–33
• The paths are disjoint and end at initially empty cells or cells of deleted keys, linking path lengths to the number of moves.The entropy comparison yields a lower bound on expected moves, which is then divided across the updates.Source: §10 · pp. 33, 35

11.1 Properties of Sub-Gaussian Random Variables

• Poisson coupling, clipping, and binomial thinning provide key sub-Gaussian tools; thinning yields a smaller variance when the original variance is sufficiently large.The Poisson coupling agrees with the Poisson variable with probability at least 1 − e^(-cµ).Source: §11.1 · pp. 36–37

11.2 Proof of the Static Placement Theorem

• With sufficiently large construction constant c, the Static Placement Theorem holds with high probability: no forwarded element reaches a full bin, and after placement only final-layer slots remain free.The theorem states that these events hold simultaneously.Source: §11.2 · p. 37
• The proxy analysis couples primary arrivals to integer-valued sub-Gaussian variables and clips each non-final bin’s proxy overflow to at most B.The proxy process is introduced to simplify analysis; the passage says the proof will later show when it matches the true process.Source: §11.2 · pp. 38–39
• Each bin has six predecessor bins whose proxy overflows are mutually independent, and each predecessor forwards to it according to a conditionally independent Bin(bVq′,1/3) count.The six predecessors’ forwarding counts are independent over predecessors.Source: §11.2 · p. 39
• In the proxy process, every non-final bin’s overflow is sub-Gaussian with variance O(B), established through a layer-by-layer variance invariant.The proof combines independent predecessor overflows, binomial thinning, and clipping.Source: §11.2 · pp. 40–41
• The proxy mean analysis defines a layer recurrence with ∆1 = τ and ∆i = 2∆i−1 + τ for i ≥ 2.The stated invariant applies to every non-final layer, though its bound is not visible in the supplied passage.Source: §11.2 · p. 42
• The Static Placement Theorem’s conclusions hold in the fixed-n model with failure probability 1/poly(n), by proving them in the Poissonized model and conditioning on N = n.In the Poissonized model, the conclusions hold with probability at least 1 − n^-D for any desired constant D when B = c log n and c is sufficiently large.Source: §11.2 · pp. 43, 45

11.3 Analyzing n′ < n Keys

• For any fixed n′ ≤ n, with high probability every forwarded element is placed successfully, each later-layer bin receives at most 3B/4 forwarded elements, and every final-layer bin has a free slot.The first two conclusions follow by monotonicity under deleting keys from an n-key instance satisfying the Static Placement Theorem.Source: §11.3 · pp. 45–46
• For bins in layers 2 through ℓ, the proof establishes the additional structural condition using H_q′,q ≥ 2B/100 for every predecessor q′ of a full bin q.The proof transfers the Poissonized result to the fixed-n′ model while retaining polynomially small failure probability.Source: §11.3 · pp. 45, 47, 48

• O(log ε^-1) worst-case insertions and deletions remove the previous O(ε^-1) expected-time cost while preserving worst-case O(log ε^-1) queries.Source: §12 · p. 48
• The open probe-count question is whether O(log ε^-1) insertion/deletion time can coexist with (1 + o(1))lnε^-1 probes for every query.The cited d-ary cuckoo hashing scheme uses that probe count, which is optimal even among static hash tables [FP10, DGM+10].Source: §12 · p. 48
• Open extensions include dynamic resizing, O(1) expected query time, load factor exactly 1, and operation times that adapt as ε varies.A [BKZ24]-based route to O(1) expected queries would increase expected insertion time by O(log log log ε^-1) and could increase worst-case insertion time by much more; exact load 1 and adaptive times appear to require new techniques.Source: §12 · p. 48

• With α = 1/5, the construction retains Theorem 6.2's guarantees using m = n + O(n^4/5) slots.Source: A Proof of Theorem 7.1 · pp. 54–55
• The table uses Θ(n^1/5) blocks of capacity Θ(n^4/5), each with bin size Θ(log n), and each element interacts only with its randomly selected block.Source: A Proof of Theorem 7.1 · p. 54
• Each block has M = N + Θ(N^3/4) slots, and the per-block operation guarantees apply when its live-key count stays at or below capacity.Source: A Proof of Theorem 7.1 · p. 55
• A union-bound argument reduces the polynomial-length workload to bounding one fixed block at one time; concentration then ensures no block exceeds N live keys with high probability.Source: A Proof of Theorem 7.1 · p. 55

• Lemma 11.1 treats the relationship between sub-Gaussian tails and moment-generating-function bounds for a random variable Y with mean μ.Source: B Proof of Lemma 11.1 · p. 55
• The converse gives an absolute-constant sub-Gaussian bound from a tail condition and concludes that Y ∈ SG(μ,Cv).Source: B Proof of Lemma 11.1 · pp. 55–57
• For the forward direction, centering Y and applying Markov's inequality to both X and −X yields a two-sided tail bound.Source: B Proof of Lemma 11.1 · p. 56

C Proof of Lemma 11.5

• For any constant C > 0, a constant γ > 0 depending only on C is available under the stated condition v ≤ CB.Source: C Proof of Lemma 11.5 · p. 57
• The map ϕ is nondecreasing and 1-Lipschitz, so the proof applies the standard one-dimensional contraction principle.Source: C Proof of Lemma 11.5 · p. 57
• Both clipping thresholds, 0 and B, are at least B/5 from µ, allowing a sub-Gaussian tail bound.Source: C Proof of Lemma 11.5 · p. 58
• Clipping changes X only outside [0, B], and the proof bounds the resulting expectation change using tail integrals.The lower-tail bound uses the tail-integral formula; the upper tail is handled by the same calculation.Source: C Proof of Lemma 11.5 · p. 58

D Proof of Lemma 11.6

• For X ∼ Pois(µ), µ ≥ 1, there is a coupling G with mean µ, sub-Gaussian proxy Cµ, and agreement probability at least 1 − e^(−cµ).G may also be chosen integer-valued.Source: D Proof of Lemma 11.6 · p. 59
• The construction makes G agree with X on A and replaces it on A^c; this preserves the mean by setting the replacement value to m.The proof bounds the exceptional-event probability using a Poisson Chernoff bound and controls G−µ using Poisson tails and its bounded support.Source: D Proof of Lemma 11.6 · p. 59
• Replacing m on A^c with a two-point integer-valued variable preserves the mean and coupling probability, changing only constants in the sub-Gaussian proxy.Source: D Proof of Lemma 11.6 · p. 60

E Proof of Lemma 11.7

• For G bounded in [0, B] and sub-Gaussian with mean µ, the proof considers H | G ∼ Bin(G, 1/3) and combines conditional bounds.It conditions on G, applies Lemma 11.4, and then combines the resulting bounds.Source: E Proof of Lemma 11.7 · p. 60