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