也談哈希表 - lukyw－IT工程師數位筆記本

文章出處

基本概念

　　哈希表（Hash Table）是一種根據關鍵字直接訪問內存存儲位置的數據結構。通過哈希表，數據元素的存放位置和數據元素的關鍵字之間建立起某種對應關系，建立這種對應關系的函數稱為哈希函數（如圖）。

哈希函數構造方法

　　哈希表的構造方法是：假設要存儲的數據元素個數為n，設置一個長度為m（m≥n）的連續存儲單元，分別以每個數據元素的關鍵字為自變量，通過哈希函數，把映射為內存單元的某個地址，并將該數據元素存儲在該內存單元中。

　　從數學的角度來看，哈希函數實際上是關鍵字到內存單元的映射，因此我們希望通過哈希函數通過盡量簡單的運算使得通過哈希函數計算出的哈希地址盡量均勻地被映射到一系列的內存單元中。構造哈希函數有三個要點：第一，運算過程要盡量簡單高效，以提高哈希表的插入和檢索效率；第二，哈希函數應該具有較好的散列性，以降低哈希沖突的概率；第三，哈希函數應具有較大的壓縮性，以節省內存。一般有以下幾種常見的方法：

直接定址法，該方法是曲關鍵字的某個線性函數值為哈希地址。可以簡單的表示為：，優點是不會產生沖突，但缺點空間復雜度可能會很高，適用于元素較少的情況下；
除留余數法，它是用數據元素關鍵字除以某個常數所得的余數作為哈希地址，該方法計算簡單，適用范圍廣，是最經常使用的一種哈希函數，可以表示為：，該方法的關鍵是常數的選取，一般要求是接近或等于哈希表本身的長度，理論研究表明，該常數取素數時效果最好。
數字分析法：該方法是取數據元素關鍵字中某些取值較均勻的數字位來作為哈希地址的方法，這樣可以盡量避免沖突，但是該方法只適合于所有關鍵字已知的情況。對于想要設計出更加通用的哈希表并不適用。

哈希沖突解決辦法

　　在構造哈希表時，存在這樣的問題，對于兩個不同的關鍵字，通過我們的哈希函數計算哈希地址時卻得到了相同的哈希地址，我們將這種現象稱為哈希沖突（如圖）:

　　哈希沖突主要與兩個因素相關：第一，填裝因子，所謂的填裝因子是指哈希表中已存入的數據元素個數與哈希地址空間大小的比值，即α=n/m，α越小，沖突的可能性就越小，相反則沖突可能性越大；但是α越小，哈希表的存儲空間利用率也就很低，α越大，存儲空間的利用率也就越高，為了兼顧哈希沖突和存儲空間利用率，通常將α控制在0.6-0.9之間，而.NET中的Hashtable則直接將α的最大值定義為0.72（注：雖然微軟官方MSDN中聲明Hashtable默認填裝因子為1.0，事實上所有的填裝因子都為0.72的倍數）；第二，與所用的哈希函數有關，如果哈希函數選擇得當，就可以使哈希地址盡可能的均勻分布在哈希地址空間上，從而減少沖突的產生，但一個良好的哈希函數的得來很大程度上取決于大量的實踐，不過幸好前人已經總結實踐了很多高效的哈希函數，可以參考園子里大牛Lucifer的文章：數據結構 : Hash Table [I]。

　　哈希沖突通常是很難避免的，解決哈希沖突有很多種方法，通常分為兩大類：

開放定址法，它是一類以發生哈希沖突的哈希地址為自變量，通過某種哈希函數得到一個新的空閑內存單元地址的方法（如圖），開放定址法的哈希沖突函數通常是一組；
鏈表法，當未發生沖突時，則直接存放該數據元素；當沖突產生時，把產生沖突的數據元素另外存放在單鏈表中。

Hashtable和Dictionary

