[發(fā)明專利]一種基于Hash查找CAM的方法

有效

• 申請?zhí)枺?/td>: 201110276822.9
• 申請日: 2011-09-19
• 公開（公告）號: CN102364463A
• 公開（公告）日: 2012-02-29
• 發(fā)明（設(shè)計）人: 周恒釗
• 申請（專利權(quán)）人: 浪潮電子信息產(chǎn)業(yè)股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于Hash查找CAM的方法,?其特征在于CAM給用戶提供讀、寫、查找、移動、檢驗的功能，通過特定的Hash函數(shù)的運算與Hash表中的表項相匹配求得數(shù)據(jù)的位置，再進行數(shù)據(jù)比較后即得到欲查找的地址，具體步驟如下：

通過Hash查找匹配原理，將其邏輯用硬件電路描述，待查數(shù)據(jù)寫入存儲體，???兩結(jié)構(gòu)組合成為內(nèi)容可尋址存儲體，設(shè)計分為以下幾個功能模塊：

1)總線；2)Hash函數(shù)查找表；3)Hash入口表；4)數(shù)據(jù)存儲體；5)匹配電路；6)RAM控制電路；其中：

總線1）是CAM與外部通信的通道，在CAM中總線分為請求總線和響應(yīng)總線；請求總線是一條雙向多路復(fù)用總線，請求總線由命令總線和請求數(shù)據(jù)總線組成，命令總線處理輸入命令，請求總線是主要數(shù)據(jù)通道，所有對CAM的操作命令信號，還有輸入到CAM中的數(shù)據(jù)信號都通過請求總線進行傳輸；

?Hash函數(shù)查找表2）通過查找表的方式對Hash查找函數(shù)邏輯進行，哈希查找步驟為：設(shè)哈希表為HST[0~M-1]，哈希函數(shù)取H（key），解決沖突的方法為R（x）；第一步對給定k值，計算哈希地址?Di=H（k）；若HST為空，則查找失敗；若HST=k，則查找成功；否則，執(zhí)行第二步處理沖突；第二步重復(fù)計算處理沖突的下一個存儲地址?Dk=R（Dk-1），直到HST[Dk]為空，或HST[Dk]=k為止；若HST[Dk]=K，則查找成功，否則查找失??；根據(jù)選擇的沖突處理方法，計算關(guān)鍵字key的下一個存儲地址，若下一個存儲地址仍被占用，則繼續(xù)執(zhí)行第二步，直到找到能用的存儲地址為止；

Hash入口表3）中存放Key值經(jīng)過Hash函數(shù)計算后的Hash_Key以及與之對應(yīng)的數(shù)據(jù)表項入口值；

數(shù)據(jù)存儲體4）作為待查找的數(shù)據(jù)存放區(qū)，根據(jù)系統(tǒng)的數(shù)據(jù)格式確定該存儲體的數(shù)據(jù)寬度和數(shù)據(jù)深度，通過Hash_Key查找到對應(yīng)于數(shù)據(jù)存儲體的地址后，系統(tǒng)通過RAM控制電路6）對該存儲體進行訪存，讀取數(shù)據(jù)表項中的數(shù)據(jù)；

讀取出表項中的數(shù)據(jù)后，通過匹配電路5）將待尋址的內(nèi)容與表項數(shù)據(jù)進行比對，若匹配，則輸出匹配地址，拉高數(shù)據(jù)匹配標志；

查找程序流程如下：

1）根據(jù)輸入的查找數(shù)據(jù)進行hash計算得到Hash?key，用Hash?key去訪問Hash入口表，如果Hash入口表的內(nèi)容為0，則跳到3；如果Hash入口表的內(nèi)容不為0，則跳到2；

2）根據(jù)Hash入口表的內(nèi)容，去訪問CAM數(shù)據(jù)項鏈表，并把查找數(shù)據(jù)同CAM數(shù)據(jù)項鏈表的數(shù)據(jù)一個一個比較，從鏈表頭到鏈表尾，從鏈表頭開始比較，查找不成功，接著查找鏈表的下一項，直到鏈表尾為止，跳到3；查找成功，查找數(shù)據(jù)的值同CAM數(shù)據(jù)項鏈表中一項的值相同，則記錄下此項CAM地址，接著查找鏈表的下一項，如果也成功則比較CAM地址與此前記錄的CAM地址的大小，最終取CAM地址最小者，這樣查找一直到鏈表尾為止，跳到3；

3）查找成功，返回CAM地址和CAM命中的信息，跳到4；查找不成功，返回查找結(jié)束，返回CAM沒有命中的信息，跳到4；

4）操作結(jié)束，返回。