C# 使用雜湊表搜尋物件 (1) — HashTable 原理與效能優勢

序列式容器的效能瓶頸

.NET 大多數容器為序列式：按順序儲存，功能強大但查找特定物件耗時隨元素數線性增長（未排序）或對數增長（已排序）。

雜湊表原理

雜湊表依據 hash key 將物件存入 buckets。hash value 由物件數值計算得出，每個不同值對應一個 bucket。查找時只需計算 hash value 並搜尋對應 bucket，大幅減少比較次數。

例：以信用卡號後兩碼為 hash function，建立 100 個 buckets (00~99)。查詢任一筆資料只需檢查單一 bucket，而非掃描所有資料。

限制與權衡

• 若需依「姓名」查詢，但 hash key 為「信用卡號」，則必須掃描整個雜湊表，失去優勢。
• 元素依 hash value 排序，而非 key 排序，無法按預期順序遍歷。

實作範例：員工資料庫

大型公司上千員工，以社會安全號 (SSN) 為 hash key（九位數、不變、分布均勻）。

int hash = 111223333;
for (int i = 0; i < 100; i++) {
    string lastname = "Person" + i.ToString();
    Employee e = new Employee("Employee", lastname, (200-i)*200);
    members.Add(hash++, e);
}

雜湊函數兩大原則

1. 不變性：相同 key 必產生相同 hash value，物件建立後 hash value 不可變，否則找不到對應物件。
2. 均勻分布：避免所有物件落入同一 bucket 導致退化為線性搜尋。

.NET FCL 178 個類別覆寫 GetHashCode() 確保良好分布。自訂類別應視需求覆寫，最簡單方式：選取一個不變成員（如 SSN）直接使用其 hash value。