基于智能放置策略的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
