雜湊索引 (Hash Index)
什麼是 Hash Index
利用 Hash 函數把 key 映射到固定範圍的位置，提供 O(1) 等值查詢。
hash(key) → bucket_id → 直接跳到對應 bucket → 找到資料指標
| 能力 | 表現 |
|---|---|
| 等值查詢 | ✅ 極快 O(1)（WHERE id = 123） |
| 範圍查詢 | ❌ 不支援（hash 打亂順序） |
| 排序 | ❌ 不支援（需要全掃並重排） |
結構三要素
1. Hash Function
把任意 key 轉成一個整數（hash code）。
hash(key) = key % NUM_BUCKETS # 簡化示意
好的 hash function 特性：
- 均勻分佈 — 減少碰撞
- 高速計算 — 不成為瓶頸
- 穩定 — 同 key 永遠回傳同結果
2. Hash Table（多個 bucket）
Bucket 0 → [key=8 → row#100], [key=12 → row#250] ← 碰撞
Bucket 1 → [key=5 → row#200]
Bucket 2 → [key=10 → row#300]
Bucket 3 → [key=7 → row#400]
3. Collision Handling
兩個不同 key 落到同一 bucket 時的處理方式。
| 方式 | 做法 |
|---|---|
| Chaining（鏈結法） | bucket 裡放一個 linked list / array，所有同 bucket 的 key 串起來 |
| Open Addressing（開放位址法） | 碰撞時往下一個空位找（線性探測 / 二次探測 / 雙重雜湊） |
查詢流程範例
查詢 id = 12：
1. hash(12) = 0 # 計算 bucket
2. 去 Bucket 0 找 # 其中有 key=8, key=12 兩筆（碰撞）
3. 在 linked list 中比對 key → 找到 key=12
4. 回傳 row#250 的指標 → 到資料頁讀取實際資料
碰撞少時接近 O(1)；碰撞嚴重時退化到 O(n)。
Hash Index vs B-Tree Index
| 特性 | Hash Index | 04-Database-Indexing/02-B-Tree-Index |
|---|---|---|
| 等值查詢 | O(1) 很快 | O(log n) |
| 範圍查詢 | ❌ 不支援 | ✅ 高效（有序） |
| 排序支援 | ❌ 不支援 | ✅ 可直接利用 |
| 寫入開銷 | 低 | 較高（需維持平衡） |
| 空間 | bucket 多時會浪費 | 結構比較緊湊 |
| 擴容 | Rehash 成本高 | 自動分裂節點 |
選擇原則
只做等值查詢 → Hash Index；
可能需要範圍 / 排序 / 前綴 → B-Tree Index（預設選它）。
優缺點
優點
- 等值查詢 O(1) — 精確比任何樹狀結構都快
- 插入快 — 只要算 hash、放進 bucket
- 實作簡單 — 大量現成實作可用
缺點
- 不支援範圍查詢 / 排序 —
WHERE id > 10時要掃全部 bucket - 碰撞必處理 — 影響空間和查詢效能
- Rehash 成本高 — 當 bucket 太滿（load factor 超閾值）需要重建整個表
- 惡意 key 攻擊 — 攻擊者刻意產生大量同 hash 的 key → 全落到同 bucket
→ 查詢退化 O(n)（Hash DoS）→ 需用 salted hash
Simplification-with-exceptions
邊界情況
- 並非所有 RDBMS 都有 Hash Index — MySQL InnoDB 只有 Adaptive Hash Index
（自動的內部優化）；Memory 引擎 才是顯式 Hash Index。PostgreSQL 有明確的
USING HASH語法。 - 分散式系統大量用 Hash — Sharding（
hash(user_id) % N）、Consistent Hashing、
分散式快取（Redis 底層就是 Hash Table）。 - Covering — Hash Index 只能 exact match，無法 covering index
式查詢（欄位不在 hash key 中）。 - Hash join — SQL join 執行計畫中的 Hash Join 也是利用類似概念建立臨時 hash 表。
實際應用
| 系統 | 用在哪裡 |
|---|---|
| MySQL Memory | HEAP 引擎支援 Hash Index |
| InnoDB | 自動的 Adaptive Hash Index（不可手動建） |
| PostgreSQL | CREATE INDEX ... USING HASH（但使用場景有限） |
| Redis | 底層 dict 就是 Hash Table |
| 分散式 Sharding | hash(key) % N 或 02-Distributed-Systems/04-Consistent-Hashing 決定節點 |
| Hash Join | SQL 執行計畫在 join 時臨時建立 hash 表 |
Related Notes
- 04-Database-Indexing/01-Indexing-Overview
- 04-Database-Indexing/02-B-Tree-Index — 範圍查詢場景的替代
- 04-Database-Indexing/03-LSM-Tree
- 02-Distributed-Systems/04-Consistent-Hashing（02-Distributed-Systems）— hash 在分散式 routing 的應用
- 04-Database-Indexing/Practice-Database-Indexing