本文選題：散列表 + 檢索　； 參考：《計(jì)算機(jī)研究與發(fā)展》2017年11期

【摘要】：散列表(Hash table)由于其支持高效的記錄更新與檢索操作,在計(jì)算機(jī)相關(guān)的各個(gè)領(lǐng)域中有著廣泛的應(yīng)用.但散列表有2個(gè)明顯的缺點(diǎn):沖突和低效的內(nèi)存利用.最小完美散列使用N個(gè)位置存儲(chǔ)N條記錄,解決了沖突和空間效率的問題,但該算法不支持增量的更新.目標(biāo)是設(shè)計(jì)一種高效的散列表,能夠支持高速查詢、最壞情況可以保證的高速更新、高效的空間使用以及動(dòng)態(tài)的容量改變.結(jié)合Cuckoo散列和d-left散列的實(shí)現(xiàn),提出了一個(gè)新的散列表設(shè)計(jì)方案——DCuckoo.DCuckoo使用多級(jí)子表并應(yīng)用了Cuckoo散列中移動(dòng)已有元素的機(jī)制以提高裝載率,且只保留了最末級(jí)子表的指針以減少空間浪費(fèi).為了進(jìn)一步優(yōu)化查詢性能,DCuckoo在片內(nèi)內(nèi)存中使用指紋和位圖作為摘要,在查詢時(shí)先匹配指紋,以減少對(duì)片外內(nèi)存的訪問次數(shù).對(duì)DCuckoo進(jìn)行了一系列實(shí)驗(yàn),與其他5種散列表進(jìn)行比較,發(fā)現(xiàn)DCuckoo達(dá)到了設(shè)計(jì)目標(biāo),并且在各項(xiàng)指標(biāo)上均好于已有的散列表設(shè)計(jì).
[Abstract]:Hash table is widely used in computer related fields because it supports efficient record updating and retrieval operations. But hashtables have two obvious drawbacks: conflict and inefficient memory utilization. The minimal perfect hash uses N locations to store N records, which solves the problems of conflict and spatial efficiency, but the algorithm does not support incremental updating. The goal is to design an efficient hash table that supports high speed queries, guaranteed high speed updates at worst, efficient space usage, and dynamic capacity changes. Based on the implementation of Cuckoo hash and d-left hash, a new hash table design scheme is proposed. DCuckoo.DCuckoo uses multilevel subtables and applies the mechanism of moving existing elements in Cuckoo hash to improve loading rate. Only the last subtable pointers are retained to reduce space waste. In order to further optimize the query performance DCuckoo uses fingerprint and bitmap as abstracts in in-chip memory to reduce the number of visits to out-of-chip memory. A series of experiments on DCuckoo are carried out and compared with the other five kinds of hash tables. It is found that DCuckoo has achieved the design goal and is better than the existing hash table design in every index.
【作者單位】： 北京大學(xué)信息科學(xué)技術(shù)學(xué)院;國防科學(xué)技術(shù)大學(xué)高性能計(jì)算協(xié)同創(chuàng)新中心;94782部隊(duì)65分隊(duì);西京學(xué)院控制工程系;
【基金】：國家自然科學(xué)基金項(xiàng)目(61232004,61672061) 國家"九七三"重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2014CB340400) 國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB1000300) 中國科學(xué)院先導(dǎo)科技專項(xiàng)課題(XDA06040602)~~
【分類號(hào)】：TP311.12

【相似文獻(xiàn)】

相關(guān)期刊論文 前9條

1 吳洲;散列表構(gòu)造與查找的動(dòng)態(tài)實(shí)現(xiàn)[J];電腦知識(shí)與技術(shù);2004年14期

2 王昌福,楊秀謙;散列表的一致對(duì)半探測方法[J];福州大學(xué)學(xué)報(bào)(自然科學(xué)版);2002年02期

3 賈永勝;;散列表及其沖突處理方法的性能分析[J];石家莊職業(yè)技術(shù)學(xué)院學(xué)報(bào);2014年02期

4 孔麗英;;基于差別散列表的屬性約簡算法[J];微計(jì)算機(jī)信息;2010年18期

5 高正紅;毛林;;基于散列表的關(guān)聯(lián)挖掘算法[J];科技信息;2010年10期

6 劉環(huán);多媒體教室預(yù)約系統(tǒng)研究[J];科技情報(bào)開發(fā)與經(jīng)濟(jì);2005年17期

7 何炎祥,宋 強(qiáng),李旭輝;一種符號(hào)管理的新模型[J];計(jì)算機(jī)工程與應(yīng)用;2000年10期

8 王俊龍;杜桂萍;;無限網(wǎng)狀結(jié)構(gòu)對(duì)拉鏈法解決地址沖突問題的優(yōu)化[J];無線互聯(lián)科技;2014年04期

9 田生偉;吐爾根·依布拉音;禹龍;;EBMT中高效的維吾爾語單詞散列表構(gòu)造算法[J];中文信息學(xué)報(bào);2009年04期

，

本文編號(hào)：2014634