分析C#Dictionary的实现原理
⽬录
⼀、理论知识考研政治真题答案
1.1、Hash算法
1.2、Hash桶算法
1.3、解决冲突算法
⼆、Dictionary实现
2.1、Entry结构体
2.2、其它关键私有变量
2.3、Dictionary - Add操作
scar therapy2.4、Dictionary - Find操作
2.5、Dictionary - Remove操作
2.6、Dictionary - Resize操作(扩容)
2.6.1、扩容操作的触发条件
2.6.2、扩容操作如何进⾏
2.7、Dictionary - 再谈Add操作
2.8、Collection版本控制
⼀、理论知识
对于Dictionary的实现原理，其中有两个关键的算法，⼀个是Hash算法，⼀个是⽤于应对Hash碰撞冲突解决算法。
1.1、Hash算法
Hash算法是⼀种数字摘要算法，它能将不定长度的⼆进制数据集给映射到⼀个较短的⼆进制长度数据集，常见的MD5算法就是⼀种Hash算法，通过MD5算法可对任何数据⽣成数字摘要。⽽实现了Hash
算法的函数我们叫她Hash函数。Hash函数有以下⼏点特征。
相同的数据进⾏Hash运算，得到的结果⼀定相同。HashFunc(key1) == HashFunc(key1)
不同的数据进⾏Hash运算，其结果也可能会相同，(Hash会产⽣碰撞)。key1 != key2 => HashFunc(key1) == HashFunc(key2).
Hash运算时不可逆的，不能由key获取原始的数据。key1 => hashCode但是hashCode =\=> key1。
下图就是Hash函数的⼀个简单说明，任意长度的数据通过HashFunc映射到⼀个较短的数据集中。
关于Hash碰撞下图很清晰的就解释了，可从图中得知Sandra Dee和John Smith通过hash运算后都落到了02的位置，产⽣了碰撞和冲突。
常见的构造Hash函数的算法有以下⼏种：
1. 直接寻址法：取keyword或keyword的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，当中a和b为常数（这样的散列函数叫做⾃⾝函数）新视野大学英语1
2. 数字分析法：分析⼀组数据，⽐⽅⼀组员⼯的出⽣年⽉⽇，这时我们发现出⽣年⽉⽇的前⼏位数字⼤体同样，这种话，出现冲突的⼏率就会⾮常⼤，可是我们发现年⽉⽇的后⼏位表⽰⽉份和详细⽇期的数字区别⾮常⼤，假设⽤后⾯的数字来构成散列地址，则冲突的⼏率会明显减少。因此数字分析法就是找出数字的规律，尽可能利⽤这些数据来构造冲突⼏率较低的散列地址。
3. 平⽅取中法：取keyword平⽅后的中间⼏位作为散列地址。
4. 折叠法：将keyword切割成位数同样的⼏部分，最后⼀部分位数能够不同，然后取这⼏部分的叠加和（去除进位）作为散列地址。
5. 随机数法：选择⼀随机函数，取keyword的随机值作为散列地址，通经常使⽤于keyword长度不同的场合。
6. 除留余数法：取keyword被某个不⼤于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅能够对keyword直接取模，也可在折叠、平⽅取中等运算之后取模。对p的选
择⾮常重要，⼀般取素数或m，若p选的不好，容易产⽣碰撞.
1.2、Hash桶算法
说到Hash算法⼤家就会想到Hash表，⼀个Key通过Hash函数运算后可快速的得到hashCode，通过hashCode的映射可直接Get到Value，但是hashCode⼀般取值都是⾮常⼤的，经常是2^32以上，不可能对每个hashCode都指定⼀个映射。
因为这样的⼀个问题，所以⼈们就将⽣成的HashCode以分段的形式来映射，把每⼀段称之为⼀个Bucket（桶），⼀般常见的Hash桶就是直接对结果取余。
假设将⽣成的hashCode可能取值有2^32个，然后将其切分成⼀段⼀段，使⽤8个桶来映射，那么就可以通过bucketIndex = HashFunc(key1) % 8这样⼀个算法来确定这个hashCode映射到具体的哪个桶中。
⼤家可以看出来，通过hash桶这种形式来进⾏映射，所以会加剧hash的冲突。
1.3、解决冲突算法
对于⼀个hash算法，不可避免的会产⽣冲突，那么产⽣冲突以后如何处理，是⼀个很关键的地⽅，⽬
前常见的冲突解决算法有拉链法(Dictionary实现采⽤的)、开放定址法、再Hash法、公共溢出分区法，本⽂只介绍拉链法与再Hash法，对于其它算法感兴趣的同学可参考⽂章最后的参考⽂献。
1. 拉链法：这种⽅法的思路是将产⽣冲突的元素建⽴⼀个单链表，并将头指针地址存储⾄Hash表对应桶的位置。这样定位到Hash表桶的位置后可通过遍历单链表的形式来查找元素。
mak
2. 再Hash法：顾名思义就是将key使⽤其它的Hash函数再次Hash，直到找到不冲突的位置为⽌。
对于拉链法有⼀张图来描述，通过在冲突位置建⽴单链表，来解决冲突。
⼆、Dictionary实现
Dictionary实现我们主要对照源码来解析，⽬前对照源码的版本是.Net Framwork 4.7。地址可戳⼀戳这个链接源码地址：
这⼀章节中主要介绍Dictionary中⼏个⽐较关键的类和对象，然后跟着代码来⾛⼀遍插⼊、删除和扩容的流程，相信⼤家就能理解它的设计原理。
2.1、Entry结构体
⾸先我们引⼊Entry这样⼀个结构体，它的定义如下代码所⽰。这是Dictionary种存放数据的最⼩单位，调⽤Add(Key,Value)⽅法添加的元素都会被封装在这样的⼀个结构体中。
private struct Entry {
public int hashCode; // 除符号位以外的31位hashCode值, 如果该Entry没有被使⽤，那么为-1
public int next; // 下⼀个元素的下标索引，如果没有下⼀个就为-1
public TKey key; // 存放元素的键
public TValue value; // 存放元素的值
}treble
2.2、其它关键私有变量
除了Entry结构体外，还有⼏个关键的私有变量，其定义和解释如下代码所⽰。
private int[] buckets; // Hash桶
private Entry[] entries; // Entry数组，存放元素
private int count; // 当前entries的index位置
private int version; // 当前版本，防⽌迭代过程中集合被更改
private int freeList; // 被删除Entry在entries中的下标index，这个位置是空闲的
private int freeCount; // 有多少个被删除的Entry，有多少个空闲的位置
private IEqualityComparer<TKey> comparer; // ⽐较器
private KeyCollection keys; // 存放Key的集合
private ValueCollection values; // 存放Value的集合
上⾯代码中，需要注意的是buckets、entries这两个数组，这是实现Dictionary的关键。
2.3、Dictionary - Add操作
经过上⾯的分析，相信⼤家还不是特别明⽩为什么需要这么设计，需要这么做。那我们现在来⾛⼀遍Dictionary的Add流程，来体会⼀下。
⾸先我们⽤图的形式来描述⼀个Dictionary的数据结构，其中只画出了关键的地⽅。桶⼤⼩为4以及Entry⼤⼩也为4的⼀个数据结构。
日射
然后我们假设需要执⾏⼀个Add操作，dictionary.Add("a","b")，其中key = "a",value = "b"。
1.根据key的值，计算出它的hashCode。我们假设"a"的hash值为6（GetHashCode("a") = 6）。
2.通过对hashCode取余运算，计算出该hashCode落在哪⼀个buckets桶中。现在桶的长度（buckets.Length）为4，那么就是6 % 4最后落在index为2的桶中，也就是buckets[2]。
3.避开⼀种其它情况不谈，接下来它会将hashCode、key、value等信息存⼊entries[count]中，因为count位置是空闲的；继续count++指向下⼀个空闲位置。上图中第⼀个位置，index=0就是空闲的，所以就存放在entries[0]的位置。
4.将Entry的下标entryIndex赋值给buckets中对应下标的bucket。步骤3中是存放在entries[0]的位置，所以buckets[2]=0。
5.最后version++，集合发⽣了变化，所以版本需要+1。只有增加、替换和删除元素才会更新版本
rambus上⽂中的步骤1~5只是⽅便⼤家理解，实际上有⼀些偏差，后⽂再谈Add操作⼩节中会补充。
完成上⾯Add操作后，数据结构更新成了下图这样的形式。
这样是理想情况下的操作，⼀个bucket中只有⼀个hashCode没有碰撞的产⽣，但是实际上是会经常产⽣碰撞；那么Dictionary类中⼜是如何解决碰撞的呢。
我们继续执⾏⼀个Add操作，dictionary.Add("c","d")，假设GetHashCode(“c”)=6，最后6 % 4 = 2。最后桶的index也是2，按照之前的步骤1~3是没有问题的，执⾏完后数据结构如下图所⽰。
如果继续执⾏步骤4那么buckets[2] = 1，然后原来的buckets[2]=>entries[0]的关系就会丢失，这是我们不愿意看到的。现在Entry中的next就发挥⼤作⽤了。
如果对应的buckets[index]有其它元素已经存在，那么会执⾏以下两条语句，让新的指向之前的元素，让buckets[index]指向现在的新的元素，就构成了⼀个单链表。entries[index].next = buckets[targetBucket];
...
buckets[targetBucket] = index;
实际上步骤4也就是做⼀个这样的操作，并不会去判断是不是有其它元素，因为buckets中桶初始值就是-1，不会造成问题。
经过上⾯的步骤以后，数据结构就更新成了下图这个样⼦。
2.4、Dictionary - Find操作
为了⽅便演⽰如何查找，我们继续Add⼀个元素dictionary.Add("e","f")，GetHashCode(“e”) = 7; 7% buckets.Length=3，数据结构如下所⽰。
假设我们现在执⾏这样⼀条语句dictionary.GetValueOrDefault("a")，会执⾏以下步骤.
1.获取key的hashCode，计算出所在的桶位置。我们之前提到，"a"的hashCode=6，所以最后计算出来targetBucket=2。
2.通过buckets[2]=1找到entries[1],⽐较key的值是否相等，相等就返回entryIndex，不想等就继续entries[next]查找，直到找到key相等元素或者next == -1的时候。这⾥我们找到了key == "a"的元素，返回entryIndex=0。
3.如果entryIndex >= 0那么返回对应的entries[entryIndex]元素，否则返回default(TValue)。这⾥我们直接返回entries[0].value。
整个查找的过程如下图所⽰.
diplomatic是什么意思
将查找的代码摘录下来，如下所⽰。
// 寻找Entry元素的位置
private int FindEntry(TKey key) {
if( key == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets != null) {
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; // 获取HashCode，忽略符号位
// int i = buckets[hashCode % buckets.Length] 找到对应桶，然后获取entry在entries中位置
// i >= 0; i = entries[i].next 遍历单链表
qinhuangdaofor (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
/
/ 找到就返回了
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
}
}
return -1;
}vertical是什么意思
...
internal TValue GetValueOrDefault(TKey key) {
int i = FindEntry(key);
// ⼤于等于0代表找到了元素位置，直接返回value
// 否则返回该类型的默认值
if (i >= 0) {
return entries[i].value;
}
return default(TValue);
}
2.5、Dictionary - Remove操作
前⾯已经向⼤家介绍了增加、查找，接下来向⼤家介绍Dictionary如何执⾏删除操作。我们沿⽤之前的Dictionary数据结构。
删除前⾯步骤和查找类似，也是需要找到元素的位置，然后再进⾏删除的操作。
我们现在执⾏这样⼀条语句dictionary.Remove("a")，hashFunc运算结果和上⽂中⼀致。步骤⼤部分与查找类似，我们直接看摘录的代码，如下所⽰。
