[發明專利]一種嵌入式哈希表及其操作方法、遍歷方法和裝置

在審

• 申請號: 202110341716.8
• 申請日: 2021-03-30
• 公開（公告）號: CN112948642A
• 公開（公告）日: 2021-06-11
• 發明（設計）人: 任文龍;劉嵩義;溫奎;羅勇
• 申請（專利權）人: 四川九洲電器集團有限責任公司
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 成都行之專利代理事務所(普通合伙) 51220
• 代理人: 唐邦英

1.一種嵌入式哈希表，包括鏈接法哈希表，其特征在于，還包括雙向鏈表；

所述雙向鏈表包括若干用于存儲key鍵值的鍵值結點，所述鏈接法哈希表包括若干用于存儲value數據的鏈接結點；

各個鍵值結點之間均為雙向連接，且每個鍵值結點與對應的鏈接結點之間為雙向連接。

2.根據權利要求1所述的一種嵌入式哈希表，其特征在于，所述鍵值結點僅存儲key鍵值且存儲類型為uint32。

3.根據權利要求1所述的一種嵌入式哈希表，其特征在于，所述鏈接結點僅存儲value數據的首地址，存儲類型為指針類型。

4.根據權利要求1-3任一項所述的一種嵌入式哈希表，其特征在于，所述鏈接結點由桶結點elem1～elemM和擴展結點node1～nodeN組成，鍵值結點為key1～keyK，

其中，K值等于哈希表中存儲的k-v對數量，M+N≥K。

5.一種嵌入式哈希表的操作方法，其特征在于，包括查找操作：

S1、基于散列函數計算key鍵值對應的哈希碼，讀取哈希碼對應的鏈接結點；

S2、比較鏈接結點指向的鍵值結點與所查找的key鍵值，判斷key鍵值是否已經存在，若存在則返回鏈接結點中的數據。

6.根據權利要求5所述的一種嵌入式哈希表的操作方法，其特征在于，還包括插入操作：

如果查找操作判斷結果為key鍵值不存在，則進行以下操作：

S3、申請一個新的鍵值結點存儲key鍵值并插入雙向鏈表的首位置，申請一個新的鏈接結點存儲value數據并插入鏈接結點的最后位置；

S4、建立鍵值結點和鏈接結點之間的雙向關系。

7.根據權利要求5所述的一種嵌入式哈希表的操作方法，其特征在于，還包括刪除操作：

基于所查找的鏈接結點讀取其指向的鍵值結點，刪除鍵值結點和鏈接結點，釋放對應的存儲空間。

8.根據權利要求5所述的一種嵌入式哈希表的操作方法，其特征在于，還包括更新操作：

基于查找操作判斷結果，如果key鍵值不存在，則不予處理，如果存在，則直接更新鏈接結點中的數值。

9.一種嵌入式哈希表的遍歷方法，其特征在于，包括以下步驟：

步驟S01：根據雙向鏈表中結束標識判斷是否存在鍵值結點，若不存在則直接結束遍歷；若存在則轉入步驟S02；

步驟S02：讀取鍵值結點中的key鍵值；

步驟S03：根據鍵值結點和鏈接結點的雙向關系，從鍵值結點中找到對應的鏈接結點并讀取鏈接結點中存儲的value數據。

10.一種嵌入式哈希表的遍歷裝置，其特征在于，包括：

判斷單元：用于判斷雙向鏈表中是否存在鍵值結點；

第一讀取單元：用于讀取鍵值結點中的key鍵值；

第二讀取單元：用于讀取鏈接結點中的value數據；

數據處理單元：用于執行具體的數據操作。