Lecture 07B：雜湊函數、雜湊表與攤銷複雜度

上一節說 與 平均只要 \(\bigO{1}\)——不管裡面有一百個還是一億個元素。 這聽起來像魔法：在 裡找東西要 \(\bigO{n}\)，在排序好的 裡要 \(\bigO{\log n}\)， 怎麼可能不看幾乎所有元素就知道某個鍵在不在？答案是雜湊。隨附程式在 。

核心想法：把鍵變成陣列索引

陣列有一個其他結構都沒有的超能力： 是 \(\bigO{1}\)，不管陣列多大。 如果我們能把任何鍵（字串、座標、學號……）算成一個 \(0 \ldots m-1\) 的整數，就能直接把它放進大小為 \(m\) 的陣列。 這個「算成整數」的函式就是雜湊函數，那個陣列就是雜湊表。

雜湊函數

字串最常用的雜湊是多項式滾動雜湊，也正是 的演算法：

/** h = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]；每步「乘 31 再加下一個字元」。 */
static int goodHash(String s) {
    int h = 0;
    for (int i = 0; i < s.length(); i++) {
        h = 31 * h + s.charAt(i);          // int 會溢位——沒關係，溢位後仍是確定性的
    }
    return h;
}

static int mediocreHash(String s) {        // 只把字元加總：位置資訊丟了
    int h = 0;
    for (char c : s.toCharArray()) h = h + c;
    return h;
}

static int badHash(String s) { return 0; } // 「正確」但沒用：所有鍵撞在同一桶

/** 雜湊值 → 桶索引。floorMod 永遠回傳 0..capacity-1（hashCode 可能是負數！） */
static int bucketOf(int hash, int capacity) {
    return Math.floorMod(hash, capacity);
}

goodHash("hello") = 99162322，String.hashCode() = 99162322
  goodHash(ab) = 3105，goodHash(ba) = 3135
  mediocreHash(ab) = 195，mediocreHash(ba) = 195（碰撞！）
  goodHash(長句) = -609428141（可能是負數）
=== 4. 分布品質：1000 個鍵放進 128 個桶 ===
  goodHash      最擠的桶 =  21 個鍵，空桶 =  28 / 128
  mediocreHash  最擠的桶 =  70 個鍵，空桶 =  73 / 128
  badHash       最擠的桶 = 1000 個鍵，空桶 = 127 / 128
  （理想狀況：1000/128 ≈ 8 個鍵一桶）

• 乘 31 讓位置影響結果（ \(\ne\) ）；31 是奇質數，且 \(31h = 32h - h\) 可以用位移快速計算。

• 三個函式都滿足「尊重等價」與「確定性」，所以都正確；差別全在分布。 讓雜湊表退化成一條鏈結串列——每個操作 \(\bigO{n}\)。

• 加密雜湊（SHA-256 等）為了「無法從雜湊值反推、無法刻意製造碰撞」而設計，慢上幾百倍。 雜湊表不需要這些性質，所以不用加密雜湊。

雜湊表：桶與碰撞

方法一：鏈結（chaining）

每個桶是一條鏈結串列，串著所有雜湊到該桶的 (key, value)。這是 Java 的基本策略。

public class ChainingHashMap<K, V> {
    private static class Node<K, V> {          // (key, value) + 同桶的下一個節點
        final K key;
        V value;
        Node<K, V> next;
        Node(K key, V value, Node<K, V> next) {
            this.key = key; this.value = value; this.next = next;
        }
    }
    private static final double MAX_LOAD_FACTOR = 0.75;
    private Node<K, V>[] buckets;
    private int size = 0;

    private int indexFor(K key, int length) {
        return Math.floorMod(key.hashCode(), length);
    }

    private Node<K, V> findNode(K key) {
        int idx = indexFor(key, this.buckets.length);      // 1. 用 hashCode 找桶
        Node<K, V> n = this.buckets[idx];
        while (n != null) {
            if (n.key.equals(key)) return n;               // 2. 用 equals 確認
            n = n.next;
        }
        return null;
    }

    public V put(K key, V value) {
        Node<K, V> existing = findNode(key);
        if (existing != null) {                            // 已存在：覆蓋，回傳舊值
            V old = existing.value;
            existing.value = value;
            return old;
        }
        int idx = indexFor(key, this.buckets.length);
        this.buckets[idx] = new Node<>(key, value, this.buckets[idx]);   // 插在鏈頭：O(1)
        this.size = this.size + 1;
        if ((double) this.size / this.buckets.length > MAX_LOAD_FACTOR) {
            resize();                                      // 負載因子超標：倍增＋重新雜湊
        }
        return null;
    }

