Dictionary和hashtable用法有點相似，他們都是基于(yu)鍵值對的數(shu)據集合，但實際上他們內部的實現原理有很大的差異(yi)，

先簡要概(gai)述一(yi)下他們主要的區別，稍后在分析Dictionary內部實現的大(da)概(gai)原理。

區別：

1. Dictionary支持泛型，而Hashtable不支持。
2. Dictionary沒有裝填因子（Load Facto）概念，當容量不夠時才擴容（擴容跟Hashtable一樣，也是兩倍于當前容量最小素數，比如當前數組長度是3,那么新數組長度為7（2x3=6，比6大的最小素數是7），Hashtable是“已裝載元素”與”bucket數組長度“大于裝載因子時擴容。
3. Dictionary內部的存儲value的數組按先后插入的順序排序，Hashtable不是。
4. 當不發生碰撞時，查找Dictionary需要進行兩次索引定位，Hashtable需一次，。

Dictionary采用(yong)除法(fa)散列法(fa)來計算存(cun)儲地址，想詳細了(le)(le)解(jie)的可以百度一下，簡單來說就(jiu)是(shi)其內部有兩個(ge)(ge)數組(zu)(zu)：buckets數組(zu)(zu)和entries數組(zu)(zu)(entries是(shi)一個(ge)(ge)Entry結構數組(zu)(zu))，entries有一個(ge)(ge)next用(yong)來模擬(ni)鏈表，該字段存(cun)儲一個(ge)(ge)int值(zhi)，指向下一個(ge)(ge)存(cun)儲地址（實際就(jiu)是(shi)bukets數組(zu)(zu)的索引），當(dang)沒有發生碰(peng)撞(zhuang)(zhuang)時，該字段為-1，發生了(le)(le)碰(peng)撞(zhuang)(zhuang)則存(cun)儲一個(ge)(ge)int值(zhi)，該值(zhi)指向bukets數組(zu)(zu).

內部實現

下面跟上次(ci)一樣(yang)，按正(zheng)常使用Dictionary時，看(kan)內部是如何(he)實現(xian)的(de)。

1. 實例化一個Dictionary

Dictionary<string,string> dic=new Dictionary<string,string>();

• 調用Dictionary默認無參構造函數。
• 初始化Dictionary內部數組容器：buckets int[]和entries<T,V>[]，分別分配長度3。（內部有一個素數數組:3,7,11,17....如圖：）；

2. 向dic添加一個值,dic.add("a","abc");

• a, 將bucket數組和entries數組擴容3個長度。
• b, 計算"a"的哈希值,
• c, 然后與bucket數組長度（3）進行取模計算，假如結果為：2
• d, 因為a是第一次寫入，則自動將a的值賦值到entriys[0]的key,同理將"abc"賦值給entriys[0].value,將上面b步驟的哈希值賦值給entriys[0].hashCode,
  entriys[0].next賦值為-1,hashCode賦值b步驟計算出來的哈希值。
• e, 在bucket[2]存儲0。

3. 通過key獲取對應的value, var v=dic["a"];

• a, 先計算"a"的哈希值，假如結果為2，
• b,根據上一步驟結果，找到buckets數組索引為2上的值，假如該值為0.
• c, 找到到entriys數組上索引為0的key,
  • 如果該key值和輸入的的“a”字符相同，則對應的value值就是需要查找的值。
  • 如果該key值和輸入的"a"字符不相同，說明發生了碰撞，這時獲取對應的next值，根據next值定位buckets數組（buckets[next]），然后獲取對應buckets上存儲的值在定位到entriys數組上,......,一直到找到為止。
  • 如果該key值和輸入的"a"字符不相同并且對應的next值為-1,則說明Dictionary不包含字符“a”。

Dictionary里的(de)其他方法就不說了，各(ge)位可以自己去看源碼，下面(mian)來通過實驗(yan)來對(dui)比Hashtable和(he)Dictionary的(de)添(tian)加(jia)和(he)查找性能，