[發(fā)明專利]哈希表的表項添加、刪除、查找方法及哈希表存儲裝置

有效

• 申請?zhí)枺?/td>: 201110138340.7
• 申請日: 2011-05-25
• 公開（公告）號: CN102194002A
• 公開（公告）日: 2011-09-21
• 發(fā)明（設(shè)計）人: 李彧;張煒;孫遠(yuǎn)航;崔玉姣;鄭永梅
• 申請（專利權(quán)）人: 中興通訊股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 深圳鼎合誠知識產(chǎn)權(quán)代理有限公司 44281
• 代理人: 宋鷹武

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

本發(fā)明涉及通信技術(shù)領(lǐng)域，尤其涉及一種哈希表的表項添加、刪除、查找方法及其存儲裝置。

背景技術(shù)

在通信領(lǐng)域中，存在著多種的匹配算法，例如，對于精確匹配的查找，可以采用哈希算法。所述的哈希查找的過程就是用哈希函數(shù)對輸入的查找鍵值(Key)進(jìn)行縮位運(yùn)算，再用計算得到的哈希值在哈希索引表中尋址，找到匹配項后讀出對應(yīng)項中存放的哈希索引(Hash?Index)，最后用哈希索引在直接地址映射表尋址，得到所需的查找結(jié)果。

哈希算法是一種常見的快速查找算法，它的基本思想是以線性表中每個元素的關(guān)鍵字k為自變量。通過一定的函數(shù)關(guān)系H(k)，計算出對應(yīng)的函數(shù)值來，并把這個值解釋為一塊連續(xù)存儲空間的單元，將該元素存儲到這個單元中。哈希算法將元素的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系，查找時，不需要比較，一次哈希映射就可以查找所需元素。

在哈希函數(shù)中，對不同的關(guān)鍵字可能得到同一哈希地址，即key1≠key2，而H(key1)＝H(key2)，這種情況叫沖突(Collision)。一般來說，遇到?jīng)_突是很正常的事情，關(guān)鍵在于遇到?jīng)_突后怎么處理，以達(dá)到要求的查找目的。處理沖突，主要有以下兩種方法：一是選擇和改進(jìn)比較好的哈希函數(shù)；二是選擇比較合適的表項存儲結(jié)構(gòu)。

目前，對于路由查找這類的應(yīng)用，采用CRC(Cyclic?Redundancy?Checking，循環(huán)冗余碼校驗)類的哈希函數(shù)是比較適合的。通過選取不同的CRC多項式，可以實現(xiàn)同一個位寬下的不同哈希函數(shù)。

在選擇合適的表存儲結(jié)構(gòu)解決沖突問題方面，可以采用多維哈希表、沖突鏈、Double?Hashing等。仿真實驗結(jié)果表明，使用這些方法，在保證無表項遺留即所有表項都能存入的前提條件下，計算哈希值的次數(shù)跟需要的存儲表空間存在對立的關(guān)系，也就是說如果想要以足夠小的存儲空間放下所有的表項，則需要進(jìn)行足夠多次數(shù)的哈希運(yùn)算。這樣就會造成對同一塊表的多次訪問，由于表只有一張，所以查找只能順序進(jìn)行，這會嚴(yán)重影響查表的速度；另一方面，如果想要以足夠少的計算次數(shù)就能找到存儲空位，那么就要保證存儲空間足夠的大，空間利用率就會大大的降低。如果采用多張哈希表并行查找，則需要占用多個存儲器接口，不利于硬件上的實現(xiàn)。

發(fā)明內(nèi)容

本發(fā)明要解決的主要技術(shù)問題是，提供一種哈希表的表項添加、刪除、查找方法，及其存儲裝置，以極小的查找時間代價以及較高的表空間利用率實現(xiàn)全部表項存儲而無表項遺留；同時只需訪問一次就能夠準(zhǔn)確的查找到需要的表項；同時也便于硬件與存儲器之間接口的實現(xiàn)，能夠在表空間大小，查找效率以及硬件實現(xiàn)方面獲得比較好的均衡。

為解決上述技術(shù)問題，本發(fā)明采用的技術(shù)方案如下：

一種哈希表的表項添加方法，包括：

將哈希表拆分為多張哈希子表，每一張哈希子表對應(yīng)一張位圖，每一張位圖對應(yīng)一個哈希函數(shù)；

確定當(dāng)前目標(biāo)哈希子表，利用當(dāng)前目標(biāo)哈希子表所對應(yīng)的位圖相應(yīng)的哈希函數(shù)計算待存儲表項的鍵值的哈希值，根據(jù)所述哈希值確定當(dāng)前目標(biāo)哈希子表所對應(yīng)的存儲位置是否空位，如是，將所述待存儲表項的信息存入該空位中，否則，更新當(dāng)前目標(biāo)哈希子表直至找到空位存儲所述待存儲表項的信息。

進(jìn)一步地，所述位圖包含了沖突位和有效位，根據(jù)所述哈希值確定當(dāng)前目標(biāo)哈希子表所對應(yīng)的存儲位置是否空位，如是，將所述待存儲表項的信息存入該空位中，否則，更新當(dāng)前目標(biāo)哈希子表直至找到空位存儲所述待存儲表項的信息的步驟，包括：

以所述哈希值作為索引，查找所述當(dāng)前目標(biāo)哈希子表對應(yīng)的位圖；

判斷所述位圖的有效位是否有效，且所述位圖的沖突位是否為無效；

如果所述有效位為有效，且所述沖突位為無效，則確定所述當(dāng)前目標(biāo)哈希子表所對應(yīng)的存儲位置為空位，則將所述待存儲表項的信息存入該空位；否則，更新當(dāng)前目標(biāo)哈希子表直至找到空位存儲所述待存儲表項的信息。

更進(jìn)一步地，所述以所述哈希值作為索引，查找所述當(dāng)前目標(biāo)哈希子表對應(yīng)的位圖的步驟，包括：

判斷當(dāng)前目標(biāo)哈希子表的容量是否小于計算得到的所述哈希值的位數(shù)；

如果所述當(dāng)前目標(biāo)哈希子表的容量小于計算得到的所述哈希值的位數(shù)，則截取所述哈希值，并將截取后的哈希值作為索引，查找所述當(dāng)前目標(biāo)哈希子表對應(yīng)的位圖。

更進(jìn)一步地，將所述待存儲表項的信息存入空位后，還包括：

將所述位圖的有效位置為無效，并將所述待存儲表項的鍵值存儲到該位圖中。

更進(jìn)一步地，更新當(dāng)前目標(biāo)哈希子表直至找到空位存儲所述待存儲表項的信息的步驟，包括：