Cuckoo Hashing with Pages
Cuckoo Hashing with Pages
复制标题
布谷鸟哈希与页面
DOI：
10.1007/978-3-642-23719-5_52
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Michael Rink
中科院分区：
文献类型：
--
作者：
Martin Dietzfelbinger;Michael Mitzenmacher;Michael Rink
布谷鸟散列的一个缺点是它需要查找多个位置，当查找成本很高时，它就不那么引人注目了。一种这样的设置是当内存被安排在大的页面中时，主要的成本是页面访问的次数。我们建议用页面研究布谷鸟哈希，提倡每个键在单个页面上有几个可能的位置或单元，并在第二个备份页面上有其他选择的方法。我们通过实验证明，在一个页面上使用kcell选择和一个备份cell选择时，可以获得与每个密钥任务+ 1个随机单元选择时几乎相同的负载，大多数查找只需要访问一个页面，即使使用简单的算法在线放置密钥也是如此。虽然我们的结果目前是实验性的，但它们为布谷鸟页面哈希提出了几个有趣的新开放理论问题。
A downside of cuckoo hashing is that it requires lookups to multiple locations, making it a less compelling alternative when lookups are expensive. One such setting is when memory is arranged in large pages, and the major cost is the number of page accesses. We propose the study of cuckoo hashing with pages, advocating approaches where each key has several possible locations, or cells, on a single page, and additional choices on a second backup page. We show experimentally that withkcell choices on one page and a single backup cell choice, one can achieve nearly the same loads as when each key hask+ 1 random cells to choose from, with most lookups requiring just one page access, even when keys are placed online using a simple algorithm. While our results are currently experimental, they suggest several interesting new open theoretical questions for cuckoo hashing with pages.
登录
查看更多内容
DOI：
--
发表时间：
2006
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
Philipp Woelfel
通讯作者：
Philipp Woelfel
3.5 路 Cuckoo 哈希，只需 2 比特的价格
DOI：
--
发表时间：
2009
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
E. Lehman;R. Panigrahy
通讯作者：
R. Panigrahy
随机二部图中的最大匹配与布谷鸟哈希表的空间利用率
DOI：
--
发表时间：
2009
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
A. Frieze;Páll Melsted
通讯作者：
Páll Melsted
随机超图的可定向性和多重选择的力量
DOI：
--
发表时间：
2010
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
N. Fountoulakis;K. Panagiotou
通讯作者：
K. Panagiotou