原文鏈接：Part 2: The Queue, Stack, and Hashtable
本文是"考察數據結構"系列文章的第二部分，考察了三種研究得最多的數據結構：隊列（Queue)，堆棧（Stack)和哈希表（Hashtable)。正如我們所知，Quenu和Stack其實一種特殊的ArrayList，提供大量不同類型的數據對象的存儲，只不過訪問這些元素的順序受到了限制。Hashtable則提供了一種類數組（array-like)的數據抽象，它具有更靈活的索引訪問。數組需要通過序數進行索引，而Hashtable允許通過任何一種對象索引數據項。
目錄：
簡介
“排隊順序”的工作進程
“反排隊順序”——堆棧數據結構
序數索引限制
System.Collections.Hashtable類
結論
簡介
在第一部分中，我們了解了什么是數據結構，評估了它們各自的性能，并了解了選擇何種數據結構對特定算法的影響。另外我們還了解并分析了數據結構的基礎知識，介紹了一種最常用的數據結構：數組。
數組存儲了同一類型的數據，并通過序數進行索引。數組實際的值是存儲在一段連續的內存空間中，因此讀寫數組中特定的元素非常迅速。
因其具有的同構性及定長性，.Net Framework基類庫提供了ArrayList數據結構，它可以存儲不同類型的數據，并且不需要顯式地指定長度。前文所述，ArrayList本質上是存儲object類型的數組，每次調用Add()方法增加元素，內部的object數組都要檢查邊界，如果超出，數組會自動以倍數增加其長度。
第二部分，我們將繼續考察兩種類數組結構：Queue和Stack。和ArrayList相似，他們也是一段相鄰的內存塊以存儲不同類型的元素，然而在訪問數據時，會受到一定的限制。
之后，我們還將深入了解Hashtable數據結構。有時侯，我們可以把Hashtable看作殺一種關聯數組（associative array)，它同樣是存儲不同類型元素的集合，但它可通過任意對象（例如string)來進行索引，而非固定的序數。
“排隊順序”的工作進程
如果你要創建不同的服務，這種服務也就是通過多種資源以響應多種請求的程序；那么當處理這些請求時，如何決定其響應的順序就成了創建服務的一大難題。通常解決的方案有兩種：
“排隊順序”原則
“基于優先等級”的處理原則
當你在商店購物、銀行取款的時候，你需要排隊等待服務。“排隊順序”原則規定排在前面的比后面的更早享受服務。而“基于優先等級”原則，則根據其優先等級的高低決定服務順序。例如在醫院的急診室，生命垂危的病人會比病情輕的更先接受醫生的診斷，而不用管是誰先到的。
設想你需要構建一個服務來處理計算機所接受到的請求，由于收到的請求遠遠超過計算機處理的速度，因此你需要將這些請求按照他們遞交的順序依此放入到緩沖區中。
一種方案是使用ArrayList，通過稱為nextJobPos的整型變量來指定將要執行的任務在數組中的位置。當新的工作請求進入，我們就簡單使用ArrayList的Add()方法將其添加到ArrayList的末端。當你準備處理緩沖區的任務時，就通過nextJobPos得到該任務在ArrayList的位置值以獲取該任務，同時將nextJobPos累加1。下面的程序實現該算法：
using System;
using System.Collections;
public class JobProcessing
{
private static ArrayList jobs = new ArrayList();
private static int nextJobPos = 0;
public static void AddJob(string jobName)
{
jobs.Add(jobName);
}
public static string GetNextJob()
{
if (nextJobPos > jobs.Count - 1)
return "NO JOBS IN BUFFER";
else
{
string jobName = (string) jobs[nextJobPos];
nextJobPos++;
return jobName;
}
}
public static void Main()
{
AddJob("1");
AddJob("2");
Console.WriteLine(GetNextJob());
AddJob("3");
Console.WriteLine(GetNextJob());
Console.WriteLine(GetNextJob());
Console.WriteLine(GetNextJob());
Console.WriteLine(GetNextJob());
AddJob("4");
AddJob("5");
Console.WriteLine(GetNextJob());
}
}
輸出結果如下：
1
2
3
NO JOBS IN BUFFER
NO JOBS IN BUFFER
4
這種方法簡單易懂，但效率卻可怕得難以接受。因為，即使是任務被添加到buffer中后立即被處理，ArrayList的長度仍然會隨著添加到buffer中的任務而不斷增加。假設我們從緩沖區添加并移除一個任務需要一秒鐘，這意味一秒鐘內每調用AddJob()方法，就要調用一次ArrayList的Add()方法。隨著Add()方法持續不斷的被調用，ArrayList內部數組長度就會根據需求持續不斷的成倍增長。五分鐘后，ArrayList的內部數組增加到了512個元素的長度，這時緩沖區中卻只有不到一個任務而已。照這樣的趨勢發展，只要程序繼續運行，工作任務繼續進入，ArrayList的長度自然會繼續增長。
出現如此荒謬可笑的結果，原因是已被處理過的舊任務在緩沖區中的空間沒有被回收。也即是說，當第一個任務被添加到緩沖區并被處理后，此時ArrayList的第一元素空間應該被再利用。想想上述代碼的工作流程，當插入兩個工作——AddJob("1")和AddJob("2")后——ArrayList的空間如圖一所示：
圖一：執行前兩行代碼后的ArrayList
注意這里的ArrayList共有16個元素，因為ArrayList初始化時默認的長度為16。接下來，調用GetNextJob()方法，移走第一個任務，結果如圖二：
圖二：調用GetNextJob()方法后的ArrayList
當執行AddJob(“3”)時，我們需要添加新任務到緩沖區。顯然，ArrayList的第一元素空間（索引為0）被重新使用，此時在0索引處放入了第三個任務。不過別忘了，當我們執行了AddJob(“3”)后還執行了AddJob(“4”)，緊接著用調用了兩次GetNextJob()方法。如果我們把第三個任務放到0索引處，則第四個任務會被放到索引2處，問題發生了。如圖三：
圖三：將任務放到0索引時，問題發生
現在調用GetNextJob()，第二個任務從緩沖中移走，nextJobPos指針指向索引2。因此，當再一次調用GetNextJob()時，第四個任務會先于第三個被移走，這就有悖于與我們的“排序順序”原則。
問題發生的癥結在于ArrayList是以線形順序體現任務列表的。因此我們需要將新任務添加到就任務的右惻以保證當前的處理順序是正確的。不管何時到達ArrayList的末端，ArrayList都會成倍增長。如果產生產生未被使用的元素，則是因為調用了GetNextJob()方法。
解決之道是使我們的ArrayList成環形。環形數組沒有固定的起點和終點。在數組中，我們用變量來維護數組的起止點。環形數組如圖四所示：
圖四：環形數組圖示
在環形數組中，AddJob()方法添加新任務到索引endPos處（譯注：endPos一般稱為尾指針），之后“遞增”endPos值。GetNextJob()方法則根據頭指針startPos獲取任務，并將頭指針指向null，且“遞增”startPos值。我之所以把“遞增”兩字加上引號，是因為這里所說的“遞增”不僅僅是將變量值加1那么簡單。為什么我們不能簡單地加1呢？請考慮這個例子：當endPos等于15時，如果endPos加1，則endPos等于16。此時調用AddJob()，它試圖去訪問索引為16的元素，結果出現異常IndexOutofRangeException。
事實上，當endPos等于15時，應將endPos重置為0。通過遞增（increment）功能檢查如果傳遞的變量值等于數組長度，則重置為0。解決方案是將變量值對數組長度值求模（取余），increment()方法的代碼如下：
int increment(int variable)
{
return (variable + 1) % theArray.Length;
}
注：取模操作符，如x % y，得到的是x 除以 y后的余數。余數總是在0 到 y-1之間。
這種方法好處就是緩沖區永遠不會超過16個元素空間。但是如果我們要添加超過16個元素空間的新任務呢？就象ArrayList的Add()方法一樣，我們需要提供環形數組自增長的能力，以倍數增長數組的長度。
System.Collection.Queue類
就象我們剛才描述的那樣，我們需要提供一種數據結構，能夠按照“排隊順序”的原則插入和移除元素項，并能最大化的利用內存空間，答案就是使用數據結構Queue。在.Net Framework基類庫中已經內建了該類——System.Collections.Queue類。就象我們代碼中的AddJob()和GetNextJob()方法，Queue類提供了Enqueue()和Dequeue()方法分別實現同樣的功能。
Queue類在內部建立了一個存放object對象的環形數組，并通過head和tail變量指想該數組的頭和尾。默認狀態下，Queue初始化的容量為32，我們也可以通過其構造函數自定義容量。既然Queue內建的是object數組，因此可以將任何類型的元素放入隊列中。
Enqueue（）方法首先判斷queue中是否有足夠容量存放新元素。如果有，則直接添加元素，并使索引tail遞增。在這里tail使用求模操作以保證tail不會超過數組長度。如果空間不夠，則queue根據特定的增長因子擴充數組容量。增長因子默認值為2.0，所以內部數組的長度會增加一倍。當然你也可以在構造函數中自定義該增長因子。
Dequeue()方法根據head索引返回當前元素。之后將head索引指向null，再“遞增”head的值。也許你只想知道當前頭元素的值，而不使其輸出隊列（dequeue，出列），則Queue類提供了Peek()方法。
Queue并不象ArrayList那樣可以隨機訪問，這一點非常重要。也就是說，在沒有使前兩個元素出列之前，我們不能直接訪問第三個元素。（當然，Queue類提供了Contains()方法，它可以使你判斷特定的值是否存在隊列中。）如果你想隨機的訪問數據，那么你就不能使用Queue這種數據結構，而只能用ArrayList。Queue最適合這種情況，就是你只需要處理按照接收時的準確順序存放的元素項。
注：你可以將Queues稱為FIFO數據結構。FIFO意為先進先出（First In, First Out），其意等同于“排隊順序（First come, first served）”。
譯注：在數據結構中，我們通常稱隊列為先進先出數據結構，而堆棧則為先進后出數據結構。然而本文沒有使用First in ,first out的概念，而是first come ,first served。如果翻譯為先進先服務，或先處理都不是很適合。聯想到本文在介紹該概念時，以商場購物時需要排隊為例，索性將其譯為“排隊順序”。我想，有排隊意識的人應該能明白其中的含義吧。那么與之對應的，對于堆棧，只有名為“反排隊順序”，來代表（First Come, Last Served）。希望各位朋友能有更好地翻譯來取代我這個拙劣的詞語。為什么不翻譯為“先進先出”，“先進后出”呢？我主要考慮到這里的英文served，它所包含的含義很廣，至少我們可以將其認為是對數據的處理，因而就不是簡單地輸出那么簡單。所以我干脆避開這個詞語的含義。
“反排隊順序”——堆棧數據結構
Queue數據結構通過使用內部存儲object類型的環形數組以實現“排隊順序”的機制。Queue提供了Enqueue()和Dequeue()方法實現數據訪問。“排隊順序”在處理現實問題時經常用到，尤其是提供服務的程序，例如web服務器，打印隊列，以及其他處理多請求的程序。
在程序設計中另外一個經常使用的方式是“反排隊順序（first come,last served）”。堆棧就是這樣一種數據結構。在.Net Framework基類庫中包含了System.Collection.Stack類，和Queue一樣，Stack也是通過存儲object類型數據對象的內部環形數組來實現。Stack通過兩種方法訪問數據——Push(item)，將數據壓入堆棧；Pop()則是將數據彈出堆棧，并返回其值。
一個Stack可以通過一個垂直的數據元素集合來形象地表示。當元素壓入堆棧時，新元素被放到所有其他元素的頂端，彈出時則從堆棧頂端移除該項。下面兩幅圖演示了堆棧的壓棧和出棧過程。首先按照順序將數據1、2、3壓入堆棧，然后彈出：
圖五：向堆棧壓入三個元素
圖六：彈出所有元素后的Stack
注意Stack類的缺省容量是10個元素，而非Queue的32個元素。和Queue和ArrayList一樣，Stack的容量也可以根據構造函數定制。如同ArrayList，Stack的容量也是自動成倍增長。（回憶一下：Queue可以根據構造函數的可選項設置增長因子。）
注：Stack通常被稱為“LIFO先進后出”或“LIFO后進先出”數據結構。
堆棧：計算機科學中常見的隱喻
現實生活中有很多同Queue相似的例子：DMV（譯注：不知道其縮寫，恕我孤陋寡聞，不知其意）、打印任務處理等。然而在現實生活很難找到和Stack近似的范例，但它在各種應用程序中卻是一種非常重要的數據結構。
設想一下我們用以編程的計算機語言，例如：C#。當執行C#程序時，CLR（公共語言運行時）將調用Stack以跟蹤功能模塊（譯注：這里原文為function，我理解作者的含義不僅僅代表函數，事實上很多編譯器都會調用堆棧以確定其地址）的執行情況。每當調用一個功能模塊，相關信息就會壓入堆棧。調用結束則彈出堆棧。堆棧頂端數據為當前調用功能的信息。（如要查看功能調用堆棧的執行情況，可以在Visual Studio.Net下創建一個項目，設置斷點（breakpoint），在執行調試。當執行到斷點時，會在調試窗口（Debug/Windows/Call Stack）下顯示堆棧信息。
序數索引的限制
我們在第一部分中講到數組的特點是同種類型數據的集合，并通過序數進行索引。即：訪問第i個元素的時間為定值。（請記住此種定量時間被標記為O(1)。）
也許我們并沒有意識到，其實我們對有序數據總是“情有獨鐘”。例如員工數據庫。每個員工以社保號（social security number）為其唯一標識。社保號的格式為DDD-DD-DDDD（D的范圍為數字0——9）。如果我們有一個隨機排列存儲所有員工信息的數組，要查找社保號為111-22-3333的員工，可能會遍歷數組的所有元素——即執行O(n）次操作。更好的辦法是根據社保號進行排序，可將其查找時間縮減為O(log n)。
理想狀態下，我們更愿意執行O(1)次時間就能查找到某員工的信息。一種方案是建立一個巨型的數組，以實際的社保號值為其入口。這樣數組的起止點為000-00-0000到999-99-9999，如下圖所示：
圖七：存儲所有9位數數字的巨型數組
如圖所示，每個員工的信息都包括姓名、電話、薪水等，并以其社保號為索引。在這種方式下，訪問任意一個員工信息的時間均為定值。這種方案的缺點就是空間極度的浪費——共有109，即10億個不同的社保號。如果公司只有1000名員工，那么這個數組只利用了0.0001%的空間。（換個角度來看，如果你要讓這個數組充分利用，也許你的公司不得不雇傭全世界人口的六分之一。）
用哈希函數壓縮序數索引
顯而易見，創建10億個元素數組來存儲1000名員工的信息是無法接受的。然而我們又迫切需要提高數據訪問速度以達到一個常量時間。一種選擇是使用員工社保號的最后四位來減少社保號的跨度。這樣一來，數組的跨度只需要從0000到9999。圖八顯示了壓縮后的數組。
圖八：壓縮后的數組
此方案既保證了訪問耗時為常量值，又充分利用了存儲空間。選擇社保號的后四位是隨機的，我們也可以任意的使用中間四位，或者選擇第1、3、8、9位。
在數學上將這種9位數轉換為4位數成為哈希轉換（hashing）。哈希轉換可以將一個索引器空間（indexers space）轉換為哈希表（hash table）。
哈希函數實現哈希轉換。以社保號的例子來說，哈希函數H()表示為：
H(x) = x 的后四位
哈希函數的輸入可以是任意的九位社保號，而結果則是社保號的后四位數字。數學術語中，這種將九位數轉換為四位數的方法稱為哈希元素映射，如圖九所示：
圖九：哈希函數圖示
圖九闡明了在哈希函數中會出現的一種行為——沖突（collisions）。即我們將一個相對大的集合的元素映射到相對小的集中時時，可能會出現相同的值。例如社保號中所有后四位為0000的均被映射為0000。那么000-99-0000，113-14-0000，933-66-0000，還有其他的很多都將是0000。
看看之前的例子，如果我們要添加一個社保號為123-00-0191的新員工，會發生什么情況？顯然試圖添加該員工會發生沖突，因為在0191位置上已經存在一個員工。
數學標注：哈希函數在數學術語上更多地被描述為f：A->B。其中|A|>|B|，函數f不是一一映射關系，所以之間會有沖突。
顯然沖突的發生會產生一些問題。在下一節，我們會看看哈希函數與沖突發生之間的關系，然后簡單地犯下處理沖突的幾種機制。接下來，我們會將注意力放在System.Collection.Hashtable類，并提供一個哈希表的實現。我們會了解有關Hashtable類的哈希函數，沖突解決機制，以及一些使用Hashtable的例子。
避免和解決沖突
當我們添加數據到哈希表中，沖突是導致整個操作被破壞的一個因素。如果沒有沖突，則插入元素操作成功，如果發生了沖突，就需要判斷發生的原因。由于沖突產生提高了代價，我們的目標就是要盡可能將沖突壓至最低。
哈希函數中沖突發生的頻率與傳遞到哈希函數中的數據分布有關。在我們的例子中，假定社保號是隨機分配的，那么使用最后四位數字是一個不錯的選擇。但如果社保號是以員工的出生年份或出生地址來分配，因為員工的出生年份和地址顯然都不是均勻分配的，那么選用后四位數就會因為大量的重復而導致更大的沖突。
注：對于哈希函數值的分析需要具備一定的統計學知識，這超出了本文討論的范圍。必要地，我們可以使用K維（k slots）的哈希表來保證避免沖突，它可以將一個隨機值從哈希函數的域中映射到任意一個特定元素，并限定在1/k的范圍內。（如果這讓你更加的糊涂，千萬別擔心！）
我們將選擇合適的哈希函數的方法成為沖突避免機制（collision avoidance），已有許多研究設計這一領域，因為哈希函數的選擇直接影響了哈希表的整體性能。在下一節，我們會介紹在.Net Framework的Hashtable類中對哈希函數的使用。
有很多方法處理沖突問題。最直接的方法，我們稱為“沖突解決機制”（collision resolution），是將要插入到哈希表中的對象放到另外一塊空間中，因為實際的空間已經被占用了。其中一種最簡單的方法稱為“線性挖掘”（linear probing），實現步驟如下：
1． 當要插入一個新的元素時，用哈希函數在哈希表中定位；
2． 檢查表中該位置是否已經存在元素，如果該位置內容為空，則插入并返回，否則轉向步驟3。
3． 如果該地址為i，則檢查i+1是否為空，如果已被占用，則檢查i+2，依此類推，知道找到一個內容為空的位置。
例如：如果我們要將五個員工的信息插入到哈希表中：Alice(333-33-1234)，Bob(444-44-1234), Cal (555-55-1237), Danny (000-00-1235), and Edward (111-00-1235)。當添加完信息后，如圖十所示：
圖十：有相似社保號的五位員工
Alice的社保號被“哈希（這里做動詞用，譯注）”為1234，因此存放位置為1234。接下來來，Bob的社保號也被“哈希”為1234，但由于位置1234處已經存在Alice的信息，所以Bob的信息就被放到下一個位置——1235。之后，添加Cal，哈希值為1237，1237位置為空，所以Cal就放到1237處。下一個是Danny，哈希值為1235。1235已被占用，則檢查1236位置是否為空。既然為空，Danny就被放到那兒。最后，添加Edward的信息。同樣他的哈希好為1235。1235已被占用，檢查1236，也被占用了，再檢查1237，直到檢查到1238時，該位置為空，于是Edward被放到了1238位置。
搜索哈希表時，沖突仍然存在。例如，如上所示的哈希表，我們要訪問Edward的信息。因此我們將Edward的社保號111-00-1235哈希為1235，并開始搜索。然而我們在1235位置找到的是Bob，而非Edward。所以我們再搜索1236，找到的卻是Danny。我們的線性搜索繼續查找知道找到Edward或找到內容為空的位置。結果我們可能會得出結果是社保號為111-00-1235的員工并不存在。
線性挖掘雖然簡單，但并是解決沖突的好的策略，因為它會導致同類聚合（clustering）。如果我們要添加10個員工，他們的社保號后四位均為3344。那么有10個連續空間，從3344到3353均被占用。查找這10個員工中的任一員工都要搜索這一簇位置空間。而且，添加任何一個哈希值在3344到3353范圍內的員工都將增加這一簇空間的長度。要快速查詢，我們應該讓數據均勻分布，而不是集中某幾個地方形成一簇。
更好的挖掘技術是“二次挖掘”（quadratic probing），每次檢查位置空間的步長以平方倍增加。也就是說，如果位置s被占用，則首先檢查s+12處，然后檢查s-12，s+22，s-22，s+32 依此類推，而不是象線性挖掘那樣從s+1，s+2……線性增長。當然二次挖掘同樣會導致同類聚合。
下一節我們將介紹第三種沖突解決機制——二度哈希，它被應用在.Net Framework的哈希表類中。
System.Collections.Hashtable 類
.Net Framework 基類庫包括了Hashtable類的實現。當我們要添加元素到哈希表中時，我們不僅要提供元素（item），還要為該元素提供關鍵字（key）。Key和item可以是任意類型。在員工例子中，key為員工的社保號，item則通過Add()方法被添加到哈希表中。
要獲得哈希表中的元素（item），你可以通過key作為索引訪問，就象在數組中用序數作為索引那樣。下面的C#小程序演示了這一概念。它以字符串值作為key添加了一些元素到哈希表中。并通過key訪問特定的元素。
using System;
using System.Collections;
public class HashtableDemo
{
private static Hashtable ages = new Hashtable();
public static void Main()
{
// Add some values to the Hashtable, indexed by a string key
ages.Add("Scott", 25);
ages.Add("Sam", 6);
ages.Add("Jisun", 25);
// Access a particular key
if (ages.ContainsKey("Scott"))
{
int scottsAge = (int) ages["Scott"];
Console.WriteLine("Scott is " + scottsAge.ToString());
}
else
Console.WriteLine("Scott is not in the hash table...");
}
}
程序中的ContainsKey()方法，是根據特定的key判斷是否存在符合條件的元素，返回布爾值。Hashtable類中包含keys屬性（property），返回哈希表中使用的所有關鍵字的集合。這個屬性可以通過遍歷訪問，如下：
// Step through all items in the Hashtable
foreach(string key in ages.Keys)
Console.WriteLine("Value at ages[\"" + key + "\"] = " + ages[key].ToString());
要認識到插入元素的順序和關鍵字集合中key的順序并不一定相同。關鍵字集合是以存儲的關鍵字對應的元素為基礎，上面的程序的運行結果是：
Value at ages["Jisun"] = 25
Value at ages["Scott"] = 25
Value at ages["Sam"] = 6
即使插入到哈希表中的順序是：Scott，Sam， Jisun。
Hashtable類的哈希函數
Hashtable類中的哈希函數比我們前面介紹的社保號的哈希值更加復雜。首先，要記住的是哈希函數返回的值是序數。對于社保號的例子來說很容易辦到，因為社保號本身就是數字。我們只需要截取其最后四位數，就可以得到合適的哈希值。然而Hashtable類中可以接受任何類型的值作為key。就象上面的例子，key是字符串類型，如“Scott”或“Sam”。在這樣一個例子中，我們自然想明白哈希函數是怎樣將string轉換為數字的。
這種奇妙的轉換應該歸功于GetHashCode()方法，它定義在System.Object類中。Object類中GetHashCode()默認的實現是返回一個唯一的整數值以保證在object的生命期中不被修改。既然每種類型都是直接或間接從Object派生的，因此所以object都可以訪問該方法。自然，字符串或其他類型都能以唯一的數字值來表示。
Hashtable類中的對于哈希函數的定義如下：
H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))] % hashsize
這里的GetHash(key)，默認為對key調用GetHashCode()方法的返回值（雖然在使用Hashtable時，你可以自定義GetHash()函數）。GetHash(key)>>5表示將得到key的哈希值，向右移動5位，相當于將哈希值除以32。%操作符就是之前介紹的求模運算符。Hashsize指的是哈希表的長度。因為要進行求模，因此最后的結果H（k）在0到hashsize-1之間。既然hashsize為哈希表的長度，因此結果總是在可以接受的范圍內。
Hashtable類中的沖突解決方案
當我們在哈希表中添加或獲取一個元素時，會發生沖突。插入元素時，必須查找內容為空的位置，而獲取元素時，即使不在預期的位置處，也必須找到該元素。前面我們簡單地介紹了兩種解決沖突的機制——線性和二次挖掘。在Hashtable類中使用的是一種完全不同的技術，成為二度哈希（rehasing）(有的資料也將其稱為雙精度哈希double hashing)。
二度哈希的工作原理如下：有一個包含多個哈希函數（H1……Hn）的集合。當我們要從哈希表中添加或獲取元素時，首先使用哈希函數H1。如果導致沖突，則嘗試使用H2，一直到Hn。各個哈希函數極其相似，不同的是它們選用的乘法因子。通常，哈希函數Hk的定義如下：
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize
注：運用二度哈希重要的是在執行了hashsize次挖掘后，哈希表中的每一個位置都確切地被有且僅有一次訪問。也就是說，對于給定的key，對哈希表中的同一位置不會同時使用Hi和Hj。在Hashtable類中使用二度哈希公式，其保證為：(1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))與hashsize兩者互為素數。（兩數互為素數表示兩者沒有共同的質因子。）如果hashsize是一個素數，則保證這兩個數互為素數。
二度哈希較前兩種機制較好地避免了沖突。
調用因子（load factors）和擴充哈希表
Hashtable類中包含一個私有成員變量loadFactor，它指定了哈希表中元素個數與表位置總數之間的最大比例。例如：loadFactor等于0.5，則說明哈希表中只有一半的空間存放了元素值，其余一半皆為空。
哈希表的構造函數以重載的方式，允許用戶指定loadFactor值，定義范圍為0.1到1.0。要注意的是，不管你提供的值是多少，范圍都不超過72%。即使你傳遞的值為1.0，Hashtable類的loadFactor值還是0.72。微軟認為loadFactor的最佳值為0.72，因此雖然默認的loadFactor為1.0，但系統內部卻自動地將其改變為0.72。所以，建議你使用缺省值1.0（事實上是0.72，有些迷惑，不是嗎？）
注：我花了好幾天時間去咨詢微軟的開發人員為什么要使用自動轉換？我弄不明白，為什么他們不直接規定值為0.072到0.72之間。最后我從編寫Hashtable類的開發團隊的到了答案，他們非常將問題的緣由公諸于眾。事實上，這個團隊經過測試發現如果loadFactor超過了0.72，將會嚴重的影響哈希表的性能。他們希望開發人員能夠更好地使用哈希表，但卻可能記不住0.72這個無規律數，相反如果規定1.0為最佳值，開發者會更容易記住。于是，就形成現在的結果，雖然在功能上有少許犧牲，但卻使我們能更加方便地使用數據結構，而不用感到頭疼。
向Hashtable類添加新元素時，都要進行檢查以保證元素與空間大小的比例不會超過最大比例。如果超過了，哈希表空間將被擴充。步驟如下：
1． 哈希表的位置空間近似地成倍增加。準確地說，位置空間值從當前的素數值增加到下一個最大的素數值。（回想一下前面講到的二度哈希的工作原理，哈希表的位置空間值必須是素數。）
2． 既然二度哈希時，哈希表中的所有元素值將依賴于哈希表的位置空間值，所以表中所有值也需要二度哈希（因為在第一步中位置空間值增加了）。
幸運的是，Hashtable類中的Add()方法隱藏了這些復雜的步驟，你不需要關心它的實現細節。
調用因子（load factor）對沖突的影響決定于哈希表的總體長度和進行挖掘操作的次數。Load factor越大，哈希表越密集，空間就越少，比較于相對稀疏的哈希表，進行挖掘操作的次數就越多。如果不作精確地分析，當沖突發生時挖掘操作的預期次數大約為1/(1-lf)，這里lf指的是load factor。
如前所述，微軟將哈希表的缺省調用因子設定為0.72。因此對于每次沖突，平均挖掘次數為3.5次。既然該數字與哈希表中實際元素個數無關，因此哈希表的漸進訪問時間為O（1），顯然遠遠好于數組的O(n)。
最后，我們要認識到對哈希表的擴充將以性能損耗為代價。因此，你應該預先估計你的哈希表中最后可能會容納的元素總數，在初始化哈希表時以合適的值進行構造，以避免不必要的擴充。