淺談Hashtable與Dictionary的異同
以前對于這兩個集合類的認識只是停留在是否支持泛型上，這幾天趁著看算法導論的機會，把兩個類的內部的實現機制好好的了解了一下。
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));
BTW,我當時看這個方法的時候覺得搜尋函數其實也可以通過跳過bucket.key == this.buckets的項來寫，因為在移除方法中如果bucket.hash_coll < 0的話，那么bucket.key = this.buckets， 后來想了一下，bucket.hash_coll < 0這樣效率更高，這里就不說為什么了，愛思考的朋友在后面寫下你的答案吧。
在Add方法里面需要對count進行檢查，如果達到了設定的值，這個時候需要對Hashtable進行擴容，擴大的容量是當前容量的2倍以上的一個質數，然后對里面已經存在的元素重新進行hash操作，相當于重新插入新的槽數組中。對于Insert方法中的index這個變量的作用我在看代碼的時候還是有點疑問的，如果有知道的朋友麻煩在留言中告知。
Dictionary<TKey, TValue>這個泛型類采用的是鏈接法來解決碰撞，其中的bucket存儲的是指向Entry的下標，Entry就相當于鏈表中的節點，Entry中存儲的又有指向下一個產生碰撞的元素的下標。稍有不同的是，這里的Entry是一個數組。
- public struct Entry<TKey, TValue>
- {
- public int hashCode;
- public int next;
- public TKey key;
- public TValue value;
- }
Dictionary的Add操作首先計算元素的Hash值，然后根據Hash值尋找bucket,找到相應的bucket后將值存入Entry中，并將bucket指向相應的Entry.查詢操作邏輯是根據Hash值找到相應的bucket然后通過bucket到Entry數組中進行尋找。
稍微需要提一下的是Remove方法，為了將刪除的節點的Entry進行重用，Dictionary中有一個freeList字段，刪除的節點的下標值，為賦給freeList，在Add操作的時候如果freeList>0則將數據插入到freeList指向的Entry中去。
原文鏈接：http://www.cnblogs.com/MichaelYin/archive/2011/02/14/1954724.html
【編輯推薦】
