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

在審

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

本申請公開了一種哈希表管理方法及裝置、計算機可讀存儲介質，包括創建哈希表，并根據待寫入哈希表中的若干個表項的大小配置創建的哈希表的容量；獲取待寫入哈希表中的若干個表項對應的一組關鍵字，使用若干個哈希函數分別對該組關鍵字進行計算，得到若干組預索引；選擇沖突最少的一組預索引，將該組預索引中的每個預索引分別除以配置的哈希表的容量，得到待寫入哈希表中的若干個表項對應的最終索引；將每個待寫入哈希表中的表項寫入計算出的最終索引對應的存儲位置。本發明通過對哈希函數計算出的預索引根據哈希表容量進行再處理，使得計算出的最終索引根據哈希表容量的不同而不同，保證了哈希表存儲空間的靈活分配且計算出的最終索引不越界。

技術領域

本發明涉及通信技術領域，尤其涉及一種哈希表管理方法及裝置、計算機可讀存儲介質。

背景技術

網絡處理器是面向網絡應用領域的專用指令處理器，是面向數據分組處理的、具有特定電路的軟件可編程器件。它將精簡指令集計算機(Reduced Instruction SetComputer，RISC)處理器的低成本、靈活性與專用集成電路(Application SpecificIntegrated Circuits，ASIC)的高性能、可擴展性很好地結合在一起，開發者可以利用網絡處理器實現快速地編程、靈活提供客戶所需功能,它使得網絡系統能夠具備高性能和高靈活性。

哈希(Hash)算法是網絡處理器中常用的一種索引算法，即將每個查找鍵值通過哈希函數計算出對應的索引，查找時通過這些索引，直接查找到所需要的內容。在實際使用的情況中，網絡處理器中用于存儲表項的空間通常有限，如何分配不同哈希表的存儲空間，從而合理利用存儲空間、不造成存儲空間的浪費是一個很關鍵的問題。

發明內容

為了解決上述技術問題，本發明提供了一種哈希表管理方法及裝置、計算機可讀存儲介質，能夠提升存儲表項的空間利用率。

為了達到本發明目的，本發明實施例的技術方案是這樣實現的：

本發明實施例提供了一種哈希表管理方法，包括：

創建哈希表，并根據待寫入哈希表中的若干個表項的大小配置所創建的哈希表的容量；

獲取待寫入哈希表中的若干個表項對應的一組關鍵字，使用若干個哈希函數分別對該組關鍵字進行計算，得到若干組預索引；

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

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

進一步地，所述配置的哈希表的容量為所述哈希表存儲的表項個數。

進一步地，所述將該組預索引中的每個預索引分別除以所配置的哈希表的容量，具體包括：

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

本發明實施例還提供了一種計算機可讀存儲介質，所述計算機可讀存儲介質上存儲有哈希表管理程序，所述哈希表管理程序被處理器執行時實現如以上任一項所述的哈希表管理方法的步驟。

本發明實施例還提供了一種哈希表管理方法，包括：

獲取要查找的哈希表的表號以及要查找的哈希表中的表項的關鍵字；

根據所述要查找的哈希表的表號確定對應的用于計算預索引的哈希函數，使用所確定的哈希函數對所述關鍵字進行計算，得到要查找的哈希表中的表項的預索引；

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

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