一種基于智能放置策略的CucKoo哈希表

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