Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing

Abstract

In this paper, we introduce braided cuckoo hashing, an open-addressed hash table that supports load factor up to $1-\epsilon$ (for some parameter $\epsilon \in (0,1)$), while supporting queries, insertions, and deletions in worst-case time $O(\log {\epsilon }^{-1})$, 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 $\Omega ({\epsilon }^{-1})$.

arXiv comment60 pages, 1 figure, to appear in SODA 2027