当前位置：首页 > news >正文

C# Dictionary的实现原理

news 来源：原创 2025/5/10 20:06:35

在 C# 中，Dictionary<TKey, TValue> 是一个基于哈希表（Hash Table）实现的键值对集合。它提供了高效的插入、删除和查找操作，平均时间复杂度接近 O(1)。下面是 Dictionary 的核心实现原理：

1. Dictionary 的核心数据结构

C# 的 Dictionary<TKey, TValue> 主要由以下几个部分组成：

数组（buckets）：存储哈希桶（Bucket）的索引。
数组（entries）：存储键值对（哈希表中的实际数据）。
哈希函数（GetHashCode）：将键映射到哈希桶。
碰撞解决（拉链法）：采用 链地址法（Chaining with Linked List）。
负载因子（Load Factor）：决定何时扩容，默认为 0.75。

数据结构

private int[] buckets;         // 哈希桶数组，存储 entry 的索引
private Entry[] entries;       // 存储实际的键值对
private int count;             // 当前存储的元素个数
private int freeList;          // 指向空闲 entry（删除后形成的空位）
private int freeCount;         // 空闲 entry 的数量private struct Entry
{public int hashCode;       // 计算出的哈希值public int next;           // 指向下一个冲突的元素（-1 表示无冲突）public TKey key;           // 键public TValue value;       // 值
}

2. Dictionary 的主要操作

（1）添加元素

当调用 dictionary.Add(key, value) 时，Dictionary 执行以下步骤：

计算哈希值：调用 key.GetHashCode() 计算哈希值 hashCode。
计算索引：对哈希值取模，index = hashCode % buckets.Length，确定应该存放的桶。
检查冲突：
- 如果该桶为空，则直接存储。此时count字段记录字典中元素个数。令bucket[index] = count，然后将内容存储到Entry[count]中，随后count++。
- 如果发生哈希冲突，则使用链地址法存储，即将 entries 中的 next 指向旧的 Entry，形成链表。

扩容（如有必要）：

如果 count > capacity * 0.75，则触发扩容，通常是 2 倍扩容。

public void Add(TKey key, TValue value)

{

 int hashCode = key.GetHashCode() & 0x7FFFFFFF;  // 计算哈希值int index = hashCode % buckets.Length;  // 计算桶的索引// 处理哈希冲突：如果桶为空，直接插入if (buckets[index] == -1){buckets[index] = count;  // 将当前元素插入桶数组entries[count] = new Entry { hashCode = hashCode, key = key, value = value, next = -1 	};count++;}else{// 发生哈希冲突，遍历链表int current = buckets[index];while (current >= 0){Entry entry = entries[current];if (entry.hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entry.key, key)){entries[current].value = value;  // 如果找到相同的键，更新值return;}current = entry.next;  // 查找下一个节点}// 如果没有找到，插入新的元素到链表头部entries[count] = new Entry { hashCode = hashCode, key = key, value = value, next = buckets[index] };buckets[index] = count;  // 更新桶的索引count++;}// 扩容检查if (count > buckets.Length * 0.75){Resize();  // 扩容}

}

（2）查找元素

当调用 dictionary[key] 或 TryGetValue(key, out value) 时：

计算哈希值：hashCode = key.GetHashCode()。
计算索引：index = hashCode % buckets.Length。
遍历链表

：
- 如果桶中第一个元素匹配，则直接返回。
- 如果有哈希冲突（next != -1），遍历 entries 直到找到 key。

（3）删除元素

当调用 dictionary.Remove(key) 时：

计算哈希值，找到哈希桶索引。
遍历链表，找到匹配的 Entry。
更新链表指针：
- 如果是第一个元素，则更新 buckets 指向 next 位置。
- 如果在链表中，则调整 next 以跳过该元素。
回收 entry：
- 将 entry 记录到 freeList，方便后续使用。

（4）扩容机制

当 count >= capacity * 0.75 时，Dictionary 会进行 2 倍扩容：

