sp.Net中使用Couchbase——Memcached緩存入門篇也談哈希表

基本概念

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

哈希函數構造方法

　　哈希表的構造方法是：假設要存儲的資料元素個數為n，設定一個長度為m（m≥n）的連續存儲單元，分别以每個資料元素的關鍵字

為自變量，通過哈希函數

，把

映射為記憶體單元的某個位址

，并将該資料元素存儲在該記憶體單元中。

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

1. 直接定址法，該方法是曲關鍵字的某個線性函數值為哈希位址。可以簡單的表示為：

   

   ，優點是不會産生沖突，但缺點空間複雜度可能會很高，适用于元素較少的情況下；
2. 除留餘數法，它是用資料元素關鍵字除以某個常數所得的餘數作為哈希位址，該方法計算簡單，适用範圍廣，是最經常使用的一種哈希函數，可以表示為：

   

   ，該方法的關鍵是常數的選取，一般要求是接近或等于哈希表本身的長度，理論研究表明，該常數取素數時效果最好。
3. 數字分析法：該方法是取資料元素關鍵字中某些取值較均勻的數字位來作為哈希位址的方法，這樣可以盡量避免沖突，但是該方法隻适合于所有關鍵字已知的情況。對于想要設計出更加通用的哈希表并不适用。

哈希沖突解決辦法

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

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

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

1. 開放定址法，它是一類以發生哈希沖突的哈希位址為自變量，通過某種哈希函數得到一個新的空閑記憶體單元位址的方法（如圖），開放定址法的哈希沖突函數通常是一組；

   

2. 連結清單法，當未發生沖突時，則直接存放該資料元素；當沖突産生時，把産生沖突的資料元素另外存放在單連結清單中。

   

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。

1. 插入元素[20, “elem1”]，根據Hashtable類哈希函數通項式，是以其哈希代碼的值為

   

   ，此時為第一次插入資料，是以不存在沖突，直接尋址到bucket[2]，由于不存在沖突，是以hash_coll的值即為其key的哈希代碼，存儲結構如下圖：

   

2. 插入元素[33, “elem2”]，同理

   

   ，此時仍然不存在沖突，存儲結構如下：

   

3. 插入元素[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，表示其出現了沖突，是以完成插入後哈希表結構如下圖：

   

4. 插入元素[55, “elem4”]，同理，

   

   ，産生沖突，進行二度哈希：

   

   

   ，完成插入後哈希表的存儲結構為：

   

5. 删除元素[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插入和删除元素的簡單過程：

1. 插入元素[20, “elem1”]，跟Hashtable類似，Dictionary初始化容量也為3（如果未指定初始化容量），Dictionary的哈希函數就非常簡單了，除留餘數法直接擷取其哈希位址，

   

   ，那麼此時在entries[0]直接儲存下元素的鍵值以及哈希碼，并将此時元素在entries數組中的索引指派給buckets[2]，如下圖：

   

2. 插入元素[33, “elem2”]，其哈希位址為：

   

   ，插入後存儲結構如下：

   

3. 插入元素[40, “elem3”]，計算後的哈希位址為

   

   ，剛好未發生沖突，由于不受填裝因子（此時填裝因子為1）的限制，此時無須擴容，插入該元素後的存儲結構為：

   

4. 插入元素[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”]，計算其哈希位址：

   

   ，再次發生沖突，那麼按照剛剛的沖突解決辦法，插入該元素之後的存儲結構為：

   

5. 最後插入元素[13, “elem5”]，

   

   ，再次沖突發生，那麼插入該元素之後的結構圖如下：

   

6. 删除元素對于Dictionary來說就很簡單了，如果在非沖突鍊上删除元素，非常簡單，通過雜湊演算法尋址找到對應的元素删除并将buckets中對應的元素值修改為-1，如果在沖突鍊上删除元素，那麼就是一個簡單的删除連結清單元素的操作，在這裡就留給讀者去思考。

參考資料

• 陳皓 - 可視化的資料結構和算法
• 張逸  - 考察資料結構——第二部分：隊列、堆棧和哈希表[譯]
• abatei - C#與資料結構--哈希表（HASHTABLE）
• 維基百科 – 散清單
• Angel Lucifer - 資料結構 : Hash Table [I]

作者：LukyW