网站地图怎么做,网站加上视频对seo影响,视频教学网站怎么做,高端品牌网站定制一、前言二、理论知识1、Hash 算法2、Hash 桶算法3、解决冲突算法三、Dictionary 实现1. Entry 结构体2. 其它关键私有变量3. Dictionary - Add 操作4. Dictionary - Find 操作5. Dictionary - Remove 操作6. Dictionary - Resize 操作(扩容)7. Dictionary - 再谈 Add 操作8. C…一、前言二、理论知识1、Hash 算法2、Hash 桶算法3、解决冲突算法三、Dictionary 实现1. Entry 结构体2. 其它关键私有变量3. Dictionary - Add 操作4. Dictionary - Find 操作5. Dictionary - Remove 操作6. Dictionary - Resize 操作(扩容)7. Dictionary - 再谈 Add 操作8. Collection 版本控制四、参考文献及总结一、前言本篇文章配图以及文字其实整理出来很久了但是由于各种各样的原因推迟到现在才发出来还有之前立 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 映射到一个较短的数据集中。1548491108167关于 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, pm。不仅能够对 keyword 直接取模也可在折叠、平方取中等运算之后取模。对 p 的选择非常重要一般取素数或 m若 p 选的不好容易产生碰撞.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 的冲突。3、解决冲突算法对于一个 hash 算法不可避免的会产生冲突那么产生冲突以后如何处理是一个很关键的地方目前常见的冲突解决算法有拉链法(Dictionary 实现采用的)、开放定址法、再 Hash 法、公共溢出分区法本文只介绍拉链法与再 Hash 法对于其它算法感兴趣的同学可参考文章最后的参考文献。**1. 拉链法**这种方法的思路是将产生冲突的元素建立一个单链表并将头指针地址存储至 Hash 表对应桶的位置。这样定位到 Hash 表桶的位置后可通过遍历单链表的形式来查找元素。**2. 再 Hash 法**顾名思义就是将 key 使用其它的 Hash 函数再次 Hash直到找到不冲突的位置为止。对于拉链法有一张图来描述通过在冲突位置建立单链表来解决冲突。1548485607652三、Dictionary 实现Dictionary 实现我们主要对照源码来解析目前对照源码的版本是**.Net Framwork 4.7**。地址可戳一戳这个链接 源码地址Link[1]这一章节中主要介绍 Dictionary 中几个比较关键的类和对象然后跟着代码来走一遍插入、删除和扩容的流程相信大家就能理解它的设计原理。1. Entry 结构体首先我们引入Entry这样一个结构体它的定义如下代码所示。这是 Dictionary 种存放数据的最小单位调用Add(Key,Value)方法添加的元素都会被封装在这样的一个结构体中。private struct Entry {public int hashCode; // 除符号位以外的31位hashCode值, 如果该Entry没有被使用那么为-1public int next; // 下一个元素的下标索引如果没有下一个就为-1public 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 IEqualityComparerTKey comparer; // 比较器
private KeyCollection keys; // 存放Key的集合
private ValueCollection values; // 存放Value的集合上面代码中需要注意的是buckets、entries这两个数组这是实现 Dictionary 的关键。3. Dictionary - Add 操作经过上面的分析相信大家还不是特别明白为什么需要这么设计需要这么做。那我们现在来走一遍 Dictionary 的 Add 流程来体会一下。首先我们用图的形式来描述一个 Dictionary 的数据结构其中只画出了关键的地方。桶大小为 4 以及 Entry 大小也为 4 的一个数据结构。1548491185593然后我们假设需要执行一个Add操作dictionary.Add(a,b)其中key a,value b。根据key的值计算出它的 hashCode。我们假设a的 hash 值为 6GetHashCode(a) 6。通过对 hashCode 取余运算计算出该 hashCode 落在哪一个 buckets 桶中。现在桶的长度buckets.Length为 4那么就是6 % 4最后落在index为 2 的桶中也就是buckets[2]。避开一种其它情况不谈接下来它会将hashCode、key、value等信息存入entries[count]中因为count位置是空闲的继续count指向下一个空闲位置。上图中第一个位置index0 就是空闲的所以就存放在entries[0]的位置。将Entry的下标entryIndex赋值给buckets中对应下标的bucket。步骤 3 中是存放在entries[0]的位置所以buckets[2]0。最后version集合发生了变化所以版本需要1。只有增加、替换和删除元素才会更新版本上文中的步骤 1~5 只是方便大家理解实际上有一些偏差后文再谈 Add 操作小节中会补充。完成上面 Add 操作后数据结构更新成了下图这样的形式。1548492100757这样是理想情况下的操作一个 bucket 中只有一个 hashCode 没有碰撞的产生但是实际上是会经常产生碰撞那么 Dictionary 类中又是如何解决碰撞的呢。我们继续执行一个Add操作dictionary.Add(c,d)假设GetHashCode(“c”)6最后6 % 4 2。最后桶的index也是 2按照之前的步骤 1~3是没有问题的执行完后数据结构如下图所示。1548493287583如果继续执行步骤 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不会造成问题。经过上面的步骤以后数据结构就更新成了下图这个样子。15484943575664. Dictionary - Find 操作为了方便演示如何查找我们继续 Add 一个元素dictionary.Add(e,f)GetHashCode(“e”) 7; 7% buckets.Length3,数据结构如下所示。1548494583006假设我们现在执行这样一条语句dictionary.GetValueOrDefault(a)会执行以下步骤.获取 key 的 hashCode计算出所在的桶位置。我们之前提到a的hashCode6所以最后计算出来targetBucket2。通过buckets[2]1找到entries[1],比较 key 的值是否相等相等就返回entryIndex不想等就继续entries[next]查找直到找到 key 相等元素或者next -1的时候。这里我们找到了key a的元素返回entryIndex0。如果entryIndex 0那么返回对应的entries[entryIndex]元素否则返回default(TValue)。这里我们直接返回entries[0].value。整个查找的过程如下图所示.1548495296415将查找的代码摘录下来如下所示。// 寻找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 数据结构。1548494583006删除前面步骤和查找类似也是需要找到元素的位置然后再进行删除的操作。我们现在执行这样一条语句dictionary.Remove(a)hashFunc 运算结果和上文中一致。步骤大部分与查找类似我们直接看摘录的代码如下所示。public bool Remove(TKey key) {if(key null) {ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);}if (buckets ! null) {// 1. 通过key获取hashCodeint 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. 版本号1version;return true;}}}return false;
}执行完上面代码后数据结构就更新成了下图所示。需要注意varsion、freeList、freeCount的值都被更新了。15484968151796. Dictionary - Resize 操作(扩容)有细心的小伙伴可能看过了Add操作以后就想问了buckets、entries不就是两个数组么那万一数组放满了怎么办接下来就是我所要介绍的**Resize扩容**这样一种操作对我们的buckets、entries进行扩容。6.1 扩容操作的触发条件首先我们需要知道在什么情况下会发生扩容操作**第一种情况自然就是数组已经满了没有办法继续存放新的元素。**如下图所示的情况。1548498710430从上文中大家都知道Hash 运算会不可避免的产生冲突Dictionary 中使用拉链法来解决冲突的问题但是大家看下图中的这种情况。1548498901496所有的元素都刚好落在buckets[3]上面结果就是导致了时间复杂度 O(n)查找性能会下降所以**第二种Dictionary 中发生的碰撞次数太多会严重影响性能**也会触发扩容操作。目前.Net Framwork 4.7 中设置的碰撞次数阈值为 100.public const int HashCollisionThreshold 100;6.2 扩容操作如何进行为了给大家演示的清楚模拟了以下这种数据结构大小为 2 的 Dictionary假设碰撞的阈值为 2现在触发 Hash 碰撞扩容。1548499708530开始扩容操作。1.申请两倍于现在大小的 buckets、entries 2.将现有的元素拷贝到新的 entries完成上面两步操作后新数据结构如下所示。15484997854413、如果是 Hash 碰撞扩容使用新 HashCode 函数重新计算 Hash 值上文提到了这是发生了 Hash 碰撞扩容所以需要使用新的 Hash 函数计算 Hash 值。新的 Hash 函数并一定能解决碰撞的问题有可能会更糟像下图中一样的还是会落在同一个bucket上。15485001743054、对 entries 每个元素 bucket newEntries[i].hashCode % newSize 确定新 buckets 位置**5、重建 hash 链newEntries[i].nextbuckets[bucket]; buckets[bucket]i; **因为buckets也扩充为两倍大小了所以需要重新确定hashCode在哪个bucket中最后重新建立 hash 单链表.1548500290419这就完成了扩容的操作如果是达到Hash 碰撞阈值触发的扩容可能扩容后结果会更差。在 JDK 中HashMap如果碰撞的次数太多了那么会将单链表转换为红黑树提升查找性能。目前**.Net Framwork中还没有这样的优化.Net Core中已经有了类似的优化以后有时间在分享.Net Core**的一些集合实现。每次扩容操作都需要遍历所有元素会影响性能。所以创建 Dictionary 实例时最好设置一个预估的初始大小。private void Resize(int newSize, bool forceNewHashCodes) {Contract.Assert(newSize entries.Length);// 1. 申请新的Buckets和entriesint[] 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操作步骤中提到了这样一段话这里提到会有一种其它的情况那就是有元素被删除的情况。避开一种其它情况不谈接下来它会将hashCode、key、value等信息存入entries[count]中因为count位置是空闲的继续count指向下一个空闲位置。上图中第一个位置index0 就是空闲的所以就存放在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获取hashCodeint 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 (IEqualityComparerTKey) HashHelpers.GetRandomizedEqualityComparer(comparer);Resize(entries.Length, true);}
}上面就是完整的Add代码还是很简单的对不对8. Collection 版本控制在上文中一直提到了version这个变量在每一次新增、修改和删除操作时都会使version那么这个version存在的意义是什么呢首先我们来看一段代码这段代码中首先实例化了一个 Dictionary 实例然后通过foreach遍历该实例在foreach代码块中使用dic.Remove(kv.Key)删除元素。1548504444217结果就是抛出了System.InvalidOperationException:Collection was modified...这样的异常迭代过程中不允许集合出现变化。如果在 Java 中遍历直接删除元素会出现诡异的问题所以.Net 中就使用了version来实现版本控制。那么如何在迭代过程中实现版本控制的呢我们看一看源码就很清楚的知道。1548504844162在迭代器初始化时就会记录dictionary.version版本号之后每一次迭代过程都会检查版本号是否一致如果不一致将抛出异常。这样就避免了在迭代过程中修改了集合造成很多诡异的问题。四、参考文献及总结本文在编写过程中主要参考了以下文献在此感谢其作者在知识分享上作出的贡献http://www.cnblogs.com/mengfanrong/p/4034950.htmlhttps://en.wikipedia.org/wiki/Hash_tablehttps://www.cnblogs.com/wuchaodzxx/p/7396599.htmlhttps://www.cnblogs.com/liwei2222/p/8013367.htmlhttps://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,fd1acf96113fbda9笔者水平有限如果错误欢迎各位批评指正参考资料[1] Link: https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,d3599058f8d79be0