创建更大的 buckets 和 entries 数组（通常是 2 倍大小）。
重新计算索引，重新分配 buckets 和 entries。
重新插入所有 Entry，因为 hashCode % newCapacity 结果不同，所有键值对需要重新计算索引。

3. Dictionary 的碰撞处理

C# 的 Dictionary 采用 链地址法 处理哈希冲突：

entries 形成链表，每个 Entry 记录 next 指向同一个桶的下一个 Entry。
遍历链表时，检查 hashCode 和 key 是否匹配。

示例假设 buckets 长度为 5，并插入以下键值对：

dict.Add(1, "Apple");
dict.Add(6, "Banana"); // 6 % 5 == 1，与 1 发生哈希冲突

哈希桶结构如下：

buckets: [ -1,  0 -> 1, -1, -1, -1 ]   // index 1 存储链表 (1 → 6)
entries: 0: { hashCode=1, key=1, value="Apple", next=1 }1: { hashCode=6, key=6, value="Banana", next=-1 }

查找 dict[6] 时：

计算 index = 6 % 5 = 1。
遍历链表：
- entries[0] (key=1) 不匹配，继续遍历 next=1。
- entries[1] (key=6) 匹配，返回 "Banana"。

4. Dictionary 的优缺点

优点

查找快：平均时间复杂度 O(1)。
插入删除快：平均时间复杂度 O(1)。
自动扩容：避免手动管理大小。

缺点

内存占用大：数组 + 链表可能浪费额外空间。
哈希碰撞影响性能：冲突越多，查找速度降至 O(n)。
不保证顺序：Dictionary 无序存储键值对。

5. Dictionary 的替代方案

数据结构	适用场景
`SortedDictionary<TKey, TValue>`	需要按键排序（基于红黑树，O(log n)）
`SortedList<TKey, TValue>`	适用于小数据量，查找快但插入慢
`HashSet<T>`	仅存储键，不存储值
`ConcurrentDictionary<TKey, TValue>`	多线程安全字典

C# Dictionary的实现原理

在 C# 中，Dictionary<TKey, TValue> 是一个基于哈希表（Hash Table）实现的键值对集合。它提供了高效的插入、删除和查找操作，平均时间复杂度接近 O(1)。下面是 Dictionary 的核心实现原理： 1. Dictionary 的核心数…...

编程日记 2025/5/10 20:06:35

在项目中操作 MySQL

在现代Web开发中，Node.js因其非阻塞I/O模型和高效的性能成为了构建后端服务的热门选择之一。与此同时，MySQL作为最流行的关系型数据库管理系统之一，凭借其稳定性、可靠性和易用性，在数据存储方面扮演着重要角色。本文将详细介绍如…...

编程日记 2025/5/6 4:50:14

第6章 6.4 ASP.NET Core Web API各种技术及选择

6.4.1 控制器父类用哪个 6.2小节和6.3小节所演示的ASP.NET Core Web API 的控制器类都继承自ControllerBase，而6.1中MVC的控制器继承自Controller，Controller又继承自ControllerBase。所以，一般情况下，编写的WebAPI控制器类继承…...

编程日记 2025/5/7 21:28:34

DeepSeek本地化部署【window下安装】【linux下安装】

一、window 本地安装指导 1.1、下载window安装包 https://ollama.com/download/OllamaSetup.exe 1.2、点击下载好的安装包进行安装检测安装是否成功： C:\Users\admin>ollama -v ollama version is 0.5.7有上面的输出，则证明已经安装成功。配置…...

编程日记 2025/5/9 15:58:37

字玩FontPlayer开发笔记14 Vue3实现多边形工具

目录字玩FontPlayer开发笔记14 Vue3实现多边形工具笔记整体流程临时变量多边形组件数据结构初始化多边形工具mousedown事件mousemove事件监听mouseup事件渲染控件将多边形转换为平滑的钢笔路径字玩FontPlayer开发笔记14 Vue3实现多边形工具字玩FontPlayer是笔者开源的一款字…...