　　.NET中實現了哈希表的類分別是Hashtable和Dictionary<TKey, TValue>，Hashtable由包含集合元素的存儲桶組成，存儲桶是Hashtable中各元素的虛擬子組，與大多數集合中進行的搜索相比，存儲桶可使搜索更為便捷。Dictionary則是泛型版本的哈希表，與Hashtable的功能相同，對于值類型，特定類型（不包括Object）的性能優先于Hashtable，這是因為Hashtable的元素屬于Object類型，所以在存儲或者檢索類型時通常發生裝箱和拆箱操作；除此之外，雖然微軟宣稱Hashtable是線程安全的，可以允許多個讀線程或一個寫線程訪問，但是事實是它也并非線程安全，在.NET Framework 2.0新引入的Dictionary仍舊為解決這個問題，其中限于公共靜態方法是線程安全的，因此可以說Dictionary是非線程安全的，而且對整個集合的枚舉過程對二者而言都不是線程安全的，因為當出現枚舉與寫訪問互相爭用這種情況發生時，則必須在整個枚舉過程中對整個集合加鎖。如果我們在使用.NET Framework 4.0以上版本，我們可以使用線程安全的ConcurrentDictionary；另一個比較重要的區別在于，雖然它們都實現了哈希表，但是二者卻使用了完全不同的哈希沖突解決方法，Hashtable解決沖突的方式是開放定址法，而Dictionary則采用了鏈表法。

Hashtable的實現原理

　　Hashtable類中哈希函數的定義可以用如下遞推公式來表示：

通過簡單的數學推導就可以得出其通項式公式即Hashtable的哈希函數簇為：

因此我們就擁有了一系列的哈希函數：，當我們向哈希表中增加元素時，則依次嘗試使用這些哈希函數，直到找到相應的空閑內存單元地址為止，這種方式稱為二度哈希。

　　在Hashtable類中，包含元素的存儲桶被定義在結構體bucket中：

1 private struct bucket
2 {
3     public object key;
4     public object val;
5     public int hash_coll;
6 }

其中前兩個字段很容易理解，分別代表了哈希表中的關鍵字和值，對于第三個字段hash_coll，實際上保存了兩種信息：關鍵字的哈希碼和是否沖突，coll為collision（沖突）的縮寫，該字段為32位整型類型，最高位為符號位，當最高位為0時，表示該數為正數，表示未發生沖突，為1時為負數，表示發生了沖突，剩下的其他位則用于保存哈希碼。

　　下面我們來看一個簡單的哈希表元素增刪過程，使得我們對于哈希表的具體工作方式有一個更直觀的了解，當我們未指定具體Hashtable容量大小時，來進行一組數據的插入操作，此時Hashtable類會自動初始化其容量為默認最小值3。

插入元素[20, “elem1”]，根據Hashtable類哈希函數通項式，所以其哈希代碼的值為，此時為第一次插入數據，因此不存在沖突，直接尋址到bucket[2]，由于不存在沖突，因此hash_coll的值即為其key的哈希代碼，存儲結構如下圖：
插入元素[33, “elem2”]，同理，此時仍然不存在沖突，存儲結構如下：
插入元素[40, “elem3”]，此時的哈希表進行擴容，為什么會在此時擴容呢，哈希表的填裝因子為2/3=0.66并未超過0.72，在.NET中，微軟對填裝因子進行了換算，通過填裝因子與哈希表大小的乘積取整獲得哈希表的最佳填裝量即：3×0.72=2。擴容后的哈希表大小為原表容量大小的2倍后的質數，在本例中再次擴容后哈希表大小為7。進行擴容之后，原哈希表的已經存儲的元素必須按照新的哈希表的哈希函數（其實哈希函數本身沒有發生變動，發生變動的是哈希表的長度）進行計算，重新尋址，擴容后的哈希表如下：

完成擴容過程后才會對[40, “elem3”]進行插入操作，，現在我們發現沖突產生了，因為此時bucket[5]的位置已經有元素了，此時進行二度哈希：

此時哈希表中位置為1的空間仍舊處于空閑狀態，因此進行插入操作，在將元素插入之前，由于bucket[5]出現了沖突，因此需要對其進行標記，將hash_coll的最高位置為1，表示其出現了沖突，所以完成插入后哈希表結構如下圖：
插入元素[55, “elem4”]，同理，，產生沖突，進行二度哈希：

