[發明專利]處理哈希沖突的方法及系統

無效

• 申請號: 201210405722.6
• 申請日: 2012-10-23
• 公開（公告）號: CN102880724A
• 公開（公告）日: 2013-01-16
• 發明（設計）人: 黃嫻婷;顧祥洪
• 申請（專利權）人: 盛科網絡（蘇州）有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 蘇州威世朋知識產權代理事務所(普通合伙) 32235
• 代理人: 楊林潔

技術領域

本發明涉及網絡通信領域技術，尤其涉及一種處理哈希沖突的方法及系統。

背景技術

哈希（Hash）表是根據關鍵值（key）而直接進行訪問的數據結構，它通過把關鍵碼值映射到表項中一個位置（index）來存儲，以加快數據查找的速度。其中，此映射函數叫做哈希函數（f），而存放記錄的數組便是哈希表，哈希表的數學表達式為：index=f（key）。在網絡通信領域以路由查找為例，哈希函數輸入值（key）的有效范圍是整個地址空間，哈希函數輸出值（Index）有效范圍是系統支持該表項的最大規格。顯然，輸出值的有效范圍遠遠小于輸入值的有效范圍，在這個前提下，無論怎么去構造哈希函數（f），都不可避免會出現key1≠key2，而f（key1）=f（key2）的情況，此情況便為哈希沖突。

現有技術中，除了擴充表項空間和構造更合適的哈希函數以外，常用的解決哈希沖突的方法為“建立公共溢出區”，此方法將發生哈希沖突的數據存放于TCAM（三態可尋址寄存器）里面，然而，上述方法雖然可在一定程度避免哈希沖突的發生，但由于TCAM空間有限，且成本高昂，如果哈希沖突率高，而TCAM空間不足，那么會導致沖突的表項無處存放，額外增設TCAM也勢必提高整個設備的成本。

發明內容

本發明所需解決的技術問題在于提供一種成本低廉的處理哈希沖突的方法。

相應地，本發明還提供一種處理哈希沖突的系統。

為解決上述技術問題，本發明所采取的技術方案為：

一種處理哈希沖突的方法，其包括如下步驟：

S1、將用于存儲哈希數據的表項進行拆分，所述表項包括對應于第一哈希函數的第一表項、對應于第二哈希函數的第二表項；

S2、接收哈希關鍵字，并判斷是否發生哈希沖突，若在第一表項中發生沖突，則按照第二哈希函數將所述哈希關鍵字存儲于第二表項的相應位置；若無沖突，則按照第一哈希函數將所述哈希關鍵字存儲于第一表項的相應位置；

S3、根據所述第一、第二哈希函數，依次在第一、第二表項中查找哈希關鍵字對應的條目。

本發明進一步地，若待存關鍵字在第一、第二表項中均發生哈希沖突，其中，第一表項中相沖突的為第一關鍵字，第二表項中相沖突的為第二關鍵字，則所述步驟S2還包括：將第一關鍵字從第一表項移除，并按照第二哈希函數存儲于第二表項的相應位置；將待存關鍵字按照第一哈希函數存儲于第一表項的相應位置。

本發明進一步地，所述步驟S2在另一實施例中可進行另一種移除方式：將第二關鍵字從第二表項移除，并按照第一哈希函數存儲于第一表項的相應位置；將待存關鍵字按照第二哈希函數存儲于第二表項的相應位置。

本發明進一步地，在所述步驟S2之后，該方法還包括：設置公共溢出區，若待存關鍵字在第一、第二表項仍發生哈希沖突，則將其存儲于所述公共溢出區。

本發明進一步地，所述步驟S3具體為：S31、根據第一哈希函數，在第一表項中相應位置處查找待查哈希關鍵字，若查找成功，則結束查找；若未查找成功，跳轉步驟S32；S32、根據第二哈希函數，在第二表項中相應位置處查找待查哈希關鍵字，若查找成功，則結束查找；若未查找成功，跳轉步驟S33；S33、在所述公共溢出區查找待查哈希關鍵字。

此外，本發明還提供一種處理哈希沖突的系統，其包括如下單元：

表項拆分單元、用于將用于存儲哈希數據的表項進行拆分，所述表項包括對應于第一哈希函數的第一表項、對應于第二哈希函數的第二表項；

哈希存儲單元、用于接收哈希關鍵字，并判斷是否發生哈希沖突，若在第一表項中發生沖突，則按照第二哈希函數將所述哈希關鍵字存儲于第二表項的相應位置；若無沖突，則按照第一哈希函數將所述哈希關鍵字存儲于第一表項的相應位置；

哈希查找單元、用于根據所述第一、第二哈希函數，依次在第一、第二表項中查找哈希關鍵字對應的條目。

本發明進一步地，若待存關鍵字在第一、第二表項中均發生哈希沖突，其中，第一表項中相沖突的為第一關鍵字，第二表項中相沖突的為第二關鍵字，則所述哈希存儲單元還包括一哈希遷移單元，該哈希遷移單元用于：將第一關鍵字從第一表項移除，并按照第二哈希函數存儲于第二表項的相應位置；將待存關鍵字按照第一哈希函數存儲于第一表項的相應位置。

本發明進一步地，在另一實施例中，上述哈希遷移單元也可用于：將第二關鍵字從第二表項移除，并按照第一哈希函數存儲于第一表項的相應位置；將待存關鍵字按照第二哈希函數存儲于第二表項的相應位置。