.NET Framework中的大多數容器都是序列式容器（sequence containers）：它們按順序存儲對象。這 種類型的容器功能很多——你可以以任何特殊的順序來存儲任意數量的對象。
然而，這種多功能性是以一定的性能為代價的。在一個序列中查找一個特殊的對象所需要的時間取決 於容器中對象的數量。如果我們沒有對容器中元素進行排序，那麼隨著元素數量的增加，你所需要的查找 時間也就直線增加了：如果容器中元素的數量增加了一倍，那麼你用來查找一個特殊元素的時間也就增加 了一倍。然而，如果我們對容器中的元素進行了排序，那麼查找時間就是隨著元素數量的對數而增加的了 ：要使查找一個元素的時間增加一倍，你必須使集合中的元素數量增加四倍。如果你用一個key來搜索對 象，你可以用比序列式容器更好的方法來存儲你的對象。你可以用哈希表（hash table）。
哈希表根據一個叫做hash的數字關鍵字（key）將對象存儲在buckets中。hash value是從對象中的值 計算得來的一個數字。每個不同的hash value都會創建一個新的bucket。要查找一個對象，你只需要計算 這個對象的hash value並搜索相應的bucket就行了。通過快速地找到相應的bucket，就可以減少你需要搜 索的對象數量了。
例如，設想在一個數據結構中有一些客戶記錄，你想通過信用卡號來搜索那些記錄。一個簡單的哈希 函數將運用信用卡號的後兩位數字，這會形成100個buckets——從00到99的每個兩位數的數字都會創建一 個bucket。（同樣，運用後三位數字會創建1000個buckets。）只需要查詢一個bucket，你就可以找到任 何記錄了，而不需要查詢所有的buckets。
然而，同任何事情一樣，並不是一切都這麼簡單的。如果你用信用卡號創建了一個哈希函數，而你想 通過姓名來查找客戶，你就需要查詢整個哈希表，這樣會花很多時間。這是因為哈希表是用一個不同的字 段作為key的。而且，如果你查詢整個哈希表，那麼元素就沒有必要按你期望的順序來排列了。元素是根 據hash value來排列的，而不是根據keys排列的。
在本篇文章中，我將詳述我在前面的文章（“為更好的集合創建類”）中的樣例，讓你修改一條員工 記錄。假設有一個很大的公司，公司裡有上千位員工，你想用最快的方法來找到一條記錄。所有員工的一 個哈希表可以使搜索在最短的時間完成。
一個哈希函數需要有一定的屬性。對於初學者來說，哈希函數必須是不變的。這就是說相同的key必須 生成相同的hash value，一旦創建了對象，hash value就不能改變了。如果hash value改變了，你在哈希 表中就再也找不到相應的對象了。
哈希函數需要的第二個屬性就是能夠平均分配buckets。如果所有的對象都生成相同的hash value，那 麼就需要更多的時間來查找一個特殊的對象。
實際上，這兩個原則是很容易遵循的。在.NET Framework中有178個類重載了GetHashCode()，從而更 好地發揮它們的作用。所有的.NET FCL（Framework Class Library）中類的實現都確保了hash value的 更好的分配，並遵循了唯一性的原則。你應該確定你自己的類和結構是否需要重載GetHashCode()方法。 最簡單的（通常也是最好的）方法就是在key中選取一個不變的成員，並運用那個成員所生成的hash value。
員工數據庫的一個明顯的hash key就是社會保險號（Social Security Number）。它不僅不會改變， 而且九位數的這個號碼也可以讓你任意運用以得到你期望的性能。你可以下載樣例，看看運用hash keys 進行搜索和運用序列式容器進行搜索有什麼不同。
要把員工添加到一個哈希表中，你可以創建一個九位數的號碼並把它作為key：
int hash = 111223333;
for (int i = 0; i < 100; i++)
{
string lastname = "Person" + i.ToString();
e = new Employee ("Employee", lastname, (200-i)*200);
members.Add(hash++, e);
}
社會保險號滿足了一個好的hash key的要求：它不會改變，它可以合理地分配、value取決於號碼而不 是reference。（你需要運用基於value的hash key而不是基於reference的hash key以避免我以前提到過 的問題。）運用這個hash key來查找對象也很簡單：
int ssn = Int32.Parse(this.SSN.Text);
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#中，你可以用數組語法在哈希表中查找對象。該語法強調了恆定時間搜索的概念：你可以把數組 訪問看做是一個快速的操作，而不是一個代價很高的函數調用。
關於哈希表最後的一個重點是，同所有的集合一樣，它們也存儲引用（references）。你不需要任何 額外的工作來更新哈希表中的對象。一旦你引用了哈希表中的一個對象，你可以隨意修改它。記住，同樣 的原則不適用於keys。你可以編寫代碼來改變keys，但如果那個代碼修改了hash value，你就會丟失你的 集合中的對象。
哈希表是很有用的、有效的容器。但是，要有效地運用它們，你需要了解容器和容器中對象的狀態之 間的關系。當你可以用從對象計算得來的不變的value來搜索對象時，哈希表就很有用。如果你用不同的 順序（通過姓名、社會保險號、或年齡）在對象中搜索，那麼哈希表就不那麼有用了。
Bill Wagner是 SRT Solutions 的Windows技術專家。他是 Visual Studio Magazine 的撰稿編輯，也 是 The C# Core Language Little Black Book 一書的作者，這是一本C#開發人員的高級參考書。在16年 的軟件開發實踐中，Bill在許多項目中都是重要的開發人員。他曾為工程和商務應用程序、桌面和Web環 境開發過軟件。他在2D和3D圖象和多媒體軟件方面也很有經驗，包括為The Lion King Animated Storybook開發的視頻回放引擎。他的聯系方式是 [email protected]。
本文配套源碼
