[發明專利]處理哈希查找沖突問題的方法和裝置

無效

• 申請號: 201010111309.X
• 申請日: 2010-02-10
• 公開（公告）號: CN102147798A
• 公開（公告）日: 2011-08-10
• 發明（設計）人: 李猛;郭玲波
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;H04L12/56;H04L29/06;H04L29/08
• 代理公司: 北京中博世達專利商標代理有限公司 11274
• 代理人: 申健

技術領域

本發明涉及移動通信領域，尤其涉及一種處理哈希查找沖突問題的方法和裝置。

背景技術

現階段，基于哈希函數的查找技術(哈希查找)被廣泛應用在通信領域，通信裝置經常采用基于報文中的關鍵詞進行查找，得到下一步對報文的處理方法。但是，哈希查找存在一個固定的缺陷，就是對于一組關鍵詞，進行哈希運算后，難免會有沖突出現，即不同的關鍵詞經過哈希運算后得到相同的結果。

為了解決哈希查找沖突問題，現有技術提供幾種基本方法：鏈表存儲法、多哈希函數法、完美哈希函數法，以及CAM(Content?Addressable?Memory，內容尋址存儲器)彌補法。

其中，鏈表存儲法將沖突表項存入鏈表中，如圖1所示。該方法對接收到的關鍵字進行哈希運算得到哈希值，根據哈希值查找哈希表，從哈希表得到指向存有沖突表項的鏈表的地址，再使用該地址訪問哈希鏈表，然后遍歷鏈表來查找需要的信息，在惡劣情況下，可能需要很多次存儲器訪問，查找速度很慢。

多哈希函數法是使用多個哈希函數對要查找的關鍵字進行計算后，到對應的多個哈希表中讀取信息進行查找，如圖2所示。當向系統添加信息時，使用第一個哈希函數對關鍵字進行計算得到哈希值，如果對應哈希表的相應位置沒有哈希表項時(無沖突)，則將相應信息存入該位置，其它的哈希函數不進行計算。如果仍然存在沖突，則繼續使用其它哈希函數進行計算，直到無沖突發生。查找時，使用多個哈希函數對關鍵字進行計算，同時獲取對應信息，與待查找的關鍵字進行比較后，找到相應的信息。但是，該方法需要極高的存儲器帶寬，給硬件設計帶來的很大的困難。

完美哈希函數法是根據現有數據庫中存在的表項，動態計算出選取的哈希函數，使用此函數對數據庫中存儲的表項進行計算，得到的哈希值不會存在沖突。由于需要動態計算哈希函數，導致向數據庫中添加關鍵字時速度很慢，在需要快速添加、刪除表項的場景中，基本無法使用。

CAM可以根據提供的關鍵字，通過硬件并行查找，輸出對應信息的存儲地址，然后根據該地址從對應的外部存儲器中返回附屬信息到邏輯控制器中。這樣，只用一次存儲器讀取操作即可獲得需要的信息。正是因為CAM查找的快速性，基于CAM的方法在現有的通訊裝置中，尤其是路由器中被大量應用。但是由于工藝的約束，不能夠制作大容量的CAM芯片，對于大量的數據信息(大于1M的32bit信息)，是不能夠存儲的。另外，對于CAM芯片的成本和功耗也隨著容量的增加而大幅提高。CAM彌補法利用CAM的特性，當某一關鍵字進行哈希運算后發現表項沖突，如圖3所示，則把沖突表項存儲到CAM中，這樣CAM中只需要存儲沖突的表項，則大大減小了對CAM空間的依賴，節約了成本。但是，該方法在大量添加和刪除表項時，使得原來存儲在CAM中的沖突表項，變成了不再沖突的表項，如果不解決動態回收的問題，會導致CAM中存儲的表項越來越多。

發明內容

本發明所要解決的技術問題在于提供一種處理哈希查找沖突問題的方法和裝置，能夠實現CAM中存儲的沖突表項的動態回收。

為解決上述技術問題，本發明處理哈希查找沖突問題的方法和裝置采用如下技術方案：

一種處理哈希查找沖突問題的方法，包括：

采用鏈表方式將沖突的表項存儲到CAM數據單元中；

當哈希數據單元中存儲有所要刪除的表項時，則刪除所述表項，并從CAM數據單元中回收一個表項存儲到所述哈希數據單元中，當哈希數據單元中未存儲所要刪除的表項時，則刪除存儲在CAM數據單元中的所述表項。

一種處理哈希查找沖突問題的裝置，包括：

添加模塊，用于采用鏈表方式將沖突的表項存儲到CAM數據單元中；

刪除模塊，用于當哈希數據單元中存儲有所要刪除的表項時，則刪除所述表項，并從CAM數據單元中回收一個表項存儲到所述哈希數據單元中，當哈希數據單元中未存儲所要刪除的表項時，則刪除存儲在CAM數據單元中的所述表項。

本發明實施例提供的處理哈希查找沖突問題的方法和裝置，通過采用鏈表方式添加和刪除表項，實現了CAM中存儲的沖突表項的動態回收，解決了在進行大量表項更新時，可能造成的存儲在CAM中的表項大量增加的問題。

附圖說明

為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對于本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他的附圖。

圖1為現有技術鏈表存儲法的示意圖；

圖2為現有技術多哈希函數法的示意圖；