Tight Bounds for Classical Open Addressing
Preprint
Abstract
We introduce a classical open-addressed hash table, called rainbow hashing, that supports a load factor of up to $1 - \varepsilon$, while also supporting $O(1)$ expected-time queries, and $O(\log \log \varepsilon^{-1})$ expected-time insertions and deletions. We further prove that this tradeoff curve is optimal: any classical open-addressed hash table that supports load factor $1 - \varepsilon$ must incur $Ω(\log \log \varepsilon^{-1})$ expected time per operation. Finally, we extend rainbow hashing to the setting where the hash table is dynamically resized over time. Surprisingly, the addition of dynamic resizing does not come at any time cost -- even while maintaining a load factor of $\ge 1 - \varepsilon$ at all times, we can support $O(1)$ queries and $O(\log \log \varepsilon^{-1})$ updates. Prior to our work, achieving any time bounds of the form $o(\varepsilon^{-1})$ for all of insertions, deletions, and queries simultaneously remained an open question.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Dynamic Dictionaries for Multisets and Counting Filters with Constant Time OperationsAlgorithmica, 2022
- Balanced allocation through random walkInformation Processing Letters, 2018
- The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory ModelSIAM Journal on Computing, 2013
- Balanced allocation and dictionaries with tightly packed constant size binsTheoretical Computer Science, 2007
- Space Efficient Hash Tables with Worst Case Constant Access TimeTheory of Computing Systems, 2004
- Implicit $O(1)$ Probe SearchSIAM Journal on Computing, 1993
- There is no fast single hashing algorithmInformation Processing Letters, 1978
- The analysis of double hashingJournal of Computer and System Sciences, 1978
- A Note on the Efficiency of Hashing FunctionsJournal of the ACM, 1972
- The quadratic hash method when the table size is a power of 2The Computer Journal, 1972