    public V get(K key) {
        Node<K, V> n = findNode(key);
        return n == null ? null : n.value;
    }
}

=== 1. 手刻的鏈結雜湊表 ===
  容量 4，size 3：
    [0] → (Alice, 28) → (Thomas, 25)
    [1] → (Liam, 30)
    [2]
    [3]
  put(Bob) 後容量 8（倍增＋重新雜湊）：
    [0] → (Alice, 28)
    [1] → (Liam, 30)
    [4] → (Thomas, 25)
    [5] → (Bob, 41)
=== 2. 大量資料：鏈保持很短 ===
  100000 個鍵，容量 262144，最長的鏈 = 3

注意擴容後 Thomas 從桶 0 搬到桶 4：桶索引依賴 ， 變了每個鍵都要重新雜湊（rehash）。 十萬個鍵放進 262144 個桶，最長的鏈只有 3——這就是平均 \(\bigO{1}\) 的來源： 每個桶平均只有 \(n/m\) 個元素，只要把 \(n/m\) 壓在常數以下，找一個鍵只需看常數個節點。

方法二：開放定址與線性探測

不用鏈結串列，所有元素直接放在桶陣列裡；碰撞時往下一格找空位（到尾端繞回開頭）。

public boolean add(int x) {
    if (contains(x)) return false;
    if ((this.size + 1) * 2 > this.table.length) resize();   // 負載因子超過 0.5 就倍增
    int i = indexFor(x, this.table.length);
    while (this.table[i] != EMPTY) {                         // 線性探測：往下一格找
        i = (i + 1) % this.table.length;                     // 到尾端就繞回開頭
    }
    this.table[i] = x;
    this.size = this.size + 1;
    return true;
}

負載因子、擴容與攤銷複雜度

擴容一次要 \(\bigO{n}\)（每個元素重新雜湊），看起來會拖垮「\(\bigO{1}\)」的宣稱。 關鍵在於擴容很少發生。這和第 [sec:junit] 節陣列倍增的情況一模一樣，我們用那個更簡單的例子分析：

雜湊表的 rehash 完全同理：桶數倍增、負載因子固定，所以 的攤銷成本是 \(\bigO{1}\)。 這就是為什麼我們說 是「平均 \(\bigO{1}\)」而不是「最差 \(\bigO{1}\)」： 單一次 可能觸發整表重建，但攤平後每次只多付常數。

與 的契約

雜湊表先用 找桶，再用 確認。若你的類別覆寫了 卻沒有覆寫 ， 兩個「相等」的物件會落在不同的桶——放進去，卻找不到：

static class PointNoHash {                      // 錯誤：只覆寫 equals，忘了 hashCode
    final int x, y;
    @Override public boolean equals(Object o) { return o instanceof PointNoHash p && p.x == x && p.y == y; }
}

static class Point {                            // 正確：兩個一起覆寫，且用同一組欄位
    final int x, y;
    @Override public boolean equals(Object o) { return o instanceof Point p && p.x == x && p.y == y; }
    @Override public int hashCode() { return Objects.hash(x, y); }
}

record Coord(int x, int y) {}                   // 正確：record 自動產生一致的 equals 與 hashCode

=== 5. equals/hashCode 契約 ===
  只覆寫 equals：contains(new PointNoHash(1,2)) = false  ← 找不到！
  equals+hashCode：contains(new Point(1,2)) = true
  record：contains(new Coord(1,2)) = true

List<String> key = new ArrayList<>(List.of("a"));
Map<List<String>, Integer> map = new HashMap<>();
map.put(key, 42);
key.add("b");                 // 改變了鍵 → hashCode 變了
map.get(key);                 // null！值還在表裡，卻永遠找不到；size 仍是 1

標準函式庫： 與

Map<String, Integer> wordCount = new HashMap<>();
for (String w : words) {
    wordCount.merge(w, 1, Integer::sum);          // 有就 +1，沒有就放 1（一行完成計數）
}
// {the=3, and=2, bird=1, cat=1, dog=1}（順序不保證）

Set<Integer> seen = new HashSet<>();
for (int d : new int[]{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}) {
    if (!seen.add(d)) System.out.println("重複：" + d);   // add 回傳 false = 已存在
}

三種常用容器的複雜度總表（\(n\) 個元素）：

練習

class StudentId {
    String faculty; int number;
    @Override public boolean equals(Object o) {
        return o instanceof StudentId s && s.faculty.equals(faculty) && s.number == number;
    }
}