编程日记 2025/5/10 9:35:59

kkFileView二开之pdf转图片接口

kkFileView二开之Pdf转图片接口 1 kkFileView源码下载及编译2 Pdf转图片接口2.1 背景2.2 分析2.2 接口开发2.2.1 编写Pdf转图片方法2.2.2 编写转换接口 2.3 接口测试2.3.1 Pdf文件准备2.3.2 pdf2Image 3 部署 1 kkFileView源码下载及编译前文【kkFileView二开之源码编译及部…...

编程日记 2025/5/10 15:22:49

达梦tpcc压测

造数在这个日志输出中，主要执行了一系列数据库操作，涵盖了数据库信息检查、表的创建与数据加载、索引的添加、数据验证等步骤。具体分析如下： 数据库信息检查： 查询了数据库的版本、实例名称、日志文件大小、字符集等信息。删…...

编程日记 2025/5/9 2:20:07

计算机毕业设计PySpark+hive招聘推荐系统职位用户画像推荐系统招聘数据分析招聘爬虫数据仓库 Django Vue.js Hadoop

温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 作者简介：Java领…...

编程日记 2025/5/6 10:57:10

DeepSeek正重构人形机器人和具身大模型赛道！

中国人工智能公司DeepSeek（深度求索）以“低成本、高效率、强开放”的研发范式横空出世，火遍并震撼全球科技圈；DeepSeek展现出来的核心竞争力，除了低成本及推理能力，更重要的是开源模型能力追赶上了最新的闭…...

编程日记 2025/5/6 6:44:53

第1章信息化发展（一）

1.1信息与信息化 1.1.1信息基础 1.信息的定义信息是物质、能量及其属性的标示的集合，是确定性的增加。它以物质介质为载体，传递和反映世界各种事物存在方式、运动状态等的表征。信息不是物质也不是能量，它以一种普遍形式，表达…...

编程日记 2025/5/1 6:26:54

面试经典150题——字典树

文章目录 1、实现 Trie (前缀树)1.1 题目链接1.2 题目描述1.3 解题代码1.4 解题思路 2、添加与搜索单词 - 数据结构设计2.1 题目链接2.2 题目描述2.3 解题代码2.4 解题思路 3、单词搜索 II3.1 题目链接3.2 题目描述3.3 解题代码3.4 解题思路对于字典树而言，之前做过…...

编程日记 2025/5/1 6:08:42

【前端 DevOps】GitHub Actions 与 GitLab CI 实战：实现前端项目的自动化测试与部署

网罗开发 （小红书、快手、视频号同名） 大家好，我是展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等…...

编程日记 2025/5/6 4:15:04

SQLMesh系列教程-3：SQLMesh模型属性详解

SQLMesh 的 MODEL 提供了丰富的属性，用于定义模型的行为、存储、调度、依赖关系等。通过合理配置这些属性，可以构建高效、可维护的数据管道。在 SQLMesh 中，MODEL 是定义数据模型的核心结构，初学SQLMesh，定义模型看到属…...

编程日记 2025/5/6 6:39:45

【Maven】多module项目优雅的实现pom依赖管理

【Maven】多module项目优雅的实现pom依赖管理【一】方案设计原则【二】项目结构示例【三】实现思路【1】可能的问题点：【2】解决方案的思路：【3】需要注意的地方：【4】可能的错误： 【四】实现案例【1】父POM设计（pare…...

编程日记 2025/5/6 11:25:44

【数字】异步FIFO面试的几个小问题与跨时钟域时序约束

入门数字设计的时候，跨时钟域的数据处理是绕不开的课题，特别是多比特数据跨时钟域时，都会采用异步FIFO的方法。异步FIFO中涉及较多的考点这里记录几个以供大家参考。 1. 异步FIFO的空满判断分别在哪个域？ 根据异步FIFO的结构&…...

