散列表原理#

散列表（Hash Table）是一種基於陣列的資料結構，透過散列函式將 key 映射為陣列下標，實現 O(1) 時間複雜度的查找。

散列函式#

設計要求#

1. 計算得到的值是非負整數（陣列下標從 0 開始）
2. 相同的 key 必須得到相同的散列值
3. 不同的 key 盡量得到不同的散列值（理想情況，實際無法完全避免衝突）

常見設計方法#

• 資料分析法：根據資料特徵選取部分作為散列值（如手機號後四位）
• 進位相加法：將字串各字元 ASCII 值加權相加
• 直接定址法：key 本身或線性變換作為散列值
• 取模法：hash(key) % table_size

def hash_word(word, table_size):
    hash_value = 0
    for i, char in enumerate(word):
        hash_value += (ord(char) - ord('a')) * (26 ** i)
    return hash_value % table_size

散列衝突#

不同的 key 可能得到相同的散列值，這稱為散列衝突（Hash Collision）。

解決方法一：開放定址法#

衝突時，按某種規則探測下一個空位。

刪除問題：不能直接置空，需標記為 deleted，否則會影響查找。

優點：

• 資料存在陣列中，對 CPU 快取友好
• 序列化簡單

缺點：

• 裝載因子不能太高（建議 < 0.5）
• 刪除麻煩

解決方法二：鏈結串列法#

每個槽位維護一個鏈結串列，衝突的元素串在同一鏈結串列上。

優點：

• 記憶體利用率高
• 對大裝載因子容忍度高（可 > 1）
• 靈活，可改用紅黑樹/跳表優化

缺點：

• 指標佔用額外空間
• 對 CPU 快取不友好

選擇建議：

• 資料量小、裝載因子低 → 開放定址法（如 Java ThreadLocalMap）
• 資料量大、存大物件 → 鏈結串列法（如 Java HashMap）

裝載因子與動態擴容#

裝載因子#

$$裝載因子 = \frac{已存元素數量}{散列表容量}$$

裝載因子越大，衝突概率越高，效能越差。

動態擴容#

當裝載因子超過閾值時，擴容為原來的 2 倍並重新散列。

擴容代價高：需要重新計算所有元素的散列值並搬移。

漸進式擴容（避免卡頓）#

1. 申請新空間，但不立即搬移資料
2. 每次插入時，順便搬移一個舊資料
3. 查詢時同時查新舊兩個表
4. 逐漸完成資料搬移

工業級散列表：Java HashMap#

設計要點#

散列函式#

int hash(Object key) {
    int h = key.hashCode();
    return (h ^ (h >>> 16)) & (capacity - 1);
}

高 16 位與低 16 位異或，使散列更均勻。

散列表 + 鏈結串列的組合#

散列表支援快速查找，但資料無序。若需要按順序走訪，可結合鏈結串列使用。

典型應用#

1. LRU 快取：散列表 + 雙向鏈結串列
2. Redis 有序集合：散列表 + 跳表
3. Java LinkedHashMap：散列表 + 雙向鏈結串列

每個節點包含：
- data: 資料
- prev: 前驅指標（雙向鏈結串列）
- next: 後繼指標（雙向鏈結串列）
- hnext: 散列衝突鏈結串列指標

操作複雜度：
- 查找：O(1)（散列表）
- 刪除：O(1)（雙向鏈結串列）
- 添加：O(1)（尾部插入）