Tight Thresholds for Cuckoo Hashing via XORSAT
Tight Thresholds for Cuckoo Hashing via XORSAT
复制标题
DOI：
10.1007/978-3-642-14165-2_19
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
Martin Dietzfelbinger;A. Goerdt;M. Mitzenmacher;A. Montanari;R. Pagh;Michael Rink
中科院分区：
文献类型：
--
作者：
Martin Dietzfelbinger;A. Goerdt;M. Mitzenmacher;A. Montanari;R. Pagh;Michael Rink
我们解决了离线布谷鸟哈希的严格阈值问题。这个问题可以表述如下：我们需要将密钥散列到每个桶中，每个桶只能保存一个密钥。每个密钥任务至少有3个（不同的）关联桶，均匀随机选择，独立于其他密钥的选择。如果每个键都可以放入其中一个桶中，则可以成功构造散列表。我们寻求这样的阈值sck，当趋于无穷时，如果n/m≤c（对于某些<ck），则哈希表可以高概率地构建成功，如果n/m≥c（对于某些<ck），则哈希表不能高概率地构建成功。这里我们考虑的是这个问题的离线版本，其中所有的键和哈希值都是给定的，所以这个问题相当于以前的多选题哈希模型。我们通过显示它们实际上与之前已知的randomk-XORSAT问题的阈值相同，找到了k >2的所有值的阈值。然后，我们将这些结果扩展到键可以有不同数量的选择的设置，并做出一个猜想（基于实验观察），将我们的结果扩展到在一个桶中存储多个键的布谷鸟哈希表。
We settle the question of tight thresholds for offline cuckoo hashing. The problem can be stated as follows: we havenkeys to be hashed intombuckets each capable of holding a single key. Each key hask≥ 3 (distinct) associated buckets chosen uniformly at random and independently of the choices of other keys. A hash table can be constructed successfully if each key can be placed into one of its buckets. We seek thresholdscksuch that, asngoes to infinity, ifn/m≤cfor somec<ckthen a hash table can be constructed successfully with high probability, and ifn/m≥cfor somec>cka hash table cannot be constructed successfully with high probability. Here we are considering the offline version of the problem, where all keys and hash values are given, so the problem is equivalent to previous models of multiple-choice hashing. We find the thresholds for all values ofk> 2 by showing that they are in fact the same as the previously known thresholds for the randomk-XORSAT problem. We then extend these results to the setting where keys can have differing number of choices, and make a conjecture (based on experimental observations) that extends our result to cuckoo hash tables storing multiple keys in a bucket.