编程日记 2025/5/9 17:35:38

云原生时代的开发利器

云原生时代的开发工具集之中，至少应有这样一种利器：基于微服务架构的低代码开发平台，同时与业界标准的云原生技术支撑设施能够完全协同和融合。低代码开发平台的构建不仅仅是采用微服务开发框架，更加重要的是符合当前主流的中台和…...

编程日记 2025/5/10 20:00:47

利用IDEA将Java.class文件反编译为Java文件：原理、实践与深度解析

文章目录引言：当.class文件遇到源代码缺失第一章：反编译技术基础认知1.1 Java编译执行原理1.2 反编译的本质1.3 法律与道德边界第二章：IDEA内置反编译工具详解2.1 环境准备2.2 三步完成基础反编译2.3 高级反编译技巧2.3.1 调试模式反编译2.…...

编程日记 2025/5/5 0:24:39

C++ Primer 参数传递

欢迎阅读我的【CPrimer】专栏专栏简介：本专栏主要面向C初学者，解释C的一些基本概念和基础语言特性，涉及C标准库的用法，面向对象特性，泛型特性高级用法。通过使用标准库中定义的抽象设施，使你更加适应高级…...

编程日记 2025/5/5 17:33:11

2.7 静态方法/构造函数Mock

静态方法/构造函数Mock 在单元测试中，静态方法和构造函数的Mock是相对复杂的需求，因为Mockito的核心设计基于对象实例的模拟。然而，通过扩展工具或特定技巧，可以实现对这些场景的处理。本章详解两种主流方案：PowerMoc…...

编程日记 2025/5/9 15:00:47

注册Gmail如何跳过手机验证环节？

很多小伙伴在注册Gmail的时候都会遇到一个难题：手机号码验证，有可能包括了“手机号无法验证” “国内手机号验证失败” “收不到验证码”等等问题，但根据真实案例，还有部分人则是“幸运地”没有手机号验证环节，那么今…...

编程日记 2025/5/1 3:53:12

【算法专场】哈希表

目录前言哈希表 1. 两数之和 - 力扣（LeetCode） 算法分析算法代码面试题 01.02. 判定是否互为字符重排编辑算法分析算法代码 217. 存在重复元素算法分析算法代码 219. 存在重复元素 II 算法分析算法代码解法二算法代码算法…...

编程日记 2025/5/5 23:15:11

5、pod 详解（kubernetes）

pod 详解 （kubernetes） Pod 的基础概念pause 容器Pod 的分类与创建自主式 Pod控制器管理的 Pod静态 Pod Pod容器的分类基础容器（infrastructure container）初始化容器（initcontainers）应用容器（…...

编程日记 2025/5/10 6:58:49

二叉树详解：Java实现与应用

在计算机科学中，数据结构是构建高效算法的基石，而二叉树作为一种基础且重要的树形结构，在诸多领域都有着广泛应用，如数据库索引、文件系统、编译器设计等。本文将从基础概念入手，带你逐步深入理解二叉树，并…...

编程日记 2025/4/28 17:39:09

GPT和BERT

笔记来源： Transformer、GPT、BERT，预训练语言模型的前世今生（目录） - B站-水论文的程序猿 - 博客园 ShusenWang的个人空间-ShusenWang个人主页-哔哩哔哩视频（RNN模型与NLP应用） 一、GPT 1.1 GPT 模型的…...

编程日记 2025/5/10 14:30:54

【工业安全】-CVE-2024-30891- Tenda AC18路由器命令注入漏洞

1.漏洞描述 2.漏洞复现 2.1 qemu-user 模拟： 2.2 qemu-system模拟： 3.漏洞分析 4.poc代码： 1.漏洞描述漏洞编号：CVE-2024-30891 漏洞名称：Tenda AC18 命令注入威胁等级：高危漏洞详情：Ten…...

编程日记 2025/5/9 17:25:35

如何从0开始将vscode源码编译、运行、打包桌面APP

