STOC Conference 2022 Conference Paper
On the optimal time/space tradeoff for hash tables
- Michael A. Bender
- Martín Farach-Colton
- John Kuszmaul
- William Kuszmaul
- Mingmou Liu
For nearly six decades, the central open question in the study of hash tables has been to determine the optimal achievable tradeoff curve between time and space. State-of-the-art hash tables offer the following guarantee: If keys/values are Θ(log n ) bits each, then it is possible to achieve constant-time insertions/deletions/queries while wasting only O (loglog n ) bits of space per key when compared to the information-theoretic optimum—this bound has been proven to be optimal for a number of closely related problems (e.g., stable hashing, dynamic retrieval, and dynamically-resized filters). This paper shows that O (loglog n ) wasted bits per key is not the end of the line for hashing. In fact, for any k ∈ [log * n ], it is possible to achieve O ( k )-time insertions/deletions, O (1)-time queries, and the k -th iterated logarithm O (log ( k ) n ) wasted bits per key (all with high probability in n ), while also supporting dynamic resizing as the size of the table changes. We further show that this tradeoff curve is the best achievable by any of a large class of hash tables, including any hash table designed using the current framework for making constant-time hash tables succinct. Our result holds for arbitrarily large keys/values, and in the case where keys/values are very small, we can tighten our bounds to o (1) wasted bits per key. Building on this, we obtain a constant-time dynamic filter that uses n ⌈logє −1 ⌉+ n log e + o ( n ) bits of space for a wide choice of false-positive rates є, resolving a long-standing open problem for the design of dynamic filters.