Hash Table

last update: 2025-06-09

Hash Table（雜湊表）是一種透過「鍵（key）」快速存取資料的資料結構，內部透過 Hash Function 將 key 對應到一個陣列索引位置。它廣泛應用於字典、快取、資料庫索引等。

---

一、Hash Table 結構與術語

名稱	說明
key	鍵值，使用者提供的識別符號
value	對應的資料值
hash function	將 key 轉換為陣列索引的函數
bucket	儲存資料的儲存格，可能包含單一或多個元素（如用 linked list 處理衝突）

---

二、基本操作（CRUD）

1. 插入或更新（insert / put / set）

def put(self, key, value):
    index = self.hash_function(key)
    bucket = self.table[index]
    for entry in bucket:
        if entry[0] == key:
            entry[1] = value
            return
    bucket.append([key, value])

2. 讀取資料（get / lookup）

def get(self, key):
    index = self.hash_function(key)
    bucket = self.table[index]
    for entry in bucket:
        if entry[0] == key:
            return entry[1]
    return None

3. 刪除（delete / remove）

def delete(self, key):
    index = self.hash_function(key)
    bucket = self.table[index]
    for i, entry in enumerate(bucket):
        if entry[0] == key:
            del bucket[i]
            return True
    return False

---

三、Hash Function（雜湊函數）

def hash_function(self, key):
    return hash(key) % self.capacity

一個良好的雜湊函數應該具備：

• 高分散性（減少碰撞）

• 快速計算

• 穩定輸出（同樣輸入產生相同結果）

---

四、碰撞處理（Collision Handling）

方法	說明
鏈結法（chaining）	每個 bucket 是一個 linked list，碰撞元素加入尾端
開放定址法（open addressing）	若發生碰撞，尋找下一個空位（如線性探查、二次探查）

---

五、Hash Table 特性

• 插入、查詢、刪除的平均時間複雜度為 O(1)

• 較差雜湊函數可能導致 O(n) 效能下降

• 動態調整容量與重新雜湊（Rehashing）可維持效率

---

六、Hash Table vs Array vs Linked List

特性	Hash Table	Array	Linked List
查找速度	O(1)	O(1)	O(n)
插入效率	O(1)	O(n)	O(1)
支援 key/value	✅	❌	部分支援
儲存方式	非連續	連續	非連續

---

Hash Table 是現代程式語言中 Dictionary、Map、Set 等資料結構的核心基礎，適合用於快速查找、資料關聯與去重等應用。