以前對于這兩個集合類的認識只是停留在是否支持泛型上，這幾天趁著看算法導論的機會，把兩個類的內部的實現機制好好的了解了一下。

Hashtable和Dictionary從數據結構上來說都屬于Hashtable，都是對關鍵字（鍵值）進行散列操作，將關鍵字散列到Hashtable的某一個槽位中去，不同的是處理碰撞的方法。散列函數有可能將不同的關鍵字散列到Hashtable中的同一個槽中去，這個時候我們稱發生了碰撞，為了將數據插入進去，我們需要另外的方法來解決這個問題。

鏈接法(chaining)

在鏈接法中，把散列到同一個槽中的所有元素放在一個鏈表中，槽中有一個指針，指向鏈表的頭，如果沒有的話，則為NIL。對于一個能存放n個元素，具有m個槽位的散列表，我們定義裝載因子a為n/m,即一個鏈中平均存儲的元素的個數。

鏈接法中的加入，刪除，尋找操作其實基本上就是鏈表的基本操作。在這里就不仔細講了。

開放尋址法(open addressing)

在開放尋址法中，所有的元素都保存在散列表中，而不是像鏈接法，數據保存在外部的鏈表中，在開放尋址法中，由于數據全部存儲在散列表中，所以槽位一定會大于等于n,也就是說，裝載因子一定會小于等于1。

在開放尋址法中，當要插入一個元素時，我們將關鍵字和探查號(從0開始累加)作為輸入傳給散列函數，散列函數返回對應的槽位。插入的時候首先查找hash(key,0)這個槽，如果不為空則探查號+1,繼續查下一個槽，直到找到空槽，或者得知散列表已滿。查找的過程和插入類似，查找關鍵字的時候如果我們碰到了空槽，查找就結束，因為如果關鍵字存在的話，那么也應該會出現在這個地方。

開放尋址法中比較特殊的是刪除操作，如果刪除數據置為null的話，那么就會有一個問題，比如我們插入過程中插入k的時候發現槽i已經被占用，我們插到后面的槽中，如果刪除的時候我們簡單的將槽i置為null,那么查找的時候關鍵字k就不會被找到。這個問題我們可以用一個標志位來解決。具體的實現會在下面講到。

雙重散列

開放尋址法的探查方法有多種，在這里只講一下雙重探查，因為這種方法是最好的方法之一，而且它被用在Hashtable中。

這里和為輔助散列函數，第一次為，后續的探查位置在的基礎上加上偏移量,然后對m進行模運算。這里需要提一下的是為了查找整個散列表，需要與槽的大小m互質，等下可以看到在Hashtable類中是如何滿足這個條件的。

在解釋了鏈接法和開放尋址法后，來講講Hashtable和Dictionary。

Hashtable這個類采用的是開放尋址法來解決碰撞的問題，下面來看看Hashtable的一個構造函數

this.loadFactor = 0.72f * loadFactor;    
 double num = ((float) capacity) / this.loadFactor;    
 if (num > 2147483647.0)    
 {    
   throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));    
}    
 int num2 = (num > 11.0) ? HashHelpers.GetPrime((int) num) : 11;    
 this.buckets = new bucket[num2];    
 this.loadsize = (int) (this.loadFactor * num2);    
 this.isWriterInProgress = false;  

構造函數會在傳入裝載因子的基礎上乘以0.72,這個值是微軟認為的比較理想的一個值。上面已經說過了在雙重散列時需要保持和槽的大小m互質，我們只需要保證m為質數，而比m小，這樣就能保證他們總是互質。在這里HashHelpers.GetPrime實現的就是傳回一個比num大的質數，這樣能保證num2這個量總為一個質數，然后把槽數組建立起來。

(this.GetHash(key) & 0x7fffffff)這個相當于雙散列公式中的，1 + ((uint) (((seed >> 5) + 1) % (hashsize - 1)));則相當于,

槽中的hash_coll用來存放key對應的hashcode,最高位用來標識是否發生了碰撞，發生碰撞的槽的最高位會被置為1，搜索的時候，如果最高位為1那么搜尋函數會繼續搜索，注意contains方法中的while條件,

do   
 {    
    bucket = buckets[index];    
   if (bucket.key == null)    
   {    
      return false;    
    }    
    if (((bucket.hash_coll & 0x7fffffff) == num3) && this.KeyEquals(bucket.key, key))    
    {    
       return true;    
   }    
    index = (int) ((index + num2) % ((ulong) buckets.Length));    
 }    
 while ((bucket.hash_coll < 0) && (++num4 < buckets.Length));  

public struct Entry<TKey, TValue>    
{    
   public int hashCode;    
   public int next;    
  public TKey key;    
   public TValue value;    
 }  

稍微需要提一下的是Remove方法，為了將刪除的節點的Entry進行重用，Dictionary中有一個freeList字段，刪除的節點的下標值，為賦給freeList，在Add操作的時候如果freeList>0則將數據插入到freeList指向的Entry中去。

原文鏈接：http://www.cnblogs.com/MichaelYin/archive/2011/02/14/1954724.html

【編輯推薦】

1. 深入探究J2ME Hashtable實現原理
2. J2ME數據結構中Hashtable和Vector的使用
3. 淺談C#與數據結構中的哈希表（Hashtable）
4. .Net類庫中實現的HashTable
5. VB.NET Hashtable用法相關概念詳解