这就导致同一个bucket可能有多个key对应,即下图中的Johon Smith和Sandra Dee,但是bucket只能记录一个内存地址(索引),也就是警察叔叔通过家庭地址找到我家时,正常来说,只有一个人过来开门,那么,如何找到也在这个家里的我的呢?我爸记录这我妈在厨房,我妈记录着我在书房,就这样,我就被揪出来了,我爸,我妈,我 就是字典中的一个entry.
如果有一天,我妈妈老来得子又生了一个小宝宝,怎么办呢?很简单,我妈记录小宝宝的位置,那么我的只能巴结小宝宝,让小宝宝来记录我的位置了.
既然大的原理明白了,是不是要看看源码,来研究研究代码中字典怎么实现的呢?
DictionaryMini
上次在苏州参加苏州微软技术俱乐部成立大会时,有幸参加了蒋金楠 老师讲的Asp .net core框架解密,蒋老师有句话让我印象很深刻,"学好一门技术的最好的方法,就是模仿它的样子,自己造一个出来"于是他弄了个Asp .net core mini,所以我效仿蒋老师,弄了个DictionaryMini
其源代码我放在了Github仓库,有兴趣的可以看看:https://github.com/liuzhenyulive/DictionaryMini
我觉得字典这几个方面值得了解一下:
数据存储的最小单元的数据结构
字典的初始化
添加新元素
字典的扩容
移除元素
字典中还有其他功能,但我相信,只要弄明白的这几个方面的工作原理,我们也就恰中肯綮,他么问题也就迎刃而解了.
数据存储的最小单元(Entry)的数据结构
private struct Entry
{
public int HashCode;
public int Next;
public TKey Key;
public TValue Value;
}
一个Entry包括该key的HashCode,以及下个Entry的索引Next,该键值对的Key以及数据Vaule.
字典初始化
private void Initialize(int capacity)
{
int size = HashHelpersMini.GetPrime(capacity);
_buckets = new int[size];
for (int i = 0; i < _buckets.Length; i++)
{
_buckets[i] = -1;
}
_entries = new Entry[size];
_freeList = -1;
}
字典初始化时,首先要创建int数组,分别作为buckets和entries,其中buckets的index是key的哈希值%size,它的value是数据在entries中的index,我们要取的数据就存在entries中.当某一个bucket没有指向任何entry时,它的value为-1.
另外,很有意思得一点,buckets的数组长度是多少呢?这个我研究了挺久,发现取的是大于capacity的最小质数.
添加新元素
private void Insert(TKey key, TValue value, bool add)
{
if (key == null)
{
throw new ArgumentNullException();
}
//如果buckets为空,则重新初始化字典.
if (_buckets == null) Initialize(0);
//获取传入key的 哈希值
var hashCode = _comparer.GetHashCode(key);
//把hashCode%size的值作为目标Bucket的Index.
var targetBucket = hashCode % _buckets.Length;
//遍历判断传入的key对应的值是否已经添加字典中
for (int i = _buckets[targetBucket]; i > 0; i = _entries[i].Next)
{
if (_entries[i].HashCode == hashCode && _comparer.Equals(_entries[i].Key, key))
{
//当add为true时,直接抛出异常,告诉给定的值已存在在字典中.
if (add)
{
throw new Exception("给定的关键字已存在!");
}
//当add为false时,重新赋值并退出.
_entries[i].Value = value;
return;
}
}
//表示本次存储数据的数据在Entries中的索引
int index;
//当有数据被Remove时,freeCount会加1
if (_freeCount > 0)
{
//freeList为上一个移除数据的Entries的索引,这样能尽量地让连续的Entries都利用起来.
index = _freeList;
_freeList = _entries[index].Next;
_freeCount--;
}
else
{
//当已使用的Entry的数据等于Entries的长度时,说明字典里的数据已经存满了,需要对字典进行扩容,Resize.
if (_count == _entries.Length)
{
Resize();
targetBucket = hashCode % _buckets.Length;
}
//默认取未使用的第一个
index = _count;
_count++;
}
//对Entries进行赋值
_entries[index].HashCode = hashCode;
_entries[index].Next = _buckets[targetBucket];
_entries[index].Key = key;
_entries[index].Value = value;
//用buckets来登记数据在Entries中的索引.
_buckets[targetBucket] = index;
}
字典的扩容
private void Resize()
{
//获取大于当前size的最小质数
Resize(HashHelpersMini.GetPrime(_count), false);
}
private void Resize(int newSize, bool foreNewHashCodes)
{
var newBuckets = new int[newSize];
//把所有buckets设置-1
for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
var newEntries = new Entry[newSize];
//把旧的的Enties中的数据拷贝到新的Entires数组中.
Array.Copy(_entries, 0, newEntries, 0, _count);
if (foreNewHashCodes)
{
for (int i = 0; i < _count; i++)
{
if (newEntries[i].HashCode != -1)
{
newEntries[i].HashCode = _comparer.GetHashCode(newEntries[i].Key);
}
}
}
//重新对新的bucket赋值.
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;
}
移除元素
//通过key移除指定的item
public bool Remove(TKey key)
{
if (key == null)
throw new Exception();
if (_buckets != null)
{
//获取该key的HashCode
int hashCode = _comparer.GetHashCode(key);
//获取bucket的索引
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中
_freeList = i;
//把空Entry的数量加1
_freeCount++;
return true;
}
}
}
return false;
}
