浅析C# Dictionary实现原理一、前言本篇文章配图以及文

一、前言本篇文章配图以及文字其实整理出来很久了，但是由于各种各样的原因推迟到现在才发出来，还有之前立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。

【浅析C# Dictionary实现原理】下图就是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选的不好，容易产生碰撞.
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法，对于其它算法感兴趣的同学可参考文章最后的参考文献。