您现在的位置：程式碼之家 >> 編程語言 > >> .NET 網頁程式設計 >> C# >> 關於C#

C# 使用 HashTable 加速物件搜尋：從序列式容器到雜湊表的效能躍升

編輯：關於C#

.NET Framework 大多數容器都是序列式容器：依順序儲存物件。這類容器功能強大——可任意順序儲存任意數量物件。但多功能性以效能為代價。在序列中尋找特定物件所需時間取決於容器物件數量。未排序時，查找時間隨元素數量線性增長：元素翻倍，查找時間翻倍。若已排序，查找時間隨元素數量對數增長：查找時間翻倍需元素數量增長四倍。若使用 Key 搜尋物件，可用比序列式容器更好的方法——雜湊表。

雜湊表運作原理

雜湊表根據稱為 hash 的數字關鍵字將物件儲存在 buckets 中。Hash value 從物件值計算而來。每個不同 hash value 建立新 bucket。尋找物件只需計算其 hash value 並搜尋對應 bucket。快速找到 bucket 即可減少搜尋物件數量。

例：資料結構有客戶記錄，想透過信用卡號搜尋。簡單雜湊函數使用信用卡號後兩位，形成 100 個 buckets (00-99)。只需查詢一個 bucket 即可找到任何記錄，無需查詢所有 buckets。

雜湊表限制

若用信用卡號建立雜湊函數，但想透過姓名查找客戶，需查詢整個雜湊表，花費大量時間。因雜湊表用不同欄位作 Key。且查詢整個雜湊表時，元素不按預期順序排列，而是依 hash value 排列。

實作範例：員工資料庫

假設大公司有上千員工，想用最快方法找到記錄。所有員工的雜湊表可使搜尋最短時間完成。

良好 Hash Key 特性

不變性：相同 Key 必須產生相同 hash value，物件建立後 hash value 不能改變。若改變，在雜湊表找不到對應物件。
均勻分佈：所有物件產生相同 hash value 會導致查找特定物件需更多時間。

.NET Framework 有 178 個類別覆寫 GetHashCode() 以發揮更好作用。所有 .NET FCL 類別實作確保 hash value 較好分佈並遵循唯一性原則。應確認自訂類別與結構是否需覆寫 GetHashCode()。最簡單（通常最好）方法：在 Key 中選取一個不變成員，使用該成員產生的 hash value。

員工資料庫明顯 hash key 為社會安全號 (SSN)。它不變，九位數字可任意運用獲得預期效能。

加入員工至雜湊表

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);
}

SSN 滿足良好 hash key 需求：不變、合理分佈、value 取決於號碼而非參考。（需使用基於 value 的 hash key 避免參考型雜湊問題。）

使用 Hash Key 查找物件

int ssn = Int32.Parse(this.SSN.Text);
Employee currentEmp = (Employee)members[ssn];
if (currentEmp != null) {
    LastName.Text = currentEmp.LastName;
    FirstName.Text = currentEmp.FirstName;
    Salary.Text = currentEmp.Salary.ToString();
} else {
    LastName.Text = "Not Found";
}

C# 中可用陣列語法在雜湊表查找物件。此語法強調恆定時間搜尋概念：陣列存取視為快速操作，而非高成本函數呼叫。