浅谈C# Dictionary实现原理

时光错 發表於 2020-3-4 14:30:00

使用C#已经有好多年头了，然后突然有一天被问到C#Dictionary的基本实现，这让我反思到我一直处于拿来主义，能用就好，根本没有去考虑和学习一些底层架构，想想令人头皮发麻。下面开始学习一些我平时用得理所当然的东西，今天先学习一下字典，Dictionary
一、Dictionary源码学习
Dictionary实现我们主要对照源码来解析，目前对照的源码版本是.Net Framwork4.8，源码地址。
这边主要介绍Dictionary中几个比较关键的类和对象，然后跟着代码来走一遍插入、删除和扩容的流程。
1、Entry结构体
首先，我们引入Entry这样一个结构体，它的定义如下面代码所示，这是Dictionary中存放数据的最小单位，调用Add(Key,Value)方法添加的元素都会被封装在这样的一个结构体中。
<div class="cnblogs_code">
<pre>1 private struct Entry
2 {
3 public int hashCode; // Lower 31 bits of hash code, -1 if unused
4 public int next; // Index of next entry, -1 if last
5 public TKey key; // Key of entry
6 public TValue value; // Value of entry
7 }</pre>
</div>
2、其他关键私有变量
<div class="cnblogs_code">
<pre>1 private int[] buckets; // Hash桶
2 private Entry[] entries; // Entry数组，存放元素
3 private int count; // 当前entries的index位置
4 private int version; // 当前版本，防止迭代过程中集合被更改
5 private int freeList; // 被删除Entry在entries中的下标index，这个位置是空闲的
6 private int freeCount; // 有多少个被删除的Entry，有多少个空闲的位置
7 private IEqualityComparer<TKey> comparer; // 比较器
8 private KeyCollection keys; // 存放Key的集合
9 private ValueCollection values; // 存放Value的集合</pre>
</div>
3、Dictionary的构造
<div class="cnblogs_code">
<pre> 1 private void Initialize(int capacity)
 2 {
 3 int prime = HashHelpers.GetPrime(capacity);
 4 this.buckets = new int;
 5 for (int i = 0; i < this.buckets.Length; i++)
 6 {
 7 this.buckets = -1;
 8 }
 9 this.entries = new Entry<TKey, TValue>;
10 this.freeList = -1;
11 }</pre>
</div>
我们看到，Dictionary在构造的时候做了以下几件事：
1、初始化一个this.buchkets=new int
2、初始化一个this.entries=new Entry<TKey,TValue>
3、Bucket和entries的容量都为大于字典容量的一个最小的质数
其中this.buckets主要用来进行Hash碰撞，this.entries用来存储字典的内容，并且标识下一个元素的位置。
4、Dictionary——Add操作
我们以Dictionary<int,string>为例，来展示一下Dictinoary如何添加元素：
首先，我们构造一个，容量为6：
<div class="cnblogs_code">
<pre>Dictionary<int, string> test = new Dictionary<int, string>(6);</pre>
</div>
<img src="https://img2020.cnblogs.com/i-beta/799221/202003/799221-20200303221909829-1764328324.png">
 
<div class="cnblogs_code">
<pre>Test.Add(4,"4")</pre>
</div>
 
根据Hash算法：4.GetHashCode()%7=4，因此碰撞到buckets中下表为4的槽上，此时由于Count为0，因此元素放在Entries中第0个元素上，添加后，Count变为1
 <img src="https://img2020.cnblogs.com/i-beta/799221/202003/799221-20200303222156007-780038641.png">
 
 
<div class="cnblogs_code">
<pre>Test.Add(11,"11")</pre>
</div>
 
 根据Hash算法，11.GetHashCode()%7=4，因此再次碰撞到Buckets中下标为4的槽上，由于此槽上的值已经不是-1，此时Count=1，因此把这个新加的元素放到entries中下标为1的数组中，并且让Buckets槽指向下表为1的entries中，下标为1的entry之下下表为0的entries。
