[發明專利]基于散列鏈表的內容尋址方法及相應的存儲器電路

有效

• 申請號: 201210579916.8
• 申請日: 2012-12-27
• 公開（公告）號: CN103064948A
• 公開（公告）日: 2013-04-24
• 發明（設計）人: 田澤;張榮華;張玲;劉航
• 申請（專利權）人: 中國航空工業集團公司第六三一研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F12/02
• 代理公司: 西安智邦專利商標代理有限公司 61211
• 代理人: 王少文

1.一種基于鏈接散列的內容尋址方法，其特征在于：包括以下步驟：

步驟1、用戶定義檢索關鍵字和檢索深度，其中檢索關鍵字位寬為M，檢索關鍵字關聯內容位寬為C，檢索深度為2^S；

步驟2、取檢索關鍵字最高位作為分支BR，從次高位開始依次取3位作為迷你關鍵字MKEY，檢索關鍵字剩余位作為散列地址HASHADD；

步驟3、定義檢索散列函數，將檢索關鍵字作為散列函數的輸入，散列地址HASHADD作為散列函數的結果；

步驟4、構造鏈表存儲器，在鏈表存儲器中動態創建散列函數結果沖突的檢索數據鏈表，其中沖突數目大于1且小于等于4時，創建一級鏈表存儲器，沖突數目大于4時，創建二級鏈表存儲器；鏈表存儲器地址寬度為S/2,存儲器數據寬度為W=4×（關鍵字有效位+迷你關鍵字+偏移地址），存儲4個檢索關鍵字對應的關鍵字有效位#_VAL、迷你關鍵字#_MKEY、偏移地址#_OFFSET，所述#_VAL代表3_VAL，2_VAL，1_VAL，0_VAL；所述#_MKEY代表3_MKEY，2_MKEY，1_MKEY，0_MKEY；所述#_OFFSET代表3_OFFSET，2_OFFSET，1_OFFSET，0_OFFSET；

當3_VAL為1時，鏈表存儲器3_VAL、3_MKEY、3_OFFSET字段為一個有效的數據項對應的檢索信息；當3_VAL為0且3_MKEY為111時，字段3_OFFSET為一個二級鏈表指針；當3_VAL為0且3_MKEY為100時，字段3_OFFSET為下一個空閑鏈表指針；當3_VAL為0且3_MKEY為其他值時，3_MKEY、3_OFFSET字段為無效的數據項；

步驟5、構造鏈表存儲器管理電路，包括位寬為S/2的空閑鏈表頭指針、位寬為S/2的空閑鏈表尾指針、位寬為S/2+1的空閑鏈表計數器、位寬為S/2+1的鏈表使用計數器；

步驟5.1，內容尋址存儲器復位后，空閑鏈表頭指針為0，空閑鏈表尾指針為2^S/2-1，空閑鏈表計數為2^S/2，鏈表初始化狀態信號為0，鏈表使用計數器為2；

步驟5.2，當內容尋址存儲器新增數據項的散列結果沖突，且為第2個或第5個沖突數據項，將動態分配空閑鏈表頭指針作為新的散列沖突數據項存儲位置；當鏈表使用計數器小于2^S/2時，空閑鏈表計數器減1，空閑鏈表頭指針加1，鏈表使用計數器加1；當鏈表使用計數器大于等于2^S/2時，首先按照空閑頭指針訪問鏈表存儲器，將獲取的下一個空閑鏈表指針作為新的空閑鏈表頭指針，然后空閑鏈表計數器減1，鏈表使用計數器不變；

步驟5.3，當內容尋址存儲器刪除某數據項時，如果刪除前該地址散列結果沖突數目為2或5，要求對刪除后的散列沖突數據項排列進行移位，釋放一個鏈表存儲器地址。并將釋放的鏈表存儲器地址作為下一個空閑鏈表指針寫到空閑鏈表尾指針指向的鏈表存儲器地址，然后將釋放的鏈表存儲器地址作為新的空閑鏈表尾指針，然后空閑鏈表計數器加1，鏈表使用計數器不變；

步驟6、構造一個散列存儲器，散列存儲器地址寬度為（M-4），數據寬度＝2×(迷你關鍵字位寬+檢索關鍵字對應的偏移地址位寬+鏈表存儲器地址位寬+鏈表指針有效位)；存儲器數據內容包括位數相等的高字段和低字段，其中高字段對應分支BR=1的數據、低字段對應分支BR=0的數據，字段數據依次為鏈表指針有效位EXL，一級鏈表指針LINK,關鍵字有效位VAL，迷你關鍵字MKEY,偏移地址OFFSET；

步驟7，構造一個內容存儲器，內容存儲器地址寬度S，數據寬度為C；

步驟8，構造一個插入檢索數據計數器，位寬為S，計數器范圍0~2^S，復位初始值為0；

步驟9，獲取與檢索關鍵字相關的所有數據項：

步驟9.1，將散列函數結果作為散列存儲器地址，執行存儲器讀操作，獲取散列存儲器存儲數據；

步驟9.2，根據檢索關鍵字的分支BR的值，相應選擇散列存儲器存儲數據的高字段或低字段進行判斷，具體如下：如果該字段中鏈表指針有效位EXL為1，按照獲取散列存儲器存儲的一級鏈表指針訪問一級鏈表存儲器，執行步驟9.3；如果該字段中鏈表指針有效位EXL為0，執行步驟10；

步驟9.3，執行一級鏈表存儲器讀操作，如果一級鏈表存儲數據字段3_VAL為0且3_MKEY為111，根據字段3_OFFSET對應的二級鏈表指針訪問二級鏈表存儲器,執行步驟9.4，否則執行步驟10；

步驟9.4，執行二級鏈表存儲器讀操作，獲取二級鏈表存儲器檢索數據；

步驟10，將獲取的與檢索關鍵字相關的數據項進行排列和比較：

步驟10.1，如果沒有一級鏈表指針，散列存儲器的分支作為第1個排列數據，第2~8個排列數據以無效數據代替；

如果沒有二級鏈表指針，散列存儲器的分支作為第1個排列數據，一級鏈表存儲器第0、1、2個數據項分別作為第2、3、4個排列數據，第5～8個排列數據以無效數據代替；

如果有一級鏈表指針和二級鏈表指針，散列存儲器的分支作為第1個排列數據，一級鏈表存儲器第0、1、2個數據項分別作為第2、3、4個排列數據，二級鏈表存儲器第0、1、2、3個數據項分別作為第5、6、7、8個排列數據，第1個排列數據位于最左邊，第8個排列數據位于最右邊；

步驟10.2，將檢索關鍵字的迷你關鍵字段與上述8個排列數據中的迷你關鍵字段進行比較，如果上述8個排列數據中的迷你關鍵字段有且只有一個與檢索迷你關鍵字段完全相同，則顯示匹配成功，執行步驟10.3，否則，顯示匹配失敗；

步驟10.3，將匹配成功的排列數據中的偏移地址OFFSET作為內容存儲器地址，訪問內容存儲器，輸出內容存儲器的數據。