Dictionary实现原理(元素位置浅析操作扩容)

对于C#中的 Dictionary 类相信大家都不陌生，这是一个 Collection(集合) 类型，可以通过 Key/Value(键值对 的形式来存放数据；该类最大的优点就是它查找元素的时间复杂度接近 O(1) ，实际项目中常被用来做一些数据的本地缓存，提升整体效率。

那么是什么样的设计能使得 Dictionary 类能实现 O(1) 的时间复杂度呢？那就是本篇文章想和大家讨论的东西；这些都是个人的一些理解和观点， 如有表述不清楚、错误之处，请大家批评指正，共同进步。

对于Dictionary的实现原理，其中有两个关键的算法，一个是 Hash 算法，一个是用于应对Hash碰撞 冲突解决 算法。

Hash算法是一种 数字摘要 算法，它能将不定长度的二进制数据集给 映射 到一个较短的二进制长度数据集，常见的MD5算法就是一种Hash算法，通过MD5算法可对任何数据生成数字摘要。
而实现了Hash算法的函数我们叫她 Hash函数 。
Hash函数有以下几点特征。

下图就是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, p<=m。
不仅能够对keyword直接取模，也可在折叠、平方取中等运算之后取模。
对p的选择非常重要，一般取素数或m，若p选的不好，容易产生碰撞.

说到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的冲突。

对于一个hash算法，不可避免的会产生冲突，那么产生冲突以后如何处理，是一个很关键的地方，目前常见的冲突解决算法有 拉链法(Dictionary实现采用的)、开放定址法、再Hash法、公共溢出分区法 ，本文只介绍拉链法与再Hash法，对于其它算法感兴趣的同学可参考文章最后的参考文献。

1. 拉链法：这种方法的思路是将产生冲突的元素建立一个单链表，并将头指针地址存储至Hash表对应桶的位置。
这样定位到Hash表桶的位置后可通过遍历单链表的形式来查找元素。

2. 再Hash法：顾名思义就是将key使用其它的Hash函数再次Hash，直到找到不冲突的位置为止。

对于拉链法有一张图来描述，通过在冲突位置建立单链表，来解决冲突。

三、Dictionary实现

Dictionary实现我们主要对照源码来解析，目前对照源码的版本是 .Net Framwork 4.7 。
地址可戳一戳这个链接 源码地址：Link

这一章节中主要介绍Dictionary中几个比较关键的类和对象，然后跟着代码来走一遍插入、删除和扩容的流程，相信大家就能理解它的设计原理。

首先我们引入 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; // 存放元素的值}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的关键。

经过上面的分析，相信大家还不是特别明白为什么需要这么设计，需要这么做。
那我们现在来走一遍Dictionary的Add流程，来体会一下。

首先我们用图的形式来描述一个Dictionary的数据结构，其中只画出了关键的地方。
桶大小为4以及Entry大小也为4的一个数据结构。

然后我们假设需要执行一个 Add 操作， dictionary.Add("a","b") ，其中 key = "a",value = "b" 。

完成上面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] 有其它元素已经存在，那么会执行以下两条语句，让新的 entry.next 指向之前的元素，让 buckets[index] 指向现在的新的元素，就构成了一个单链表。

entries[index].next = buckets[targetBucket];...buckets[targetBucket] = index;

实际上 步骤4 也就是做一个这样的操作，并不会去判断是不是有其它元素，因为 buckets 中桶初始值就是-1，不会造成问题。

经过上面的步骤以后，数据结构就更新成了下图这个样子。

4. Dictionary - Find操作

为了方便演示如何查找，我们继续Add一个元素 dictionary.Add("e","f") ， GetHashCode(“e”) = 7; 7% buckets.Length=3 ,数据结构如下所示。

假设我们现在执行这样一条语句 dictionary.GetValueOrDefault("a") ，会执行以下步骤.

整个查找的过程如下图所示.

将查找的代码摘录下来，如下所示。

// 寻找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);}5. Dictionary - Remove操作

前面已经向大家介绍了增加、查找，接下来向大家介绍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 的值都被更新了。

6. Dictionary - Resize操作(扩容)

有细心的小伙伴可能看过了 Add 操作以后就想问了， buckets、entries 不就是两个数组么，那万一数组放满了怎么办？接下来就是我所要介绍的 Resize（扩容） 这样一种操作，对我们的 buckets、entries 进行扩容。

首先我们需要知道在什么情况下，会发生扩容操作； 第一种情况自然就是数组已经满了，没有办法继续存放新的元素。
如下图所示的情况。

从上文中大家都知道，Hash运算会不可避免的产生冲突，Dictionary中使用拉链法来解决冲突的问题，但是大家看下图中的这种情况。

所有的元素都刚好落在 buckets[3] 上面，结果就是导致了 时间复杂度O(n) ，查找性能会下降；所以 第二种，Dictionary中发生的碰撞次数太多，会严重影响性能， 也会触发扩容操作。

public const int HashCollisionThreshold = 100;6.2 扩容操作如何进行

为了给大家演示的清楚，模拟了以下这种数据结构，大小为2的Dictionary，假设碰撞的阈值为2；现在触发Hash碰撞扩容。

开始扩容操作。

1.申请两倍于现在大小的buckets、entries

2.将现有的元素拷贝到新的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 的一些集合实现。

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;}7. Dictionary - 再谈Add操作

在我们之前的 Add 操作步骤中，提到了这样一段话，这里提到会有一种其它的情况，那就是 有元素被删除 的情况。

因为 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<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer); Resize(entries.Length, true); }}

上面就是完整的 Add 代码，还是很简单的对不对？

在上文中一直提到了 version 这个变量，在每一次新增、修改和删除操作时，都会使 version++ ；那么这个 version 存在的意义是什么呢？

首先我们来看一段代码，这段代码中首先实例化了一个Dictionary实例，然后通过 foreach 遍历该实例，在 foreach 代码块中使用 dic.Remove(kv.Key) 删除元素。

结果就是抛出了 System.InvalidOperationException:"Collection was modified..." 这样的异常， 迭代过程中不允许集合出现变化 。
如果在Java中遍历直接删除元素，会出现诡异的问题，所以.Net中就使用了 version 来实现版本控制。

那么如何在迭代过程中实现版本控制的呢？我们看一看源码就很清楚的知道。

在迭代器初始化时，就会记录 dictionary.version 版本号，之后每一次迭代过程都会检查版本号是否一致，如果不一致将抛出异常。

作者：InCerry

出处：https://www.cnblogs.com/InCerry/p/10325290.html