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

在審

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

本發明公開了一種嵌入式哈希表及其操作方法、遍歷方法和裝置，嵌入式哈希表，包括鏈接法哈希表和包括雙向鏈表；所述雙向鏈表包括若干用于存儲key鍵值的鍵值結點，所述鏈接法哈希表包括若干用于存儲value數據的鏈接結點；各個鍵值結點之間均為雙向連接，且每個鍵值結點與對應的鏈接結點之間為雙向連接。本發明通過在現有鏈接法哈希表的基礎上增加一個雙向鏈表構成雙層結構，且雙向鏈表和鏈接法哈希表分別獨立存儲key鍵值和value數據，使得遍歷操作不同于現有鏈接法哈希表，而是簡化了邏輯，降低了代碼復雜度，提高了哈希表遍歷的效率，其遍歷的算法復雜度為O(n)，與數組遍歷操作相同。

技術領域

本發明涉及數據存儲技術領域，具體涉及一種嵌入式哈希表及其操作方法、遍歷方法和裝置。

背景技術

隨著智能技術和物聯網技術的快速發展，各種設備互聯互通，嵌入式設備開始承擔越來越多的功能，需要集成的模塊越來越多，嵌入式軟件開發的規模和復雜度也越來越高。一方面為了應對軟件功能邏輯的高復雜度，許多在計算機領域比較成熟的數據結構和算法被直接使用在嵌入式設備中，如隊列、鏈表和哈希表等；另一方面目前嵌入式OS(如FreeRTOS和DSP BIOS)無法直接支持一些常見的算法，需要用戶自主實現，但嵌入式設備有限的計算能力和較小的內存資源限制了這些算法的應用及性能。

在嵌入式軟件處理中，數組是最常用的數據結構，比較適合于處理有序的順序數據。哈希表實現簡單，查找速度快，常用于數據檢索等方面。在無序的數據索引實現中，哈希表往往較數組有更大的靈活性和易于理解的表達形式。

現有的鏈接法哈希表如圖1所示，鏈接結點由桶結點elem1～elemM和擴展結點node1～nodeN組成，k-v對的鍵值和數據存儲在每個結點。通常情況下elem1～elemM是靜態結點，node1～nodeN是動態結點。M的大小和哈希表的大小成正比，哈希表越大M值越大。N表示了哈希碰撞的次數，取決于散列函數的選用和k-v對的數量。

鏈接法的遍歷過程是依次讀取elem1～elemM結點和node1～nodeN結點中鍵值和數據。在哈希表較大而實際存儲的k-v較少時效率低下。例如：在一個鍵值為正整數1-65535的無序索引場景下，散列函數使用簡單的鍵值對M取余方法，為了減少哈希碰撞，鏈接法哈希表在設計時取M＝500，假設有100個k-v存儲在哈希表且無碰撞發生N＝0，那么為了遍歷哈希表的所有k-v對，需要依次讀取500個結點的鍵值和數據并判斷有效性。

發明內容

本發明的目的在于提供嵌入式哈希表及構建方法、遍歷方法和遍歷裝置，以解決現有鏈接法哈希表遍歷效率低的問題。

此外，本發明還提供基于上述嵌入式哈希表的構建方法、遍歷方法和遍歷裝置。

本發明通過下述技術方案實現：

嵌入式哈希表，包括鏈接法哈希表，還包括雙向鏈表；

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

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

本申請的發明構思在于：

在現有鏈接法哈希表的基礎上增加一個雙向鏈表，雙向鏈表中的鍵值結點用于存儲key鍵值，鏈接法哈希表的鏈接結點用于存儲value數據，且基于k-v映射關系建立各個鍵值結點之間的雙向連接關系，以及每個鍵值結點與對應的鏈接結點之間的雙向連接關系，及本發明中key鍵值和value數據為獨立存儲，在利用雙向鏈表優先保證高效遍歷的情況下采用鍵值和數據的獨立存儲節約了內存，有效擴大了哈希表在嵌入式軟件中的適用場景。