DCuckoo：基于片内摘要的高性能散列表

来源：计算机研究与发展杂志2017年第11期北京时间：

作者：蒋捷,杨仝,张梦瑜,代亚非,黄亮,郑廉清,

摘要：散列表(Hashtable)由于其支持高效的记录更新与检索操作，在计算机相关的各个领域中有着广泛的应用.但散列表有2个明显的缺点：冲突和低效的内存利用.最小完美散列使用N个位置存储N条记录，解决了冲突和空间效率的问题，但该算法不支持增量的更新.目标是设计一种高效的散列表，能够支持高速查询、最坏情况可以保证的高速更新、高效的空间使用以及动态的容量改变.结合Cuckoo散列和d-left散列的实现，提出了一个新的散列表设计方案——DCuckoo.DCuckoo使用多级子表并应用了Cuckoo散列中移动已有元素的机制以提高装载率，且只保留了最末级子表的指针以减少空间浪费.为了进一步优化查询性能，DCuckoo在片内内存中使用指纹和位图作为摘要，在查询时先匹配指纹，以减少对片外内存的访问次数.对DCuckoo进行了一系列实验，与其他5种散列表进行比较，发现DCuckoo达到了设计目标，并且在各项指标上均好于已有的散列表设计.

关键词：散列表, 检索, 指纹, 片内内存, 键值存储,