參考：https://blog.csdn.net/exiaojiu/article/details/51252515
http://www.cnblogs.com/wangjun1234/p/3719635.html
源代碼版本為 .NET Framework 4.6.1
Dictionary是Hashtable的一種泛型實作（也是一種哈希表）實作了IDictionary泛型接口和非泛型接口等，将鍵映射到相應的值。任何非 null 對象都可以用作鍵。使用與Hashtable不同的沖突解決方法，Dictionary使用拉鍊法。
概念重播
對于不同的關鍵字可能得到同一哈希位址，即key1 != key2 => F(key1)=F(fey2)，這種現象叫做沖突，在一般情況下，沖突隻能盡可能的少，而不能完全避免。因為，哈希函數是從關鍵字集合到位址集合的映像。通常，關鍵字集合比較大，它的元素包括很多有可能的關鍵字。既然如此，那麼，如何處理沖突則是構造哈希表不可缺少的一個方面。
通常用于處理沖突的方法有：開放定址法、再哈希法、鍊位址法、建立一個公共溢出區等。
在哈希表上進行查找的過程和哈希造表的過程基本一緻。給定K值，根據造表時設定的哈希函數求得哈希位址，若表中此位置沒有記錄，則查找不成功；否則比較關鍵字，若和給定值相等，則查找成功；否則根據處理沖突的方法尋找“下一位址”，隻到哈希表中某個位置為空或者表中所填記錄的關鍵字等于給定值時為止。
哈希函數
Dictionary使用的哈希函數是除留餘數法，在源碼中的公式為：
h = F(k) % m; m 為哈希表長度（這個長度一般為素數）
（内部有一個素數數組:3,7,11,17....如圖：
C# Dictionary源碼剖析
）；
通過給定或預設的GetHashCode()函數計算出關鍵字的哈希碼模以哈希表長度，計算出哈希位址。
拉鍊法
Dictionary使用的解決沖突方法是拉鍊法，又稱鍊位址法。
拉鍊法的原理：将所有關鍵字為同義詞的結點連結在同一個單連結清單中。若標明的散清單長度為m，則可将散清單定義為一個由m個頭指針組成的指針數 組T[0..m-1]。凡是散列位址為i的結點，均插入到以T[i]為頭指針的單連結清單中。T中各分量的初值均應為空指針。結構圖大緻如下：
特别強調：拉鍊法隻是使用連結清單的原理去解決沖突，并不是真的有一個連結清單存在。
基本成員
1 private struct Entry {
2 public int hashCode; //31位散列值，32最高位表示符号位，-1表示未使用
3 public int next; //下一項的索引值，-1表示結尾
4 public TKey key; //鍵
5 public TValue value; //值
6 }
7
8 private int[] buckets;//内部維護的資料位址
9 private Entry[] entries;//元素數組，用于維護哈希表中的資料
10 private int count;//元素數量
11 private int version;
12 private int freeList;//空閑的清單
13 private int freeCount;//空閑清單元素數量
14 private IEqualityComparer<TKey> comparer;//哈希表中的比較函數
15 private KeyCollection keys;//鍵集合
16 private ValueCollection values;//值集合
17 private Object _syncRoot; buckets 就想在哈希函數與entries之間解耦的一層關系，哈希函數的F(k)變化不在直接影響到entries。
freeList 類似一個單連結清單，用于存儲被釋放出來的空間即空連結清單，一般有被優先存入資料。
freeCount 空連結清單的空位數量。
初始化函數
該函數用于，初始化的資料構造
1 private void Initialize(int capacity) {
2 //根據構造函數設定的初始容量，擷取一個近似的素數
3 int size = HashHelpers.GetPrime(capacity);
4 buckets = new int[size];
5 for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
6 entries = new Entry[size];
7 freeList = -1;
8 } 初始化Dictionary内部數組容器：buckets int[]和entries<T,V>[]，分别配置設定長度3。
（内部有一個素數數組:3,7,11,17....如圖：
）；
size 哈希表的長度是素數，可以使元素更均勻地分布在每個節點上。
buckets 中的節點值，-1表示空值。
freeList 為-1表示沒有空連結清單。
buckets 和 freeList 所值指向的資料其實全是存儲于一塊連續的記憶體空間（entries ）之中。
插入元素
1 public void Add(TKey key, TValue value) {
2 Insert(key, value, true);
3 }
4 private void Insert(TKey key, TValue value, bool add){
5 if( key == null ) {
6 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
7 }
8
9 if (buckets == null) Initialize(0);
10 int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
11 int targetBucket = hashCode % buckets.Length;
12
13 //循環沖突
14 for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
15 if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
16 if (add) {
17 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
18 }
19 entries[i].value = value;
20 version++;
21 return;
22 }
23
24 collisionCount++;
25 }
26
27 //添加元素
28 int index;
29 //是否有空清單
30 if (freeCount > 0) {
31 index = freeList;
32 freeList = entries[index].next;
33 freeCount--;
34 }
35 else {
36 if (count == entries.Length)
37 {
38 Resize();//自動擴容
39 targetBucket = hashCode % buckets.Length;//哈希函數尋址
40 }
41 index = count;
42 count++;
43 }
44
45 entries[index].hashCode = hashCode;
46 entries[index].next = buckets[targetBucket];
47 entries[index].key = key;
48 entries[index].value = value;
49 buckets[targetBucket] = index;
50
51 //單連結的節點數（沖突數）達到了一定的門檻值，之後更新散列值
52 if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer))
53 {
54 comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer);
55 Resize(entries.Length, true);
56 }
57 } 思路分析：
（1）通過哈希函數尋址，計算出哈希位址（因為中間有一個解耦關系buckets，是以不再直接指向entries的索引值，而是buckets的索引）。
（2）判斷buckets中映射到的值是否為-1（即為空位）。若不為-1，表示有沖突，周遊沖突鍊，不允許重複的鍵。
（3）判斷是否有空連結清單，有則插入空連結清單的目前位置，将freeList指針後移，freeCount減一，否則将元素插入目前空位。在這一步，容量不足将自動擴容，若目前位置已經存在元素則将該元素的位址存在插入元素的next中，形成一個單連結清單的形式。類似下圖中的索引0。
移除
1 public bool Remove(TKey key) {
2 if(key == null) {
3 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
4 }
5
6 if (buckets != null) {
7 int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
8 int bucket = hashCode % buckets.Length;
9 int last = -1;//記錄上一個節點
10 //定位到一個單連結清單，每一個節點都會儲存下一個節點的位址，操作不再重新計算哈希位址
11 for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) {
12 if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
13 if (last < 0) {
14 buckets[bucket] = entries[i].next;
15 }
16 else {
17 entries[last].next = entries[i].next;
18 }
19 entries[i].hashCode = -1;//移除的元素散列值值為-1
20 entries[i].next = freeList;//将移除的元素放入空清單
21 entries[i].key = default(TKey);
22 entries[i].value = default(TValue);
23 freeList = i;//記錄目前位址，以便下個元素能直接插入
24 freeCount++;//空連結清單節點數+1
25 version++;
26 return true;
27 }
28 }
29 }
30 return false;
31 } Dictionary中存儲元素的結構非常有趣，通過一個資料桶buckets将哈希函數與資料數組進行了解耦，使得每一個buckets的值對應的都是一條單連結清單，在記憶體空間上卻是連續的存儲塊。同時Dictionary在空間與性能之間做了一些取舍，消耗了空間，提升了性能（影響性能的最大因素是哈希函數）。
移除思路分析：
（1）通過哈希函數确定單連結清單的位置，然後進行周遊。
（2）該索引對應的值為-1，表示沒有沒有單連結節點，傳回false，結束
（3）該索引對應的值大于-1，表示有單連結清單節點，進行周遊，對比散列值與key，将映射到的entries節點散列值賦-1，next指向空連結清單的第一個元素位址（-1為頭節點），freeList指向頭節點位址，空連結清單節點數+1，傳回true，結束；否則傳回false，結束。（此處的節點位址統指索引值）。
查詢
1 public bool TryGetValue(TKey key, out TValue value) {
2 int i = FindEntry(key);//關鍵方法
3 if (i >= 0) {
4 value = entries[i].value;
5 return true;
6 }
7 value = default(TValue);
8 return false;
9 }
10
11
12 private int FindEntry(TKey key) {
13 if( key == null) {
14 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
15 }
16
17 if (buckets != null) {
18 int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
19 for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
20 if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
21 }
22 }
23 return -1;
24 } 代碼是不是一目了然，在FindEntry方法中，定位單連結的位置，進行周遊，對比散列值與key，比較成功則傳回true，結束。
擴容
1 private void Resize() {
2 Resize(HashHelpers.ExpandPrime(count), false);
3 }
4
5 private void Resize(int newSize, bool forceNewHashCodes) {
6 Contract.Assert(newSize >= entries.Length);
7
8 //重新初始化一個比原來空間還要大2倍左右的buckets和Entries，用于接收原來的buckets和Entries的資料
9 int[] newBuckets = new int[newSize];
10 for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
11 Entry[] newEntries = new Entry[newSize];
12
13 //資料搬家
14 Array.Copy(entries, 0, newEntries, 0, count);
15
16 //将散列值重新整理，這是在某一個單連結清單節點數到達一個門檻值（100）時觸發
17 if(forceNewHashCodes) {
18 for (int i = 0; i < count; i++) {
19 if(newEntries[i].hashCode != -1) {
20 newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);
21 }
22 }
23 }
24
25 //單連結清單資料對齊,無關順序
26 for (int i = 0; i < count; i++) {
27 if (newEntries[i].hashCode >= 0) {
28 int bucket = newEntries[i].hashCode % newSize;
29 newEntries[i].next = newBuckets[bucket];
30 newBuckets[bucket] = i;
31 }
32 }
33 buckets = newBuckets;
34 entries = newEntries;
35 } foreach周遊
Dictionary實作了IEnumerator接口，是可以用foreach進行周遊的，周遊的集合元素類型為KeyValuePair，是一種鍵值對的結構，實作是很簡單的，包含了最基本的鍵屬性和值屬性，
從代碼中可以看出，用foreach周遊Dictionary就像用for周遊一個基礎數組一樣。
這是内部類Enumerator（周遊就是對它進行的操作）中的方法MoveNext（實作IEnumerator接口的MoveNext方法）。
1 public bool MoveNext() {
2 if (version != dictionary.version) {
3 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
4 }
5
6 while ((uint)index < (uint)dictionary.count) {
7 if (dictionary.entries[index].hashCode >= 0) {
8 current = new KeyValuePair<TKey, TValue>(dictionary.entries[index].key, dictionary.entries[index].value);
9 index++;
10 return true;
11 }
12 index++;
13 }
14
15 index = dictionary.count + 1;
16 current = new KeyValuePair<TKey, TValue>();
17 return false;
18 }
19
20
21 public struct KeyValuePair<TKey, TValue> {
22 private TKey key;
23 private TValue value;
24
25 public KeyValuePair(TKey key, TValue value) {
26 this.key = key;
27 this.value = value;
28 }
29
30 //鍵屬性
31 public TKey Key {
32 get { return key; }
33 }
34
35 //值屬性
36 public TValue Value {
37 get { return value; }
38 }
39
40 public override string ToString() {
41 StringBuilder s = StringBuilderCache.Acquire();
42 s.Append('[');
43 if( Key != null) {
44 s.Append(Key.ToString());
45 }
46 s.Append(", ");
47 if( Value != null) {
48 s.Append(Value.ToString());
49 }
50 s.Append(']');
51 return StringBuilderCache.GetStringAndRelease(s);
52 }
53 } Dictionary内部實作結構比Hashtable複雜，因為具有單連結清單的特性，效率也比Hashtable高。
舉例說明：
一，執行個體化一個Dictionary, Dictionary<string,string> dic=new Dictionary<string,string>();
a,調用Dictionary預設無參構造函數。
b,初始化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,
1），如果該key值和輸入的的“a”字元相同，則對應的value值就是需要查找的值。
2) ，如果該key值和輸入的"a"字元不相同，說明發生了碰撞，這時擷取對應的next值，根據next值定位buckets數組（buckets[next]），然後擷取對應buckets上存儲的值在定位到entriys數組上,......,一直到找到為止。
3），如果該key值和輸入的"a"字元不相同并且對應的next值為-1,則說明Dictionary不包含字元“a”。