[發(fā)明專利]一種哈希表管理方法及裝置、計算機可讀存儲介質(zhì)

在審

• 申請?zhí)枺?/td>: 201710702186.9
• 申請日: 2017-08-16
• 公開（公告）號: CN109947762A
• 公開（公告）日: 2019-06-28
• 發(fā)明（設(shè)計）人: 王曉涇;包闖;閆振林;劉振偉;陳西
• 申請（專利權(quán)）人: 深圳市中興微電子技術(shù)有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 北京安信方達知識產(chǎn)權(quán)代理有限公司 11262
• 代理人: 韓輝峰;李丹

1.一種哈希表管理方法，其特征在于，包括：

創(chuàng)建哈希表，并根據(jù)待寫入哈希表中的若干個表項的大小配置所創(chuàng)建的哈希表的容量；

獲取待寫入哈希表中的若干個表項對應(yīng)的一組關(guān)鍵字，使用若干個哈希函數(shù)分別對該組關(guān)鍵字進行計算，得到若干組預(yù)索引；

選擇沖突最少的一組預(yù)索引，將該組預(yù)索引中的每個預(yù)索引分別除以所配置的哈希表的容量，得到待寫入哈希表中的若干個表項對應(yīng)的最終索引；

將每個待寫入哈希表中的表項寫入該表項對應(yīng)的最終索引對應(yīng)的存儲位置。

2.根據(jù)權(quán)利要求1所述的哈希表管理方法，其特征在于，所述配置的哈希表的容量為所述哈希表存儲的表項個數(shù)。

3.根據(jù)權(quán)利要求1所述的哈希表管理方法，其特征在于，所述將該組預(yù)索引中的每個預(yù)索引分別除以所配置的哈希表的容量，具體包括：

通過若干條除法運算流水線逐個計算每個預(yù)索引除以所配置的哈希表的容量的商。

4.一種計算機可讀存儲介質(zhì)，其特征在于，所述計算機可讀存儲介質(zhì)上存儲有哈希表管理程序，所述哈希表管理程序被處理器執(zhí)行時實現(xiàn)如權(quán)利要求1至3中任一項所述的哈希表管理方法的步驟。

5.一種哈希表管理方法，其特征在于，包括：

獲取要查找的哈希表的表號以及要查找的哈希表中的表項的關(guān)鍵字；

根據(jù)所述要查找的哈希表的表號確定對應(yīng)的用于計算預(yù)索引的哈希函數(shù)，使用所確定的哈希函數(shù)對所述關(guān)鍵字進行計算，得到要查找的哈希表中的表項的預(yù)索引；

將得到的預(yù)索引除以要查找的哈希表的容量，得到要查找的哈希表中的表項的最終索引；

從得到的最終索引對應(yīng)的存儲位置讀取要查找的哈希表中的表項。

6.根據(jù)權(quán)利要求5所述的哈希表管理方法，其特征在于，所述要查找的哈希表的容量為所述哈希表存儲的表項個數(shù)。

7.根據(jù)權(quán)利要求5所述的哈希表管理方法，其特征在于，所述將得到的預(yù)索引除以要查找的哈希表的容量，具體包括：

通過若干條除法運算流水線逐個計算得到的預(yù)索引除以要查找的哈希表的容量的商。

8.一種計算機可讀存儲介質(zhì)，其特征在于，所述計算機可讀存儲介質(zhì)上存儲有哈希表管理程序，所述哈希表管理程序被處理器執(zhí)行時實現(xiàn)如權(quán)利要求5至7中任一項所述的哈希表管理方法的步驟。

9.一種哈希表管理裝置，其特征在于，包括第一配置模塊、第一預(yù)索引計算模塊、第一索引計算模塊和寫入模塊，其中：

第一配置模塊，用于創(chuàng)建哈希表，并根據(jù)待寫入哈希表中的若干個表項的大小配置所創(chuàng)建的哈希表的容量，將所配置的哈希表的容量輸出至第一索引計算模塊；并存儲第一預(yù)索引計算模塊輸出的各個哈希表用于計算預(yù)索引的哈希函數(shù)；

第一預(yù)索引計算模塊，用于獲取待寫入哈希表中的若干個表項對應(yīng)的一組關(guān)鍵字，使用若干個哈希函數(shù)分別對該組關(guān)鍵字進行計算，得到若干組預(yù)索引，選擇沖突最少的一組預(yù)索引，將該組預(yù)索引對應(yīng)的哈希函數(shù)和所述哈希表的對應(yīng)關(guān)系存儲至第一配置模塊，將所選擇的該組預(yù)索引輸出至第一索引計算模塊；

第一索引計算模塊，用于接收來自第一預(yù)索引計算模塊的該組預(yù)索引和來自第一配置模塊的所配置的哈希表的容量，將該組預(yù)索引中的每個預(yù)索引分別除以所配置的哈希表的容量，得到待寫入哈希表中的若干個表項對應(yīng)的最終索引，將得到的最終索引輸出至寫入模塊；

寫入模塊，用于將每個待寫入哈希表中的表項寫入該表項對應(yīng)的最終索引對應(yīng)的存儲位置。

10.一種哈希表管理裝置，其特征在于，包括第二配置模塊、第二預(yù)索引計算模塊、第二索引計算模塊和讀取模塊，其中：

第二配置模塊，用于存儲若干個哈希表的表號、每個哈希表的容量以及每個哈希表用于計算預(yù)索引的哈希函數(shù)；

第二預(yù)索引計算模塊，用于獲取要查找的哈希表的表號以及要查找的哈希表中的表項的關(guān)鍵字，根據(jù)所述要查找的哈希表的表號確定第二配置模塊中對應(yīng)的用于計算預(yù)索引的哈希函數(shù)，使用所確定的哈希函數(shù)對所述關(guān)鍵字進行計算，得到要查找的哈希表中的表項的預(yù)索引，將得到的預(yù)索引輸出至第二索引計算模塊；

第二索引計算模塊，用于接收第二預(yù)索引計算模塊輸出的預(yù)索引，從第二配置模塊讀取要查找的哈希表的容量，將接收的預(yù)索引除以要查找的哈希表的容量，得到要查找的哈希表中的表項的最終索引，將得到的最終索引輸出至讀取模塊；

讀取模塊，用于從得到的最終索引對應(yīng)的存儲位置讀取要查找的哈希表中的表項。