Hash Table / Map

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

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

白話理解

想像查電話簿或字典，你不會從第一頁翻到最後一頁找某個名字或單字，而是直接翻到對應的字母、對應的區塊。Hash Table 的概念就是這樣：用一個 Hash Function 把 Key「算」出它應該放在哪個位置，之後要找的時候，一樣算一次就能直接跳過去，不用整本翻過一遍。

複雜度

前面提到讀取、新增、刪除的平均時間複雜度都是 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，用最簡易的方式實作。

Python
JavaScript
Java

class HashTable:
    def __init__(self, size=50):
        # 初始化一個固定大小的陣列作為儲存空間
        self.key_map = [None] * size

    # 1. 內部雜湊函數：將 Key 轉成 array index (Key 的長度)）
    def _hash(self, key):
        total = 0
        weird_prime = 31  # 使用質數可以減少雜湊衝突的機率

        for char in key[:100]:
            value = ord(char) - 96
            total = (total * weird_prime + value) % len(self.key_map)
        return abs(total)

    # 2. 新增或修改資料：O(1)
    def set(self, key, value):
        index = self._hash(key)

        # 如果該位置是空的，先初始化一個 array（Separate Chaining）
        if not self.key_map[index]:
            self.key_map[index] = []

        # 檢查 Key 是否已經存在，存在就更新 Value
        for pair in self.key_map[index]:
            if pair[0] == key:
                pair[1] = value
                return

        # 不存在就直接放入內容 [key, value]
        self.key_map[index].append([key, value])

    # 3. 讀取資料：O(1)
    def get(self, key):
        index = self._hash(key)
        bucket = self.key_map[index]

        if bucket:
            # 在 array 尋找對應的 key
            for pair in bucket:
                if pair[0] == key:
                    return pair[1]  # 回傳 value
        return None  # 找不到回傳 None

    # 4. 刪除資料：
    # 平均 - O(1)
    # 最差 - O(n)，當所有資料都衝突在同一個桶子時
    def remove(self, key):
        index = self._hash(key)
        bucket = self.key_map[index]

        if bucket:
            for i, pair in enumerate(bucket):
                # 找到對應的 key
                if pair[0] == key:
                    removed_pair = bucket.pop(i)  # 將該資料從 array 中移除
                    return removed_pair[1]  # 回傳被刪除的 value
        return None  # 找不到該 key 則回傳 None

    # 5. 獲取所有鍵（Keys）：O(m) - m 為 hash table 分配的總容量 (Size)
    def keys(self):
        keys_array = []
        for bucket in self.key_map:
            # 如果桶子裡有資料，就遍歷裡面的 array
            if bucket:
                for pair in bucket:
                    keys_array.append(pair[0])
        return keys_array

    # 6. 獲取所有值（Values）：O(m) - 同時幫你過濾掉重複的值
    def values(self):
        values_array = []
        for bucket in self.key_map:
            if bucket:
                for pair in bucket:
                    value = pair[1]
                    # 避免塞入重複的 Value（可依需求調整是否要不重複）
                    if value not in values_array:
                        values_array.append(value)
        return values_array

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;
  }
}

import java.util.ArrayList;
import java.util.List;

class HashTable {
    private static class Entry {
        String key;
        Object value;

        Entry(String key, Object value) {
            this.key = key;
            this.value = value;
        }
    }

    private List<Entry>[] keyMap;

    @SuppressWarnings("unchecked")
    public HashTable(int size) {
        // 初始化一個固定大小的陣列作為儲存空間
        this.keyMap = new List[size];
    }

    public HashTable() {
        this(50);
    }

    // 1. 內部雜湊函數：將 Key 轉成 array index (Key 的長度)）
    private int hash(String key) {
        int total = 0;
        int weirdPrime = 31; // 使用質數可以減少雜湊衝突的機率

        for (int i = 0; i < Math.min(key.length(), 100); i++) {
            char c = key.charAt(i);
            int value = c - 96;
            total = (total * weirdPrime + value) % this.keyMap.length;
        }
        return Math.abs(total);
    }

