A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits
William Kuszmaul · 2022
This paper considers the basic question of how strong of a probabilistic guarantee can a hash table, storing $n(1+\Theta(1))\log n$-bit key/value pairs, offer? Past work on this question has been bottlenecked by limitations of the known families of hash functions: The only hash tables to achieve failure probabilities less than $1/2^{\text{polylog}n}$ require access to fully-random hash functions-if the same hash tables are implemented using the known explicit families of hash functions, their failure probabilities become $1/{poly}(n)$. To get around these obstacles, we show how to construct a randomized data structure that has the same guarantees as a hash table, but that avoids the direct use of hash functions. Building on this, we able to construct a hash table using $O(n)$ random bits that achieves failure probability $1/n^{n^{1-\varepsilon}}$ for an arbitrary positive constant $\varepsilon$. In fact, we show that this guarantee can even be achieved by a succinct dictionary, that is, by a dictionary that uses space within a $1+o(1)$ factor of the information-theoretic optimum. Finally we also construct a succinct hash table whose probabilistic guarantees fall on a different extreme, offering a failure probability of $1/{poly}(n)$ while using only $\tilde{O}(\log n)$ random bits. This latter result replicates a guarantee previously achieved by Dietzfelbinger et al., but with increased space efficiency and with several surprising technical components.