今天来介绍一下 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[bucketIndex]
// 获取空闲的Entry对象，并设置数据
Entry entry = _entries[_freeList]
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[_freeList].next;- 第一步，先用 key 哈希计算后获得 hashCode。
- 第二步，用 hashCode 取余 _buckets.Length 获得 bucketIndex。这里取余 _buckets.Length 是为了将 hashCode 映射到 _buckets 数组内。
- 第三步，通过 _buckets[bucketIndex] 获得 bucket 值，通过bucket 值获取 _entries 数组中的Entry 对象。
- 最后则是更新 bucket 值和 _freeList 值。
下面给出示例数据来讲解一下。
// 假设 hashCode1 值获取为 123
uint hashCode1 = key1.GetHashCode()
// bucketIndex1 值为 0
int bucketIndex1 = hashCode % _buckets.Length// 假设 hashCode2 值获取为 456
uint hashCode2 = key2.GetHashCode()
// bucketIndex2 值为 0
int bucketIndex2 = hashCode % _buckets.Length_buckets = [4, -1, -1] // 长度为3的桶数组
_entries = [[hashCode=456, next=-1, key="a", value=1], // 0 - 使用中[hashCode=-1, next=3, key=null, value=null], // 1 - 已删除[hashCode=-1, next=1, key=null, value=null], // 2 - 已删除(当前_freeList)[hashCode=-1, next=-1, key=null, value=null], // 3 - 已删除[hashCode=123, next=0, key="b", value=2] // 4 - 使用中
]
_freeList = 2假设通过 key1 获取到的 hashCode 为123，通过取余获取到bucketIndex为0，由_buckets[0]可以获取到_entries[4]中的Entry对象，通过比对hashCode 查找的对象为_entries[4]。
同样，key2获取到hashCode为456，同样取余获取到bucketIndex为0，由_buckets[0]获取到_entries[4]中的对象，由于hashCode不同，则需要继续通过next查找下一个Entry对象，通过查找_entries[0]对象，比对hashCode，key2查找的对象为_entries[0]。
查找空闲中的Entry对象则需要用到_freeList，此时_freeList=2，获取空闲Entry对象时会先获取_entries[2]对象，通过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