** 网上关于此的内容很少，今天第二次的完整运行了，按照下文的顺序走不会出什么问题。最重要的就是环境的安装，否则极其容易报错，请参考我的依赖版本以及文末附上的vscode官方指南 ** 第一步：克隆 VSCode 源码首先…...

编程日记 2025/5/6 3:28:07

登录弹窗效果

1，要求点击登录按钮，弹出登录窗口提示1：登录窗口 display:none 隐藏状态； 提示2：登录按钮点击后，触发事件，修改 display:block 显示状态提示3：登录窗口中点击关闭按钮&#xff0…...

编程日记 2025/5/9 11:39:33

wps或office的word接入豆包API(VBA版本)

直接上代码，由于时间匆忙，以后写个详细的教程 #If VBA7 ThenPrivate Declare PtrSafe Function URLDownloadToFile Lib "urlmon" Alias "URLDownloadToFileA" (ByVal pCaller As Long, ByVal szURL As String, ByVal szFileName As…...

编程日记 2025/5/10 8:37:13

深入浅出 Python Logging：从基础到进阶日志管理

在 Python 开发过程中，日志（Logging）是不可或缺的调试和监控工具。合理的日志管理不仅能帮助开发者快速定位问题，还能提供丰富的数据支持，让应用更具可观测性。本文将带你全面了解 Python logging 模块，涵盖…...

编程日记 2025/5/7 20:12:12

系统巡检脚本分享：守护服务器的“健康卫士”

在日常的运维工作中，系统巡检是一项至关重要的任务。它可以帮助我们及时发现服务器的潜在问题，确保系统的稳定运行。今天，我想和大家分享一个实用的系统巡检脚本，它能够帮助我们快速、全面地检查服务器的健康状况。一、为什么需…...

编程日记 2025/4/30 19:41:48

【Elasticsearch】运行时字段（Runtime Fields）索引时定义运行时字段

在 Elasticsearch 中，运行时字段（Runtime Fields）是一种在查询时动态计算的字段，而不是在索引时预先存储的字段。运行时字段为数据处理提供了极大的灵活性，尤其是在处理结构不固定的日志数据或需要动态生成字段值的场景…...

编程日记 2025/5/1 17:23:30

C++从入门到实战（四）C++引用与inline，nullptr

C从入门到实战（四）C引用与inline，nullptr 前言一、C 引用（一）什么是引用（二）引用的特点（三）引用作为函数参数（四）引用作为函数返回值（…...

编程日记 2025/5/6 15:20:00

DeepSeek 助力 Vue 开发：打造丝滑的卡片（Card）

前言：哈喽，大家好，今天给大家分享一篇文章！并提供具体代码帮助大家深入理解，彻底掌握！创作不易，如果能帮助到大家或者给大家一些灵感和启发，欢迎收藏关注哦 💕 目录 Deep…...

编程日记 2025/5/5 15:34:23

Azure Synapse Dedicated SQL Pool统计指定表中各字段的空值、空字符串或零值比例

-- 创建临时表存储结果 CREATE TABLE #Results (DatabaseName NVARCHAR(128),TableName NVARCHAR(128),ColumnName NVARCHAR(128),DataType NVARCHAR(128),NullOrEmptyCount INT,TotalRows INT,Percentage DECIMAL(10,2) );DECLARE db_name SYSNAME DB_NAME(); -- 获取当前数…...

编程日记 2025/5/6 4:46:38

【深度学习】计算机视觉（CV）-目标检测-SSD（Single Shot MultiBox Detector）—— 单次检测多框检测器

🔹 SSD（Single Shot MultiBox Detector）—— 单次检测多框检测器 1️⃣ 什么是 SSD？ SSD (Single Shot MultiBox Detector) 是一种用于目标检测（Object Detection） 的深度学习模型，由 Wei L…...

编程日记 2025/5/3 22:34:39

力扣100. 相同的树（利用分解思想解决）

