浅谈C#Dictionary实现原理
使⽤C#已经有好多年头了，然后突然有⼀天被问到C#Dictionary的基本实现，这让我反思到我⼀直处于拿来主义，能⽤就好，根本没有去考虑和学习⼀些底层架构，想想令⼈头⽪发⿇。下⾯开始学习⼀些我平时⽤得理所当然的东西，今天先学习⼀下字典，Dictionary
⼀、Dictionary源码学习
Dictionary实现我们主要对照源码来解析，⽬前对照的源码版本是.Net Framwork4.8，。
这边主要介绍Dictionary中⼏个⽐较关键的类和对象，然后跟着代码来⾛⼀遍插⼊、删除和扩容的流程。
1、Entry结构体
⾸先，我们引⼊Entry这样⼀个结构体，它的定义如下⾯代码所⽰，这是Dictionary中存放数据的最⼩单位，调⽤Add(Key,Value)⽅法添加的元素都会被封装在这样的⼀个结构体中。一战原因
1private struct Entry
2 {
列举英文
3public int hashCode; // Lower 31 bits of hash code, -1 if unud
4public int next; // Index of next entry, -1 if last
5public TKey key; // Key of entry
6public TValue value; // Value of entry
7 }
2、其他关键私有变量
1private int[] buckets; // Hash桶
2private Entry[] entries; // Entry数组，存放元素
3private int count; // 当前entries的index位置
4private int version; // 当前版本，防⽌迭代过程中集合被更改
5private int freeList; // 被删除Entry在entries中的下标index，这个位置是空闲的
6private int freeCount; // 有多少个被删除的Entry，有多少个空闲的位置
7private IEqualityComparer<TKey> comparer; // ⽐较器
8private KeyCollection keys; // 存放Key的集合
9private ValueCollection values; // 存放Value的集合
3、Dictionary的构造
1private void Initialize(int capacity)
2 {
3int prime = HashHelpers.GetPrime(capacity);
4this.buckets = new int[prime];
5for (int i = 0; i < this.buckets.Length; i++)
6 {
美人鱼的童话故事
7this.buckets[i] = -1;
8 }
10this.freeList = -1;
11 }
我们看到，Dictionary在构造的时候做了以下⼏件事：
1、初始化⼀个this.buchkets=new int[prime]
2、初始化⼀个ies=new Entry<TKey,TValue>[prime]
3、Bucket和entries的容量都为⼤于字典容量的⼀个最⼩的质数斗马
其中this.buckets主要⽤来进⾏Hash碰撞，ies⽤来存储字典的内容，并且标识下⼀个元素的位置。
4、Dictionary——Add操作
我们以Dictionary<int,string>为例，来展⽰⼀下Dictinoary如何添加元素：
⾸先，我们构造⼀个，容量为6：
Dictionary<int, string> test = new Dictionary<int, string>(6);
Test.Add(4,"4")
根据Hash算法：4.GetHashCode()%7=4，因此碰撞到buckets中下表为4的槽上，此时由于Count为0，因此元素放在Entries中第0个元素上，添加后，Count变为1
Test.Add(11,"11")
根据Hash算法，11.GetHashCode()%7=4，因此再次碰撞到Buckets中下标为4的槽上，由于此槽上的值已经不是-1，此时Count=1，因此把这个新加的元素放到entries中下标为1的数组中，并且让Buckets槽指向下表为1的entries中，下标为1的entry之下下表为0的entries。
Test.Add(18,"18")
Test.Add(19,"19")
5、Dictionary——Remove操作
Test.Remove(4)
我们删除元素时，通过⼀次碰撞，并且沿着链表寻找3次，找到key为4的元素所在的位置，删除当前元素，并且把FreeList的位置指向当前删除元素的位置，FreeCount置为1。
删除的数据会形成⼀个FreeList的链表，添加数据的时候，优先向FreeList链表中添加数据，FreeList为空则按照count⼀次排序。
6、Dictionary——Resize操作（扩容）
有细⼼的⼩伙伴可能看过Add操作后就想问了，buckets、entries不就是两个数组么，那万⼀数组放满了怎么办？接下来就是我要介绍的Resize（扩容）这样⼀种操作，对我们的buckets、entries进⾏扩容。
6.1 扩容操作的触发条件
⾸先我们需要直到在什么情况下，会发⽣扩容操作：
第⼀种情况⾃然就是数组已经满了，没有办法继续存放新的元素，如下图所⽰。深情凄美
第⼆种，Dictionary中发⽣的碰撞次数太多，会严重影响性能，也会出发扩容操作。
Hash运算会不可避免的产⽣冲突，Dictionary中使⽤拉链发来解决冲突的问题，但是，⼤家看下图中的这种情况，所有的元素都刚好落在buckets[3]上⾯，结果就导致了时间复杂度O(n)，查找性能会下降：
6.2 扩容操作如何进⾏
为了给⼤家演⽰清楚，模拟了以下这种数据结构，⼤⼩为2的Dictionary，假设碰撞的阈值为2；现在出发Hash碰撞扩容。
1、申请两倍于现在⼤⼩的buckets、entries
2、将现有的元素拷贝到新的entries
3、如果时Hash碰撞扩容，使⽤新HashCode函数重新计算Hash值
4、对entries每个元素bucket=newEntries[i].hashCode%newSize确定新buckets位置
5、重建hash链，newEntries[i].next=buckets[bucket];buckets[bucket]=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
关于Hash碰撞下图很清晰的就解释了，可从图中得知Sandra Dee 和 John Smith 通过hash运算后，落到了02位置，产⽣了碰撞和冲突。
常见的构造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就是这⽤的哈希桶算法。
水中生活int hashCode =comparer.GetHashCode(key)&0x7FFFFFFF;
int targetBucket = hashCode %buckets.Length;
四、Hash碰撞冲突解决算法
对于⼀个hash算法，不可避免地会产⽣冲突，那么产⽣冲突以后如何处理，是⼀个很关键的地⽅，⽬前常见的冲突解决算法有拉链法(Dictionary实现采⽤的)、开放定址法、再Hash法、公共溢出分区法。
1、拉链法（开散列）：将产⽣冲突的元素建⽴⼀个单链表，并将头指针地址存储之Hash表对应桶的位置，这样定位到Hash表桶的位置后通过遍历单链表的形式来查找元素。
2、开放定址法（闭散列）：当发⽣哈希冲突时，如果哈希表未被装满，说明再哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下⼀个”空位置中去。
3、再Hash法：顾名思义就是将key使⽤其他的Hash函数再次Hash，直到找到不冲突的位置为⽌。
拉链法：
邀约话术
开放地址法：
假设现在有⼀个关键码集合（1、4、5、6、7、9），哈希结构的容量为10，哈希函数为Hash(key)=key%10。将所有关键码插⼊到该哈希结构中，如图：
假如仙⼦啊有⼀个关键码24要插⼊该结构中，使⽤哈希函数求得哈希地址为24，但是该地址已经存放了元素，此时发⽣哈希冲突。
线性探测：从发⽣哈希冲突的位置开始，⼀次向后探测，直到找到下⼀个空位置为⽌，例如上⾯的地址，插⼊关键码24时，进⾏线性探测，插⼊后如下图：
限制：
1、⽤该⽅法需要关键码必须为整形才能被模，所以我们需要实现将⾮整形转化为整形。
2、模的数值最好为素数，需要我们创建⼀个素数表。
3、增容问题。
好了，关于Dictionary的相关知识，就先介绍到这⾥了。
