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

有效

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

1.一種字符串散列表實現方法，其特征在于，包括：

根據字符串長度，將該字符串分發至對應的散列表；該散列表包括數組散列表、數值型散列表和字符型雙散列表；

其中，當該字符串的長度大于或等于第二長度閾值時，將該字符串分發至字符型雙散列表，該字符型雙散列表包括一級散列和二級散列，該一級散列的散列槽存儲該字符串的前綴散列值或完全散列值，以及記錄當前散列槽的存儲狀態的標簽；若該一級散列的散列槽為空，則標識該標簽為空；若該字符串的完全散列值小于或等于該一級散列的散列槽，則將該完全散列值存儲于該一級散列的散列槽，標識該標簽為滿，并使用該字符串的完全散列值進行索引；若該完全散列值大于該一級散列的散列槽，則將該字符串的前綴散列值存儲于該一級散列的散列槽，標識該標簽為溢出，將該完全散列值存儲于該二級散列的散列槽，并使用該前綴散列值和完全散列值進行索引。

2.如權利要求1所述的字符串散列表實現方法，其特征在于，當該字符串的長度小于或等于第一長度閾值時，將該字符串分發至數組散列表，使用數組進行索引，并將該字符串轉為數值型作為索引數組的下標。

3.如權利要求1所述的字符串散列表實現方法，其特征在于，當該字符串的長度大于第一長度閾值且小于該第二長度閾值時，將該字符串分發至數值型散列表，使用該字符串的散列值進行索引，并在該數值型散列表的散列槽末尾字節記錄該字符串到對應槽位的距離。

4.一種字符串散列表實現系統，其特征在于，包括：

字符串分發模塊，用于根據該字符串的長度，將該字符串分發至對應的散列表；該散列表包括數組散列表、數值型散列表和字符型雙散列表；

該字符串分發模塊具體包括：

長字符串散列模塊，用于長字符串散列表實現；其中當該字符串的長度大于或等于第二長度閾值時，將該字符串分發至字符型雙散列表，該字符型雙散列表包括一級散列和二級散列，該一級散列的散列槽存儲該字符串的前綴散列值或完全散列值，以及記錄當前散列槽的存儲狀態的標簽；若該一級散列的散列槽為空，則標識該標簽為空；若該字符串的完全散列值小于或等于該一級散列的散列槽，則將該完全散列值存儲于該一級散列的散列槽，標識該標簽為滿，并使用該字符串的完全散列值進行索引；若該完全散列值大于該一級散列的散列槽，則將該字符串的前綴散列值存儲于該一級散列的散列槽，標識該標簽為溢出，將該完全散列值存儲于該二級散列的散列槽，并使用該前綴散列值和完全散列值進行索引。

5.如權利要求4所述的字符串散列表實現系統，其特征在于，該字符串分發模塊還包括：

極短字符串散列模塊，用于極短字符串散列表實現；其中當該字符串的長度小于或等于第一長度閾值時，將該字符串分發至數組散列表，使用數組進行索引，并將該字符串轉為數值型作為索引數組的下標。

6.如權利要求4所述的字符串散列表實現系統，其特征在于，該字符串分發模塊還包括：

短字符串散列模塊，用于短字符串散列表實現；其中當該字符串的長度大于第一長度閾值且小于該第二長度閾值時，將該字符串分發至數值型散列表，使用該字符串的散列值進行索引，并在該數值型散列表的散列槽末尾字節記錄該字符串到對應槽位的距離。

7.一種可讀存儲介質，存儲有可執行指令，該可執行指令用于執行如權利要求1～3任一項所述的字符串散列表實現方法。

8.一種數據處理裝置，其特征在于，包括：

如權利要求7所述的可讀存儲介質；

處理器，用于調取并執行該可讀存儲介質中的可執行指令，以實現字符串散列表。