Problem: 100. 相同的树文章目录题目描述思路Code 题目描述思路题目要求判断两个二叉树是否完全相同，而此要求可以利用问题分解的思想解决，即判断当前节点的左右子树是否完全相同，而在二叉树问题分解的一般题目中均会带有返回值&#xff…...

编程日记 2025/5/7 6:11:08

在SpringBoot服务器端采购上，如何选择操作系统、Cpu、内存和带宽、流量套餐

在Spring Boot服务器端采购时，选择操作系统、CPU、内存、带宽和流量套餐需根据应用需求、预算和性能要求综合考虑。以下是具体建议： 1. 操作系统 Linux发行版（如Ubuntu、CentOS）：适合大多数Spring Boot应用&#xff…...

编程日记 2025/5/9 2:26:10

我的新书《青少年Python趣学编程（微课视频版）》出版了！

🎉 激动人心的时刻来临啦！ 🎉 小伙伴们久等了，我的第一本新书《青少年Python趣学编程（微课视频版）》正式出版啦！ 📚✨ 在这个AI时代，市面上的Python书籍常常过于枯燥&…...

编程日记 2025/5/6 6:37:35

elementUI rules 判断 el-cascader控件修改值未生效

今天修改一个前端项目，增加一个多选字段，使用的是el-cascader控件，因页面是通过引用子页面组件形式使用，出现一个点选后再勾选原有值，输入框内不展示或取消后的也未正常隐藏，如果勾选的值是全新的则其他已选…...

编程日记 2025/5/9 20:22:22

深度学习与人工智能：解锁未来的无限可能

在当今这个科技飞速发展的时代，深度学习和人工智能已不再只是科幻小说中的概念，它们正以惊人的速度渗透到我们生活的方方面面，从智能手机上的语音助手到医疗领域的疾病诊断，从自动驾驶汽车到金融市场的风险预测，其影响…...

编程日记 2025/5/6 15:11:28

pwa应用进阶2-动态加载manifest.json文件

接pwa应用进阶-区分AB面-添加安装按钮而且区分不同的系统和浏览器的各种情况继续优化，主要是让manifest.json文件动态加载。 pwa应用进阶2-动态加载manifest.json文件主要用途如下： 动态切换PWA的清单文件，例如根据不同的语言或者主题加载不…...

编程日记 2025/5/7 10:34:59

UI用例调试_元素能定位到且不在frame内_无法点击/录入文本

关于单据新增，编辑子集信息遇到的2个阻塞点，做记录已供后续参考 1、新增按钮元素能定位，就是无法点击实现效果： 单据新增时，前面单据数据编辑完之后，开始新增证件信息，需要先点击新增按钮。…...

编程日记 2025/5/8 20:02:39

Python的web框架Flask适合哪些具体的应用开发？

Flask 适用的具体应用及实现案例代码 Flask 是一个轻量级的 Web 应用框架，以其简洁性和灵活性而广受欢迎。以下是 Flask 适合的具体应用场景及相关的实现案例代码： 1. 小型网站或博客由于 Flask 的简洁性和易于使用的特性，它非常适合用来搭建个人博客或者小型的企业网站…...

编程日记 2025/5/9 14:24:22

oracle使用动态sql将多层级组织展平

ERP或者其他企业管理软件中都会有一张组织机构表，可以写固定sql的方式将其展平获取组织表中的字段信息，如负责人、上级组织负责人、分管领导、成立时间等。但是这种方式有个缺陷，就是如果只写到处理4个层级，那么后期层级增多就无法…...

编程日记 2025/5/10 4:57:50

vue学习笔记10

ChatGPT & Copilot AI 的认知两个工具 1、ChatGPT 3.5 2、Github Copilot ChatGPT 的基本使用 - Prompt 优化 AI 互动的过程中，容易出现的问题： 1、 AI未能理解问题的核心要点 2、 AI的回答过于宽泛或过于具体 3、 AI提供了错误的信息或…...

编程日记 2025/5/7 21:10:52