论文标题
没有哈希功能的哈希表，以及如何充分利用随机位
A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits
论文作者
论文摘要
本文考虑了一个基本问题，即概率保证的强度如何，存储$ n $ $（1 +θ（1））\ log n $ bit键/值对，要约？过去在这个问题上的工作已经被已知的哈希函数家族的局限性所瓶装：实现故障概率的唯一哈希表小于$ 1 /2^{\ polylog n} $需要访问全面的哈希函数 - 如果使用已知的ext aff table table figity hash函数来实现同样的hash表，则它们的失败概率为$ 1 / n $。 为了解决这些障碍，我们展示了如何构建具有与哈希表相同保证的随机数据结构，但是\ emph {避免直接使用哈希函数}。在此基础上，我们能够使用$ o（n）$随机位构造哈希表，以实现故障概率$ 1 / n^{n^{1 -ε}} $，用于任意正常数$ε$。 实际上，我们表明，甚至可以通过\ emph {简洁的字典}来实现此保证，也就是说，通过使用$ 1 + o（1）$属于信息理论最佳的$ 1 + o（1）$的词典。 最后，我们还构建了一个简洁的哈希表，其概率保证属于另一个极端，而失败概率为$ 1 / \ poly（n）$，而仅使用$ \ tilde {o}（\ log n）$随机位。后者的结果匹配（低阶术语）先前由Dietzfelbinger等人获得的保证，但是空间效率提高，并且具有多个令人惊讶的技术组件。
This paper considers the basic question of how strong of a probabilistic guarantee can a hash table, storing $n$ $(1 + Θ(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^{\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 \emph{avoids the direct use of hash functions}. Building on this, we are able to construct a hash table using $O(n)$ random bits that achieves failure probability $1 / n^{n^{1 - ε}}$ for an arbitrary positive constant $ε$. In fact, we show that this guarantee can even be achieved by a \emph{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 matches (up to low-order terms) a guarantee previously achieved by Dietzfelbinger et al., but with increased space efficiency and with several surprising technical components.
