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

有效

• 申請號: 201110138340.7
• 申請日: 2011-05-25
• 公開（公告）號: CN102194002A
• 公開（公告）日: 2011-09-21
• 發明（設計）人: 李彧;張煒;孫遠航;崔玉姣;鄭永梅
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 深圳鼎合誠知識產權代理有限公司 44281
• 代理人: 宋鷹武

1.一種哈希表的表項添加方法，其特征在于，包括：

將哈希表拆分為多張哈希子表，每一張哈希子表對應一張位圖，每一張位圖對應一個哈希函數；

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

2.如權利要求1所述的方法，其特征在于，所述位圖包含了沖突位和有效位，根據所述哈希值確定當前目標哈希子表所對應的存儲位置是否空位，如是，將所述待存儲表項的信息存入該空位中，否則，更新當前目標哈希子表直至找到空位存儲所述待存儲表項的信息的步驟，包括：

以所述哈希值作為索引，查找所述當前目標哈希子表對應的位圖；

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

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

3.如權利要求2所述的方法，其特征在于，所述以所述哈希值作為索引，查找所述當前目標哈希子表對應的位圖的步驟，包括：

判斷當前目標哈希子表的容量是否小于計算得到的所述哈希值的位數；

如果所述當前目標哈希子表的容量小于計算得到的所述哈希值的位數，則截取所述哈希值，并將截取后的哈希值作為索引，查找所述當前目標哈希子表對應的位圖。

4.如權利要求2所述的方法，其特征在于，將所述待存儲表項的信息存入空位后，還包括：

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

5.如權利要求2所述的方法，其特征在于，更新當前目標哈希子表直至找到空位存儲所述待存儲表項的信息的步驟，包括：

當所述位圖的沖突位為無效，有效位為無效，則將該位圖對應的哈希子表中已存的表項取出，將該沖突位置為有效，并將取出表項的鍵值與當前的待存儲表項的鍵值存入該位圖中；

判斷當前的目標哈希子表是否為最后一張哈希子表，如果不是最后一張哈希子表，則將當前目標哈希子表更新為下一張哈希子表，直至查找到空位存儲所述待存儲表項的信息。

6.如權利要求2所述的方法，其特征在于，更新當前目標哈希子表直至找到空位存儲所述待存儲表項的信息的步驟，包括：

當該位圖的沖突位為有效，則當前的待存儲表項的鍵值直接存入到該位圖中；

判斷當前目標哈希子表是否為最后一張哈希子表，如果不是最后一張哈希子表，則將當前目標哈希子表更新為下一張哈希子表，直至找到空位存儲所述待存儲表項的信息。

7.如權利要求1至6中任意一項所述的方法，其特征在于，還包括：

當所述待存儲表項存儲完成后，同步更新位圖的沖突位信息和哈希子表的信息。

8.如權利要求1至6中任意一項所述的方法，其特征在于，所述哈希子表對應的哈希函數為循環冗余碼校驗函數。

9.如權利要求1至6中任意一項所述的方法，其特征在于，所述多張哈希子表對應的哈希函數之間采用不同的循環冗余碼校驗多項式。

10.一種哈希表的表項刪除方法，其特征在于，哈希表包括多張哈希子表，每一張哈希子表對應一張位圖，每一張位圖對應一個哈希函數，且每張所述位圖包括多個條目，則所述方法包括：

每張位圖所對應的哈希函數并行計算需要刪除的條目的哈希值；

根據計算得到的哈希值，在其各自對應的位圖中并行查找；

將每一張位圖的查找結果順序進行比較，當第一次出現沖突位為無效時，將該位圖的地址對應的哈希子表中的表項取出；

將取出的表項的鍵值與需要查找的鍵值進行比較，如果相同，則將所述表項從所述哈希子表中刪除。

11.如權利要求10所述的方法，其特征在于，刪除表項后還包括；

將對應的位圖的沖突位置為無效，有效位置為有效。