# On the Optimal Time/Space Tradeoff for Hash Tables

arXiv: https://arxiv.org/abs/2111.00602 · HTML: https://mlsanity.com/paper/2111.00602/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2021.

## Built on by (most cited first, 2 of 2)

- [LSHBloom: Memory-efficient, Extreme-scale Document Deduplication](https://mlsanity.com/paper/2411.04257/) (2024)
- [Daisy Bloom Filters](https://mlsanity.com/paper/2205.14894/) (2022)

## Abstract (arXiv)

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 Theta(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. Even prior to this bound being achieved, the target of O(loglog n) wasted bits per key was known to be a natural end goal, and was 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 O(log(k) n) wasted bits per key (all with high probability in n). This means that, each time we increase insertion/deletion time by an additive constant, we reduce the wasted bits per key exponentially. 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.