學習資源

https://labuladong.online/algo/data-structure-basic/hashmap-basic/

學習記錄

今天是學習的第 12 天，主要學習了哈希表核心原理：

哈希表的基本概念

哈希表可以理解為一個加強版的陣列，它通過哈希函式將任意類型的 key 映射到陣列索引，從而實現快速的資料存取。

哈希表的工作原理

• 哈希表的底層實現就是一個陣列（也可稱為 table）
• 透過哈希函式（hash）將 key 轉換為陣列索引 index
• 可以在 O(1) 時間複雜度內進行增刪查改
• key 可以是數字、字串等多種類型

// 哈希表偽程式碼邏輯
class MyHashMap {
    constructor() {
        this.table = new Array(1000).fill(null);
    }

    // 增/改，複雜度 O(1)
    put(key, value) {
        const index = this.hash(key);
        this.table[index] = value;
    }

    // 查，複雜度 O(1)
    get(key) {
        const index = this.hash(key);
        return this.table[index];
    }

    // 刪，複雜度 O(1)
    remove(key) {
        const index = this.hash(key);
        this.table[index] = null;
    }

    // 哈希函式，把 key 轉化成 table 中的合法索引
    // 時間複雜度必須是 O(1)，才能保證上述方法的複雜度都是 O(1)
    hash(key) {
        // ...
    }
}

哈希函式

哈希函式負責將任意長度的輸入（key）轉化為固定長度的輸出（索引）。

如果哈希函式的複雜度是 O(n)，那麼整個哈希表的操作性能都會降至 O(n)，失去哈希表的優勢。

哈希衝突

當兩個不同的 key 通過哈希函式得到相同的索引時，就發生了哈希衝突。

當出現了哈希衝突，有兩種常見的解決方案：

1. 拉鏈法
   • 原理：陣列中每個位置存放一個鏈表
   • 衝突處理：多個 key-value 對儲存在同一個鏈表中
   • 查找過程：計算索引後遍歷對應鏈表
   • 時間複雜度：最壞情況 O(K)，K 為鏈表長度
2. 線性探查法（開放尋址法）
   • 原理：發現衝突時，依序檢查下一個位置
   • 衝突處理：從 index + 1 開始尋找空位置
   • 查找過程：需要連續探查直到找到目標或空位置
   • 時間複雜度：最壞情況 O(K)，K 為連續探查次數

擴容和負載因子

負載因子衡量哈希表的填充程度，計算公式為：

負載因子 = size / table.length

• size：哈希表中 key-value 對的數量
• table.length：底層陣列的容量

擴容時機與影響

• 觸發條件：當負載因子達到預設閾值時
• 擴容過程：創建更大的陣列，重新計算所有元素的位置
• 性能考量：負載因子越大，哈希衝突機率越高，操作效率越低

遍歷順序不可預期

哈希表中鍵的遍歷順序是無序的，因為哈希表的遍歷本質上就是遍歷底層的 table 陣列：

// 哈希表底層的 table 陣列
KVNode[] table = new KVNode[1000];

// 獲取哈希表中的所有鍵
// 我們不能依賴這個 keys 列表的順序
List<KeyType> keys = new ArrayList<>();

for (int i = 0; i < table.length; i++) {
    KVNode node = table[i];
    if (node != null) {
        keys.add(node.key);
    }
}

• 哈希函式讓 key 在陣列中隨機分佈
• 擴容會改變陣列大小，重新計算所有元素位置
• 同一個 key 在不同容量下可能有不同索引

遍歷時禁止修改

• 在 for 迴圈中增刪元素可能觸發擴容
• 擴容會改變整個 table 陣列結構
• 可能導致遍歷行為不可預期

最佳實踐：避免在任何資料結構的遍歷過程中進行修改操作。

Key 必須是不可變型別

只有不可變型別才能作為哈希表的 key。

• 如果 key 的值改變，其哈希值也會改變
• 這會導致無法正確找到原本的鍵值對
• 造成資料意外遺失的嚴重問題

// 可以把不可變型別當作 key
Map<String, AnyOtherType> map1 = new HashMap<>();
Map<Integer, AnyOtherType> map2 = new HashMap<>();

// 不應該把可變類型當作 key
// 注意，這樣寫並不會產生語法錯誤，但程式碼非常容易出 bug
Map<ArrayList<Integer>, AnyOtherType> map3 = new HashMap<>();

學習總結

• 哈希表的底層實現就是一個陣列
• 哈希函式複雜度必須是 O(1)，才能確保其他操作也是 O(1)
• 遍歷順序會因擴容而改變，不可依賴
• key 必須是不可變類型，避免遍歷時修改