[發明專利]一種哈希表數據沖突處理方法及裝置

有效

• 申請號: 201711261924.7
• 申請日: 2017-12-04
• 公開（公告）號: CN107992577B
• 公開（公告）日: 2020-08-11
• 發明（設計）人: 徐立堅;陶耀東;白巖;于博
• 申請（專利權）人: 奇安信科技集團股份有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2453
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩;李相雨

本發明實施例公開了一種哈希表數據沖突處理方法及裝置，方法包括：若判斷獲知哈希表數據發生沖突，則啟動沖突棧線程和沖突樹線程，根據發生沖突的目標沖突數據對哈希桶中的沖突數據進行檢索；通過沖突棧線程對沖突棧進行檢索，并通過沖突樹線程對沖突樹進行檢索；若判斷獲知沖突棧線程或沖突樹線程檢索到目標沖突數據，則獲取哈希桶中的目標沖突數據。本發明實施例通過啟動沖突棧線程和沖突樹線程對哈希桶中的沖突數據進行檢索，一旦沖突棧線程或沖突樹線程檢索到目標沖突數據，則獲取目標沖突數據，充分利用了現有計算機系統中的多核、多CPU的硬件特性，采用雙線程競爭方式優化了哈希表數據沖突處理時的處理數度，大大提高沖突數據的檢索效率。

技術領域

本發明實施例涉及計算機技術領域，具體涉及一種哈希表數據沖突處理方法及裝置。

背景技術

在各種軟件的開發過程中，經常會用到哈希表，哈希表是根據關鍵碼值(哈希鍵值)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。在實際使用中，網絡設備對網絡數據進行管理時通常通過哈希表來實現數據的快速查找。例如防火墻采用哈希表實現對數據的快速查找。在哈希表查找時，鍵值不同的元素可能會映射到哈希表的同一個地址上，這種現象稱之為沖突，并且這種沖突不可避免。

現有的網絡設備對沖突的處理方法采用紅黑樹較多，其檢索效率為O(log2n)，但是在實際使用過程中，當網絡設備端的數據量較大時，紅黑樹方法的檢索效率仍然過低，無法滿足用戶要求。

發明內容

由于現有方法存在上述問題，本發明實施例提出一種哈希表數據沖突處理方法及裝置。

第一方面，本發明實施例提出一種哈希表數據沖突處理方法，包括：

若判斷獲知哈希表數據發生沖突，則啟動沖突棧線程和沖突樹線程，根據發生沖突的目標沖突數據對哈希桶中的沖突數據進行檢索；

通過所述沖突棧線程對沖突棧進行檢索，并通過所述沖突樹線程對沖突樹進行檢索；

若判斷獲知所述沖突棧線程或所述沖突樹線程檢索到所述目標沖突數據，則獲取所述哈希桶中的所述目標沖突數據。

可選地，所述方法還包括：

若判斷獲知所述沖突棧線程或所述沖突樹線程檢索到所述目標沖突數據，則中止所述沖突棧線程和所述沖突樹線程。

可選地，所述若判斷獲知所述沖突棧線程或所述沖突樹線程檢索到所述目標沖突數據，則獲取所述哈希桶中的所述目標沖突數據之后，還包括：

將所述目標沖突數據存儲至所述沖突棧的棧頂。

可選地，所述方法還包括：

若判斷獲知哈希表中需添加、讀取或刪除目標哈希表數據，則啟動所述沖突樹線程，對應地將所述目標哈希表數據添加進所述哈希表、或從所述哈希表中讀取或刪除所述目標哈希表數據。

可選地，所述若判斷獲知哈希表數據發生沖突，則啟動沖突棧線程和沖突樹線程，根據發生沖突的目標沖突數據對哈希桶中的沖突數據進行檢索，具體包括：

若判斷獲知哈希表數據發生沖突且發生沖突的目標沖突數據首次發生沖突，則將所述目標沖突數據存儲至所述哈希桶。

第二方面，本發明實施例還提出一種哈希表數據沖突處理裝置，包括：

線程啟動模塊，用于若判斷獲知哈希表數據發生沖突，則啟動沖突棧線程和沖突樹線程，根據發生沖突的目標沖突數據對哈希桶中的沖突數據進行檢索；

數據檢索模塊，用于通過所述沖突棧線程對沖突棧進行檢索，并通過所述沖突樹線程對沖突樹進行檢索；