以前對(duì)于這兩個(gè)集合類的認(rèn)識(shí)只是停留在是否支持泛型上，這幾天趁著看算法導(dǎo)論的機(jī)會(huì)，把兩個(gè)類的內(nèi)部的實(shí)現(xiàn)機(jī)制好好的了解了一下。

Hashtable和Dictionary從數(shù)據(jù)結(jié)構(gòu)上來(lái)說(shuō)都屬于Hashtable，都是對(duì)關(guān)鍵字（鍵值）進(jìn)行散列操作，將關(guān)鍵字散列到Hashtable的某一個(gè)槽位中去，不同的是處理碰撞的方法。散列函數(shù)有可能將不同的關(guān)鍵字散列到Hashtable中的同一個(gè)槽中去，這個(gè)時(shí)候我們稱發(fā)生了碰撞，為了將數(shù)據(jù)插入進(jìn)去，我們需要另外的方法來(lái)解決這個(gè)問(wèn)題。

鏈接法(chaining)

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

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

開(kāi)放尋址法(open addressing)

在開(kāi)放尋址法中，所有的元素都保存在散列表中，而不是像鏈接法，數(shù)據(jù)保存在外部的鏈表中，在開(kāi)放尋址法中，由于數(shù)據(jù)全部存儲(chǔ)在散列表中，所以槽位一定會(huì)大于等于n,也就是說(shuō)，裝載因子一定會(huì)小于等于1。

在開(kāi)放尋址法中，當(dāng)要插入一個(gè)元素時(shí)，我們將關(guān)鍵字和探查號(hào)(從0開(kāi)始累加)作為輸入傳給散列函數(shù)，散列函數(shù)返回對(duì)應(yīng)的槽位。插入的時(shí)候首先查找hash(key,0)這個(gè)槽，如果不為空則探查號(hào)+1,繼續(xù)查下一個(gè)槽，直到找到空槽，或者得知散列表已滿。查找的過(guò)程和插入類似，查找關(guān)鍵字的時(shí)候如果我們碰到了空槽，查找就結(jié)束，因?yàn)槿绻P(guān)鍵字存在的話，那么也應(yīng)該會(huì)出現(xiàn)在這個(gè)地方。

開(kāi)放尋址法中比較特殊的是刪除操作，如果刪除數(shù)據(jù)置為null的話，那么就會(huì)有一個(gè)問(wèn)題，比如我們插入過(guò)程中插入k的時(shí)候發(fā)現(xiàn)槽i已經(jīng)被占用，我們插到后面的槽中，如果刪除的時(shí)候我們簡(jiǎn)單的將槽i置為null,那么查找的時(shí)候關(guān)鍵字k就不會(huì)被找到。這個(gè)問(wèn)題我們可以用一個(gè)標(biāo)志位來(lái)解決。具體的實(shí)現(xiàn)會(huì)在下面講到。

雙重散列

開(kāi)放尋址法的探查方法有多種，在這里只講一下雙重探查，因?yàn)檫@種方法是最好的方法之一，而且它被用在Hashtable中。

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

在解釋了鏈接法和開(kāi)放尋址法后，來(lái)講講Hashtable和Dictionary。

Hashtable這個(gè)類采用的是開(kāi)放尋址法來(lái)解決碰撞的問(wèn)題，下面來(lái)看看Hashtable的一個(gè)構(gòu)造函數(shù)

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;  

構(gòu)造函數(shù)會(huì)在傳入裝載因子的基礎(chǔ)上乘以0.72,這個(gè)值是微軟認(rèn)為的比較理想的一個(gè)值。上面已經(jīng)說(shuō)過(guò)了在雙重散列時(shí)需要保持和槽的大小m互質(zhì)，我們只需要保證m為質(zhì)數(shù)，而比m小，這樣就能保證他們總是互質(zhì)。在這里HashHelpers.GetPrime實(shí)現(xiàn)的就是傳回一個(gè)比num大的質(zhì)數(shù)，這樣能保證num2這個(gè)量總為一個(gè)質(zhì)數(shù)，然后把槽數(shù)組建立起來(lái)。

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

槽中的hash_coll用來(lái)存放key對(duì)應(yīng)的hashcode,最高位用來(lái)標(biāo)識(shí)是否發(fā)生了碰撞，發(fā)生碰撞的槽的最高位會(huì)被置為1，搜索的時(shí)候，如果最高位為1那么搜尋函數(shù)會(huì)繼續(xù)搜索，注意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方法，為了將刪除的節(jié)點(diǎn)的Entry進(jìn)行重用，Dictionary中有一個(gè)freeList字段，刪除的節(jié)點(diǎn)的下標(biāo)值，為賦給freeList，在Add操作的時(shí)候如果freeList>0則將數(shù)據(jù)插入到freeList指向的Entry中去。

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

【編輯推薦】

1. 深入探究J2ME Hashtable實(shí)現(xiàn)原理
2. J2ME數(shù)據(jù)結(jié)構(gòu)中Hashtable和Vector的使用
3. 淺談C#與數(shù)據(jù)結(jié)構(gòu)中的哈希表（Hashtable）
4. .Net類庫(kù)中實(shí)現(xiàn)的HashTable
5. VB.NET Hashtable用法相關(guān)概念詳解