    // 2. 新增或修改資料：O(1)
    public void set(String key, Object value) {
        int index = hash(key);

        // 如果該位置是空的，先初始化一個 array（Separate Chaining）
        if (this.keyMap[index] == null) {
            this.keyMap[index] = new ArrayList<>();
        }

        // 檢查 Key 是否已經存在，存在就更新 Value
        for (Entry pair : this.keyMap[index]) {
            if (pair.key.equals(key)) {
                pair.value = value;
                return;
            }
        }

        // 不存在就直接放入內容 [key, value]
        this.keyMap[index].add(new Entry(key, value));
    }

    // 3. 讀取資料：O(1)
    public Object get(String key) {
        int index = hash(key);
        List<Entry> bucket = this.keyMap[index];

        if (bucket != null) {
            // 在 array 尋找對應的 key
            for (Entry pair : bucket) {
                if (pair.key.equals(key)) {
                    return pair.value; // 回傳 value
                }
            }
        }
        return null; // 找不到回傳 null
    }

    // 4. 刪除資料：
    // 平均 - O(1)
    // 最差 - O(n)，當所有資料都衝突在同一個桶子時
    public Object remove(String key) {
        int index = hash(key);
        List<Entry> bucket = this.keyMap[index];

        if (bucket != null) {
            for (int i = 0; i < bucket.size(); i++) {
                // 找到對應的 key
                if (bucket.get(i).key.equals(key)) {
                    Entry removedPair = bucket.remove(i); // 將該資料從 array 中移除
                    return removedPair.value; // 回傳被刪除的 value
                }
            }
        }
        return null; // 找不到該 key 則回傳 null
    }

    // 5. 獲取所有鍵（Keys）：O(m) - m 為 hash table 分配的總容量 (Size)
    public List<String> keys() {
        List<String> keysArray = new ArrayList<>();
        for (int i = 0; i < this.keyMap.length; i++) {
            // 如果桶子裡有資料，就遍歷裡面的 array
            if (this.keyMap[i] != null) {
                for (Entry pair : this.keyMap[i]) {
                    keysArray.add(pair.key);
                }
            }
        }
        return keysArray;
    }

    // 6. 獲取所有值（Values）：O(m) - 同時幫你過濾掉重複的值
    public List<Object> values() {
        List<Object> valuesArray = new ArrayList<>();
        for (int i = 0; i < this.keyMap.length; i++) {
            if (this.keyMap[i] != null) {
                for (Entry pair : this.keyMap[i]) {
                    Object value = pair.value;
                    // 避免塞入重複的 Value（可依需求調整是否要不重複）
                    if (!valuesArray.contains(value)) {
                        valuesArray.add(value);
                    }
                }
            }
        }
        return valuesArray;
    }
}

適用情況

當資料是鍵值對（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"}。
搭配 Prefix Sum 或 Sliding Window：例如記錄「某個前綴和出現過幾次」來判斷子陣列和是否等於特定值，或記錄視窗內元素的出現次數。

常見誤區

誤以為 O(1) 是保證值，而非平均值：Hash Table 的 O(1) 是「平均」時間複雜度。如果 Hash Function 設計不良，導致大量資料集中碰撞（Collision）在同一個 Bucket，最壞情況下讀取、新增、刪除都會退化成 O(n)。
誤以為 Key 的順序有保障：在部分語言或版本中，Hash Table 內部的資料順序不一定等於你塞入的順序（雖然現代 JavaScript 的 Object／Map 已經會保留插入順序，但這是語言的額外保證，不是 Hash Table 這個資料結構本身的特性），如果程式邏輯依賴特定順序，應改用 Array 或明確排序。
用可變（Mutable）物件當 Key：例如直接把一個 array 或物件當作 Key，之後如果內容被修改，會導致算出來的 Hash 值改變，反而找不到原本存進去的資料。Key 應盡量使用不可變的型別，例如字串或數字。

複雜度​

Hash Function & Collision​

實作​

適用情況​

常見誤區​

複雜度

Hash Function & Collision

實作

適用情況

常見誤區