，完成插入后哈希表的存儲結構為：
刪除元素[20, “elem1”]，在刪除元素時，同樣需要根據哈希函數來進行尋址，如果有沖突，則進行二度哈希，但是值得注意的一點是，刪除沖突標記元素（即元素的hash_coll值為負數）和非沖突標記元素是有差別的，在刪除非沖突標記元素時，則直接將要刪除的元素的鍵和值修改為null并將hash_coll置0即可，但是在刪除沖突標記元素時，需將hash_coll的hash部分（即0-30位）置0以及將元素的值置為null，還需將該元素的鍵指向整個哈希表，之所以這樣做是因為當索引為0的元素也出現沖突時，將無法判斷該位置是一個空位還是非空位，那么再次進行插入時很可能將索引為0處的元素覆蓋。刪除[20， “elem1”]后的結構為：

Dictionary的實現原理

　　從.NET Framework 2.0開始，隨著泛型的引入，類庫提供一個新的命名空間System.Collection.Generic，并且在該命名空間下新增了Dictionary等泛型類。

　　Dictionary的哈希函數就相對簡單，就是簡單的除留余數法，對于沖突解決，Dictionary則采用了鏈表法，但是此時buckets數組已經退化為專門用于存儲元素的位置（下標）的整型數組，包含元素的數據結構被定義為結構體Entry，通過一個Entry類型的數組entries專門用于存儲元素，Entry的定義如下：

1 private struct Entry
2 {
3     public int hashCode;
4     public int next;
5     public TKey key;
6     public TValue value;
7 }

其中的next字段表示數組鏈表的下一個元素的下標，一個關于數據存儲結構的簡單圖示如下：

我們用同樣的方式來看看Dictionary插入和刪除元素的簡單過程：

插入元素[20, “elem1”]，跟Hashtable類似，Dictionary初始化容量也為3（如果未指定初始化容量），Dictionary的哈希函數就非常簡單了，除留余數法直接獲取其哈希地址，，那么此時在entries[0]直接保存下元素的鍵值以及哈希碼，并將此時元素在entries數組中的索引賦值給buckets[2]，如下圖：
插入元素[33, “elem2”]，其哈希地址為：，插入后存儲結構如下：
插入元素[40, “elem3”]，計算后的哈希地址為，剛好未發生沖突，由于不受填裝因子（此時填裝因子為1）的約束，此時無須擴容，插入該元素后的存儲結構為：
插入元素[55, “elem4”]，此時Dictionary的容量已滿，必須進行擴容操作，Dictionary的擴容和Hashtable的擴容策略一致，擴容后的Dictionary的容量大小為原Dictionary容量大小2倍后的質數即也為7，然后根據擴容后的Dictionary重新尋址，這意味著部分數據可能會引起沖突從而導致已有的鏈表會被打亂重新組織；Dictionary首先會將擴容前Dictionary中的entries中的元素全部復制到新的entries中，緊接著進行重新尋址，對于第一個元素[20, “elem1”]，新的哈希地址為：，于是buckets[6]的值被修改為0（即元素[20, “elem1”]在entries中的索引），同理對于33：，所以，buckets[5]=1，最后處理40，，此時發生沖突，在通過鏈表法處理沖突時，Dictionary首先將新元素的next指向沖突位置的元素索引buckets[5]，然后再將buckets[5]指向新的元素，此時一條只有兩個元素的基于數組的鏈表形成，因此擴容之后的存儲結構如下圖：

在這里可以看出無論是Dictionary還是Hashtable，擴容帶來的性能損耗代價都是相當昂貴的，因此我們最好能夠預估出哈希表中最后容納元素的總數，在哈希表初始化時就對其進行內存分配，從而避免不必要的擴容帶來的性能損耗；
此時再插入元素[55, “elem4”]，計算其哈希地址：，再次發生沖突，那么按照剛剛的沖突解決辦法，插入該元素之后的存儲結構為：
最后插入元素[13, “elem5”]，，再次沖突發生，那么插入該元素之后的結構圖如下：
刪除元素對于Dictionary來說就很簡單了，如果在非沖突鏈上刪除元素，非常簡單，通過哈希算法尋址找到對應的元素刪除并將buckets中對應的元素值修改為-1，如果在沖突鏈上刪除元素，那么就是一個簡單的刪除鏈表元素的操作，在這里就留給讀者去思考。