哈希表管理方法及裝置的製作方法
2023-06-07 04:56:36
專利名稱：哈希表管理方法及裝置的製作方法
技術領域：
本發明涉及通信領域，具體而言，涉及一種哈希表管理方法及裝置。
背景技術：
在網絡通信領域，表的查找是必不可少的，例如媒體接入控制(Media Access Control，簡稱為MAC)表的查找、地址解析協議(Address Resolution Protocol，簡稱為 ARP)表的查找、訪問控制列表(Access Control List，簡稱為ACL)的查找、多協議標籤交 換(Multi-Protocol Label Switching，簡稱為MPLS)表的查找。為了快速獲得查表結果， 哈希表是一種廣泛應用的方法，利用哈希表，可以一次存取便得到所查記錄。哈希表的基本思想為在記錄的存儲位置和它的關鍵字之間建立一個確定的對應 關係F，使得每個關鍵字和哈希存儲表中一個唯一的存儲地址相對應。因而在查找時，只需 要根據這個對應關係F找到給定值K的像F (K)。若結構中存在與關鍵字K相等的記錄，則 必定在F(K)的存儲位置上，由此，不需要進行比較便可直接取得所查記錄。而對應關係F 就為哈希函數，按照這個基本思想建立的表為哈希表。但是，對不同的關鍵字執行F(K)計算，可能得到同一哈希地址，即keyl興key2，而 F(keyl) =F(key2)，這種現象稱為哈希衝突。為解決哈希衝突，通常做法是在同一哈希地 址下建立哈希桶，每個哈希桶能存儲N個記錄。在查找時，首先通過哈希函數F找到給定值 K的哈希地址F (K)，然後以F (K)為地址讀出其哈希桶內的N個記錄。最後以關鍵字K對讀 出的N個記錄進行精確匹配，如有發現匹配的則查找成功，否則查找失敗。但是，上述解決哈希衝突的方法存在的弊端是，哈希表內的每個記錄都需要存儲 關鍵字K的值，以便在哈希表查找時進行精確匹配。這種方法增加了哈希表的存儲寬度，從 而增加了硬體實現空間，增大了資源消耗。
發明內容
針對相關技術中哈希表內的每個記錄都需要存儲關鍵字的值的問題而提出本發 明，為此，本發明的主要目的在於提供一種哈希表管理方法及裝置，以解決上述問題。為了實現上述目的，根據本發明的一個方面，提供了 一種哈希表管理方法。根據本發明的哈希表管理方法包括獲取待寫入哈希表中的內容的關鍵字；使用 主哈希函數和子哈希函數對關鍵字進行計算，得到哈希表中的空閒記錄的地址；將待寫入 哈希表中的內容和空閒記錄的地址寫入空閒記錄的地址對應的空閒記錄。進一步地，使用主哈希函數和子哈希函數對關鍵字進行計算，得到哈希表中的空 閒記錄的地址包括使用主哈希函數計算關鍵字對應的第一地址；根據第一地址，獲取哈 希表中的哈希桶中的多條空閒記錄；使用子哈希函數計算關鍵字對應的第二地址，其中第 二地址為多條空閒記錄中的一條空閒記錄的地址；確定第二地址為哈希表中的空閒記錄的 地址。進一步地，在使用子哈希函數計算關鍵字對應的第二地址之前，上述方法還包括在多個子哈希函數中確定一個子哈希函數；在多條空閒記錄中寫入確定的子哈希函數在多 個子哈希函數中的序列號。進一步地，根據哈希表的深度和哈希桶的深度確定主哈希函數計算結果的位寬。進一步地，根據空閒記錄的地址的位寬確定子哈希函數計算結果的位寬。為了實現上述目的，根據本發明的一個方面，還提供了 一種哈希表管理方法。根據本發明的哈希表管理方法包括使用主哈希函數和子哈希函數對關鍵字進行 計算，得到哈希表中的空閒記錄的地址；查找寫有空閒記錄的地址的空閒記錄；獲取空閒 記錄中的內容。進一步地，使用主哈希函數和子哈希函數對關鍵字進行計算，得到哈希表中的空 閒記錄的地址包括使用主哈希函數計算關鍵字對應的第一地址；根據第一地址，獲取哈 希表中的哈希桶中的多條空閒記錄；使用子哈希函數計算關鍵字對應的第二地址，其中第 二地址為多條空閒記錄中的一條空閒記錄的地址；確定第二地址為哈希表中的空閒記錄的 地址。進一步地，在使用子哈希函數計算關鍵字對應的第二地址之前，上述方法還包括 在多個子哈希函數中確定一個子哈希函數；在多條空閒記錄中寫入確定的子哈希函數在多 個子哈希函數中的序列號。為了實現上述目的，根據本發明的另一個方面，提供了 一種哈希表管理裝置。根據本發明的哈希表管理裝置包括第一獲取模塊，用於獲取待寫入哈希表中的 內容的關鍵字；第一計算模塊，用於使用主哈希函數和子哈希函數對關鍵字進行計算，得到 哈希表中的空閒記錄的地址；寫入模塊，用於將待寫入哈希表中的內容和空閒記錄的地址 寫入空閒記錄的地址對應的空閒記錄。為了實現上述目的，根據本發明的另一個方面，還提供了 一種哈希表管理裝置。根據本發明的哈希表管理裝置包括第二計算模塊，使用主哈希函數和子哈希函 數對關鍵字進行計算，得到哈希表中的空閒記錄的地址；查找模塊，用於查找寫有空閒記錄 的地址的空閒記錄；第二獲取模塊，用於獲取空閒記錄中的內容。通過本發明，使用主哈希函數和子哈希函數對關鍵字進行計算，從而得到哈希表 中的待寫入的地址，可以充分利用該關鍵字和哈希地址之間的關聯性，從而減少哈希表的 存儲寬度，進而減小硬體實現空間，減小資源消耗。
此處所說明的附圖用來提供對本發明的進一步理解，構成本申請的一部分，本發 明的示意性實施例及其說明用於解釋本發明，並不構成對本發明的不當限定。在附圖中圖1是根據相關技術的哈希表的存儲結構的示意圖；圖2是根據本發明實施例的哈希表的存儲結構的示意圖；圖3是根據本發明實施例的哈希表管理方法的流程圖一；圖4是根據本發明實施例的哈希表管理方法的流程圖二 ；圖5是根據本發明實施例的哈希表建立過程的流程圖；圖6是根據本發明實施例的哈希表查找過程的流程圖；圖7是根據本發明實施例的哈希表管理裝置的結構框圖一；
圖8是根據本發明實施例的哈希表管理裝置的結構框圖二。
具體實施例方式需要說明的是，在不衝突的情況下，本申請中的實施例及實施例中的特徵可以相 互組合。下面將參考附圖並結合實施例來詳細說明本發明。圖2是根據本發明實施例的哈希表的存儲結構的示意圖，如圖2所示，存儲的內容 為子哈希函數選擇位(F_SEL)、子哈希函數計算結果(F_VAL)、哈希表動作(F_ACT)。本發明實施例提供了一種哈希表管理方法。圖3是根據本發明實施例的哈希表管 理方法的流程圖一，如圖3所示，包括如下的步驟S302至步驟S306。步驟S302，獲取待寫入哈希表中的內容的關鍵字。步驟S304，使用主哈希函數和子哈希函數對關鍵字進行計算，得到哈希表中的空 閒記錄的地址。步驟S306，將待寫入哈希表中的內容和空閒記錄的地址寫入空閒記錄的地址對應 的空閒記錄。相關技術中，哈希表內的每個記錄都需要存儲關鍵字的值，以便在哈希表查找時 進行精確匹配。本發明實施例中，使用主哈希函數和子哈希函數對關鍵字進行計算，從而得 到哈希表中的待寫入的地址，這樣可以充分利用該關鍵字和哈希地址之間的關聯性，從而 減少哈希表的存儲寬度，進而減小硬體實現空間，減小資源消耗。優選地，預先規劃出哈希表存儲空間；建立主哈希函數F_MAIN並建立N個子哈希
函數Fl，F2，F3.....Fn ；其中主哈希函數？_默訊和N個子哈希函數(F1, F2，F3. . . Fn)需
要保證能將同一關鍵字K值，映射到不同空間。優選地，每條哈希表中的空閒記錄，需要開闢出如下的比特空間①、η比特空間，記作F_SEL，用於標誌本記錄採用的子哈希函數；2、彡N。當這η 比特空間的值為m時，說明其採用的子哈希函數為Fm ；②、A比特空間，記作F_VAL，用於存儲Fm⑷的值；③、B比特空間，記作F_ACTI0N，用於存儲其他信息，如哈希表命中之後的動作信
肩、^^ ο優選地，使用主哈希函數和子哈希函數對關鍵字進行計算，得到哈希表中的空閒 記錄的地址包括使用主哈希函數計算關鍵字對應的第一地址；根據第一地址，獲取哈希 表中的哈希桶中的多條空閒記錄；使用子哈希函數計算關鍵字對應的第二地址，其中第二 地址為多條空閒記錄中的一條空閒記錄的地址；確定第二地址為哈希表中的空閒記錄的地 址。優選地，在使用子哈希函數計算關鍵字對應的第二地址之前，上述方法還包括在 多個子哈希函數中確定一個子哈希函數；在多條空閒記錄中寫入確定的子哈希函數在多個 子哈希函數中的序列號。具體地，在哈希桶內的空閒記錄的F_SEL域寫入確定的子哈希函數在多個子哈希 函數中的序列號。優選地，根據哈希表的深度和哈希桶的深度確定主哈希函數計算結果的位寬。優選地，根據空閒記錄的地址的位寬確定子哈希函數計算結果的位寬。
本發明實施例還提供了一種哈希表管理方法。圖4是根據本發明實施例的哈希表 管理方法的流程圖二，如圖4所示，包括如下的步驟S402至步驟S406。步驟S402，使用主哈希函數和子哈希函數對關鍵字進行計算，得到哈希表中的空 閒記錄的地址。步驟S404，查找寫有空閒記錄的地址的空閒記錄。步驟S406，獲取空閒記錄中的內容。優選地，使用主哈希函數和子哈希函數對關鍵字進行計算，得到哈希表中的空閒 記錄的地址包括使用主哈希函數計算關鍵字對應的第一地址；根據第一地址，獲取哈希 表中的哈希桶中的多條空閒記錄；使用子哈希函數計算關鍵字對應的第二地址，其中第二 地址為多條空閒記錄中的一條空閒記錄的地址；確定第二地址為哈希表中的空閒記錄的地 址。優選地，在使用子哈希函數計算關鍵字對應的第二地址之前，上述方法還包括在 多個子哈希函數中確定一個子哈希函數；在多條空閒記錄中寫入確定的子哈希函數在多個 子哈希函數中的序列號。下面將結合實例對本發明實施例的實現過程進行詳細描述。圖5是根據本發明實施例的哈希表建立過程的流程圖，如圖5所示，包括如下的步 驟S502至步驟S516。步驟S502，規劃出哈希表存儲空間。步驟S504，建立主哈希函數F_MAIN ；主哈希函數計算結果的位寬取決於哈希表的 深度以及哈希桶的深度。步驟S506，建立N個子哈希函數Fl，F2，F3，F4，... 。子哈希函數的個數一般不 超過哈希桶的深度。各個子哈希函數的計算結果的位寬取決於哈希表項中的F_VAL的位
覓ο步驟S508，判斷是否有哈希表項需要添加，如果是，則進行步驟S510，否則重複進 行步驟S508。步驟S510，將欲存入哈希表的內容，取出關鍵字K，計算F_MAIN⑷。步驟S512，找出對&F_MAIN(K)下的哈希桶內的空閒記錄；步驟S514，挑選一個子哈希函數Fm。步驟S516，將序列號m寫入哈希桶內的空閒記錄的F_SEL域，並將Fm⑷寫入F_ VAL域，同時將相關信息寫入F_ACTI0N，然後返回步驟S508。圖6是根據本發明實施例的哈希表查找過程的流程圖，如圖6所示，包括如下的步 驟S602至步驟S620。步驟S602，對關鍵字K進行F_MAIN(K)計算。步驟S604，置變量η等於1。步驟S606，判斷η是否大於N，如果是則進行步驟S620，否則進行步驟S608。步驟S608，讀出F_MAIN(K)對應的哈希桶內的N個記錄。步驟S610，根據各個哈希桶內的哈希表項的F_SEL，選擇對應的子哈希函數Fm，對 關鍵字K機型Fm (K)。步驟S612，將Rn(K)和哈希記錄的F_VALUE進行比較。
步驟S614，判斷Fm(K)和哈希記錄的F_VALUE是否相等，如果是則進行步驟S616， 否則進行步驟S618，並返回步驟S606。步驟S616，命中，查找成功，讀出對應的F_ACTI0N。步驟S618，將 η 加 1。步驟S620，不命中，查找失敗。需要說明的是，在附圖的流程圖示出的步驟可以在諸如一組計算機可執行指令的 計算機系統中執行，並且，雖然在流程圖中示出了邏輯順序，但是在某些情況下，可以以不 同於此處的順序執行所示出或描述的步驟。本發明實施例提供了 一種哈希表管理裝置，該哈希表管理裝置可以用於實現上述 哈希表管理方法。圖7是根據本發明實施例的哈希表管理裝置的結構框圖一，如圖7所示， 包括第一獲取模塊72，第一計算模塊74和寫入模塊76。下面對其結構進行詳細描述。第一獲取模塊72，用於獲取待寫入哈希表中的內容的關鍵字；第一計算模塊74， 連接至第一獲取模塊72，用於使用主哈希函數和子哈希函數對第一獲取模塊72獲取的關 鍵字進行計算，得到哈希表中的空閒記錄的地址；寫入模塊76，連接至第一計算模塊74，用 於將待寫入哈希表中的內容和第一計算模塊74計算得到的空閒記錄的地址寫入空閒記錄 的地址對應的空閒記錄。本發明實施例提供了 一種哈希表管理裝置，該哈希表管理裝置可以用於實現上述 哈希表管理方法。圖8是根據本發明實施例的哈希表管理裝置的結構框圖二，如圖8所示， 包括第二計算模塊82、查找模塊84和第二獲取模塊86。下面對其結構進行詳細描述。第二計算模塊82，使用主哈希函數和子哈希函數對關鍵字進行計算，得到哈希表 中的空閒記錄的地址；查找模塊84，連接至第二計算模塊82，用於查找寫有第二計算模塊 82計算得到的空閒記錄的地址的空閒記錄；第二獲取模塊86，連接至查找模塊84，用於獲 取查找模塊84查找的空閒記錄中的內容。需要說明的是，裝置實施例中描述的哈希表管理裝置對應於上述的方法實施例， 其具體的實現過程在方法實施例中已經進行過詳細說明，在此不再贅述。 綜上所述，根據本發明的上述實施例，提供了 一種哈希表管理方法及裝置。通過使 用主哈希函數和子哈希函數對關鍵字進行計算，從而得到哈希表中的待寫入的地址，可以 充分利用該關鍵字和哈希地址之間的關聯性，從而減少哈希表的存儲寬度，進而減小硬體 實現空間，減小資源消耗。顯然，本領域的技術人員應該明白，上述的本發明的各模塊或各步驟可以用通用 的計算裝置來實現，它們可以集中在單個的計算裝置上，或者分布在多個計算裝置所組成 的網絡上，可選地，它們可以用計算裝置可執行的程序代碼來實現，從而，可以將它們存儲 在存儲裝置中由計算裝置來執行，或者將它們分別製作成各個集成電路模塊，或者將它們 中的多個模塊或步驟製作成單個集成電路模塊來實現。這樣，本發明不限制於任何特定的 硬體和軟體結合。以上所述僅為本發明的優選實施例而已，並不用於限制本發明，對於本領域的技 術人員來說，本發明可以有各種更改和變化。凡在本發明的精神和原則之內，所作的任何修 改、等同替換、改進等，均應包含在本發明的保護範圍之內。
權利要求
1.一種哈希表管理方法，其特徵在於，包括 獲取待寫入哈希表中的內容的關鍵字；使用主哈希函數和子哈希函數對所述關鍵字進行計算，得到所述哈希表中的空閒記錄 的地址；將所述待寫入哈希表中的內容和所述空閒記錄的地址寫入所述空閒記錄的地址對應 的空閒記錄。
2.根據權利要求1所述的方法，其特徵在於，使用主哈希函數和子哈希函數對所述關 鍵字進行計算，得到所述哈希表中的空閒記錄的地址包括使用所述主哈希函數計算所述關鍵字對應的第一地址； 根據所述第一地址，獲取所述哈希表中的哈希桶中的多條空閒記錄； 使用所述子哈希函數計算所述關鍵字對應的第二地址，其中所述第二地址為所述多條 空閒記錄中的一條空閒記錄的地址；確定所述第二地址為所述哈希表中的空閒記錄的地址。
3.根據權利要求2所述的方法，其特徵在於，在使用所述子哈希函數計算所述關鍵字 對應的第二地址之前，所述方法還包括在多個子哈希函數中確定一個子哈希函數；在所述多條空閒記錄中寫入所述確定的子哈希函數在所述多個子哈希函數中的序列號。
4.根據權利要求2所述的方法，其特徵在於，根據所述哈希表的深度和所述哈希桶的 深度確定所述主哈希函數計算結果的位寬。
5.根據權利要求1所述的方法，其特徵在於，根據所述空閒記錄的地址的位寬確定所 述子哈希函數計算結果的位寬。
6.一種哈希表管理方法，其特徵在於，包括使用主哈希函數和子哈希函數對關鍵字進行計算，得到哈希表中的空閒記錄的地址； 查找寫有所述空閒記錄的地址的空閒記錄； 獲取所述空閒記錄中的內容。
7.根據權利要求6所述的方法，其特徵在於，使用主哈希函數和子哈希函數對關鍵字 進行計算，得到哈希表中的空閒記錄的地址包括使用所述主哈希函數計算所述關鍵字對應的第一地址； 根據所述第一地址，獲取所述哈希表中的哈希桶中的多條空閒記錄； 使用所述子哈希函數計算所述關鍵字對應的第二地址，其中所述第二地址為所述多條 空閒記錄中的一條空閒記錄的地址；確定所述第二地址為所述哈希表中的空閒記錄的地址。
8.根據權利要求7所述的方法，其特徵在於，在使用所述子哈希函數計算所述關鍵字 對應的第二地址之前，所述方法還包括在多個子哈希函數中確定一個子哈希函數；在所述多條空閒記錄中寫入所述確定的子哈希函數在所述多個子哈希函數中的序列號。
9.一種哈希表管理裝置，其特徵在於，包括第一獲取模塊，用於獲取待寫入哈希表中的內容的關鍵字；第一計算模塊，用於使用主哈希函數和子哈希函數對所述關鍵字進行計算，得到所述 哈希表中的空閒記錄的地址；寫入模塊，用於將所述待寫入哈希表中的內容和所述空閒記錄的地址寫入所述空閒記 錄的地址對應的空閒記錄。
10. 一種哈希表管理裝置，其特徵在於，包括第二計算模塊，使用主哈希函數和子哈希函數對關鍵字進行計算，得到哈希表中的空 閒記錄的地址；查找模塊，用於查找寫有所述空閒記錄的地址的空閒記錄； 第二獲取模塊，用於獲取所述空閒記錄中的內容。
全文摘要
本發明公開了一種哈希表管理方法及裝置，該方法包括獲取待寫入哈希表中的內容的關鍵字；使用主哈希函數和子哈希函數對關鍵字進行計算，得到哈希表中的空閒記錄的地址；將待寫入哈希表中的內容和空閒記錄的地址寫入空閒記錄的地址對應的空閒記錄。本發明可以減少哈希表的存儲寬度，進而減小硬體實現空間，減小資源消耗。
文檔編號G06F17/30GK102073733SQ20111002167
公開日2011年5月25日 申請日期2011年1月19日 優先權日2011年1月19日
發明者吳春華 申請人:中興通訊股份有限公司