雜湊表原理 (Hash Table)#

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

雜湊函式#

設計要求#

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

常見設計方法#

fun hashWord(word: String, tableSize: Int): Int {
    var hash = 0L
    var weight = 1L  // 26^i：每個字元的位權，逐位遞增
    for (ch in word) {
        hash += (ch - 'a') * weight
        weight *= 26   // 注意：長字串時 weight 會超出 Long 範圍而溢位，
                       // 實務上會把 % tableSize 折進每一步以避免溢位
    }
    return (hash % tableSize).toInt()
}

雜湊衝突#

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

開放定址法#

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

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

優點：

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

缺點：

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

鏈結串列法#

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

優點：

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

缺點：

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

選擇建議：

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

碰撞解決法的完整光譜#

前面把碰撞處理分成「開放定址」與「鏈結串列」兩大類。實務上這兩類底下還能再細分，形成一條從「實作最簡單」到「最壞情況最穩」的光譜。把它們攤平在同一張表上對照，最能看出取捨。

鏈結法：從鏈結串列到平衡樹#

最基本的鏈結法把同一個槽的所有元素串成一條鏈結串列。插入快（接在鏈頭即可），但查找得沿著鏈一個一個比對。當大量 key 碰巧落在同一槽（極端情況下全部擠在一起），這條鏈會長到讓查找退化成 O(n)——和沒有雜湊表沒兩樣。

解法是：當某條鏈長到超過閾值時，把它從鏈結串列改建成平衡樹（紅黑樹），讓最壞查找從 O(n) 降到 O(log n)。這正是 Java 8 之後 HashMap 的做法——單一桶內鏈長超過 8 就轉成紅黑樹，元素變少時再轉回鏈結串列。紅黑樹之所以能保證 O(log n)，靠的是它嚴格的高度平衡性質，細節見 紅黑樹。

開放定址：群聚問題#

開放定址不另開鏈，而是在原陣列裡「就近找空位」。線性探測最直觀：槽被佔了就看下一格、再下一格，直到找到空位。

問題出在它的副作用——群聚（clustering）：一旦某段連續的槽被填滿，任何雜湊到這段範圍的 key 都會被迫沿著這段一路探測到尾端，而這又讓佔用區段繼續往後長。連續佔用越長，後續碰撞就越嚴重，形成惡性循環。

緩解的方向是讓探測位置「跳得更開」：

• 二次探測（Quadratic Probing）：步長改用平方數（hash+1²、hash+2²、hash+3²…），避開線性群聚，但雜湊到同一槽的 key 仍走相同探測序列，會有較輕的「二次群聚」。
• 雙重雜湊（Double Hashing）：用第二個雜湊函數算出每個 key 專屬的步長，連探測序列都打散，群聚最少，代價是每次探測要多算一次雜湊。

怎麼選？

• 鏈結法：實作簡單、對裝載因子寬容（裝載因子 > 1 仍可運作），適合資料量大或元素較大的場景。
• 開放定址：資料連續存放、快取友善又省下指標空間，但對裝載因子敏感——一旦逼近滿載，探測成本急速上升，通常需把裝載因子控制在 0.7 以下，並更早觸發擴容。

裝載因子與動態擴容#

裝載因子#

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

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

動態擴容#

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

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

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

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

工業級雜湊表：Java HashMap#

設計要點#

雜湊函式#

fun hashIndex(key: Any?, capacity: Int): Int {
    val h = key.hashCode()  // Kotlin/JVM 的 hashCode() 本就是 32 位 Int，可能為負
    // 高 16 位用「無號右移」(ushr) 後與低位異或，讓高位也參與定址；
    // capacity 為 2 的次方，and (capacity - 1) 等同取模
    val spread = h xor (h ushr 16)
    return spread and (capacity - 1)
}

高 16 位與低 16 位異或，使雜湊更均勻。

雜湊表 + 鏈結串列的組合#

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

典型應用#

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

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