布谷鸟哈希页面 - Sci-Hub|Scidown

Scidown文献预览系统！

作者：scidown 发布时间：2021-07-28 16:03:20 文章标题：

布谷鸟哈希页面( Cuckoo Hashing with Pages )

文章作者：

M Dietzfelbinger M Mitzenmacher M Rink pattern matching compression Lempel-Ziv

文章简述：

尽管cuckoo散列在理论和实际设置中都有重要的应用，但相关的缺点是它需要查找多个位置。在许多查找成本很高的设置中，布谷鸟散列成为一种不那么引人注目的替代方法。一个这样的标准设置是当内存被安排在大页中时，一个主要的成本是页访问的数量。我们提出了用页面进行布谷鸟散列的研究，提倡每个键在单个页面上有几个可能的位置或单元格，并在第二个备份页面上有额外的选择。我们通过实验证明，在一个页面上选择k个单元和选择单个备份单元时，可以实现与每个密钥有k+1个随机单元可供选择时几乎相同的负载，大多数查找只需要一个页面访问，即使使用简单的算法将密钥在线放置时也是如此。虽然我们的结果目前是实验性的，但它们为用页面进行布谷鸟散列提出了几个有趣的新的开放理论问题。

文章下载地址（开放版）：