哈希表HashMap数据结构全解析从哈希码、桶、冲突处理到从零实现【免费下载链接】curriculumThe open curriculum for learning web development项目地址: https://gitcode.com/GitHub_Trending/cu/curriculum本篇技术指南以本仓库中 hash_map_data_structure.md 为核心脉络系统讲解哈希表Hash Map / Hash Table这一编程语言中最常用数据结构之一的内部工作原理什么是哈希码、桶Bucket与键值对如何存取、冲突Collision为何必然发生以及如何用链表和质数哈希缓解、容量与负载因子Load Factor如何驱动扩容。在理解原理之后你还将结合本仓库配套的 project_hash_map.md 实战指南用 JavaScript 从零实现一个具备hash、set、get、has、remove、keys等完整方法的HashMap类并亲手验证其扩容与均匀分布行为。哈希码Hash Code什么是哈希哈希Hashing的本质是把一个输入值转换成对应的输出值。这个输出值就叫哈希码。哈希函数必须是一个纯函数pure function相同的输入永远产生相同的哈希码过程中不掺杂任何随机成分。以文档中的第一个例子为例一个最简单的哈希函数可以只取姓名的首字母function hash(name) { return name.charAt(0); }把Carlos传入得到哈希码C。这就是一个基础哈希函数。哈希与加密的关键区别不可逆哈希和加密ciphering之间有一条根本分界线可逆性。哈希是单向过程——你可以从姓名得到哈希码却永远无法从哈希码还原出原始姓名。Carlos哈希成C之后你无法断定它原来究竟是Carlos、Carla还是Carrot。正是这种不可逆性让哈希天然适合安全场景见下方哈希的收益对于密码我们可以只保存密码的哈希值而不是明文即使攻击者窃取了哈希数据也无法据此还原出原始密码。使用场景从按首字母归档到数值哈希文档用学校归档的类比来解释哈希的用途一个文件夹系统按姓名首字母组织每个子文件夹存放同首字母学生的档案C: carlos.txt carla.txt B: bryan.txt bob.txt beatrice.txt bella.txt benjamin.txt bianca.txt新来一位名叫Carlos的学生时运行hash(Carlos) - C就能确定他该放入C目录。但这个方案立刻暴露一个问题如果姓 C 开头的人特别多C目录会严重膨胀而其他目录可能空空如也。为了更均匀地分散学生可以改进哈希函数同时纳入名和姓的首字母function hash(name, surname) { return name.charAt(0) surname.charAt(0); }此时Carlos Smith的哈希码是CS学生被分散到更多目录中重复哈希码大量减少但仅靠首字母组合仍然不够——常见姓氏首字母组合仍会造成目录失衡。于是文档进一步把整个名字转换成数字function stringToNumber(string) { let hashCode 0; for (let i 0; i string.length; i) { hashCode string.charCodeAt(i); } return hashCode; } function hash(name, surname) { return stringToNumber(name) stringToNumber(surname); }这里不再只看首字母而是把整个名字的每个字符码值累加为数字。你可能会问为什么不直接把整个名字当作哈希码那样确实能保证唯一但在哈希表的语境下哈希码必须是数字——这个数字将作为桶的索引用来定位键值对的存储位置。桶Bucket哈希表如何存取键值对桶是存储元素的容器。可以把数组的每个下标都视为一个桶。对于某个具体的键哈希函数返回一个数字作为数组下标键值对就存储在该下标对应的桶中。以存储键Fred、值Smith为例文档给出了完整流程将Fred传入哈希函数得到哈希码385找到下标为385的桶把键值对存入该桶键是Fred值是Smith。如果下标385的桶里已经有一个键同为Fred的条目则比较键是否相同相同则用新值覆盖旧值。这正是Set能保证元素唯一的原因——Set与哈希表类似只不过它的节点只含键、不含值。按键取值时流程同样清晰哈希键并计算出它的桶下标如果桶不为空则进入该桶比较桶内节点的键是否与查询键一致一致则返回节点值否则返回null。为什么已经通过哈希码定位到桶还要再比较键因为哈希码只是位置不同的键可能生成相同的哈希码即碰撞所以必须用键来确认桶内的条目是否就是要找的那个。基于这套机制一个最简哈希表只需实现has、set、get三个方法即可工作。注意哈希表不保证插入顺序哈希表在迭代时不保证插入顺序。哈希码到下标之间的映射并非从第一个下标到最后一个下标的线性推进而是不可预测的与插入次序无关。也就是说如果你取出全部键或值来迭代它们的顺序不会是你插入的顺序。例如依次插入Mao、Zach、Xari迭代时却可能得到[Zach, Mao, Xari]。某些库如 JavaScript 原生的Map会实现为保留插入顺序但本仓库后续项目实现的是无序哈希表。如果你需要频繁地按顺序迭代数组才是更合适的选择。碰撞Collision哈希表无法回避的问题碰撞指两个不同的键生成了完全相同的哈希码从而落在同一个桶中。例如Sara和raSa由相同字母不同排列组成用简单的字符码累加会得到相同结果。解决办法是重写stringToNumber让哈希码依赖字母在字符串中的位置function stringToNumber(string) { let hashCode 0; const primeNumber 31; for (let i 0; i string.length; i) { hashCode primeNumber * hashCode string.charCodeAt(i); } return hashCode; }新的函数让Sara与raSa产生不同哈希码虽然字母相同但位置不同每次迭代都用旧哈希乘以 31 再加上当前字符码位置信息被放进了哈希码。为什么要用质数Prime Number作乘数注意这里选用了质数31。我们本可以选任何数字但质数更优乘以质数会降低哈希码能被桶数量整除的可能性从而帮助减少碰撞的发生。这是哈希函数设计中一个广为人知的工程经验。碰撞无法彻底消除即使重写了哈希函数碰撞仍无法根除——桶的数量是有限的而键可以是无穷的。所以我们只能尽量最小化碰撞而非消除碰撞。当节点数超过桶数时碰撞在数学上是被保证的即鸽笼原理。用链表处理碰撞到这一步为止哈希表还只是一维的数据结构。处理碰撞的思路是让每个桶里的Node能存多个值——引入链表Linked List。每个桶都变成一条链表插入时若桶为空则插入链表头节点若桶中已有头节点则沿链表追加到末尾。至此你应该明白为什么要写一个尽可能消除碰撞的哈希函数。实际开发中绝大多数语言都内置了哈希函数很少需要自己编写但理解其原理仍然至关重要。链表的基础概念与操作可参考本仓库的 project_linked_lists.md链表是由节点node通过指针串联的线性集合头节点head是第一个节点尾节点tail是最后一个节点。哈希表的增长Growth容量与负载因子桶的数量不能无限大内存有限但也不能一开始就开太大若哈希表里只有一条数据纯属浪费。文档给出的折中方案是从一个大小为16的小数组开始。为什么是16因为它是 2 的幂可以配合某些依赖位运算bit manipulation的索引性能优化技巧。大多数编程语言默认桶数就是16。用取模把大哈希码压缩进桶范围哈希函数可能产生像20353924这样的大数字如何映射到桶答案是取模运算%任意数字对16取模结果必在0到15之间。例如要确定值Manon落入哪个桶随着节点不断插入碰撞概率持续上升当节点数超过桶数时碰撞必然发生。理想状态下每个桶要么 0 个节点要么 1 个节点因此当负载变高时需要把桶数组扩大一倍并将所有已有节点重新哈希后复制到新数组的桶中。何时扩容capacity × load factor哈希表需要跟踪两个字段来决定扩容时机capacity容量当前桶的总数load factor负载因子初始化时分配给哈希表的数值用于判定扩容时机。不同语言实现通常取值在0.75到1之间。两者的乘积就是一个阈值当哈希表中的条目数超过该乘积时触发扩容。例如有16个桶、负载因子0.8则阈值是16 * 0.8 12.8——第13个条目插入时就要扩容。负载因子设得太低会因空桶过多而浪费内存设得太高则会在扩容前允许桶内累积大量碰撞。这是一个典型的空间-时间权衡。计算复杂度Computation Complexity哈希表在插入、检索、删除上都极其高效因为这三个操作都直接借助数组下标完成。假设实现良好以下方法平均复杂度为O(1)插入Insertion检索Retrieval删除Removal最坏情况下上述操作退化为O(n)当所有数据都被哈希到同一个桶时复杂度来自链表——需要遍历链表才能把又一个节点插入同一个桶这正是碰撞造成的。哈希表的扩容growth则始终是O(n)因为要重新哈希并复制全部节点。实战用 JavaScript 从零实现自己的 HashMap理解了全部原理之后本仓库的配套项目 project_hash_map.md 要求你亲手实现一个HashMap。以下是该项目的核心约束与设计要点。边界限制阻止越界访问JavaScript 数组的动态性允许读写超出数组长度的下标——例如创建大小为16的桶数组后依然可以往下标500存入数据。这破坏了哈希表限制存储规模的设计初衷因此每次通过下标访问桶时都应加上边界检查if (index 0 || index buckets.length) { throw new Error(Trying to access index out of bounds); }类结构与方法清单创建HashMap类或工厂函数至少维护load factor与capacity两个变量load factor取0.75初始capacity为16。需要实现的方法如下hash(key)接收字符串键并生成哈希码。文档提供了此前课程中实现的较优版本function hash(key) { let hashCode 0; const primeNumber 31; for (let i 0; i key.length; i) { hashCode primeNumber * hashCode key.charCodeAt(i); } return hashCode; }你可以直接使用它也可以自行研究其他哈希算法这是一个很深的领域。要点如下返回前必须用%对哈希码取当前容量的模确保下标始终落在桶数组范围内无论后续如何扩容长键风险键很长时累乘可能超过Number.MAX_SAFE_INTEGER导致计算失真。稳妥做法是在循环的每一次迭代内就对当前容量取模而不是等循环结束后只取一次模键与哈希码不要混淆键只是hash函数的输入我们从不直接用键访问桶而是始终通过哈希码访问。set(key, value)接收键与值两个参数。若键已存在则覆盖旧值视为更新。注意区分更新与碰撞Rama和Sita哈希后都落在下标3因为键不同这是碰撞而非更新。碰撞处理参照上文用链表处理碰撞一节。扩容逻辑与set紧密相关——应在桶被填满达到负载因子时正好触发扩容因此建议把扩容功能放在较后实现但要意识到它由set驱动。get(key)接收键返回其对应的值键不存在则返回null。has(key)接收键返回true或false表示键是否存在于哈希表中。remove(key)接收键若键存在则删除该条目并返回true不存在则返回false。length()返回哈希表中已存储键的数量。clear()清空哈希表中的所有条目。keys()返回包含全部键的数组。values()返回包含全部值的数组。entries()返回包含每个key, value对的数组形如[[firstKey, firstValue], [secondKey, secondValue]]。再次提醒哈希表不保留插入顺序keys()、values()、entries()的结果乱序是正常且符合预期的。验证你的实现触发扩容并检查均匀分布项目文档给出了完整的验证脚本。创建一个 JavaScript 文件实例化哈希表负载因子0.75const test new HashMap() // or HashMap() if using a factory依次用set填充 12 个条目test.set(apple, red) test.set(banana, yellow) test.set(carrot, orange) test.set(dog, brown) test.set(elephant, gray) test.set(frog, green) test.set(grape, purple) test.set(hat, black) test.set(ice cream, white) test.set(jacket, blue) test.set(kite, pink) test.set(lion, golden)此时负载水平恰好达到0.75满容量。接下来用set覆盖若干节点的值——这只应更新已有节点的值而不新增节点因此length()不变、capacity不变。随后插入最后一个节点test.set(moon, silver)这会令负载超过负载因子触发扩容capacity翻倍。若实现正确扩容后负载水平应远低于负载因子且条目在扩容后的桶中均匀分布。最后再覆盖几个节点的值仍只更新不新增并逐一测试get、has、remove、length、clear、keys、values、entries在扩容后是否依然工作正常。额外挑战Extra Credit实现一个HashSet类或工厂函数行为与HashMap一致但只含键、不含值。小结与知识自检通过本文你已经掌握了哈希表的完整知识链条哈希码的生成与不可逆性 → 桶的下标定位与键值对存取 → 碰撞的成因鸽笼原理保证必然存在与链表达化解法 → 质数乘数对分布的改善 → 容量与负载因子驱动的 O(n) 扩容 → 平均 O(1)、最坏 O(n) 的复杂度画像并能够参照本仓库的 project_hash_map.md 从零实现一个功能完整的HashMap。理解哈希函数工作原理远比记住某个语言的现成 API 更重要——它是你日后评估各种哈希类数据结构Map、Set、对象字面量性能与行为的基础。你可以用下面四个问题检验自己的理解哈希hash意味着什么什么是桶buckets什么是碰撞collision何时是扩容桶数组的最佳时机【免费下载链接】curriculumThe open curriculum for learning web development项目地址: https://gitcode.com/GitHub_Trending/cu/curriculum创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考