【C#知识点详解】Dictionary＜TKey,TValue＞储存结构详解

        本日来介绍一下 Dictionary 内部数据的存储方式，话不多说直接开始。

内部数据

        Dictionary 接纳 哈希表 的方式实现，其焦点构成部门如下：

1. // 实际内部实现（简化版）
2. private int[] _buckets;    // 桶数组，存储条目索引
3. private Entry[] _entries;  // 条目数组，存储键值对
4. private int _freeList;     // 空闲链表头指针
6. private struct Entry {
7.     public uint hashCode;   // 31位哈希码（取绝对值）
8.     public int next;       // 同一桶中的下一个条目索引
9.     public TKey key;       // 键
10.     public TValue value;   // 值
11. }

复制代码

        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是如何协作的，示例代码如下：

1. // 获取key的哈希码
2. uint hashCode = key.GetHashCode()
3. // 计算获取_buckets索引
4. int bucketIndex = hashCode % _buckets.Length
5. // 获取bucket值
6. ref int bucket = _buckets[bucketIndex]
7. // 获取空闲的Entry对象，并设置数据
8. Entry entry = _entries[_freeList]
9. entry.hashCode = hashCode;
10. entry.next = bucket - 1; // Value in _buckets is 1-based
11. entry.key = key;
12. entry.value = value;
13. // 更新_buckets中的值，并指向对应Entry对象
14. bucket = _freeList
15. // 更新_freeList
16. _freeList = StartOfFreeList - entries[_freeList].next;

复制代码

• 第一步，先用 key 哈希盘算后获得 hashCode。
  
• 第二步，用 hashCode 取余 _buckets.Length 获得 bucketIndex。这里取余 _buckets.Length 是为了将 hashCode 映射到 _buckets 数组内。
  
• 第三步，通过 _buckets[bucketIndex] 获得 bucket 值，通过bucket 值获取 _entries 数组中的Entry 对象。
  
• 末了则是更新 bucket 值和 _freeList 值。
  

        下面给出示例数据来解说一下。

1. // 假设 hashCode1 值获取为 123
2. uint  hashCode1 = key1.GetHashCode()
3. // bucketIndex1 值为 0
4. int bucketIndex1 = hashCode % _buckets.Length
6. // 假设 hashCode2 值获取为 456
7. uint  hashCode2 = key2.GetHashCode()
8. // bucketIndex2 值为 0
9. int bucketIndex2 = hashCode % _buckets.Length
11. _buckets = [4, -1, -1]  // 长度为3的桶数组
12. _entries = [
13.     [hashCode=456, next=-1, key="a",  value=1],          // 0 - 使用中
14.     [hashCode=-1,  next=3,  key=null, value=null],  // 1 - 已删除
15.     [hashCode=-1,  next=1,  key=null, value=null],  // 2 - 已删除(当前_freeList)
16.     [hashCode=-1,  next=-1, key=null, value=null],  // 3 - 已删除
17.     [hashCode=123, next=0,  key="b",  value=2]           // 4 - 使用中
18. ]
19. _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


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。