三分钟，看懂C# 哈希表（Dictionary）

Q： hashmap/dictionary的原理是什么
A： （1）哈希函数：使用哈希函数生成hashCode（如MD5算法）
（2）哈希桶：由于hashCode通常比较大，为了节省要创建的哈希表的空间，因此需要对其分段。每一段可以称之为一个哈希桶
常见的分段方式是取余（但是hash桶会加剧碰撞）
（3）冲突解决：
①拉链法：把冲突的元素建立一个list，并将list头指针的地址(引用)存储到对应桶的位置
②再hash法：将key使用某个哈希函数再次散列，直到不冲突为止

对于C# 中的Dictionary，具体实现如下
（1）最小数据单元是一个叫Entry的结构体。用entry[]存放元素
（2）buckets[]用于存放hash桶。
（3）数据Add进字典的时候，会根据Key生成一个hashcode，根据这个hashcode去决定该数据所在的桶。
每个桶中会存放一个整型值，这个值指向桶中存放的第一个元素（真正数据都在entry数组中）。entry中的每一个值都有next指针，从而指向下一个值（拉链法）。
（4）Remove的时候，把把要删除元素的前一个节点的next指针置为-1即可
（5）C#中碰撞次数的阈值是100，碰撞过多或者数组已满的时候就说明该扩容了。扩容过程是：
①如果是数组满了：直接申请两倍于现在大小的buckets[]、entries[]，然后将现有元素拷贝到新的数组中
②如果是碰撞过多：在.net framework中会直接扩容，并重新计算哈希值，在.net core中采取和JDK相似的策略（使用红黑树来存储元素）