由于查詢時間復(fù)雜度為O（1）,Cuckoo哈希表在大數(shù)據(jù)、云計算等領(lǐng)域得到了廣泛應(yīng)用。然而,現(xiàn)有Cuckoo哈希表的寫入操作在遇到寫沖突時普遍采用隨機(jī)替換策略來替換已有表項(xiàng)。一方面,寫入操作容易出現(xiàn)高遲插入和無限循環(huán),尤其是當(dāng)哈希表負(fù)載率較高時,甚至有重構(gòu)整個哈希表的風(fēng)險;另一方面,由于現(xiàn)有隨機(jī)替換策略將數(shù)據(jù)項(xiàng)盡量散布在哈希表的各個桶中,哈希表項(xiàng)間缺乏良好的空間局部性,降低了數(shù)據(jù)正向查詢的效率。為解決以上問題,提出了一種基于智能放置策略的Cuckoo哈希表。具體地,為提升寫入操作的效率,提出了一種基于負(fù)載均衡的Cuckoo哈希表（Load-Balance Cuckoo Hash Table,LBCHT）,實(shí)時限制每個桶的負(fù)載,并使用廣度優(yōu)先搜索尋找最佳Cuckoo路徑,實(shí)驗(yàn)結(jié)果表明LBCHT能有效減少高負(fù)載率下寫入操作可能出現(xiàn)的長尾效應(yīng);為提升查詢操作的效率,提出了一種充分利用局部性原理的Cuckoo哈希表（Locality Principle Cuckoo Hash Table,LPCHT）,通過充分發(fā)掘哈希表項(xiàng)間的空間局部性,來有效減小查詢操作引起的CPU高速緩存缺失率,提高正向查... 

【文章頁數(shù)】：7 頁

【文章目錄】：
1 引言
2 相關(guān)工作
    2.1 Cuckoo哈希表及其改進(jìn)
    2.2 高性能哈希表
3 LBCHT的設(shè)計與實(shí)現(xiàn)
    3.1 LBCHT的核心思想
    3.2 實(shí)際操作
        3.2.1 插入
        3.2.2 查詢和刪除
4 LPCHT的設(shè)計與實(shí)現(xiàn)
    4.1 LPCHT的核心思想
    4.2 實(shí)際操作
        4.2.1 插入
        4.2.2 查詢和刪除
5 性能評價
    5.1 額外負(fù)載因子的影響
    5.2 長尾效應(yīng)的比較
    5.3 libcuckoo與不同額外負(fù)載因子的LBCHT的比較
    5.4 不同線程數(shù)之間寫負(fù)載效率的對比
    5.5 正向查詢效率的比較
    5.6 LBCHT和LPCHT的應(yīng)用
結(jié)束語



本文編號：3673507