C#容器源码分析 --- Dictionary<TKey,TValue>

Dictionary<TKey, TValue> 是 System.Collections.Generic 命名空间下的高性能键值对集合,其核心实现基于​​哈希表​​和​​链地址法(Separate Chaining)。

.Net4.8 Dictionary<TKey,TValue>源码地址:
dictionary.cs (microsoft.com)https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,d3599058f8d79be0

内部结构:

1.主要字段和属性: 

1.buckets:这是一个整型数组,用作哈希桶。每个元素都代表一个桶的索引,而桶是用于存放键值对的链表的头节点(即entries中的元素索引)。
2.entries:这是一个 Entry 结构体数组,Entry 结构体包含键、值、哈希码以及指向下一个 Entry 的索引。
3.count:该字段表示 Dictionary 中当前键值对的数量。
4.version:这是版本号,在对 Dictionary 进行修改操作时,版本号会更新,主要用于在迭代期间检测集合是否被修改。
5.freeList:此为空闲列表的头索引,用于管理已删除的 Entry 槽位,方便后续复用。
6.freeCount:该字段表示空闲列表中 Entry 的数量。
7.comparer:这是一个 IEqualityComparer<TKey> 类型的比较器,用于比较键的相等性。
8.keys:这是一个 KeyCollection 类型的对象,用于表示 Dictionary 中的所有键。
9.values:这是一个 ValueCollection 类型的对象,用于表示 Dictionary 中的所有值。

表示当前字典中含有的键值对数量。
注:因为在字典中移除元素时,字典的count并没有改变,count只在freeCount(字典中空闲的数量)为0时,才进行增加的操作,所以在获取字典中有效的键值对数量时,需要用count - freeCount来计算。

2.构造函数:

1.无参构造函数指定初始容量的构造函数指定比较器的构造函数指定初始容量和比较器的构造函数

最终都调用了指定容量和比较器的构造函数。

1.CoreCLR 平台的特殊处理

HashHelpers.s_UseRandomizedStringHashing​​:
​​作用​​:标志位,指示是否启用​​随机化字符串哈希​​(防御哈希碰撞攻击)。
​​默认值​​:在 .NET Core 中通常为 true。
​​comparer == EqualityComparer<string>.Default​​:
​​条件​​:检测用户是否显式使用了默认的字符串比较器。
​​替换比较器​​:
this.comparer = (IEqualityComparer<TKey>) NonRandomizedStringEqualityComparer.Default;
​​目的​​
在启用随机化哈希的平台上,若用户未指定自定义比较器,强制使用​​非随机化比较器​​。
​​兼容性​​:确保与旧版本 .NET Framework 行为一致,避免因随机化哈希导致的跨版本不一致问题。

2.初始化容量
如果指定了容量就会调用到Initialize函数,如下:

通过HashHelpers.GetPrime得到一个新的值,作为哈希桶和键值对数组的容量,代码如下:
解释
1. min|1:确保 i 初始值为大于等于 min 的最小奇数。min | 1 将 min 的最低二进制位强制设为 1。若 min 是偶数,结果为 min + 1;若 min 是奇数,结果不变。
2.IsPrime(i):验证 i 是否为质数。
3.(i - 1) % Hashtable.HashPrime != 0:确保 i - 1 不能被预定义的质数 HashPrime 整除。

作用
上述代码通常用于哈希表扩容时选择新容量​​,其设计目标包括:
​​减少哈希冲突​​:选择质数作为容量,使哈希分布更均匀。
​​避免特定冲突模式​​:通过 (i - 1) % HashPrime != 0 排除某些可能导致冲突的值。
​​性能优化​​:跳过偶数和快速终止条件提升搜索效率。

 预制的质数表数据如下

2.指定键值对容器参数的构造函数、指定键值对容器和比较器参数的构造函数:

 3. 反序列化构造函数:

​此构造函数是 .NET 序列化机制中​​延迟加载模式​​的经典实现,确保复杂数据结构(如哈希表)在反序列化时的安全性和正确性。通过暂存 SerializationInfo 并在对象图构建完成后恢复数据,有效解决了依赖项初始化和哈希计算的时序问题。

核心原理​​
​​(1) 序列化流程​​
​​序列化时​​:调用 GetObjectData 方法(实现 ISerializable 接口),将字典的键值对、容量、比较器等数据写入 SerializationInfo。
​​反序列化时​​
框架通过反射调用此受保护构造函数,传入 SerializationInfo 和上下文。
​​不立即还原哈希表​​,而是将 SerializationInfo 暂存到 HashHelpers.SerializationInfoTable(一个静态字典),等待后续处理。
​​(2) 延迟加载的原因​​
​​依赖项未就绪​​:反序列化时,字典可能依赖其他尚未反序列化的对象(如自定义比较器)。
​​哈希码计算安全​​:某些键的 GetHashCode() 可能在反序列化时抛出异常(例如,键对象未完全初始化)。
​​(3) 完成反序列化​​
在对象图完全构造后,框架调用 IDeserializationCallback.OnDeserialization 方法,此时从 HashHelpers.SerializationInfoTable 中取出暂存的数据,重建哈希表的 buckets 和 entries 数组。

动态扩容:

在字典中扩容的调用有两处
1.字典中的元素已满:会通过一个函数重新找到一个新的容量值。

ExpandPrime代码如下:



2.字典中的哈希冲突的数量已达到阈值:传入新的容量的是entries当前长度,并强制更新hashcode。

