尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
深入解析哈希表:从核心原理到动态扩展策略
目录一、hash查询的核心流程二、哈希表的两个核心设计三、装填因子四、静态哈希表1. 线性探测2. Robin Hood哈希3. Cuckoo 哈希五、动态哈希表1. 链式哈希2. 可扩展哈希3. 线性哈希六、几种方法的比较七、哈希表与B树的区别一.hash查询的核心流程键(key)通过哈希函数计算得到哈希值,然后哈希值通过取模运算映射为具体的桶O(1),然后进行桶内查找找到对应的数据1.哈希值:哈希值就是把任意长度的数据通过哈希函数计算后得到的固定长度的输出2.桶:桶就是哈希表中的一个槽位桶的本质二.哈希表的两个核心设计1.哈希函数:负责把任意长度的键转换为整数好的哈希函数的特点:计算速度快;输出分布均匀;尽量减少冲突;相似输入也可以产生差异较大的结果2.哈希方案:哈希值最终要映射到有限的槽位,而不同的键可能映射到相同的位置三.装填因子装填因子 α n / m其中n表中已有的元素总数量m哈希表的总长度影响装填因子越大发生冲突的可能性越高。装填因子越小发生冲突的可能性越低但空间利用率也越低。四.静态哈希表1.线性探测当发生冲突时依次探测下一个位置通常为 H(key)1, H(key)2, ...直到找到空闲位置为止。若探测到表尾则从表首继续探测循环探测。查询也遵循相同过程计算理想位置。从该位置向后检查。找到目标键则成功。遇到真正的空槽则说明不存在。删除问题:不能简单把被删除的位置变为空槽,应该设置删除墓碑缺点:线性探测容易产生连续占用区域,称为聚集,聚集区越长,查询和探测的次数就越多2.Robin Hood哈希它会记录每一个元素距离其理想距离有多远:探测位置 当前位置 - 理想位置插入时如果新元素的探测距离比当前位置元素更大就交换二者距离远的元素获得当前位置距离近的元素继续向后寻找3.Cuckoo 哈希Cuckoo Hashing 为一个键准备多个候选位置通常使用多个哈希函数位置1 h1(key) 位置2 h2(key)如果两个位置都被占用把其中一个旧元素踢出去。新元素占据该位置。被踢出的元素前往自己的另一个候选位置。重复这一过程。例:新键 X 想进入 A 的位置 X 踢走 A A 前往自己的另一个位置 A 又可能踢走 B五,动态哈希表1.链式哈希Chained Hashing 的每个槽位不只存一个元素而是指向一个数据集合优点实现简单容量可以动态增长装载因子可以大于1删除操作比较自然缺点可能产生很长的冲突链指针和额外桶需要更多空间随机内存访问对缓存不友好2.可扩展哈希Extendible Hashing 使用一个目录 Directory:也可说为指针多个桶 Bucket全局深度 Global Depth:决定目录使用哈希值的多少位;若为2,则表示使用2个2进制位,目录有2的平方个入口局部深度 Local Depth:表示某个桶当前依赖多少个哈希位,多个目录项可以指向同一个桶因此局部深度可能小于全局深度。桶满:“桶满”就是指这个桶里存放的数据条目已经达到了它预设的物理容量上限再也塞不进新数据了,若桶满了,怎么处理(1)局部深度小于全局深度分裂这个桶增加它的局部深度调整部分目录指针。(2)局部深度等于全局深度将目录扩大一倍全局深度加1分裂溢出的桶重新分配桶中的元素。3.线性哈希Linear Hashing 不使用可扩展哈希中的显式目录。它维护当前哈希层级一个分裂指针两组不同范围的哈希函数。例:h₀(key) hash(key) mod N h₁(key) hash(key) mod 2N桶按照固定次序逐个分裂,每次分裂分裂指针指向一个旧桶创建一个新桶使用更高层哈希函数重新分配该桶的数据分裂指针前进一步一轮分裂完成后进入下一个层级。优点不需要大型目录渐进式扩容避免一次性重建整张表缺点查询逻辑比普通哈希复杂在扩张期间不同桶可能使用不同层级的哈希函数可能需要临时溢出页六.几种方法的比较七.哈希表与B树的区别附.
RELATED

