C# Dictionary/Hashtable 內部運作原理：GetHashCode 與 Equals 正確實作

Hashtable、Dictionary<TKey, TValue> 等字典集合底層採用雜湊表演算法。鍵值對的儲存位置由 Key 的 GetHashCode() 決定；發生碰撞時再呼叫 Equals() 比對。若自訂類別作為 Key，必須正確覆寫 GetHashCode() 與 Equals()，否則會導致查找失敗、資料遺失或效能退化。

雜湊表核心機制

1. 呼叫 key.GetHashCode() 取得雜湊碼。
2. 雜湊碼經二次運算映射到桶索引。
3. 若桶內已有項目，呼叫 key.Equals(existingKey) 判斷是否相同鍵。
4. 相同鍵 → 更新值；不同鍵 → 連結/開放定址法解決碰撞。

正確覆寫規則

• 相等物件必須有相同雜湊碼：a.Equals(b) == true ⇒ a.GetHashCode() == b.GetHashCode()。
• 雜湊碼應盡量均勻分佈：減少碰撞提升效能。
• 不可變性：參與雜湊碼計算的欄位應為不可變，否則物件放入字典後修改欄位會導致找不到。
• 覆寫 Equals(object)、GetHashCode()、實作 IEquatable<T>、多載 ==/!= 運算子 形成完整相等邏輯。

範例：EmployeeID 作為 Key

public class EmployeeID : IEquatable
{
    public string Id { get; }

    public EmployeeID(string id) => Id = id ?? throw new ArgumentNullException(nameof(id));

    public override int GetHashCode()
    {
        // 使用 StringComparer.OrdinalIgnoreCase 等標準雜湊演算法
        return StringComparer.OrdinalIgnoreCase.GetHashCode(Id);
    }

    public override bool Equals(object obj) => Equals(obj as EmployeeID);

    public bool Equals(EmployeeID other)
    {
        if (other is null) return false;
        return StringComparer.OrdinalIgnoreCase.Equals(Id, other.Id);
    }

    public static bool operator ==(EmployeeID a, EmployeeID b)
        => ReferenceEquals(a, null) ? ReferenceEquals(b, null) : a.Equals(b);
    public static bool operator !=(EmployeeID a, EmployeeID b) => !(a == b);

    public override string ToString() => Id;
}

使用示範

var dict = new Dictionary
{
    [new EmployeeID("A0001")] = new EmployeeData("Johnny", 24, "Male"),
    [new EmployeeID("A0002")] = new EmployeeData("Vicky", 20, "Female")
};

EmployeeID query = new EmployeeID("A0001");
if (dict.TryGetValue(query, out var emp))
    Console.WriteLine($"{emp.Name}, {emp.Age}, {emp.Gender}");

常見錯誤

• 僅覆寫 Equals 未覆寫 GetHashCode → 繼承 object 預設雜湊碼（參考相等），導致邏輯相等但雜湊碼不同，查找失敗。
• 覆寫 GetHashCode 回傳常數（如 return 1;） → 所有物件落入同一桶，退化為 O(n) 線性搜尋。
• 使用可變欄位計算雜湊碼 → 物件放入字典後修改欄位，永久找不到。
• 結構體作為 Key 時未正確實作相等比較 → 預設逐位元比較可能包含填充位元導致誤判。

效能建議

• 優先使用 string、int、Guid 等內建型別作為 Key，已經過高度優化。
• 自訂 Key 類別盡量為 readonly struct 或 sealed class 且所有相關欄位 readonly。
• 大量資料場景考慮使用 Dictionary<TKey, TValue> 而非非泛型 Hashtable，避免裝箱拆箱。