【C#知识点详解】Dictionary＜TKey,TValue＞储存结构详解
本日来介绍一下 Dictionary 内部数据的存储方式，话不多说直接开始。内部数据
Dictionary 接纳 哈希表 的方式实现，其焦点构成部门如下：
// 实际内部实现（简化版）
private int[] _buckets; // 桶数组，存储条目索引
private Entry[] _entries;// 条目数组，存储键值对
private int _freeList; // 空闲链表头指针
private struct Entry {
public uint hashCode; // 31位哈希码（取绝对值）
public int next; // 同一桶中的下一个条目索引
public TKey key; // 键
public TValue value; // 值
} Entry 是Dictionary内部的一个数据结构，其中包含了四个成员变量，分别是：
[*]uint hashCode：哈希码，哈希码由key生成，用于比对查找数据。
[*]int next：_entries的索引值，指向下一个Entry。
[*]TKey key：存储key数据。
[*]TValue value：存储value数据。
int[] _buckets 是一个 int 型的索引数组，内部存储的是 _entries 的索引值。
Entry[] _entries 是一个 Entry 型的数组对象，是现实存储数据的地方。
_freeList 是一个 int 整数，存储的是 _entries 索引，索引指向的是空闲Entry链表，第一个空闲Entry的索引 。
数据解说
Dictionary 由 _buckets、_entries、_freeList三个紧张部门构成。
_buckets 是一个 int 数组，内部存储的是 _entries 的索引值，Dictionary 通过 key 的哈希码盘算获得 _entries 的索引值，从而获取 Entry 对象。
_entries 是一个 Entry 类型的数组，Entry 内除了生存了相干的对象数据，还通过next变量，维护了一条数据链。通过next可以快速的查找到对象数据。
_freeList 是一个整数变量，其生存的是 _entries 数组中空闲 Entry 对象的索引。全部空闲的Entry对象也是通过next变量进行链接起来的。
下面通过一段 Dictionary 添加数据的示例代码，来解说一下_buckets、_entries、_freeList是如何协作的，示例代码如下：
// 获取key的哈希码
uint hashCode = key.GetHashCode()
// 计算获取_buckets索引
int bucketIndex = hashCode % _buckets.Length
// 获取bucket值
ref int bucket = _buckets
// 获取空闲的Entry对象，并设置数据
Entry entry = _entries
entry.hashCode = hashCode;
entry.next = bucket - 1; // Value in _buckets is 1-based
entry.key = key;
entry.value = value;
// 更新_buckets中的值，并指向对应Entry对象
bucket = _freeList
// 更新_freeList
_freeList = StartOfFreeList - entries.next;
[*]第一步，先用 key 哈希盘算后获得 hashCode。
[*]第二步，用 hashCode 取余 _buckets.Length 获得 bucketIndex。这里取余 _buckets.Length 是为了将 hashCode 映射到 _buckets 数组内。
[*]第三步，通过 _buckets 获得 bucket 值，通过bucket 值获取 _entries 数组中的Entry 对象。
[*]末了则是更新 bucket 值和 _freeList 值。
下面给出示例数据来解说一下。
// 假设 hashCode1 值获取为 123
uinthashCode1 = key1.GetHashCode()
// bucketIndex1 值为 0
int bucketIndex1 = hashCode % _buckets.Length
// 假设 hashCode2 值获取为 456
uinthashCode2 = key2.GetHashCode()
// bucketIndex2 值为 0
int bucketIndex2 = hashCode % _buckets.Length
_buckets = // 长度为3的桶数组
_entries = [
, // 0 - 使用中
,// 1 - 已删除
,// 2 - 已删除(当前_freeList)
,// 3 - 已删除
// 4 - 使用中
]
_freeList = 2 假设通过 key1 获取到的 hashCode 为123，通过取余获取到bucketIndex为0，由_buckets可以获取到_entries中的Entry对象，通过比对hashCode 查找的对象为_entries。
同样，key2获取到hashCode为456，同样取余获取到bucketIndex为0，由_buckets获取到_entries中的对象，由于hashCode差别，则须要继续通过next查找下一个Entry对象，通过查找_entries对象，比对hashCode，key2查找的对象为_entries。
查找空闲中的Entry对象则须要用到_freeList，此时_freeList=2，获取空闲Entry对象时会先获取_entries对象，通过next变量获取下一个对象，当next为-1时则为结尾。
相干文档链接
Dictionary类官方文档：https://learn.microsoft.com/zh-cn/dotnet/api/system.collections.generic.dictionary-2?view=net-9.0
Dictionary源码地点：https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/Dictionary.cs
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]