3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit
3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit
复制标题
3.5 路 Cuckoo 哈希，只需 2 比特的价格
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
R. Panigrahy
中科院分区：
文献类型：
--
作者：
E. Lehman;R. Panigrahy
哈希的研究与小球的分析密切相关。两个随机垃圾桶。想法。固定的存储器数组中的大小为k的非重叠块。哈希到两个任意的大小 - 内存块。 1-（1/e + O（1））通常，对于K = 2，新方法将利用率从89.7％提高到96.5％，但在两个随机位置中，查找仅访问两个项目令人惊讶，因为相反的情况发生在非cuckoo设置中，如果在以后的插入过程中没有移动项目，则从非重叠的块转移到重叠的块会使分布较少均匀。
The study of hashing is closely related to the analysis of balls and bins; items are hashed to memory locations much as balls are thrown into bins. In particular, Azar et. al. [2] considered putting each ball in the less-full of two random bins. This lowers the probability that a bin exceeds a certain load from exponentially small to doubly exponential, giving maximum load loglogn + O(1) with high probability. Cuckoo hashing [20] draws on this idea. Each item is hashed to two buckets of capacity k. If both are full, then the insertion procedure moves previously-inserted items to their alternate buckets to make space for the new item. In a natural implementation, the buckets are represented by partitioning a fixed array of memory into non-overlapping blocks of size k. An item is hashed to two such blocks and may be stored at any location within either one. We analyze a simple twist in which each item is hashed to two arbitrary size-k memory blocks. (So consecutive blocks are no longer disjoint, but rather overlap by k − 1 locations.) This twist increases the space utilization from 1 − (2/e + o(1)) k to 1 − (1/e + o(1))1.59k in general. For k = 2, the new method improves utilization from 89.7% to 96.5%, yet lookups access only two items at each of two random locations. This result is surprising because the opposite happens in the non-cuckoo setting; if items are not moved during later insertions, then shifting from non-overlapping to overlapping blocks makes the distribution less uniform.