Dictionary和hashtable用法有點相似，他們都是基於鍵值對的數據集合，但實際上他們內部的實現原理有很大的差異， 先簡要概述一下他們主要的區別，稍後在分析Dictionary內部實現的大概原理。 區別： 1. Dictionary支持泛型，而Hashtable不支持。 2. Dictio ...
Dictionary和hashtable用法有點相似，他們都是基於鍵值對的數據集合，但實際上他們內部的實現原理有很大的差異，
先簡要概述一下他們主要的區別，稍後在分析Dictionary內部實現的大概原理。
區別：
- Dictionary支持泛型，而Hashtable不支持。
- Dictionary沒有裝填因數（Load Facto）概念，當容量不夠時才擴容（擴容跟Hashtable一樣，也是兩倍於當前容量最小素數，比如當前數組長度是3,那麼新數組長度為7（2x3=6，比6大的最小素數是7），Hashtable是“已裝載元素”與”bucket數組長度“大於裝載因數時擴容。
- Dictionary內部的存儲value的數組按先後插入的順序排序，Hashtable不是。
當不發生碰撞時，查找Dictionary需要進行兩次索引定位，Hashtable需一次，。
Dictionary採用除法散列法來計算存儲地址，想詳細瞭解的可以百度一下，簡單來說就是其內部有兩個數組：buckets數組和entries數組(entries是一個Entry結構數組)，entries有一個next用來模擬鏈表，該欄位存儲一個int值，指向下一個存儲地址（實際就是bukets數組的索引），當沒有發生碰撞時，該欄位為-1，發生了碰撞則存儲一個int值，該值指向bukets數組.
內部實現
下麵跟上次一樣，按正常使用Dictionary時，看內部是如何實現的。
- 實例化一個Dictionary
Dictionary<string,string> dic=new Dictionary<string,string>();- 調用Dictionary預設無參構造函數。
- 初始化Dictionary內部數組容器：buckets int[]和entries<T,V>[]，分別分配長度3。（內部有一個素數數組:3,7,11,17....如圖：）；
- 向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。
- 通過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里的其他方法就不說了，各位可以自己去看源碼，下麵來通過實驗來對比Hashtable和Dictionary的添加和查找性能，