扩容的主要方法如下

主要方法:

1.Add:调用字典中的Insert方法

2.Remove


3.Insert

4.Clear

5.FindEntry

6.ContainsKey

7.ContainsValue

8.TryGetValue

未完待续。。。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/75.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

STM32自学进阶指南:从入门到精通的成长路径 | 零基础入门STM32第九十九步

主题内容教学目的/扩展视频自学指导通过数据手册和搜索引擎查找资料,独立解决问题以积累经验和提升能力。自学过程中应保持敬畏之心,不断总结未知领域,持续进步。师从洋桃电子,杜洋老师 📑文章目录 一、自学指导全景图1.1 学习路线对比1.2 关键学习策略二、待探索技术领域…

FPGA 37 ,FPGA千兆以太网设计实战:RGMII接口时序实现全解析( RGMII接口时序设计,RGMII~GMII,GMII~RGMII 接口转换 )

目录 前言 一、设计流程 1.1 需求理解 1.2 模块划分 1.3 测试验证 二、模块分工 2.1 RGMII→GMII&#xff08;接收方向&#xff0c;rgmii_rx 模块&#xff09; 2.2 GMII→RGMII&#xff08;发送方向&#xff0c;rgmii_tx 模块&#xff09; 三、代码实现 3.1 顶层模块 …

健康养生:为生活注入活力的艺术

在现代社会的高速运转下&#xff0c;健康养生逐渐成为大众热议的话题&#xff0c;它不再是老年人的专属&#xff0c;而是各个年龄段人群都在积极探索的生活方式。健康养生并非复杂的学术理论&#xff0c;而是一门将生活细节转化为健康能量的艺术&#xff0c;巧妙地为我们的生活…

Aspose.Words导出word,服务器用内存流处理,不生成磁盘文件

框架集&#xff1a;.NET8 public async Task<IActionResult> ExportPDF(long? id) {var infoawait form_Dahui_ReportDao.GetAsync(id);if (info null){return Content("没找到数据");}//读取word模板string fileTemp Path.Combine(AppContext.BaseDirect…

MySQL面试题及答案,2025最新整理

文章目录 前言1.InnoDB 与 MyISAM 在事务和索引方面有哪些主要区别&#xff1f;2.简述 MySQL 的事务隔离级别及其对并发问题的解决情况&#xff1f;3.在使用 MySQL 索引时&#xff0c;如何避免索引失效&#xff0c;提高查询效率&#xff1f; 前言 本文围绕 MySQL面试题及答案&…

GGML源码逐行调试(下)

目录 前言1. 简述2. 预分配计算图内存2.1 创建图内存分配器2.2 构建最坏情况的计算图2.3 预留计算图内存 3. 分词4. 模型推理与生成4.1 模型推理4.2 采样 结语下载链接参考 前言 学习 UP 主 比飞鸟贵重的多_HKL 的 GGML源码逐行调试 视频&#xff0c;记录下个人学习笔记&#x…

考研单词笔记 2025.04.12

aware a知道的&#xff0c;意识到的&#xff0c;警觉的 awareness n意识&#xff0c;了解&#xff0c;觉察 conscious a有意识的&#xff0c;意识到的&#xff0c;有意的&#xff0c;刻意的&#xff0c;神志清醒的&#xff0c;慎重的&#xff0c;关注的 unconscious a无意识…

2025蓝桥杯省赛C/C++研究生组游记

前言 至少半年没写算法题了&#xff0c;手生了不少&#xff0c;由于python写太多导致行末老是忘记打分号&#xff0c;printf老是忘记写f&#xff0c;for和if的括号也老是忘写&#xff0c;差点连&&和||都忘记了。 题目都是回忆版本&#xff0c;可能有不准确的地方。 …

巧用递归算法:破解编程难题的“秘密武器”

专栏&#xff1a;算法的魔法世界 个人主页&#xff1a;手握风云 目录 一、递归 二、例题讲解 2.1. 汉诺塔问题 2.2. 合并两个有序链表 2.3. 反转链表 2.4. 两两交换链表中的节点 2.5. Pow(x, n) 三、总结 一、递归 递归的概念 一个方法在执行过程中调用自身, 就称为递…

代码随想录算法训练营Day28 | Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

代码随想录算法训练营Day28 | Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯 一、斐波那契数 相关题目&#xff1a;Leetcode509 文档讲解&#xff1a;Leetcode509 视频讲解&#xff1a;Leetcode509 1. Leetcode509. 斐波那契数 斐波那契数 &#xff08;通常…

CAD导入arcgis中保持面积不变的方法

1、加载CAD数据&#xff0c;选择面数据&#xff0c;如下&#xff1a; 2、加载进来后&#xff0c;右键导出数据&#xff0c;导出成面shp数据&#xff0c;如下&#xff1a; 3、选择存储路径&#xff0c;导出面后计算面积&#xff0c;如下&#xff1a; 4、与CAD中的闭合线面积核对…

备赛蓝桥杯-Python-考前突击

额&#xff0c;&#xff0c;离蓝桥杯开赛还有十个小时&#xff0c;最近因为考研复习节奏的问题&#xff0c;把蓝桥杯的优先级后置了&#xff0c;突然才想起来还有一个蓝桥杯呢。。 到目前为止python基本语法熟练了&#xff0c;再补充一些常用函数供明天考前再背背&#xff0c;算…