<img src="https://img2020.cnblogs.com/i-beta/799221/202003/799221-20200303222650197-1581269048.png">
 
 
<div class="cnblogs_code">
<pre>Test.Add(18,"18")
Test.Add(19,"19")</pre>
</div>
 
 <img src="https://img2020.cnblogs.com/i-beta/799221/202003/799221-20200303232944066-1911862902.png">
 
 
 5、Dictionary——Remove操作
<div class="cnblogs_code">
<pre>Test.Remove(4)</pre>
</div>
 
我们删除元素时，通过一次碰撞，并且沿着链表寻找3次，找到key为4的元素所在的位置，删除当前元素，并且把FreeList的位置指向当前删除元素的位置，FreeCount置为1。
<img src="https://img2020.cnblogs.com/i-beta/799221/202003/799221-20200303233309365-1932546101.png">
 
 删除的数据会形成一个FreeList的链表，添加数据的时候，优先向FreeList链表中添加数据，FreeList为空则按照count一次排序。
6、Dictionary——Resize操作（扩容）
有细心的小伙伴可能看过Add操作后就想问了，buckets、entries不就是两个数组么，那万一数组放满了怎么办？接下来就是我要介绍的Resize（扩容）这样一种操作，对我们的buckets、entries进行扩容。
6.1 扩容操作的触发条件
首先我们需要直到在什么情况下，会发生扩容操作：
第一种情况自然就是数组已经满了，没有办法继续存放新的元素，如下图所示。
<img src="https://img2020.cnblogs.com/i-beta/799221/202003/799221-20200303233801208-905770786.png">
 第二种，Dictionary中发生的碰撞次数太多，会严重影响性能，也会出发扩容操作。
Hash运算会不可避免的产生冲突，Dictionary中使用拉链发来解决冲突的问题，但是，大家看下图中的这种情况，所有的元素都刚好落在buckets上面，结果就导致了时间复杂度O(n)，查找性能会下降：
<img src="https://img2020.cnblogs.com/i-beta/799221/202003/799221-20200304102658182-1811408608.png">
 
 6.2 扩容操作如何进行
为了给大家演示清楚，模拟了以下这种数据结构，大小为2的Dictionary，假设碰撞的阈值为2；现在出发Hash碰撞扩容。
1、申请两倍于现在大小的buckets、entries
2、将现有的元素拷贝到新的entries
3、如果时Hash碰撞扩容，使用新HashCode函数重新计算Hash值
4、对entries每个元素bucket=newEntries.hashCode%newSize确定新buckets位置
5、重建hash链，newEntries.next=buckets;buckets=i;
关注点
对于Dictionary的实现原理，其中有两个关键的算法，1、Hash算法。2、用于对应Hash碰撞冲突解决算法。
二、Hash算法
Hash算法是一种术宇摘要算法，它将能不定长度的二进制数据集给映射到一个较短的二进制长度数据集。
实现了Hash算法的函数我们叫它Hash函数，Hash函数有以下几点特征。
1、相同的数据进行Hash运算，得到的结果一定是相同的，HashFunc(key1)==HashFunc(key1)
2、不同的数据进行Hash运算，其结果也可能会相同，（Hash会产生碰撞）。key1!=key2=>HashFunc(key1)==HashFunc(key2)。
3、Hash运算是不可逆的，不能由key获取原始的数据，key1=>hashCode但是hashCode==>key1
<img src="https://img2020.cnblogs.com/i-beta/799221/202003/799221-20200304130902770-1900533192.png">
 
 关于Hash碰撞下图很清晰的就解释了，可从图中得知Sandra Dee 和 John Smith 通过hash运算后，落到了02位置，产生了碰撞和冲突。
<img src="https://img2020.cnblogs.com/i-beta/799221/202003/799221-20200304131027369-2088573021.png">
 
 常见的构造Hash函数的算法有以下几种。
