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

发布时间：2018-06-13 16:23

本文选题：散列表 + 检索　；参考：《计算机研究与发展》2017年11期

【摘要】：散列表(Hash table)由于其支持高效的记录更新与检索操作,在计算机相关的各个领域中有着广泛的应用.但散列表有2个明显的缺点:冲突和低效的内存利用.最小完美散列使用N个位置存储N条记录,解决了冲突和空间效率的问题,但该算法不支持增量的更新.目标是设计一种高效的散列表,能够支持高速查询、最坏情况可以保证的高速更新、高效的空间使用以及动态的容量改变.结合Cuckoo散列和d-left散列的实现,提出了一个新的散列表设计方案——DCuckoo.DCuckoo使用多级子表并应用了Cuckoo散列中移动已有元素的机制以提高装载率,且只保留了最末级子表的指针以减少空间浪费.为了进一步优化查询性能,DCuckoo在片内内存中使用指纹和位图作为摘要,在查询时先匹配指纹,以减少对片外内存的访问次数.对DCuckoo进行了一系列实验,与其他5种散列表进行比较,发现DCuckoo达到了设计目标,并且在各项指标上均好于已有的散列表设计.
[Abstract]:Hash table is widely used in computer related fields because it supports efficient record updating and retrieval operations. But hashtables have two obvious drawbacks: conflict and inefficient memory utilization. The minimal perfect hash uses N locations to store N records, which solves the problems of conflict and spatial efficiency, but the algorithm does not support incremental updating. The goal is to design an efficient hash table that supports high speed queries, guaranteed high speed updates at worst, efficient space usage, and dynamic capacity changes. Based on the implementation of Cuckoo hash and d-left hash, a new hash table design scheme is proposed. DCuckoo.DCuckoo uses multilevel subtables and applies the mechanism of moving existing elements in Cuckoo hash to improve loading rate. Only the last subtable pointers are retained to reduce space waste. In order to further optimize the query performance DCuckoo uses fingerprint and bitmap as abstracts in in-chip memory to reduce the number of visits to out-of-chip memory. A series of experiments on DCuckoo are carried out and compared with the other five kinds of hash tables. It is found that DCuckoo has achieved the design goal and is better than the existing hash table design in every index.
【作者单位】：北京大学信息科学技术学院;国防科学技术大学高性能计算协同创新中心;94782部队65分队;西京学院控制工程系;
【基金】：国家自然科学基金项目(61232004,61672061) 国家"九七三"重点基础研究发展计划基金项目(2014CB340400) 国家重点研发计划项目(2016YFB1000300) 中国科学院先导科技专项课题(XDA06040602)~~
【分类号】：TP311.12

【相似文献】