[發(fā)明專利]一種高效的靜態(tài)哈希表實(shí)現(xiàn)方法及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201610793354.5
• 申請(qǐng)日: 2016-08-31
• 公開（公告）號(hào): CN106326475B
• 公開（公告）日: 2019-12-27
• 發(fā)明（設(shè)計(jì)）人: 劉燕兵;張春燕;盧毓海;譚建龍;郭莉
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院信息工程研究所
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22
• 代理公司: 11200 北京君尚知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 邱曉鋒

本發(fā)明涉及一種高效的靜態(tài)哈希表實(shí)現(xiàn)方法及系統(tǒng)。該方法包括以下步驟：1)設(shè)定哈希桶大小hash_bit，生成多個(gè)數(shù)據(jù)對(duì)，將key[i]和value[i]對(duì)應(yīng)于關(guān)鍵字和值；2)根據(jù)key[i]值，利用rank操作構(gòu)建哈希表，并計(jì)算C表和D表；3)根據(jù)C表和D表計(jì)算rank(h)，并根據(jù)rank(h)的值存儲(chǔ)相應(yīng)的key[i]和value[i]；4)根據(jù)所要查詢的值key判斷哈希表中是否存在該元素，若存在則在對(duì)應(yīng)存儲(chǔ)位置查詢并返回value值，否則訪問失?。?)根據(jù)步驟4)所得的結(jié)果返回結(jié)果信息。本發(fā)明利用Rank?select算法實(shí)現(xiàn)新型靜態(tài)哈希表的構(gòu)建與訪問，可用于內(nèi)容過濾、信息安全等領(lǐng)域。

技術(shù)領(lǐng)域

本發(fā)明旨在設(shè)計(jì)靜態(tài)哈希表壓縮算法，用于內(nèi)容過濾、信息安全等領(lǐng)域。由于靜態(tài)哈希表的存儲(chǔ)占用空間較大，現(xiàn)今的算法對(duì)于靜態(tài)哈希表的壓縮還有很大優(yōu)化空間。本發(fā)明旨在對(duì)靜態(tài)哈希表進(jìn)行壓縮，可支持對(duì)靜態(tài)哈希表的訪問。

背景技術(shù)

數(shù)據(jù)結(jié)構(gòu)中的查找表分為靜態(tài)查找表和動(dòng)態(tài)查找表。查找表主要針對(duì)表中的數(shù)據(jù)不斷地查找，直到找出其所需要的值為止。靜態(tài)查找表的類型主要包括順序查找、二分查找、分塊查找及靜態(tài)樹表的查找等，而動(dòng)態(tài)查找表的類型主要包括二叉排序樹、平衡二叉樹、B樹和B+樹等。上述介紹的查找算法查找的效率取決于比較次數(shù)，查找平均次數(shù)越多，其效率越低，平均而言查找表的查找效率并不高。為了快速定位數(shù)據(jù)，可以使用哈希表來提升訪問效率。

哈希表又叫做散列表，它利用鍵值對(duì)(key-value)來存儲(chǔ)數(shù)據(jù)，是一種特殊的數(shù)據(jù)結(jié)構(gòu)。哈希表通過把鍵值對(duì)映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做哈希函數(shù)，存放記錄的數(shù)組叫做哈希表。哈希表中的映射不一定是單射，故可能會(huì)產(chǎn)生哈希沖突的現(xiàn)象，數(shù)據(jù)結(jié)構(gòu)中有很多算法可以解決哈希沖突。哈希表的應(yīng)用場(chǎng)景十分廣泛，應(yīng)用哈希表存儲(chǔ)數(shù)據(jù)來實(shí)現(xiàn)快速查找是很常見的操作。在實(shí)際的計(jì)算科學(xué)中，哈希表可以在對(duì)等網(wǎng)絡(luò)(P2P)中的路由選擇、數(shù)據(jù)庫(kù)查找、壓縮序數(shù)索引和信息安全等方面發(fā)揮著巨大的應(yīng)用。

在實(shí)際生活中，哈希表也有著重要的作用。比如，銀行要進(jìn)行前臺(tái)數(shù)據(jù)和后臺(tái)數(shù)據(jù)進(jìn)行對(duì)賬處理時(shí)，可以根據(jù)鍵查找到相應(yīng)的值，從而完成前后臺(tái)數(shù)據(jù)的對(duì)賬工作；生活中利用的IC卡乘坐公交時(shí)，將IC卡的編號(hào)作為鍵，上車刷卡記錄為哈希表的插入過程，值中存儲(chǔ)上車時(shí)間和站名，下車刷卡記錄為哈希表的查找過程，同時(shí)刪除哈希表中此編號(hào)信息并計(jì)算時(shí)間和間距。

哈希表按照是否支持動(dòng)態(tài)增刪操作，分為靜態(tài)哈希表和動(dòng)態(tài)哈希表。靜態(tài)哈希表是對(duì)于HASH操作只支持查詢操作，不支持動(dòng)態(tài)增刪操作。靜態(tài)哈希表適用于一次將數(shù)據(jù)預(yù)存至哈希表中，之后的工作主要負(fù)責(zé)快速查找數(shù)據(jù)。在模式串匹配算法中，靜態(tài)哈希表很符合某些算法的應(yīng)用背景，例如Wu-Manber、Karp-Rabin等高效算法都是利用HASH函數(shù)對(duì)規(guī)則進(jìn)行處理來匹配文本，這些哈希操作往往是預(yù)先將規(guī)則一次加載至哈希表中，然后再進(jìn)行匹配。

現(xiàn)今的哈希表算法主要包括線性探測(cè)哈希算法、二分查找算法和二分哈希算法。這些算法也滿足靜態(tài)哈希表的需求，在存儲(chǔ)和查詢時(shí)可以有效地定位數(shù)據(jù)，但是其空間存儲(chǔ)與查詢效率方面還有很大提升空間。下面簡(jiǎn)要介紹各算法的思想。

線性探測(cè)算法：當(dāng)關(guān)鍵字key的通過哈希函數(shù)H(key)得到的哈希地址p沖突時(shí)，以p為標(biāo)準(zhǔn)，通過哈希函數(shù)H(key)另外得到新的哈希地址p1，……，如此進(jìn)行迭代計(jì)算，當(dāng)終于有一個(gè)哈希地址pi不出現(xiàn)沖突時(shí)為止，并將所對(duì)應(yīng)的關(guān)鍵字和值存到該哈希地址上。查找時(shí)，先通過哈希函數(shù)H(key)，找出哈希桶中是否存在關(guān)鍵字key，若存在，返回value值。

二分查找算法：存儲(chǔ)時(shí)，對(duì)關(guān)鍵字key值排序；查找時(shí)，利用二分算法查找key值，進(jìn)而查出value。

二分哈希算法：鏈地址分為不同的哈希桶，存儲(chǔ)時(shí)，每個(gè)桶內(nèi)利用二分查找算法存儲(chǔ)。查找時(shí)，先通過哈希函數(shù)判斷所在哈希桶，在哈希桶內(nèi)利用二分查找算法查找key值，進(jìn)而查出value。