On the optimal time/space tradeoff for hash tables

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(log log n) bits of space per key when compared to the information-theoretic optimum. Even prior to this bound being achieved, the target of O(log log 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(log log 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

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.

Our results hold not just for fixed-capacity hash tables, but also for hash tables that are dynamically resized (this is a fundamental departure from what is possible for filters); and for hash tables that store very large keys/values, each of which can be up to n o(1) bits (this breaks with the conventional wisdom that larger keys/values should lead to more wasted bits per key). For very small keys/values, we are able to tighten our bounds to o(1) wasted bits per key, even when k = O(1). 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.