.NET深入了解哈希表和Dictionary
引子
问题:给定一串数字{1,2,5,7,15,24,33,52},如何在时间复杂度为O(1)下,对数据进行CURD?
数组:我创建一个Length为53的数组,将元素插入相同下标处,是不是就可以实现查找复杂度O(1)了?但是添加修改元素时间复杂度为O(n)了。
链表:添加删除复杂度为O(1),但是查找时间复杂度为O(n)了。
身为.NETer肯定熟练使用Dictionary和HashSet,这两个容器的底层就是HashTable,所以带着对技术浓重的兴趣(面试),所以就从头到尾梳理一下!
理论
链地址法(拉链法)
回到问题本身,我们用数组可以实现查找复杂度为O(1),链表实现添加删除复杂度为O(1),如果我们将两个合起来,不就可以实现增删查都为O(1)了么?如何结合呢?
我们先定义一个数组,长度为7(敲黑板,思考下为什么选7?),将所有元素对7取余,这样所有元素都可以放在数组上了,如下图所示:
如上图,如果我们将数组中每个下标位置都放成一个链条,这样,复杂度不久降下去了么?
有问题么?没问题。真没问题么?有问题……
注意
-
插入元素是{0,7,14,21,28}怎么办?这样都落在下标为0的链条里,时间复杂度不又上去了?针对这种情况,隔壁Java将链表优化成了红黑书,我们.NET呢?往下看。
-
如果我的数组长度不是7,是2怎么办?所有数对2取余,不是1就是0,时间复杂度不又上去了?所以我们对数组长度应该取素数。
-
如果元素超级多或者特别少,我们的数组长度要固定么?就要动态长度
上边这种方法学名就叫拉链法!
开放地址法
上边我们聊过拉链法(为什么老想着裤子拉链……),拉链法是向下开辟新的空间,如果我们横向开辟空间呢?还是刚才的例子,我们这样搞一下试试。
线性探测法
我们插完7以后,在插24时,发现下标为2的地方有元素了,于是向后移动一位,发现有空位,于是就插进去了。
上边这种方法就是线性探测法!
二次聚集(堆积)
聪明的老鸟们,肯定疑惑啦,如果我们继续添加元素{x%11=4},{y%11=5},此时x,y元素都要往下标6插数据。这样就导致了原始哈希地址不同的元素要插入同一个地址。即添加同义词的冲突过程中又添加了非同义词的冲突。这就是二次聚集。
二次探测法
如果在线性探测法中,我们不依次寻找下一个呢?我们针对”下一个”采取{1 ^ 2,-1 ^ 2,2 ^ 2,-2 ^ 2….}(垃圾编辑器,次方样式乱了)这样的步长呢?真聪明!你已经知道二次探测法了!
这……这还能用么?不都乱了么?下标和元素对不上了呀!怎么去查找元素呢?
别急呀,家人们呐,我们按照这个思路查询就好了:
查找算法步骤
1. 给定待查找的关键字key,获取原始应该插入的下标index
2. 如果原始下标index处,元素为空,则所查找的元素不存在
3. 如果index处的元素等于key,则查找成功
4. 否则重复下述解决冲突的过程
* 按照处理冲突的方法,计算下一个地址nextIndex
* 若nextIndex为空,则查找元素不存在
* 若nextIndex等于关键词key,则查找成功
还有要注意的点么?必须有!
注意(敲重点啦)
- 数组长度必须大于给定元素的长度!
- 当数组元素快装满时,时间复杂度也是O(n)!
- 如果都装满了,就会一直循环找空位,我们应该进行扩容!
理论小结
接口设计
干活啦,干活啦,领导嫌查询效率太低,让设计一种CURD时间复杂度都为O(n)的数据结构。给了接口。接口如下:
internal interface IDictionary<TK, TV> : IEnumerable<KeyValuePair<TK, TV>>
{
TV this[TK key] { get; set; }
int Count { get; }
/// <summary>
/// 根据key判断元素是否存在
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
bool ContainsKey(TK key);
/// <summary>
/// 添加元素
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
void Add(TK key, TV value);
/// <summary>
/// 根据key移除元素
/// </summary>
/// <param name="key"></param>
void Remove(TK key);
/// <summary>
/// 清除
/// </summary>
void Clear();
}
.NET实现线性探测法
实现过程
1. 先来个对象,存储key和value
对象:KeyValuePair
internal class DictionaryKeyValuePair<TK, TV>
{
internal TK Key;
internal TV Value;
internal DictionaryKeyValuePair(TK key, TV value)
{
Key = key;
Value = value;
}
}
2. 来个类OpenAddressDictionary,继承IDictionary接口,就是我们的实现类
实现类:OpenAddressDictionary
/// <summary>
/// 使用线性探测法实现哈希表
/// </summary>
/// <typeparam name="TK"></typeparam>
/// <typeparam name="TV"></typeparam>
public class OpenAddressDictionary<TK, TV> : IDictionary<TK, TV>
{
//创建一个数组,用来存储元素
private DictionaryKeyValuePair<TK, TV>[] hashArray;
//记录已插入元素的数量
public int Count { get; private set; }
public OpenAddressDictionary(int capacity)
{
if (capacity < 0)
throw new ArgumentOutOfRangeException("初始值容量不能小于0");
hashArray = new DictionaryKeyValuePair<TK, TV>[capacity];
}
public TV this[TK key] {
get => throw new System.NotImplementedException();
set => throw new System.NotImplementedException();
}
public void Add(TK key, TV value)
{
throw new System.NotImplementedException();
}
public void Clear()
{
throw new System.NotImplementedException();
}
public System.Boolean ContainsKey(TK key)
{
throw new System.NotImplementedException();
}
public IEnumerator<KeyValuePair<TK, TV>> GetEnumerator()
{
throw new System.NotImplementedException();
}
public void Remove(TK key)
{
throw new System.NotImplementedException();
}
IEnumerator IEnumerable.GetEnumerator()
{
throw new System.NotImplementedException();
}
}
3.如何实现查找?跟着上文查找步骤就行
线性探测:查找
/// <summary>
/// 查找,按照上文线性探测查找步骤
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public bool ContainsKey(TK key)
{
//1.给定待查找的关键字key,获取原始应该插入的下标index
var hashCode = GetHash(key);
var index = hashCode % hashArray.Length;
//2.如果原始下标index处,元素为空,则所查找的元素不存在
if (hashArray[index] == null) return false;
var current = hashArray[index];//当前元素
/*这个点用来判断是否走了一整圈*/
var hitKey = current.Key;
//4.否则重复下述解决冲突的过程
while (current != null)
{
//3.如果index处的元素等于key,则查找成功
if (current.Key.Equals(key)) return true;
/*这个地方来修改获取下一个元素位置*/
index++;
/*到尾了,但是没有走完一圈*/
if (index == hashArray.Length)
index = 0;
current = hashArray[index];
/*走完一圈了,没找到*/
if (current != null && current.Key.Equals(hitKey)) break;
}
return false;
}
4. 添加
线性探测:添加
/// <summary>
/// 添加元素
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
/// <exception cref="Exception"></exception>
public void Add(TK key, TV value)
{
Grow();
//1.获取原始插入位置
var hashCode = GetHash(key);
var index = hashCode % hashArray.Length;
//2.此位置为空,直接插入
if (hashArray[index] == null)
{
hashArray[index] = new DictionaryKeyValuePair<TK, TV>(key, value);
}
//3.坑被占了,去看看下一个
else
{
var current = hashArray[index];
/*这个点用来判断是否走了一整圈*/
var hitKey = current.Key;
while (current != null)
{
if (current.Key.Equals(key)) throw new Exception("重复key");
/*这个地方来修改获取下一个元素位置*/
index++;
/*到尾了,但是没有走完一圈*/
if (index == hashArray.Length)
index = 0;
current = hashArray[index];
/*走完一圈了,没找到空位*/
if (current != null && current.Key.Equals(hitKey)) throw new Exception("容器满了");
}
hashArray[index] = new DictionaryKeyValuePair<TK, TV>(key, value);
}
Count++;
}
/// <summary>
/// 扩容
/// </summary>
private void Grow()
{
/*这个地方判断使用多少扩容*/
if (hashArray.Length * 0.7 <= Count)
{
var orghashArray = hashArray.Length;
var currentArray = hashArray;
/*这个地方改变扩容大小的规则*/
hashArray = new DictionaryKeyValuePair<TK, TV>[hashArray.Length * 2];
for (var i = 0; i < orghashArray; i++)
{
var current = currentArray[i];
/*旧数组中存在元素,添加到新数组中,Add方法会对Count++,所以加入后要Count--*/
if (current != null)
{
Add(current.Key, current.Value);
Count--;
}
}
currentArray = null;
}
}
5. 删除
线性探测:删除
/// <summary>
/// 删除元素key
/// </summary>
/// <param name="key"></param>
/// <exception cref="Exception"></exception>
public void Remove(TK key)
{
//1.获取原始插入位置
var hashCode = GetHash(key);
var curIndex = hashCode % hashArray.Length;
//2.此位置为空,无法删除
if (hashArray[curIndex] == null) throw new Exception("未找到元素key");
var current = hashArray[curIndex];
/*这个点用来判断是否走了一整圈*/
var hitKey = current.Key;
#region 找到待删除元素
DictionaryKeyValuePair<TK, TV> target = null;
while (current != null)
{
if (current.Key.Equals(key))
{
target = current;
break;
}
/*这个地方来修改获取下一个元素位置*/
curIndex++;
/*到尾了,但是没有走完一圈*/
if (curIndex == hashArray.Length)
curIndex = 0;
current = hashArray[curIndex];
/*走完一圈了,没找到空位*/
if (current != null && current.Key.Equals(hitKey)) throw new Exception("No such item for given key");
}
if (target == null)
{
throw new Exception("未找到元素key");
}
#endregion
//删除,将当前位置置空
hashArray[curIndex] = null;
#region 之前讲过删除,造成元素丢失,所以在此处处理
curIndex++;
/*到尾了,但是没有走完一圈*/
if (curIndex == hashArray.Length)
curIndex = 0;
current = hashArray[curIndex];
//直到下一个为空的点,到空说明后边的还没有被线性探测插入污染
while (current != null)
{
//先删除
hashArray[curIndex] = null;
//重新插入
Add(current.Key, current.Value);
Count--;
curIndex++;
/*到尾了,但是没有走完一圈*/
if (curIndex == hashArray.Length)
curIndex = 0;
current = hashArray[curIndex];
}
#endregion
Count--;
Shrink();
}
/// <summary>
/// 减容
/// </summary>
private void Shrink()
{
/*这个地方判断元素在什么程度算少*/
if (Count <= hashArray.Length * 0.3 && hashArray.Length / 2 > 0)
{
var orghashArray = hashArray.Length;
var currentArray = hashArray;
/*这个地方改变扩容大小的规则*/
hashArray = new DictionaryKeyValuePair<TK, TV>[hashArray.Length / 2];
for (var i = 0; i < orghashArray; i++)
{
var current = currentArray[i];
/*旧数组中存在元素,添加到新数组中,Add方法会对Count++,所以加入后要Count--*/
if (current != null)
{
Add(current.Key, current.Value);
Count--;
}
}
currentArray = null;
}
}
最终代码
线性探测:最终代码
/// <summary>
/// 使用线性探测法实现哈希表
/// </summary>
/// <typeparam name="TK"></typeparam>
/// <typeparam name="TV"></typeparam>
public class OpenAddressDictionary<TK, TV> : IDictionary<TK, TV>
{
//创建一个数组,用来存储元素
private DictionaryKeyValuePair<TK, TV>[] hashArray;
//记录已插入元素的数量
public int Count { get; private set; }
public TV this[TK key]
{
get => GetValue(key);
set => SetValue(key, value);
}
public OpenAddressDictionary(int capacity)
{
if (capacity < 0)
throw new ArgumentOutOfRangeException("初始值容量不能小于0");
hashArray = new DictionaryKeyValuePair<TK, TV>[capacity];
}
/// <summary>
/// 清除最简单
/// </summary>
public void Clear()
{
if (Count > 0)
Array.Clear(hashArray, 0, hashArray.Length);
}
/// <summary>
/// 查找,按照上文线性探测查找步骤
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public bool ContainsKey(TK key)
{
//1.给定待查找的关键字key,获取原始应该插入的下标index
var hashCode = GetHash(key);
var index = hashCode % hashArray.Length;
//2.如果原始下标index处,元素为空,则所查找的元素不存在
if (hashArray[index] == null) return false;
var current = hashArray[index];//当前元素
/*这个点用来判断是否走了一整圈*/
var hitKey = current.Key;
//4.否则重复下述解决冲突的过程
while (current != null)
{
//3.如果index处的元素等于key,则查找成功
if (current.Key.Equals(key)) return true;
/*这个地方来修改获取下一个元素位置*/
index++;
/*到尾了,但是没有走完一圈*/
if (index == hashArray.Length)
index = 0;
current = hashArray[index];
/*走完一圈了,没找到*/
if (current != null && current.Key.Equals(hitKey)) break;
}
return false;
}
/// <summary>
/// 添加元素
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
/// <exception cref="Exception"></exception>
public void Add(TK key, TV value)
{
Grow();
//1.获取原始插入位置
var hashCode = GetHash(key);
var index = hashCode % hashArray.Length;
//2.此位置为空,直接插入
if (hashArray[index] == null)
{
hashArray[index] = new DictionaryKeyValuePair<TK, TV>(key, value);
}
//3.坑被占了,去看看下一个
else
{
var current = hashArray[index];
/*这个点用来判断是否走了一整圈*/
var hitKey = current.Key;
while (current != null)
{
if (current.Key.Equals(key)) throw new Exception("重复key");
/*这个地方来修改获取下一个元素位置*/
index++;
/*到尾了,但是没有走完一圈*/
if (index == hashArray.Length)
index = 0;
current = hashArray[index];
/*走完一圈了,没找到空位*/
if (current != null && current.Key.Equals(hitKey)) throw new Exception("容器满了");
}
hashArray[index] = new DictionaryKeyValuePair<TK, TV>(key, value);
}
Count++;
}
/// <summary>
/// 删除元素key
/// </summary>
/// <param name="key"></param>
/// <exception cref="Exception"></exception>
public void Remove(TK key)
{
//1.获取原始插入位置
var hashCode = GetHash(key);
var curIndex = hashCode % hashArray.Length;
//2.此位置为空,无法删除
if (hashArray[curIndex] == null) throw new Exception("未找到元素key");
var current = hashArray[curIndex];
/*这个点用来判断是否走了一整圈*/
var hitKey = current.Key;
#region 找到待删除元素
DictionaryKeyValuePair<TK, TV> target = null;
while (current != null)
{
if (current.Key.Equals(key))
{
target = current;
break;
}
/*这个地方来修改获取下一个元素位置*/
curIndex++;
/*到尾了,但是没有走完一圈*/
if (curIndex == hashArray.Length)
curIndex = 0;
current = hashArray[curIndex];
/*走完一圈了,没找到空位*/
if (current != null && current.Key.Equals(hitKey)) throw new Exception("No such item for given key");
}
if (target == null)
{
throw new Exception("未找到元素key");
}
#endregion
//删除,将当前位置置空
hashArray[curIndex] = null;
#region 之前讲过删除,造成元素丢失,所以在此处处理
curIndex++;
/*到尾了,但是没有走完一圈*/
if (curIndex == hashArray.Length)
curIndex = 0;
current = hashArray[curIndex];
//直到下一个为空的点,到空说明后边的还没有被线性探测插入污染
while (current != null)
{
//先删除
hashArray[curIndex] = null;
//重新插入
Add(current.Key, current.Value);
Count--;
curIndex++;
/*到尾了,但是没有走完一圈*/
if (curIndex == hashArray.Length)
curIndex = 0;
current = hashArray[curIndex];
}
#endregion
Count--;
Shrink();
}
/// <summary>
/// 扩容
/// </summary>
private void Grow()
{
/*这个地方判断使用多少扩容*/
if (hashArray.Length * 0.7 <= Count)
{
var orghashArray = hashArray.Length;
var currentArray = hashArray;
/*这个地方改变扩容大小的规则*/
hashArray = new DictionaryKeyValuePair<TK, TV>[hashArray.Length * 2];
for (var i = 0; i < orghashArray; i++)
{
var current = currentArray[i];
/*旧数组中存在元素,添加到新数组中,Add方法会对Count++,所以加入后要Count--*/
if (current != null)
{
Add(current.Key, current.Value);
Count--;
}
}
currentArray = null;
}
}
/// <summary>
/// 减容
/// </summary>
private void Shrink()
{
/*这个地方判断元素在什么程度算少*/
if (Count <= hashArray.Length * 0.3 && hashArray.Length / 2 > 0)
{
var orghashArray = hashArray.Length;
var currentArray = hashArray;
/*这个地方改变扩容大小的规则*/
hashArray = new DictionaryKeyValuePair<TK, TV>[hashArray.Length / 2];
for (var i = 0; i < orghashArray; i++)
{
var current = currentArray[i];
/*旧数组中存在元素,添加到新数组中,Add方法会对Count++,所以加入后要Count--*/
if (current != null)
{
Add(current.Key, current.Value);
Count--;
}
}
currentArray = null;
}
}
private void SetValue(TK key, TV value)
{
var index = GetHash(key) % hashArray.Length;
if (hashArray[index] == null)
{
Add(key, value);
}
else
{
var current = hashArray[index];
var hitKey = current.Key;
while (current != null)
{
if (current.Key.Equals(key))
{
Remove(key);
Add(key, value);
return;
}
index++;
//wrap around
if (index == hashArray.Length)
index = 0;
current = hashArray[index];
//reached original hit again
if (current != null && current.Key.Equals(hitKey)) throw new Exception("Item not found");
}
}
throw new Exception("Item not found");
}
private TV GetValue(TK key)
{
var index = GetHash(key) % hashArray.Length;
if (hashArray[index] == null) throw new Exception("Item not found");
var current = hashArray[index];
var hitKey = current.Key;
while (current != null)
{
if (current.Key.Equals(key)) return current.Value;
index++;
//wrap around
if (index == hashArray.Length)
index = 0;
current = hashArray[index];
//reached original hit again
if (current != null && current.Key.Equals(hitKey)) throw new Exception("Item not found");
}
throw new Exception("Item not found");
}
private int GetHash(TK key)
{
return Math.Abs(key.GetHashCode());
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
//迭代器就不写了,想了解看我博客容器栏目
public IEnumerator<KeyValuePair<TK, TV>> GetEnumerator()
{
throw new System.NotImplementedException();
}
}
internal class DictionaryKeyValuePair<TK, TV>
{
internal TK Key;
internal TV Value;
internal DictionaryKeyValuePair(TK key, TV value)
{
Key = key;
Value = value;
}
}
.NET实现拉链法
实现过程
回想一下,上边的拉链法,每个下标位置放置的是一个链条,所以我们先实现一个双向链表
1. 实现一个双向链表
拉链法:构建双向链表
internal class DLinkedNode<T>
{
public T Data;
public DLinkedNode<T> Next;
public DLinkedNode<T> Previous;
public DLinkedNode(T data)
{
Data = data;
}
}
2. 创建一个拉链法实体类
拉链法:实现类
/// <summary>
/// 拉链法:实现类
/// </summary>
/// <typeparam name="TK"></typeparam>
/// <typeparam name="TV"></typeparam>
internal class SeparateChainingDictionary<TK, TV>:IDictionary<TK, TV>
{
//构建一个数组,数组每个节点都是链表
private DLinkedNode<KeyValuePair<TK, TV>>[] hashArray;
//已使用数组下标个数
private int filledBuckets;
public SeparateChainingDictionary(int capacity) {
if (capacity < 0)
throw new ArgumentOutOfRangeException("初始值容量不能小于0");
hashArray = new DLinkedNode<KeyValuePair<TK, TV>>[capacity];
}
public TV this[TK key] {
get => throw new NotImplementedException();
set => throw new NotImplementedException();
}
public int Count => throw new NotImplementedException();
public void Add(TK key, TV value)
{
throw new NotImplementedException();
}
public void Clear()
{
throw new NotImplementedException();
}
public bool ContainsKey(TK key)
{
throw new NotImplementedException();
}
public void Remove(TK key)
{
throw new NotImplementedException();
}
public IEnumerator<KeyValuePair<TK, TV>> GetEnumerator()
{
throw new NotImplementedException();
}
IEnumerator IEnumerable.GetEnumerator()
{
throw new NotImplementedException();
}
}
3. 拉链法:查找
拉链法:查找
/// <summary>
/// 查找
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public bool ContainsKey(TK key)
{
/*1.获取原始下标*/
var index = Math.Abs(key.GetHashCode()) % hashArray.Length;
/*2.为空即无*/
if (hashArray[index] == null) return false;
var current = hashArray[index];
/*3.遍历链表*/
while (current != null)
{
if (current.Data.Key.Equals(key)) return true;
current = current.Next;
}
return false;
}
4. 拉链法:添加
拉链法:添加
/// <summary>
/// 添加
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
/// <exception cref="Exception"></exception>
public void Add(TK key, TV value)
{
Grow();
var index = Math.Abs(key.GetHashCode()) % hashArray.Length;
if (hashArray[index] == null)
{
hashArray[index] = new DLinkedNode<KeyValuePair<TK, TV>>(new KeyValuePair<TK, TV>(key, value));
filledBuckets++;
}
else
{
var current = hashArray[index];
while (current != null && current.Next != null)
{
/*此处可以判断是重复修改,还是抛异常*/
if (current.Data.Key.Equals(key)) throw new Exception("重复key");
current = current.Next;
}
if (current.Data.Key.Equals(key)) throw new Exception("重复key");
current.Next = new DLinkedNode<KeyValuePair<TK, TV>>(new KeyValuePair<TK, TV>(key, value));
}
Count++;
}
/// <summary>
/// 扩容
/// </summary>
private void Grow()
{
if (filledBuckets >= hashArray.Length * 0.7)
{
filledBuckets = 0;
var newBucketSize = hashArray.Length * 2;
var biggerArray = new DLinkedNode<KeyValuePair<TK, TV>>[newBucketSize];
for (var i = 0; i < hashArray.Length; i++)
{
var item = hashArray[i];
if (item != null)
{
var current = item;
while (current != null)
{
var next = current.Next;
var newIndex = Math.Abs(current.Data.Key.GetHashCode()) % newBucketSize;
if (biggerArray[newIndex] == null)
{
filledBuckets++;
biggerArray[newIndex] = current;
}
var bItem = biggerArray[newIndex];
while(bItem.Next != null)
bItem = bItem.Next;
bItem.Next = current;
current = next;
}
}
}
hashArray = biggerArray;
}
}
5. 拉链法:删除
拉链法:删除
public void Remove(TK key)
{
var index = Math.Abs(key.GetHashCode()) % hashArray.Length;
if (hashArray[index] == null) throw new Exception("未找到key");
var current = hashArray[index];
/*查找待删除元素*/
DLinkedNode<KeyValuePair<TK, TV>> item = null;
while (current != null)
{
if (current.Data.Key.Equals(key))
{
item = current;
break;
}
current = current.Next;
}
if (item == null)
{
throw new Exception("未找到key");
}
/*删除*/
if (item.Next == null)
item = null;
else
{
item.Previous = item.Next;
item.Next.Previous =item.Previous ;
item = null;
}
if (hashArray[index] == null)
{
filledBuckets--;
}
Count--;
Shrink();
}
private void Shrink()
{
/*是否减容*/
if (Math.Abs(filledBuckets - hashArray.Length * 0.3) < 0.1 && hashArray.Length / 2 > 0)
{
filledBuckets = 0;
var newBucketSize = hashArray.Length / 2;
var smallerArray = new DLinkedNode<KeyValuePair<TK, TV>>[newBucketSize];
for (var i = 0; i < hashArray.Length; i++)
{
var item = hashArray[i];
if (item != null)
{
var current = item;
/*找到新的存储点*/
while (current != null)
{
var next = current.Next;
var newIndex = Math.Abs(current.Data.Key.GetHashCode()) % newBucketSize;
if (smallerArray[newIndex] == null)
{
filledBuckets++;
smallerArray[newIndex] = current;
}
var newItem = smallerArray[newIndex];
while(newItem.Next != null)
newItem = newItem.Next;
newItem.Next = current;
current = next;
}
}
}
hashArray = smallerArray;
}
}
最终代码
拉链法:最终代码
internal class DLinkedNode<T>
{
public T Data;
public DLinkedNode<T> Next;
public DLinkedNode<T> Previous;
public DLinkedNode(T data)
{
Data = data;
}
}
internal class SeparateChainingDictionary<TK, TV> : IDictionary<TK, TV>
{
//构建一个数组,数组每个节点都是链表
private DLinkedNode<KeyValuePair<TK, TV>>[] hashArray;
//已使用数组下标个数
private int filledBuckets;
public SeparateChainingDictionary(int capacity)
{
if (capacity < 0)
throw new ArgumentOutOfRangeException("初始值容量不能小于0");
hashArray = new DLinkedNode<KeyValuePair<TK, TV>>[capacity];
}
public TV this[TK key]
{
get => throw new NotImplementedException();
set => throw new NotImplementedException();
}
public int Count { get; private set; }
/// <summary>
/// 添加
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
/// <exception cref="Exception"></exception>
public void Add(TK key, TV value)
{
Grow();
var index = Math.Abs(key.GetHashCode()) % hashArray.Length;
if (hashArray[index] == null)
{
hashArray[index] = new DLinkedNode<KeyValuePair<TK, TV>>(new KeyValuePair<TK, TV>(key, value));
filledBuckets++;
}
else
{
var current = hashArray[index];
while (current != null && current.Next != null)
{
/*此处可以判断是重复修改,还是抛异常*/
if (current.Data.Key.Equals(key)) throw new Exception("重复key");
current = current.Next;
}
if (current.Data.Key.Equals(key)) throw new Exception("重复key");
current.Next = new DLinkedNode<KeyValuePair<TK, TV>>(new KeyValuePair<TK, TV>(key, value));
}
Count++;
}
/// <summary>
/// 扩容
/// </summary>
private void Grow()
{
if (filledBuckets >= hashArray.Length * 0.7)
{
filledBuckets = 0;
var newBucketSize = hashArray.Length * 2;
var biggerArray = new DLinkedNode<KeyValuePair<TK, TV>>[newBucketSize];
for (var i = 0; i < hashArray.Length; i++)
{
var item = hashArray[i];
if (item != null)
{
var current = item;
while (current != null)
{
var next = current.Next;
var newIndex = Math.Abs(current.Data.Key.GetHashCode()) % newBucketSize;
if (biggerArray[newIndex] == null)
{
filledBuckets++;
biggerArray[newIndex] = current;
}
var bItem = biggerArray[newIndex];
while(bItem.Next != null)
bItem = bItem.Next;
bItem.Next = current;
current = next;
}
}
}
hashArray = biggerArray;
}
}
public void Clear()
{
throw new NotImplementedException();
}
/// <summary>
/// 查找
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public bool ContainsKey(TK key)
{
/*1.获取原始下标*/
var index = Math.Abs(key.GetHashCode()) % hashArray.Length;
/*2.为空即无*/
if (hashArray[index] == null) return false;
var current = hashArray[index];
/*3.遍历链表*/
while (current != null)
{
if (current.Data.Key.Equals(key)) return true;
current = current.Next;
}
return false;
}
public void Remove(TK key)
{
var index = Math.Abs(key.GetHashCode()) % hashArray.Length;
if (hashArray[index] == null) throw new Exception("未找到key");
var current = hashArray[index];
/*查找待删除元素*/
DLinkedNode<KeyValuePair<TK, TV>> item = null;
while (current != null)
{
if (current.Data.Key.Equals(key))
{
item = current;
break;
}
current = current.Next;
}
if (item == null)
{
throw new Exception("未找到key");
}
/*删除*/
if (item.Next == null)
item = null;
else
{
item.Previous = item.Next;
item.Next.Previous =item.Previous ;
item = null;
}
if (hashArray[index] == null)
{
filledBuckets--;
}
Count--;
Shrink();
}
private void Shrink()
{
/*是否减容*/
if (Math.Abs(filledBuckets - hashArray.Length * 0.3) < 0.1 && hashArray.Length / 2 > 0)
{
filledBuckets = 0;
var newBucketSize = hashArray.Length / 2;
var smallerArray = new DLinkedNode<KeyValuePair<TK, TV>>[newBucketSize];
for (var i = 0; i < hashArray.Length; i++)
{
var item = hashArray[i];
if (item != null)
{
var current = item;
/*找到新的存储点*/
while (current != null)
{
var next = current.Next;
var newIndex = Math.Abs(current.Data.Key.GetHashCode()) % newBucketSize;
if (smallerArray[newIndex] == null)
{
filledBuckets++;
smallerArray[newIndex] = current;
}
var newItem = smallerArray[newIndex];
while(newItem.Next != null)
newItem = newItem.Next;
newItem.Next = current;
current = next;
}
}
}
hashArray = smallerArray;
}
}
public IEnumerator<KeyValuePair<TK, TV>> GetEnumerator()
{
throw new NotImplementedException();
}
IEnumerator IEnumerable.GetEnumerator()
{
throw new NotImplementedException();
}
}
Dictionary源码分析
模拟实现:一个Dictionary,存储数据{1,’a’},{‘4′,’b’},{5,’c’}
1. 创建一个单链表,用来存储K-V
private struct Entry
{
public uint hashCode;
//值为-1,表示是该链条最后一个节点
//值小于-1,表示已经被删除的自由节点
public int next;
public TKey key; // Key of entry
public TValue value; // Value of entry
}
2. 创建一个数组当桶,还有一个链表数组(核心就这两个数组)
private int[]? _buckets;
private Entry[]? _entries;
3. 模拟实现插入{1,’a’},{‘4′,’b’},{5,’c’}
初始化
第一次插入{1,’a’}
第二次插入{‘4′,’b’}
第三次插入{5,’c’}
仔细看一下这三个数据的插入,及数据的变化,应该可以理解_buckets和_entries的关系
4.删除
上边再讲哈希表,包括我们自己实现的代码中,删除一个节点后,都要重新计算后边的位置。如何解决这个问题呢?我们可以使用Entry的next,来表示是否已经删除,小于0就表示是自由节点。
关于删除就这样几个变量:
private int _freeList;//最后一个删除的Entry下标
private int _freeCount;//当前已删除,但是还未重新使用的节点数量
private const int StartOfFreeList = -3;//帮助寻找自由节点的一个常量
看一下StartOfFreeList和_freeList和Entry.next如何寻找自由节点
- 删除时:Entry[i].next=上一层中的StartOfFreeList-_freeList
- 添加&&_freeCount>0:_freeList=StartOfFreeList – entries[_freeList].next
请看图理解:
源码:简化版(debug理解)
源码:简化版可直接运行
public static void Main(string[] args)
{
Dictionary<int, char> dic = new Dictionary<int, char>();
dic.TryInsert(1, 'a');
dic.TryInsert(4, 'b');
dic.TryInsert(5, 'c');
dic.Remove(4);
dic.Remove(5);
dic.TryInsert(0, 'd');
dic.TryInsert(1, 'e');
}
public class Dictionary<TKey, TValue>
{
private int[]? _buckets;
private Entry[]? _entries;
private int _count;
private int _freeList;
private int _freeCount;
private int _version;
private const int StartOfFreeList = -3;
public Dictionary()
{
/*初始值为素数,这里就不动态了,获取素数可以使用埃及筛选法*/
Initialize(7);
}
private int Initialize(int capacity)
{
int size = capacity;
int[] buckets = new int[size];
Entry[] entries = new Entry[size];
_freeList = -1;
_buckets = buckets;
_entries = entries;
return size;
}
public bool TryInsert(TKey key, TValue value)
{
Entry[]? entries = _entries;
uint hashCode = (uint)key.GetHashCode();
uint collisionCount = 0;
ref int bucket = ref GetBucket(hashCode);
int i = bucket - 1; // Value in _buckets is 1-based
if (typeof(TKey).IsValueType)
{
while (true)
{
if ((uint)i >= (uint)entries.Length)
{
break;
}
if (entries[i].hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entries[i].key, key))
{
entries[i].value = value;
return true;
}
i = entries[i].next;
collisionCount++;
if (collisionCount > (uint)entries.Length)
{
throw new Exception("");
}
}
}
int index;
if (_freeCount > 0)
{
index = _freeList;
// Debug.Assert((StartOfFreeList - entries[_freeList].next) >= -1, "shouldn't overflow because `next` cannot underflow");
_freeList = StartOfFreeList - entries[_freeList].next;
_freeCount--;
}
else
{
int count = _count;
if (count == entries.Length)
{
//Resize();
bucket = ref GetBucket(hashCode);
}
index = count;
_count = count + 1;
entries = _entries;
}
ref Entry entry = ref entries![index];
entry.hashCode = hashCode;
entry.next = bucket - 1; // Value in _buckets is 1-based
entry.key = key;
entry.value = value; // Value in _buckets is 1-based
bucket = index + 1;
_version++;
return true;
}
public bool Remove(TKey key)
{
if (key == null) return false;
if (_buckets != null)
{
uint collisionCount = 0;
uint hashCode = (uint)key.GetHashCode();
ref int bucket = ref GetBucket(hashCode);
Entry[]? entries = _entries;
int last = -1;
int i = bucket - 1; // Value in buckets is 1-based
while (i >= 0)
{
ref Entry entry = ref entries[i];
if (entry.hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entry.key, key))
{
if (last < 0)
{
bucket = entry.next + 1;
}
else
{
entries[last].next = entry.next;
}
entry.next = StartOfFreeList - _freeList;
entry.key = default!;
entry.value = default!;
_freeList = i;
_freeCount++;
return true;
}
last = i;
i = entry.next;
collisionCount++;
if (collisionCount > (uint)entries.Length)
{
}
}
}
return false;
}
private ref int GetBucket(uint hashCode)
{
int[] buckets = _buckets!;
return ref buckets[hashCode % (uint)buckets.Length];
}
private struct Entry
{
public uint hashCode;
//值为-1,表示是该链条最后一个节点
public int next;
public TKey key; // Key of entry
public TValue value; // Value of entry
}