前置知识

Hash算法：

一种数字摘要算法，它能将不定长度的二进制数据集给映射到一个较短的二进制长度数据集
常见的MD5算法就是一种Hash算法，通过MD5算法可对任何数据生成数字摘要。

Hash桶算法：

一个Key通过Hash函数运算后可快速的得到hashCode，但是hashCode一般取值都是非常大的，经常是2^32以上，不可能对每个hashCode都指定一个映射。
将生成的HashCode以分段的形式来映射，把每一段称之为一个Bucket（桶），一般常见的Hash桶就是直接对结果取余。
hash桶进行映射会加剧hash的冲突。

解决冲突算法：

拉链法(Dictionary实现采用的)、开放定址法、再Hash法、公共溢出分区法

1548485607652

元素存储

Dictionary以数组为底层数据结构。核心是buckets和entries数组。

Dictionary中entries存储键值对的值以及其他的辅助信息（hashcode、next），然后利用Hash的桶映射，buckets的下标表示键计算后的hashcode，值为最近一个键值对在entries数组中的下标。
（可以类比一下链表，buckets就是将所有对应相同hashcode的键值对连在一起的链表结构。）

Entry结构体：Dictionary种存放数据的最小单位，调用Add(Key,Value)方法添加的元素都会被封装在这样的一个结构体中。

元素增加（Add）

存储的过程可以用一系列图示来展示：

用图的形式来描述一个Dictionary的数据结构，其中只画出了关键的地方。桶大小为4以及Entry大小也为4的一个数据结构：
执行一个Add操作，假设算出来的hashCode为6，count=0为目前的空闲位置，所以给entries[count]赋值，然后count++。

接着对hashCode取余运算6%4=2，此为buckets的位置，buckets的值为目前桶内的第一个entry的下标。
再执行一个Add操作，假设hashcode冲突，此时buckets的位置也相同，这时和链表的头插处理一样，改一下next和buckets的值。