arXiv preprint ·
Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $Ω(\varepsilon^{-1})$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Beyond 3SUM-Hardness for Geometric Problems
Approximation algorithms for identical parallel machine scheduling with assignment costs
The Exact Robustness of Smith's Rule with Predicted Processing Times
A Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions
Exact Algorithms and Complexity of the Smallest Grammar Problem
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.