C#面试常考随笔11:Dictionary<K, V>、Hashtable的内部实现原理是什么?效率如何?
Dictionary<K, V>
- 底层数据结构:使用哈希表(Hash Table),由一个数组和链表(或在.NET Core 2.1 及之后版本中,当链表长度达到一定阈值时转换为红黑树)组成。数组中的每个元素称为一个桶(Bucket),用于存储键值对。
- 工作原理:添加键值对时,先计算键(Key)的哈希码,通过哈希码对数组长度取模,得到对应的桶索引。若该桶为空,直接将键值对存入;若不为空(即发生哈希冲突),则以链表(或红黑树)的形式将新的键值对添加到该桶的链表(或红黑树)中。查找元素时,先计算键的哈希码定位到桶,然后在桶内的链表(或红黑树)中通过键的比较(调用
Equals方法)找到对应的值。
Hashtable
- 底层数据结构:同样基于哈希表实现,由数组和链表构成。数组中的每个元素是一个桶,用于存储键值对。
- 工作原理:添加键值对时,计算键的哈希码,对数组长度取模确定桶索引。若桶为空,直接存入键值对;若桶已有元素(哈希冲突),则将新键值对添加到该桶的链表中。查找元素时,先计算键的哈希码定位桶,再在桶内链表中通过键的比较(调用
Equals方法)获取对应的值。与Dictionary<K, V>不同的是,Hashtable是线程安全的,因为其方法实现中添加了synchronized关键字(在多线程环境下可确保线程同步,但性能相对Dictionary<K, V>较低),并且Hashtable的键和值都是object类型,存储和获取时可能需要类型转换,存在装箱和拆箱操作。
查找效率
- 理想情况:二者在理想情况下查找效率都较高。它们内部都基于哈希表结构,通过计算键的哈希码来定位存储位置。在没有哈希冲突(即不同键计算出的哈希码对应到哈希表中的不同位置)时,查找操作可以在接近常数时间(O (1))内完成,即能快速定位到目标键值对。
- 存在哈希冲突时:
- Hashtable:当发生哈希冲突,同一桶中存在多个键值对(以链表形式存储)时,查找时需要在链表中顺序比较键。如果哈希冲突严重,链表较长,查找效率会降低,时间复杂度可能退化为 O (n),n 为链表长度。不过,由于其内部实现对哈希函数等进行了优化,在一般情况下能较好地分散哈希值,减少冲突。
- Dictionary<K, V> :在.NET Core 2.1 之前,处理哈希冲突与
Hashtable类似,通过链表存储冲突的键值对,冲突严重时查找效率受链表长度影响。在.NET Core 2.1 及之后版本中,当链表长度达到一定阈值(通常为 8 )时,会将链表转换为红黑树。红黑树是一种自平衡的二叉搜索树,查找操作的时间复杂度为 O (log n),相比于长链表的 O (n),在冲突较多时能提供更稳定和高效的查找性能。
相关文章:
C#面试常考随笔11:Dictionary<K, V>、Hashtable的内部实现原理是什么?效率如何?
Dictionary<K, V> 底层数据结构:使用哈希表(Hash Table),由一个数组和链表(或在.NET Core 2.1 及之后版本中,当链表长度达到一定阈值时转换为红黑树)组成。数组中的每个元素称为一个桶&a…...
Linux防火墙基础
一、Linux防火墙的状态机制 1.iptables是可以配置有状态的防火墙,其有状态的特点是能够指定并记住发送或者接收信息包所建立的连接状态,其一共有四种状态,分别为established invalid new related。 established:该信息包已建立连接&#x…...
Qt u盘自动升级软件
Qt u盘自动升级软件 Chapter1 Qt u盘自动升级软件u盘自动升级软件思路:step1. 获取U盘 判断U盘名字是否正确, 升级文件是否存在。step2. 升级step3. 升级界面 Chapter2 Qt 嵌入式设备应用程序,通过U盘升级的一种思路Chapter3 在开发板上运行的…...
【Conda 和 虚拟环境详细指南】
Conda 和 虚拟环境的详细指南 什么是 Conda? Conda 是一个开源的包管理和环境管理系统,支持多种编程语言(如Python、R等),最初由Continuum Analytics开发。 主要功能: 包管理:安装、更新、删…...
Python递归函数深度解析:从原理到实战
Python递归函数深度解析:从原理到实战 递归是计算机科学中重要的编程范式,也是算法设计的核心思想之一。本文将通过20实战案例,带你深入理解Python递归函数的精髓,掌握递归算法的实现技巧。 一、递归函数核心原理 1.1 递归三要…...
OpenGL学习笔记(五):Textures 纹理
文章目录 纹理坐标纹理环绕方式纹理过滤——处理纹理分辨率低的情况多级渐远纹理Mipmap——处理纹理分辨率高的情况加载与创建纹理 ( <stb_image.h> )生成纹理应用纹理纹理单元练习1练习2练习3练习4 通过上一篇着色部分的学习,我们可以…...
【TypeScript】基础:数据类型
文章目录 TypeScript一、简介二、类型声明三、数据类型anyunknownnervervoidobjecttupleenumType一些特殊情况 TypeScript 是JavaScript的超集,代码量比JavaScript复杂、繁多;但是结构更清晰 一、简介 为什么需要TypeScript? JavaScript的…...
Notepad++消除生成bak文件
设置(T) ⇒ 首选项... ⇒ 备份 ⇒ 勾选 "禁用" 勾选禁用 就不会再生成bak文件了 notepad怎么修改字符集编码格式为gbk 如图所示...
Android NDK
Android NDK环境 D:\Android SDK\ndk\25.2.9519653 使用clang而不用gcc D:\Android SDK\ndk\25.1.8937393\toolchains\llvm\prebuilt\windows-x86_64\bin\clang --version 查看是否安装成功clang ptrace 在 C 语言中,ptrace 已经被 Linux 内核实现࿰…...
内部知识库助力组织智力激发与信息共享实现业绩增长
内容概要 内部知识库是企业知识管理的核心组件,具有不可估量的重要性。通过构建有效的知识库,组织能够将孤立的知识和信息整合成为一个系统性的体,极大提高员工访问和利用这些信息的能力。这不仅简化了决策过程,还通过减少重复劳…...
通过F12收集的信息
按 F12 键打开浏览器的开发者工具(DevTools)可以获取部分操作系统和中间件信息,但能力有限。以下是具体说明: 一、通过 F12 收集的信息 1. 客户端操作系统信息 - Console 控制台 通过 JavaScript 直接获取客户端操作系统信息&am…...
用Python替代OpenMV IDE显示openmv USB 图像
原理是利用openmv的usb模仿串口,然后用Python代码打开串口接收 能替代openmv ide 跑48帧图像 Python端需要的依赖: 需要的是: from ultralytics import YOLO import cv2 import numpy as np from serial import Serial import time from co…...
c语言:编译和链接(详解)
前言 要将编译和链接,就不得不提及编译器是如何运作的,虽然这部分知识是针对于要创造编译器和创作语言的人所需要清楚的,但作为c语言的学习者也需要了解一下,修炼内功,尤其是对于想学习c的人而言。 编译器的运作过程…...
数据结构【单链表操作大全详解】【c语言版】(只有输入输出为了方便用的c++)
单链表操作的C/C实现详解 在数据结构中,单链表是一种非常基础且重要的数据结构。它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。今天我们就来深入探讨用C/C实现的单链表及其各种操作。 一、单链表的定义 const int N 1e5; //单链表 t…...
leetcode27.删除有序数组中的重复项
目录 问题描述判题标准示例提示 具体思路思路一思路二 代码实现 问题描述 给你一个非严格递增排列的数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。元素的相对顺序应该保持一致 。然后返回nums中唯一元…...
[c语言日寄]越界访问:意外的死循环
【作者主页】siy2333 【专栏介绍】⌈c语言日寄⌋:这是一个专注于C语言刷题的专栏,精选题目,搭配详细题解、拓展算法。从基础语法到复杂算法,题目涉及的知识点全面覆盖,助力你系统提升。无论你是初学者,还是…...
【c++11】包装器
🔥个人主页:Quitecoder 🔥专栏:c笔记仓 包装器(Wrapper) 是一个常见的编程设计模式,通常用于封装或“包装”某个现有的对象、函数、数据结构或者操作,以提供额外的功能或简化接口。…...
信息学奥赛一本通 1422:【例题1】活动安排
【题目链接】 ybt 1422:【例题1】活动安排 【题目考点】 1. 贪心 【解题思路】 该题属于区间选点问题,ybt 1324:【例6.6】整数区间 是给定一些区间,选择一些点使得每个区间范围内至少有1个点。 本题为:给定一些区…...
数据库、数据仓库、数据湖有什么不同
数据库、数据仓库和数据湖是三种不同的数据存储和管理技术,它们在用途、设计目标、数据处理方式以及适用场景上存在显著差异。以下将从多个角度详细说明它们之间的区别: 1. 数据结构与存储方式 数据库: 数据库主要用于存储结构化的数据&…...
llama.cpp LLM_CHAT_TEMPLATE_DEEPSEEK_3
llama.cpp LLM_CHAT_TEMPLATE_DEEPSEEK_3 1. LLAMA_VOCAB_PRE_TYPE_DEEPSEEK3_LLM2. static const std::map<std::string, llm_chat_template> LLM_CHAT_TEMPLATES3. LLM_CHAT_TEMPLATE_DEEPSEEK_3References 不宜吹捧中国大语言模型的同时,又去贬低美国大语言…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
