跳至主要内容

Hash Table / Map

雜湊表（Hash Table / Hash Map）是一種用「鍵（Key）」直接對應到「值（Value）」的資料結構，即 key-value pair 的形式儲存資料。

它最大的特色是讀取、新增、刪除的平均時間複雜度都是 O(1)，速度超快，在 JavaScript 裡 Object 或 Map 就是用 Hash Table 實作，在 Python 則是 Dictionary。

適用情況​

當資料是鍵值對（Key-Value pairs），且你需要像查字典一樣，輸入一個 Key 就要「瞬間（O(1)）」拿到資料時。

  • 快取（Cache / Session）儲存：例如把 API 回傳的結果存起來，Key 是 url，Value 是 data。下次請求時直接拿，不用重新發請求。
  • 根據 ID 查找資料（Lookup Dictionary）：如果你有 10 萬筆使用者資料，需要頻繁用 userId 去找使用者的詳細資料。用 Array 找則要從頭到尾翻（O(n)），用 Hash Map 可以瞬間秒找（O(1)）。
  • 計數器 / 頻率統計：例如「統計一篇文章中，每個單字出現了幾次」。Key 存單字，Value 存次數。
  • 設定檔（Configuration）：例如系統環境設定，環境變數如 {theme: "dark", language: "zh-TW"}。

複雜度​

前面提到讀取、新增、刪除的平均時間複雜度都是 O(1)

  • Access - O(1)
  • Insertion - O(1)
  • Removal - O(1)

Hash Function & Collision​

Hash Table 的運作核心是 Hash Function。當你存入一個 Key 時，Hash Function 會把這個 Key 轉成一個數字（記憶體 index），並把 Value 存進該 index 對應的陣列格子（Bucket）中。

可是記憶體陣列的長度是有限的，而 Key 的組合是無限的。當兩個不同的 Key 經過 Hash Function 計算後，得到同一個 index，這就叫做碰撞（Collision），白話地說就是兩個不同的 key 存到同一個地方去。

當遇到 collision 時，常用以下方式處理：

  • Separate Chaining：在每個格子裡放一個鏈結串列（Linked List）或陣列（Array），發生 collision 時就直接把資料往後排。
  • Open Addressing：如果發現格子被佔用了，就往後找下一個空的格子坐。

實作​

設計 Hash Function 是一門艱深的學問，好的 hash 具備以下條件：

  • 快速，計算時間是 constant time
  • 不容易 collision，output 不會集中在某一特定的 index，而是均勻分散
  • 同樣的 input 會得到同樣的 output

這邊不仔細探討如何設計優良的 Hash Function，用最簡易的方式實作。

class HashTable {
  constructor(size = 50) {
    // 初始化一個固定大小的陣列作為儲存空間
    this.keyMap = new Array(size);
  }

  // 1. 內部雜湊函數：將 Key 轉成 array index (Key 的長度)）
  _hash(key) {
    let total = 0;
    const WEIRD_PRIME = 31; // 使用質數可以減少雜湊衝突的機率
    
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      let char = key[i];
      let value = char.charCodeAt(0) - 96;
      total = (total * WEIRD_PRIME + value) % this.keyMap.length;
    }
    return Math.abs(total);
  }

  // 2. 新增或修改資料：O(1)
  set(key, value) {
    const index = this._hash(key);
    
    // 如果該位置是空的，先初始化一個 array（Separate Chaining）
    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    
    // 檢查 Key 是否已經存在，存在就更新 Value
    for (let i = 0; i < this.keyMap[index].length; i++) {
      if (this.keyMap[index][i][0] === key) {
        this.keyMap[index][i][1] = value;
        return;
      }
    }
    
    // 不存在就直接放入內容 [key, value]
    this.keyMap[index].push([key, value]);
  }

  // 3. 讀取資料：O(1)
  get(key) {
    const index = this._hash(key);
    const bucket = this.keyMap[index];
    
    if (bucket) {
      // 在 array 尋找對應的 key
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) {
          return bucket[i][1]; // 回傳 value
        }
      }
    }
    return undefined; // 找不到回傳 undefined
  }
}

  // 4. 刪除資料：
    // 平均 - O(1) 
    // 最差 - O(n)，當所有資料都衝突在同一個桶子時
  remove(key) {
    const index = this._hash(key);
    const bucket = this.keyMap[index];

    if (bucket) {
      for (let i = 0; i < bucket.length; i++) {
        // 找到對應的 key
        if (bucket[i][0] === key) {
          const removedPair = bucket[i];
          bucket.splice(i, 1); // 將該資料從 array 中移除
          return removedPair[1]; // 回傳被刪除的 value
        }
      }
    }
    return undefined; // 找不到該 key 則回傳 undefined
  }

  // 5. 獲取所有鍵（Keys）：O(m) - m 為 hash table 分配的總容量 (Size)
  keys() {
    let keysArray = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      // 如果桶子裡有資料，就遍歷裡面的 array
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          keysArray.push(this.keyMap[i][j][0]);
        }
      }
    }
    return keysArray;
  }

  // 6. 獲取所有值（Values）：O(m) - 同時幫你過濾掉重複的值
  values() {
    let valuesArray = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          const value = this.keyMap[i][j][1];
          // 避免塞入重複的 Value（可依需求調整是否要不重複）
          if (!valuesArray.includes(value)) {
            valuesArray.push(value);
          }
        }
      }
    }
    return valuesArray;
  }
}
最後於 更新