Skip to content
Preprint

Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing

Oct 2026 · 0 citations
Computer Science

Abstract

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

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.