Dictionary
Dictionary与hashtable的区别：dictionary支持泛型。
通常处理哈希冲突的方法有：开放地址法，再哈希法，链地址法，建立一个公共栈区等。
在哈希表上进行查找的过程和哈希造表的过程基本一致。给定k值，根据造表时设定的哈希函数求得哈希地址，若表中此位置没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据冲突的方法寻找下一地址，直到哈希表中某个位置为空或者表中所填关键值等于给定值为止。
Dictionary使用的哈希函数是除留余数法 h = F(k) % m；m为哈希表长度。
Dictionary使用的解决冲突的方法是拉链法，又称链地址法
拉链法的原理：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数 组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。
private struct Entry {
public int hashCode; //31位散列值，32最高位表示符号位，-1表示未使用
public int next; //下一项的索引值，-1表示结尾
public TKey key; //键
public TValue value; //值
}
private int[] buckets;//内部维护的数据地址
private Entry[] entries;//元素数组，用于维护哈希表中的数据
private int count;//元素数量
private int version;
private int freeList;//空闲的列表
private int freeCount;//空闲列表元素数量
private IEqualityComparer<TKey> comparer;//哈希表中的比较函数
private KeyCollection keys;//键集合
private ValueCollection values;//值集合
private Object _syncRoot;
初始化函数
该函数用于，初始化的数据构造
private void Initialize(int capacity) {
//根据构造函数设定的初始容量，获取一个近似的素数
int size = HashHelpers.GetPrime(capacity);
buckets = new int[size];
for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
entries = new Entry[size];
freeList = -1;
}
size 哈希表的长度是素数，可以使元素更均匀地分布在每个节点上。
buckets 中的节点值，-1表示空值。
freeList 为-1表示没有空链表。
buckets 和 freeList 所值指向的数据其实全是存储于一块连续的内存空间（entries ）之中。
扩容
private void Resize() {
Resize(HashHelpers.ExpandPrime(count), false);
}
private void Resize(int newSize, bool forceNewHashCodes) {
Contract.Assert(newSize >= entries.Length);
//重新初始化一个比原来空间还要大2倍左右的buckets和Entries，用于接收原来的buckets和Entries的数据
int[] newBuckets = new int[newSize];
for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
Entry[] newEntries = new Entry[newSize];
//数据搬家
Array.Copy(entries, 0, newEntries, 0, count);
//将散列值刷新，这是在某一个单链表节点数到达一个阈值（100）时触发
if(forceNewHashCodes) {
for (int i = 0; i < count; i++) {
if(newEntries[i].hashCode != -1) {
newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);
}
}
}
//单链表数据对齐,无关顺序
for (int i = 0; i < count; i++) {
if (newEntries[i].hashCode >= 0) {
int bucket = newEntries[i].hashCode % newSize;
newEntries[i].next = newBuckets[bucket];
newBuckets[bucket] = i;
}
}
buckets = newBuckets;
entries = newEntries;
}
原文：https://www.cnblogs.com/mcyushao/p/10629599.html