[發明專利]一種哈希表創建方法及系統、計算設備及存儲介質

有效

• 申請號: 201910169079.3
• 申請日: 2019-03-06
• 公開（公告）號: CN109885576B
• 公開（公告）日: 2020-12-01
• 發明（設計）人: 李哈迪;楊林
• 申請（專利權）人: 珠海金山網絡游戲科技有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/903
• 代理公司: 北京智信禾專利代理有限公司 11637
• 代理人: 吳肖肖

1.一種哈希表創建的方法，其特征在于，包括：

基于設定的哈希算法對目標字符串分別進行初始哈希運算，得到各個字符串對應的初始哈希值；

確定目標字符串的數量M及存在沖突的初始哈希值的數量N,根據M和N確定目標字符串的初始哈希值的沖突率y，其中M和N為正整數；

設置哈希值沖突率的容忍度閾值p；

根據所述容忍度閾值p和所述沖突率y確定運算參數的個數n，n為正整數；

選取n個不相等的正整數作為所述哈希算法的運算參數；

基于所述運算參數分別對目標字符串進行哈希運算，得到目標字符串與運算參數對應的運算哈希值；

根據所述初始哈希值與所述運算哈希值構建樹表示，并基于所述樹表示創建對應的哈希表，以用于確定待查詢的目標字符串在所述哈希表中的存儲地址。

2.如權利要求1所述的方法，其特征在于，基于所述運算參數分別對目標字符串進行哈希運算，得到各目標字符串與運算參數對應的運算哈希值包括：

基于每個運算參數對目標字符串進行哈希運算，得到目標字符串與所述運算參數對應的運算哈希值。

3.如權利要求1所述的方法，其特征在于，根據所述初始哈希值與所述運算哈希值構建樹表示包括：

根據目標字符串的初始哈希值為索引在第i個樹表示中查找與所述索引對應的節點，i∈[1,n+1]，n表示運算參數的總數，i和n均為正整數；

若在第i個樹表示中未查找到相應的節點，則以所述初始哈希值和運算哈

希值為關鍵字創建節點，并將所述字符串的首地址添加到所創建節點的節點值中；

若在第i個樹表示中查找到相應的節點，則i的值增加1，判斷i與n+1的大小關系；

若i小于等于n+1，則繼續執行根據目標字符串的初始哈希值為索引在第i個樹表示中查找與所述索引對應的節點步驟；

若i大于n+1，則樹表示的構建過程結束。

4.如權利要求1所述的方法，其特征在于，所述基于所述樹表示創建對應的哈希表包括：

完成一次樹表示的遍歷；

根據遍歷得到的所述樹表示中各節點的信息創建與所述樹表示對應的哈希表。

5.如權利要求4所述的方法，其特征在于，所述根據遍歷得到的所述樹

表示中各節點的信息創建與所述樹表示對應的哈希表包括：

根據所述目標字符串的初始哈希值確定哈希表項索引；

根據所述哈希表項索引從第i個哈希表中查詢對應的哈希表項h，作為當前哈希表項，i∈[1,n+1]，h∈[1,L]，L表示哈希表的長度，n為運算參數的總數，i、L和h均為正整數；

判斷所述哈希表項h的內容是否為空；

當所述哈希表項h內容為空時，將第i個樹表示節點中目標字符串的初始哈希值、運算哈希值和字符串首地址添加到當前哈希表項的表項中；

當所述哈希表項h內容不為空時，則從所述第i個哈希表中查詢對應的哈希表項h=h+1，作為當前哈希表項，繼續執行判斷所述哈希表項h的內容是否為空的步驟。

6.如權利要求1至5中任意一項所述的方法，其特征在于，所述樹表示包括紅黑樹。

7.如權利要求1所述的方法，其特征在于，還包括：

接收字符串地址查詢請求，所述查詢請求中攜帶有待查詢的目標字符串；

基于設定的哈希算法及運算參數對所述待查詢的目標字符串進行哈希運算，得到待查詢的目標字符串的初始哈希值及運算哈希值；

獲取創建完成的哈希表;

根據待查詢的目標字符串的初始哈希值及運算哈希值對哈希表進行檢索，確定所述待查詢的目標字符串的存儲地址。