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

发布时间：2022-08-10 10:54

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

【文章页数】：7 页

【文章目录】：
1 引言
2 相关工作
    2.1 Cuckoo哈希表及其改进
    2.2 高性能哈希表
3 LBCHT的设计与实现
    3.1 LBCHT的核心思想
    3.2 实际操作
        3.2.1 插入
        3.2.2 查询和删除
4 LPCHT的设计与实现
    4.1 LPCHT的核心思想
    4.2 实际操作
        4.2.1 插入
        4.2.2 查询和删除
5 性能评价
    5.1 额外负载因子的影响
    5.2 长尾效应的比较
    5.3 libcuckoo与不同额外负载因子的LBCHT的比较
    5.4 不同线程数之间写负载效率的对比
    5.5 正向查询效率的比较
    5.6 LBCHT和LPCHT的应用
结束语



本文编号：3673507