順序/索引/樹形查找皆需「關鍵字比較」。哈希表通過散列函數 F(key) 直接計算存儲地址，實現 O(1) 平均查找。核心映射：存儲位置 = F(關鍵字)。
key1 ≠ key2 但 F(key1) = F(key2)。key1, key2 互為同義詞。| 方法 | 核心公式/思想 | 適用場景 |
|---|---|---|
| 直接定址法 | F(key) = a*key + b | 鍵值連續、範圍小、無衝突 |
| 數字分析法 | 提取鍵值分布均勻的若干位組合 | 鍵值位數大、分布已知 |
| 平方取中法 | 鍵值平方，取中間若干位 | 鍵值分布不均、位數較多 |
| 折疊法 | 鍵值分段疊加（移位/間界疊加）取後幾位 | 鍵值位數多、分布未知 |
| 除留餘數法 | F(key) = key % p (p ≤ 表長, 通常取質數) | 最常用、通用性強 |
| 隨機數法 | F(key) = 隨機函數(key)（偽隨機） | 鍵值長度不一、極度不均 |
衝突發生時，按探測序列尋找下一個空槽位：
f_i(key) = (f(key) + d_i) % m (d_i = 1,2,3... 或二次探測、雙重哈希)
d_i = i，易產生堆積，查找效率驟降。d_i = ±i²，緩解堆積，但可能無法探測到所有槽位。d_i = i * h2(key)，探測序列依鍵值動態，分布最均勻。每個槽位維護一個鏈表，同義詞掛在同一槽位鏈表上：
槽位 9: [key=3, data] → [key=6, data] → NULL
| 維度 | 開放定址法 | 鏈地址法 |
|---|---|---|
| 空間開銷 | 無指針，僅槽位陣列 | 需指針/節點開銷 |
| 負載因子上限 | < 0.7~0.8 | 可 > 1 |
| 衝突性能退化 | 嚴重（堆積） | 緩和（鏈表線性） |
| 刪除操作 | 複雜（懶惰刪除標記） | 簡單（鏈表刪除） |
| 緩存局部性 | 優（連續內存） | 差（指針跳轉） |
| 工程採用 | Python dict、Go map（早期）、Redis 數組 | Java HashMap、C++ unordered_map、Redis 字典 |
α = 元素數 / 槽位數 超過閾值（如 0.75），觸發擴容（通常 ×2）。哈希表以「計算換比較」實現極致查找速度。掌握除留餘數法構造函數、質數選擇、鏈地址法衝突解決、負載因子與擴容機制，是設計高性能快取、索引、去重、計數系統的核心功力。現代工程中，鏈地址法 + 樹化優化 + 漸進式 Rehash 已成主流標準實現範式。
