On the optimal time/space tradeoff for hash tables
On the optimal time/space tradeoff for hash tables
复制标题
DOI：
10.1145/3519935.3519969
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
M. A. Bender;Martín Farach-Colton;John Kuszmaul;William Kuszmaul;Mingmou Liu
中科院分区：
文献类型：
--
作者：
M. A. Bender;Martín Farach-Colton;John Kuszmaul;William Kuszmaul;Mingmou Liu
近六十年来，哈希表研究的核心开放问题一直是确定时间和空间之间可实现的最佳权衡曲线。最先进的哈希表提供了以下保证：如果每个键/值都是Θ（logn）位，那么与信息论的最优值相比，每个键只浪费O（loglog）位的空间，而实现恒定时间的插入/删除/查询是可能的——这个边界已被证明对于许多密切相关的问题（例如，稳定的哈希、动态检索和动态调整大小的过滤器）是最优的。本文表明，每个键浪费的0 （loglogn）位并不是散列的终点。事实上，对于任何k∈[log* n]，都有可能实现O(k)次插入/删除时间，O(1)次查询时间，以及每个键的第k次迭代对数O（log(k) n）次浪费位（所有这些都在n内具有高概率），同时还支持随着表大小的变化动态调整大小。我们进一步表明，这种权衡曲线是任何大型哈希表（包括使用当前框架设计的用于使恒定时间哈希表简洁的任何哈希表）中可以实现的最佳曲线。我们的结果适用于任意大的键/值，在键/值非常小的情况下，我们可以将边界收紧到每个键浪费0(1)位。在此基础上，我们获得了一个恒定时间的动态滤波器，它使用n≤log_−1 _ + n logge + o(n)位空间来实现广泛的假阳性率选择，解决了动态滤波器设计的长期开放问题。
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 Θ(logn) bits each, then it is possible to achieve constant-time insertions/deletions/queries while wasting only O(loglogn) 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(loglogn) 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 loge + 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.