學習資源

https://labuladong.online/algo/data-structure-basic/hashtable-with-linked-list/

學習記錄

今天是學習的第 17 天，主要學習了用鏈表加強哈希表（LinkedHashMap）：

在苦痛之路 Day 13 - 哈希表核心原理這個章節中，有提到不能依賴哈希表遍歷的 key 順序，因為哈希表的 key 是無序的。

但在實際應用中，可能需要按照插入順序來遍歷鍵值對 key-value，這就是 LinkedHashMap 要解決的問題。

哈希鏈表（LinkedHashMap）實現思路

哈希表的鍵 key 是無序儲存在底層的 table 陣列中的，並且會根據擴縮容產生變化。

哈希鏈表的思路是：把鍵值對 key-value 用鏈表節點的結構串聯起來，這樣只需要從頭節點 head 開始遍歷鏈表，就能按照插入順序訪問所有鍵了。

為什麼必須用雙鏈表？

• 單鏈表刪除節點需要先找到前驅節點，時間複雜度 O(n)
• 雙鏈表可以直接通過 prev/next 指針完成 O(1) 刪除

// 刪除給定的雙鏈表節點
Node target;

// 在雙鏈表中刪除 target 節點
target.prev.next = target.next;
target.next.prev = target.prev;
target.prev = null;
target.next = null;

學習總結

• 哈希鏈表是給哈希表的值類型套了一層雙鏈表結構
• 哈希鏈表必須使用雙鏈表，做到時間複雜度 O(1) 的刪除操作