【C#】Dictionary底层实现

Dictionary的键值对映射是通过哈希算法的函数建立的。这里不对哈希算法做过多的解释，算法本身就是将不定长度的键（可以是整数、字符串或对象）转化成一个固定值。

字典的关键成员

private struct Entry
{public int hashCode;public int next;public K key;//字典中键的类型public V value;//字典中值的类型
}private int[] buckets;//哈希桶数组
private Entry[] entries;//数据实体数组

buckets作用：存储entries 数据实体数组的索引

存储原理（添加键值对）

1.通过哈希(Hash)算法获取键的哈希值，赋值到数据实体 中hashCode
2.将hashCode对buckets数组长度取余（%）获得buckets数组中的buckets下标
3.通过buckets下标获得buckets数组中的元素（即为entries下标）
a.元素有效（!= -1）代表buckets 的索引位置 存储了 entries数组中索引，将当前元素赋值给Entry数据实体的next，并将Entry数据实体的索引赋值给buckets数组中的元素
b.元素无效（== -1）代表buckets 的索引位置 没有 entries数组中索引，将Entry数据实体的索引赋值给buckets数组中的元素

存储例子

插入数据A

Dictionary.Add("a", 123);

1. 假设* 通过哈希(Hash)算法获取键(“a”)的值为10
2. 将10对buckets数组长度取余（%）获得buckets数组中的索引2
3. 通过 下标2 获得buckets数组中的buckets[2]
4. buckets[2] == -1 代表buckets 的索引位置 没有 entries数组中索引，将Entry数据实体的索引赋值给buckets数组中的元素，即buckets[2] = 0

插入数据B

Dictionary.Add("qwe", 456);

1. 假设* 通过哈希(Hash)算法获取键(“qwe”)的值也为10
2. 将10对buckets数组长度取余（%）获得buckets数组中的索引2
3. 通过 下标2 获得buckets数组中的buckets[2]
4. buckets[2] != -1 代表buckets 的索引位置 存储了 entries数组中索引，将当前元素赋值给Entry数据实体的next，即数据B的next = buckets[2] = 0，并将Entry数据实体的索引赋值给buckets数组中的元素，即buckets[2] = 1

读取原理（通过键获取值）

1. 通过哈希(Hash)算法获取键的哈希值，赋值到数据实体 中hashCode
2. 将hashCode对buckets数组长度取余（%）获得buckets数组中的buckets下标
3. 通过buckets下标获得buckets数组中的元素（即为entries下标）
4. 根据下标获取entries中的数据，判断Entry数据的key是否与想获取的相同
   a. 相同，返回Entry数据的value
   b. 不相同，根据Entry数据的next获取entries中的数据，直到key与想获取的相同，才返回value

读取例子

获取数据A

Dictionary["a"]

1. 假设* 通过哈希(Hash)算法获取键（“a”）的哈希值，赋值到数据实体为10
2. 将10对buckets数组长度取余（%）获得buckets数组中的索引2
3. 通过 索引2 获得buckets数组中的 buckets[2] = 1
4. 根据 1 获取entries中的数据，判断 entries[1].key == “a”?
5. （entries[1].key） = ”qwe“ != “a”，根据Entry数据的next获取entries中的数据 entries[next] = entries[0]，直到key与想获取的相同 entries[0].key == “a”，才返回entries[0].value = 123

获取数据B

Dictionary["qwe"]

1. 假设* 通过哈希(Hash)算法获取键（“a”）的哈希值，赋值到数据实体为10
2. 将10对buckets数组长度取余（%）获得buckets数组中的索引2
3. 通过 索引2 获得buckets数组中的 buckets[2] = 1
4. 根据 1 获取entries中的数据，判断 entries[1].key == “qwe”?
5. 相同，返回entries[1].value = 456

因为作者精力有限，文章中难免出现一些错漏，敬请广大专家和网友批评、指正。