arXiv · Oct 23, 2026
Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing
By Andrew Krapivin, William Kuszmaul
In this paper, we introduce braided cuckoo hashing, an open-addressed hash table that supports load factor up to 1 - ε (for some parameter ε ∈ (0, 1)), while supporting queries, insertions, and deletions in worst-case time O(log ε⁻¹), with high probability. This result represents an exponential improvement on insertion/deletion time over previous constructions, and disproves a conjecture of Bender, Kuszmaul, and Zhou that the product of worst-case query time and expected insertion/deletion time must be Ω(ε⁻¹).