演算法筆記：哈希函數設計原理、Java 實現與取模陷阱

為什麼需要哈希函數？

紅黑樹查找複雜度 O(log N)。哈希表透過**哈希函數**將鍵映射為整數索引，實現**平均 O(1)** 查找。核心挑戰：

1. 如何計算高質量哈希值（分布均勻、低衝突）
2. 如何解決哈希衝突（鏈址法、開放定址法）

哈希函數的兩大核心屬性

1. 一致性：a.equals(b) ⇒ hash(a) == hash(b)
2. 分散性：!a.equals(b) ⇒ hash(a) != hash(b)（理想情況，實際追求低衝突率）

Java 標準庫型別的 hashCode 實現

Integer

public int hashCode() { return value; }

Double

public int hashCode() {
    long bits = Double.doubleToLongBits(value);
    return (int)(bits ^ (bits >>> 32));
}

String（Horner 多項式法）

public int hashCode() {
    int h = 0;
    for (char c : value) h = 31 * h + c;
    return h;
}

31 的選擇：質數、接近 2 的冪（31*i = (i<<5) - i 編譯器優化）、衝突率低。但 Horner 法易構造衝突（如 "Aa" 與 "BB"），曾導致 HashMap DoS 漏洞（CVE-2012-2739）。

自訂類別 hashCode 實現模板

public class Student {
    private int number;
    private String name;
    private String className;

    @Override
    public int hashCode() {
        int hash = 17;                    // 非零質數種子
        hash = 31 * hash + (name == null ? 0 : name.hashCode());
        hash = 31 * hash + (className == null ? 0 : className.hashCode());
        hash = 31 * hash + number;
        return hash;
    }
    // 必須重寫 equals 保持一致性
}

哈希值映射到陣列索引：取模操作的三種寫法與陷阱

原理：0x7fffffff = 2^31 - 1，保留低 31 位，等效於對正數取模，負數變正數且分布均勻。

進階：更強健的哈希混合（MurmurHash、xxHash）

標準 hashCode 針對一般用途設計。高併發、大數據、安全敏感場景建議使用：

• MurmurHash3：速度極快、分布優異、非加密
• xxHash：更快、質量更高
• SipHash：防哈希洪水攻擊、用於 HashMap 內部（Java 8+、Python、Rust）