期刊专题

10.11896/jsjkx.191200109

基于智能放置策略的Cuckoo哈希表

引用
由于查询时间复杂度为O(1),Cuckoo哈希表在大数据、云计算等领域得到了广泛应用.然而,现有Cuckoo哈希表的写入操作在遇到写冲突时普遍采用随机替换策略来替换已有表项.一方面,写入操作容易出现高迟插入和无限循环,尤其是当哈希表负载率较高时,甚至有重构整个哈希表的风险;另一方面,由于现有随机替换策略将数据项尽量散布在哈希表的各个桶中,哈希表项间缺乏良好的空间局部性,降低了数据正向查询的效率.为解决以上问题,提出了一种基于智能放置策略的Cuckoo哈希表.具体地,为提升写入操作的效率,提出了一种基于负载均衡的Cuckoo哈希表(Load-Balance Cuckoo Hash Ta-ble,LBCHT),实时限制每个桶的负载,并使用广度优先搜索寻找最佳Cuckoo路径,实验结果表明LBCHT能有效减少高负载率下写入操作可能出现的长尾效应;为提升查询操作的效率,提出了一种充分利用局部性原理的Cuckoo哈希表(Locality Prin-ciple Cuckoo Hash Table,LPCHT),通过充分发掘哈希表项间的空间局部性,来有效减小查询操作引起的CPU高速缓存缺失率,提高正向查询的效率.实验结果证明,在高负载率的压力测试环境中,与libcuckoo相比,LBCHT的写入效率提升了50%,LPCHT的正向查询效率提升了7%.

负载均衡、广度优先搜索、长尾效应、局部性原理、正向查询

47

TN393(半导体技术)

国家自然科学基金;江苏省重点研发计划

2020-08-26(万方平台首次上网日期,不代表论文的发表时间)

共7页

80-86

暂无封面信息
查看本期封面目录

计算机科学

1002-137X

50-1075/TP

47

2020,47(8)

专业内容知识聚合服务平台

国家重点研发计划“现代服务业共性关键技术研发及应用示范”重点专项“4.8专业内容知识聚合服务技术研发与创新服务示范”

国家重点研发计划资助 课题编号:2019YFB1406304
National Key R&D Program of China Grant No. 2019YFB1406304

©天津万方数据有限公司 津ICP备20003920号-1

信息网络传播视听节目许可证 许可证号:0108284

网络出版服务许可证:(总)网出证(京)字096号

违法和不良信息举报电话:4000115888    举报邮箱:problem@wanfangdata.com.cn

举报专区:https://www.12377.cn/

客服邮箱:op@wanfangdata.com.cn