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