[發明專利]一種高效的靜態哈希表實現方法及系統

有效

• 申請號: 201610793354.5
• 申請日: 2016-08-31
• 公開（公告）號: CN106326475B
• 公開（公告）日: 2019-12-27
• 發明（設計）人: 劉燕兵;張春燕;盧毓海;譚建龍;郭莉
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 11200 北京君尚知識產權代理有限公司
• 代理人: 邱曉鋒

1.一種適用于哈希表應用場景的基于高效的靜態哈希表實現的數據存儲和訪問方法，其特征在于，包括以下步驟：

1)設定哈希桶大小hash_bit，生成多個數據對，將key[i]和value[i]對應于關鍵字和值；

2)根據key[i]值，利用rank操作構建哈希表，并計算C表和D表，其中C表表示存儲固定長度r的rank操作，D表表示存儲固定長度s的rank操作；

3)根據C表和D表計算rank(h)，其中h＝key mod(hash_bits)，并根據rank(h)的值存

儲相應的key[i]和value[i]；

所述步驟3)采用以下步驟實現基于rank操作的哈希表存儲過程：

3-1)將預處理的數據分為key和value數組，key[i]、value[i]與關鍵字、鍵值相對應；

3-2)預先一次性導入key值至bitmap中，bitmap是一個大小為4的無符號的長整型數組，定義哈希桶的數量為hash_bit，按照時間度O(1)的rank操作記錄key數組的數據內容；對key與hash_bit取模得到h，確保落在哈希桶內，然后將h存儲在哈希桶對應位置上，按照h值的大小，記錄所有key值的相應位置信息；

3-3)存儲計算C數組和D數組，利用rank操作從哈希表CB[0]開始記錄C數組和D數組的相應信息；

3-4)利用C表和D表信息，計算每個key值對應的rank值；

3-5)利用rank值記錄每個哈希桶內元素個數，按照哈希表C的順序疊加記錄，利用rank值作為順序存儲key、value值；

3-6)存儲key、value值到數組中；

4)根據所要查詢的值key判斷哈希表中是否存在相應的元素，若存在則在對應存儲位置查詢并返回value值，否則訪問失敗；

5)根據步驟4)所得的結果，返回結果信息。

2.如權利要求1所述的方法，其特征在于，步驟3-2)中，hash_bit的值為CB表的大小clength和2⁸的乘積，對每個哈希桶內分配4個大小的bitmap，每個bitmap存儲64位的數據，初始化設置為各位均為0。

3.如權利要求2所述的方法，其特征在于，步驟3-2)按照如下公式記錄h的位置，直到所有的key值均依次記錄位置：

q＝h&255，

CB[h>>8].bitmap[q>>6]|＝(1<<(q&63))，

其中，CB[j].bitmap[i]表示哈希表的元素CB[j]中bitmap的元素bitmap[i]。

4.如權利要求1所述的方法，其特征在于，步驟3-5)中，在存儲key-value對時，若不同的key有同一rank值，則首要順序按照rank值大小順序存儲，次要順序按照rank值相同依次存儲。

5.如權利要求1所述的方法，其特征在于，步驟4)采用以下步驟實現基于rank操作的哈希表訪問過程：

4-1)對要查詢的數據key與hash_bit取模得到h；

4-2)計算q＝h&255，判斷CB[h>>8].bitmap[q>>6]和(1<<(q&63))做與運算是否為1，即在原來哈希桶內是否有key值；若此步判斷為0，則原哈希表內沒有該key值，查詢失敗；若此步判斷為1，則原哈希表內有該key值，則需要找到value值；

4-3)為了防止哈希沖突，即原哈希表內該位置有兩個及以上的關鍵字值命中，則在該哈希桶內依次判斷是否含有查詢數據key，若包含，返回value值，若不包含，查詢下一個關鍵字，直至關鍵字為空，查詢失敗。