[發明專利]一種字符串散列表實現方法和系統

有效

• 申請號: 201910450998.8
• 申請日: 2019-05-28
• 公開（公告）號: CN110321346B
• 公開（公告）日: 2021-09-21
• 發明（設計）人: 鄭天祺;程學旗;李冰;王征;張志斌;劉悅;趙鵬;郭嘉豐
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 祁建國;梁揮

本發明涉及一種字符串散列表實現方法，包括：根據字符串長度，將該字符串分發至對應的散列表；其中，該散列表包括數組散列表、數值型散列表和字符型雙散列表。本發明使用多種異構散列表存儲字符串，針對不同字符串的長度選擇合適的散列表；同時針對短字符串，將短字符串劃分為固定的幾個長度區間，提高內存空間利用率，利用字符串變長的特性，為每種區間的散列槽預留末尾的1字節空間原地存儲元數據信息；而針對長字符串，使用二級散列表結構，一級散列表通過僅使用部分前綴值計算字符串散列，減少了散列值的計算量；而二級散列表作為一級散列表的沖突鏈存儲表，解決了一級散列表精簡散列計算導致的沖突增大的問題。

技術領域

本發明屬于計算機技術領域，具體涉及一種字符串散列表實現方法和系統。

背景技術

散列表經典的數據結構，廣泛運用在計算機各個領域。對于數據庫應用而言，散列表是核心的數據結構之一，其支撐了數據庫的聚合操作、數據去重操作與連接操作等。隨著互聯網數據爆炸式增長，數據庫中的字符型數據占比逐漸提高，其中包括了用戶瀏覽日志，網頁元數據等等。由于這類數據的長度不定，對散列表的設計提出了新的挑戰。

當前對字符串的散列表實現主要分為兩類：(1)使用指針作為散列鍵存儲于由開放地址或鏈地址實現的散列表中。該類散列表實現簡單，使用方便。對于鏈地址實現的散列表由于其具有鍵的穩定性，能適用于更廣泛的應用場景，因此程序語言標準庫通常直接提供該類散列表的實現；(2)使用Trie樹結構原地存儲字符串實現散列表。該類散列表規避了指針存儲，同時提供字符串的前綴復用，有效地減少了散列表的空間占用率，同時其提供前綴匹配功能，能夠支撐特定的應用場景。

然而，上述現有的字符串散列表分別存在以下問題：一方面，對于使用指針作為鍵的散列表實現，由于每次操作都引入了指針的解引用，這破壞了訪存的連續性，導致性能低于數值型定長鍵散列表；另一方面，使用Trie樹作為字符串散列存儲雖然做到了原地存儲字符串，規避了指針的解引用，但是其數據結構本身的連續性不強，對鍵的檢索引入了樹型結構的遍歷操作，這不僅使得訪存局部性被破壞，還引入了額外的計算開銷，因此其性能甚至要低于由指針實現的字符串散列表。

中國國家發明“一種高效的靜態哈希表實現方法及系統”(申請號：CN201610793354.5)，提出一種高效的靜態哈希表實現方法及系統，包括：1)設定哈希桶大小hash_bit，生成多個數據對，將key[i]和value[i]對應于關鍵字和值；2)根據key[i]值，利用rank操作構建哈希表，并計算C表和D表；3)根據C表和D表計算rank(h)，并根據rank(h)的值存儲相應的key[i]和value[i]；4)根據所要查詢的值key判斷哈希表中是否存在該元素，若存在則在對應存儲位置查詢并返回value值，否則訪問失敗；5)根據步驟4)所得的結果返回結果信息。該發明利用Rank-select算法實現新型靜態哈希表的構建與訪問，可用于內容過濾、信息安全等領域，但沒有提出對字符串哈希優化的技術方案。

發明內容

本發明通過針對不同長度字符串，使用多種異構散列表進行存儲，提出了一種字符串散列表實現方法，解決了現有技術中字符串散列表的性能瓶頸問題。

具體來說，本發明的字符串散列表實現方法包括：根據輸入字符串的長度，將該字符串分發至對應的散列表；該散列表包括數組散列表、數值型散列表和字符型雙散列表。