本篇文章配图以及文字其实整理出来很久了，但是由于各种各样的原因推迟到现在才发出来，还有之前立Flag的《多线程编程》的笔记也都已经写好了，只是说还比较糙，需要找个时间整理一下才能和大家见面。
对于C#中的Dictionary类相信大家都不陌生，这是一个Collection(集合)类型，可以通过Key/Value(键值对的形式来存放数据；该类最大的优点就是它查找元素的时间复杂度接近O(1)，实际项目中常被用来做一些数据的本地缓存，提升整体效率。
那么是什么样的设计能使得Dictionary类能实现O(1)的时间复杂度呢？那就是本篇文章想和大家讨论的东西；这些都是个人的一些理解和观点，如有表述不清楚、错误之处，请大家批评指正，共同进步。
对于Dictionary的实现原理，其中有两个关键的算法，一个是Hash算法，一个是用于应对Hash碰撞冲突解决算法。
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为常数（这样的散列函数叫做自身函数）
2. 数字分析法：分析一组数据，比方一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体同样，这种话，出现冲突的几率就会非常大，可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大，假设用后面的数字来构成散列地址，则冲突的几率会明显减少。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
3. 平方取中法：取keyword平方后的中间几位作为散列地址。
4. 折叠法：将keyword切割成位数同样的几部分，最后一部分位数能够不同，然后取这几部分的叠加和（去除进位）作为散列地址。
5. 随机数法：选择一随机函数，取keyword的随机值作为散列地址，通经常使用于keyword长度不同的场合。
6. 除留余数法：取keyword被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, pentries[0]的关系就会丢失，这是我们不愿意看到的。现在Entry中的next就发挥大作用了。
如果对应的buckets[index]有其它元素已经存在，那么会执行以下两条语句，让新的entry.next指向之前的元素，让buckets[index]指向现在的新的元素，就构成了一个单链表。
entries[index].next = buckets[targetBucket];
...
buckets[targetBucket] = index;
实际上步骤4也就是做一个这样的操作，并不会去判断是不是有其它元素，因为buckets中桶初始值就是-1，不会造成问题。
经过上面的步骤以后，数据结构就更新成了下图这个样子。
为了方便演示如何查找，我们继续Add一个元素dictionary.Add("e","f")，GetHashCode(“e”) = 7; 7% buckets.Length=3,数据结构如下所示。
假设我们现在执行这样一条语句dictionary.GetValueOrDefault("a")，会执行以下步骤.
-
获取key的hashCode，计算出所在的桶位置。我们之前提到，"a"的
hashCode=6，所以最后计算出来targetBucket=2。 -
通过
buckets[2]=1找到entries[1],比较key的值是否相等，相等就返回entryIndex，不想等就继续entries[next]查找，直到找到key相等元素或者next == -1的时候。这里我们找到了key == "a"的元素，返回entryIndex=0。 -
如果
entryIndex >= 0那么返回对应的entries[entryIndex]元素，否则返回default(TValue)。这里我们直接返回entries[0].value。
整个查找的过程如下图所示.
将查找的代码摘录下来，如下所示。
// 寻找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 遍历单链表
for (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;
}
...
internal TValue GetValueOrDefault(TKey key) {
int i = FindEntry(key);
// 大于等于0代表找到了元素位置，直接返回value
// 否则返回该类型的默认值
if (i >= 0) {
return entries[i].value;
}
return default(TValue);
}
前面已经向大家介绍了增加、查找，接下来向大家介绍Dictionary如何执行删除操作。我们沿用之前的Dictionary数据结构。
删除前面步骤和查找类似，也是需要找到元素的位置，然后再进行删除的操作。
我们现在执行这样一条语句dictionary.Remove("a")，hashFunc运算结果和上文中一致。步骤大部分与查找类似，我们直接看摘录的代码，如下所示。
public bool Remove(TKey key) {
if(key == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets != null) {
// 1. 通过key获取hashCode
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
// 2. 取余获取bucket位置
int bucket = hashCode % buckets.Length;
// last用于确定是否当前bucket的单链表中最后一个元素
int last = -1;
// 3. 遍历bucket对应的单链表
for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
// 4. 找到元素后，如果last< 0，代表当前是bucket中最后一个元素，那么直接让bucket内下标赋值为 entries[i].next即可
if (last < 0) {
buckets[bucket] = entries[i].next;
}
else {
// 4.1 last不小于0，代表当前元素处于bucket单链表中间位置，需要将该元素的头结点和尾节点相连起来,防止链表中断
entries[last].next = entries[i].next;
}
// 5. 将Entry结构体内数据初始化
entries[i].hashCode = -1;
// 5.1 建立freeList单链表
entries[i].next = freeList;
entries[i].key = default(TKey);
entries[i].value = default(TValue);
// *6. 关键的代码，freeList等于当前的entry位置，下一次Add元素会优先Add到该位置
freeList = i;
freeCount++;
// 7. 版本号+1
version++;
return true;
}
}
}
return false;
}
执行完上面代码后，数据结构就更新成了下图所示。需要注意varsion、freeList、freeCount的值都被更新了。
有细心的小伙伴可能看过了Add操作以后就想问了，buckets、entries不就是两个数组么，那万一数组放满了怎么办？接下来就是我所要介绍的Resize（扩容）这样一种操作，对我们的buckets、entries进行扩容。
6.1 扩容操作的触发条件
首先我们需要知道在什么情况下，会发生扩容操作；第一种情况自然就是数组已经满了，没有办法继续存放新的元素。如下图所示的情况。
从上文中大家都知道，Hash运算会不可避免的产生冲突，Dictionary中使用拉链法来解决冲突的问题，但是大家看下图中的这种情况。
所有的元素都刚好落在buckets[3]上面，结果就是导致了时间复杂度O(n)，查找性能会下降；所以第二种，Dictionary中发生的碰撞次数太多，会严重影响性能，也会触发扩容操作。
目前.Net Framwork 4.7中设置的碰撞次数阈值为100.
public const int HashCollisionThreshold = 100;
6.2 扩容操作如何进行
为了给大家演示的清楚，模拟了以下这种数据结构，大小为2的Dictionary，假设碰撞的阈值为2；现在触发Hash碰撞扩容。
开始扩容操作。
1.申请两倍于现在大小的buckets、entries2.将现有的元素拷贝到新的entries
完成上面两步操作后，新数据结构如下所示。
3、如果是Hash碰撞扩容，使用新HashCode函数重新计算Hash值
上文提到了，这是发生了Hash碰撞扩容，所以需要使用新的Hash函数计算Hash值。新的Hash函数并一定能解决碰撞的问题，有可能会更糟，像下图中一样的还是会落在同一个bucket上。
4、对entries每个元素bucket = newEntries[i].hashCode % newSize确定新buckets位置
**5、重建hash链，newEntries[i].next=buckets[bucket]; buckets[bucket]=i; **
因为buckets也扩充为两倍大小了，所以需要重新确定hashCode在哪个bucket中；最后重新建立hash单链表.
这就完成了扩容的操作，如果是达到Hash碰撞阈值触发的扩容可能扩容后结果会更差。
在JDK中，HashMap如果碰撞的次数太多了，那么会将单链表转换为红黑树提升查找性能。目前.Net Framwork中还没有这样的优化，.Net Core中已经有了类似的优化，以后有时间在分享.Net Core的一些集合实现。
每次扩容操作都需要遍历所有元素，会影响性能。所以创建Dictionary实例时最好设置一个预估的初始大小。
private void Resize(int newSize, bool forceNewHashCodes) {
Contract.Assert(newSize >= entries.Length);
// 1. 申请新的Buckets和entries
int[] newBuckets = new int[newSize];
for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
Entry[] newEntries = new Entry[newSize];
// 2. 将entries内元素拷贝到新的entries总
Array.Copy(entries, 0, newEntries, 0, count);
// 3. 如果是Hash碰撞扩容，使用新HashCode函数重新计算Hash值
if(forceNewHashCodes) {
for (int i = 0; i < count; i++) {
if(newEntries[i].hashCode != -1) {
newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);
}
}
}
// 4. 确定新的bucket位置
// 5. 重建Hahs单链表
for (int i = 0; i < count; i++) {
if (newEntries[i].hashCode >= 0) {
int bucket = newEntries[i].hashCode % newSize;
newEntries[i].next = newBuckets[bucket];
newBuckets[bucket] = i;
}
}
buckets = newBuckets;
entries = newEntries;
}
在我们之前的Add操作步骤中，提到了这样一段话，这里提到会有一种其它的情况，那就是有元素被删除的情况。
-
避开一种其它情况不谈，接下来它会将
hashCode、key、value等信息存入entries[count]中，因为count位置是空闲的；继续count++指向下一个空闲位置。上图中第一个位置，index=0就是空闲的，所以就存放在entries[0]的位置。
因为count是通过自增的方式来指向entries[]下一个空闲的entry，如果有元素被删除了，那么在count之前的位置就会出现一个空闲的entry；如果不处理，会有很多空间被浪费。
这就是为什么Remove操作会记录freeList、freeCount，就是为了将删除的空间利用起来。实际上Add操作会优先使用freeList的空闲entry位置，摘录代码如下。
private void Insert(TKey key, TValue value, bool add){
if( key == null ) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets == null) Initialize(0);
// 通过key获取hashCode
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
// 计算出目标bucket下标
int targetBucket = hashCode % buckets.Length;
// 碰撞次数
int collisionCount = 0;
for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
// 如果是增加操作，遍历到了相同的元素，那么抛出异常
if (add) {
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
}
// 如果不是增加操作，那可能是索引赋值操作 dictionary["foo"] = "foo"
// 那么赋值后版本++，退出
entries[i].value = value;
version++;
return;
}
// 每遍历一个元素，都是一次碰撞
collisionCount++;
}
int index;
// 如果有被删除的元素，那么将元素放到被删除元素的空闲位置
if (freeCount > 0) {
index = freeList;
freeList = entries[index].next;
freeCount--;
}
else {
// 如果当前entries已满，那么触发扩容
if (count == entries.Length)
{
Resize();
targetBucket = hashCode % buckets.Length;
}
index = count;
count++;
}
// 给entry赋值
entries[index].hashCode = hashCode;
entries[index].next = buckets[targetBucket];
entries[index].key = key;
entries[index].value = value;
buckets[targetBucket] = index;
// 版本号++
version++;
// 如果碰撞次数大于设置的最大碰撞次数，那么触发Hash碰撞扩容
if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer))
{
comparer = (IEqualityComparer) HashHelpers.GetRandomizedEqualityComparer(comparer);
Resize(entries.Length, true);
}
}
上面就是完整的Add代码，还是很简单的对不对？
8. Collection版本控制在上文中一直提到了version这个变量，在每一次新增、修改和删除操作时，都会使version++；那么这个version存在的意义是什么呢？
首先我们来看一段代码，这段代码中首先实例化了一个Dictionary实例，然后通过foreach遍历该实例，在foreach代码块中使用dic.Remove(kv.Key)删除元素。
结果就是抛出了System.InvalidOperationException:"Collection was modified..."这样的异常，迭代过程中不允许集合出现变化。如果在Java中遍历直接删除元素，会出现诡异的问题，所以.Net中就使用了version来实现版本控制。
那么如何在迭代过程中实现版本控制的呢？我们看一看源码就很清楚的知道。
在迭代器初始化时，就会记录dictionary.version版本号，之后每一次迭代过程都会检查版本号是否一致，如果不一致将抛出异常。
这样就避免了在迭代过程中修改了集合，造成很多诡异的问题。
四、参考文献及总结本文在编写过程中，主要参考了以下文献，在此感谢其作者在知识分享上作出的贡献！
-
http://www.cnblogs.com/mengfanrong/p/4034950.html
-
https://en.wikipedia.org/wiki/Hash_table
-
https://www.cnblogs.com/wuchaodzxx/p/7396599.html
-
https://www.cnblogs.com/liwei2222/p/8013367.html
-
https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,fd1acf96113fbda9
