参考： https://www.cnblogs.com/InCerry/p/10325290.html
一、前言
Dictionary最大的优点就是它查找元素的时间复杂度接近O(1)，实际项目中常被用来做一些数据的本地缓存，提升整体效率。
那么是什么样的设计能使得Dictionary类能实现O(1)的时间复杂度呢？
二、理论知识
1.HASH算法
对于Dictionary的实现原理，其中有两个关键的算法，一个是Hash算法，一个是用于应对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。
常见的构造Hash函数的算法有以下几种。
- 直接寻址法：取keyword或keyword的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，当中a和b为常数（这样的散列函数叫做自身函数）
- 数字分析法：分析一组数据，比方一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体同样，这种话，出现冲突的几率就会非常大，可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大，假设用后面的数字来构成散列地址，则冲突的几率会明显减少。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
- 平方取中法：取keyword平方后的中间几位作为散列地址。
- 折叠法：将keyword切割成位数同样的几部分，最后一部分位数能够不同，然后取这几部分的叠加和（去除进位）作为散列地址。
- 随机数法：选择一随机函数，取keyword的随机值作为散列地址，通经常使用于keyword长度不同的场合。
- 除留余数法：取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法，对于其它算法感兴趣的同学可参考文章最后的参考文献。
-
拉链法：这种方法的思路是将产生冲突的元素建立一个单链表，并将头指针地址存储至Hash表对应桶的位置。这样定位到Hash表桶的位置后可通过遍历单链表的形式来查找元素。
-
再Hash法：顾名思义就是将key使用其它的Hash函数再次Hash，直到找到不冲突的位置为止。
三、Dictionary实现
- Entry结构体
首先我们引入Entry这样一个结构体，它的定义如下代码所示。这是Dictionary种存放数据的最小单位，调用Add(Key,Value)方法添加的元素都会被封装在这样的一个结构体中。
private struct Entry {
public int hashCode;
public int next;
public TKey key;
public TValue value;
}
|
- 其它关键私有变量
除了Entry结构体外，还有几个关键的私有变量，其定义和解释如下代码所示。
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;
|
上面代码中，需要注意的是buckets、entries这两个数组，这是实现Dictionary的关键。
- Dictionary - Add操作
- Dictionary - Find操作
private int FindEntry(TKey key) {
if( key == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets != null) {
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
}
}
return -1;
}
...
internal TValue GetValueOrDefault(TKey key) {
int i = FindEntry(key);
if (i >= 0) {
return entries[i].value;
}
return default(TValue);
}
|
- Dictionary - Remove
public bool Remove(TKey key) {
if(key == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets != null) {
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
int bucket = hashCode % buckets.Length;
int last = -1;
for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
if (last < 0) {
buckets[bucket] = entries[i].next;
}
else {
entries[last].next = entries[i].next;
}
entries[i].hashCode = -1;
entries[i].next = freeList;
entries[i].key = default(TKey);
entries[i].value = default(TValue);
freeList = i;
freeCount++;
version++;
return true;
}
}
}
return false;
}
|
6.Dictionary Resize
public const int HashCollisionThreshold = 100;
|
private void Resize(int newSize, bool forceNewHashCodes) {
Contract.Assert(newSize >= entries.Length);
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);
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;
}
|
- Dictionary - 再谈Add操作
在我们之前的Add操作步骤中，提到了这样一段话，这里提到会有一种其它的情况，那就是有元素被删除的情况。
避开一种其它情况不谈，接下来它会将hashCode、key、value等信息存入entries[count]中，因为count位置是空闲的；继续count++指向下一个空闲位置。上图中第一个位置，index=0就是空闲的，所以就存放在entries[0]的位置。
因为count是通过自增的方式来指向entries[]下一个空闲的entry，如果有元素被删除了，那么在count之前的位置就会出现一个空闲的entry；如果不处理，会有很多空间被浪费。
这就是为什么Remove操作会记录freeList、freeCount，就是为了将删除的空间利用起来。实际上Add操作会优先使用freeList的空闲entry位置，摘录代码如下。
private void Insert(TKey key, TValue value, bool add){
if( key == null ) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets == null) Initialize(0);
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
int targetBucket = hashCode % buckets.Length;
int collisionCount = 0;
for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
if (add) {
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
}
entries[i].value = value;
version++;
return;
}
collisionCount++;
}
int index;
if (freeCount > 0) {
index = freeList;
freeList = entries[index].next;
freeCount--;
}
else {
if (count == entries.Length)
{
Resize();
targetBucket = hashCode % buckets.Length;
}
index = count;
count++;
}
entries[index].hashCode = hashCode;
entries[index].next = buckets[targetBucket];
entries[index].key = key;
entries[index].value = value;
buckets[targetBucket] = index;
version++;
if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer))
{
comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer);
Resize(entries.Length, true);
}
}
|
- Collection版本控制
wechat
alipay