1、直接寻址法：取keyword或者keyword的某个线性函数值为散列地址，即H(key)=key或者H(key)=a·key+b，当中a和b为常数（这样的散列函数叫做自身函数）。这个的应用就是，比如我们世界地图的掩码，直接用坐标x*1000+坐标y，得到key。
2、数字分析法：找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。分析一组数据，比方一组员工的出生年月日，这时，我们发现出生年月日的前几位数字大体相同，这种话，出现冲突的几率就会非常大，可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大，假设用后面的数字来构造散列地址，则冲突几率就会明显减少。
3、平方取中法：取keyword平方后的中间几位作为散列地址。
4、折叠法：将keyword切割成位数同样的几部分，最后一部分分数能够不同，然后取这及部分的叠加和（去除进位）作为散列地址。
5、随机数法：选择一随机函数，取keyword的随机值作为散列地址，通常适用于keyword长度不同的场合。
6、除留余数法：取keyword被某个不大于散列表表长m的数p除后所得的余数为散列地址。即H(key)=key MOP p ,  p<=m。不仅能够对keyword直接取模，也可在折叠、平方取中等运算后取模，对p的选择非常重要，一般取素数或m，若p选的不好，容易产生碰撞。
三、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映射到具体哪个桶中。
Dictionary就是这用的哈希桶算法。
<div class="cnblogs_code">
<pre>int hashCode =comparer.GetHashCode(key)&0x7FFFFFFF;
int targetBucket = hashCode %buckets.Length;</pre>
</div>
四、Hash碰撞冲突解决算法
对于一个hash算法，不可避免地会产生冲突，那么产生冲突以后如何处理，是一个很关键的地方，目前常见的冲突解决算法有拉链法(Dictionary实现采用的)、开放定址法、再Hash法、公共溢出分区法。
1、拉链法（开散列）：将产生冲突的元素建立一个单链表，并将头指针地址存储之Hash表对应桶的位置，这样定位到Hash表桶的位置后通过遍历单链表的形式来查找元素。
2、开放定址法（闭散列）：当发生哈希冲突时，如果哈希表未被装满，说明再哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个”空位置中去。
3、再Hash法：顾名思义就是将key使用其他的Hash函数再次Hash，直到找到不冲突的位置为止。
拉链法：
<img src="https://img2020.cnblogs.com/i-beta/799221/202003/799221-20200304141044275-1161578177.png">
 
 开放地址法：
假设现在有一个关键码集合（1、4、5、6、7、9），哈希结构的容量为10，哈希函数为Hash(key)=key%10。将所有关键码插入到该哈希结构中，如图：
<img src="https://img2020.cnblogs.com/i-beta/799221/202003/799221-20200304141645977-2050839039.png">
 
 假如仙子啊有一个关键码24要插入该结构中，使用哈希函数求得哈希地址为24，但是该地址已经存放了元素，此时发生哈希冲突。
线性探测：从发生哈希冲突的位置开始，一次向后探测，直到找到下一个空位置为止，例如上面的地址，插入关键码24时，进行线性探测，插入后如下图：
<img src="https://img2020.cnblogs.com/i-beta/799221/202003/799221-20200304142508907-1803830354.png">
 
 限制：
1、用该方法需要关键码必须为整形才能被模，所以我们需要实现将非整形转化为整形。
2、模的数值最好为素数，需要我们创建一个素数表。
3、增容问题。
好了，关于Dictionary的相关知识，就先介绍到这里了。
<img src="https://common.cnblogs.com/images/loading.gif">
 

</div>
<div id="MySignature" role="contentinfo">
努力，不是为了要感动谁，也不是要做给哪个人看，而是要让自己随时有能力跳出自己厌恶的圈子，并拥有选择的权利。记住，用自己喜欢的方式过一生。 
来源：https://www.cnblogs.com/xiaomowang/p/12405639.html

頁: [1]

琼殿技术论坛's Archiver

浅谈C# Dictionary实现原理