相关推荐

固态继电器(SSR)原理、选型与应用实战指南

固态继电器(SSR)原理、选型与应用实战指南

1. 项目概述:从“咔哒”声到静默革命 如果你拆开过家里的老式空调或者工业控制柜,大概率见过一种会发出清脆“咔哒”声的黑色方块——电磁继电器。它通过线圈通电产生磁力,吸合机械触点来完成电路的接通与断开,是自动化控制领域几…

📅 2026/9/10 12:40:36
Unity异步编程实战:从协程到async/await的性能优化与避坑指南

Unity异步编程实战:从协程到async/await的性能优化与避坑指南

1. 项目概述:为什么Unity开发者必须掌握async/await?如果你在Unity开发中遇到过界面卡死、加载场景时游戏完全冻结,或者试图在协程里处理复杂的状态逻辑时把自己绕晕,那么你正站在异步编程的大门前。async/await这套语法糖&#x…

📅 2026/9/11 19:27:47
3分钟极速上手:用XUnity.AutoTranslator让外语游戏秒变中文版

3分钟极速上手:用XUnity.AutoTranslator让外语游戏秒变中文版

3分钟极速上手:用XUnity.AutoTranslator让外语游戏秒变中文版 【免费下载链接】XUnity.AutoTranslator 项目地址: https://gitcode.com/gh_mirrors/xu/XUnity.AutoTranslator 还在为看不懂的外语游戏而烦恼吗?面对日文、韩文或英文的游戏界面和对…

📅 2026/9/22 7:56:11
MORE NEWS

更多资讯

📰

OpenFeign自定义Encoder/Decoder:从JSON到XML、Protobuf与私有协议

刚开始接触 OpenFeign 的时候,我一直觉得它就是个 JSON 客户端:“定义接口、贴注解、注入依赖、调方法”,剩下的交给 Spring Cloud 魔法去处理。直到我被一个对接老系统 XML 接口的需求逼到墙角,才发现这个认知有多坑:…

📰

Context Menu Manager Plus 详细编辑功能完整指南:精细管理 7-Zip、Bandizip 等软件的右键菜单选项

Context Menu Manager Plus 详细编辑功能完整指南:精细管理 7-Zip、Bandizip 等软件的右键菜单选项 【免费下载链接】ContextMenuMgr Context Menu Manager Plus 是一个强大的实用程序,它可帮助您管理 Windows 上的右键菜单,并避免第三方向你…

📰

Python图片转Base64:PIL与base64完整实践指南

先说我平时处理得最多的一件事:网页里内嵌小图标。以前要么外链一张图片文件,多一次HTTP请求;要么把图片以二进制形式硬编码到代码里,维护起来都是麻烦。后来发现直接用一串以data:image/png;base64,开头的文本就能把整张图塞进HT…

📰

C++符号混淆实战:从名字泄露到二进制加固

1. 符号与名字:为什么C项目的“名字”会暴露信息1.1 C的符号是怎么进到二进制里的C符号混淆技术,说白了就是围绕“名字”做文章。许多人在写C项目时,脑子里装的是算法、类结构、内存管理,很少想到等编译链接完成之后,你…

📰

拒绝拖延:一文搞懂规则网站建设技术栈选型

拒绝拖延:一文搞懂规则网站建设技术栈选型 改个需求建站公司拖一周,这种憋屈事你是不是也干过?明明只是改个导航栏颜色,对方却以“排期太满”为由,让你再等三天。别怪对方,怪只怪你当初没把底层架构和规则引擎选对。很多新手入行做网站,上来就找外包,…

📰

FDE现场部署工程师崛起:AI时代方案落地的关键工程岗

最近被问得最多的一个词,就是FDE。年前刷招聘软件,满屏都是“FDE解决方案工程师(高级)”“FDE部署工程师”;年后再看热搜,腾讯FDE课程、FDE证书、FDE工程师学习路线已经铺天盖地。很多朋友的第一反应都一样…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