《Hello 算法》哈希章节总结哈希表 O(1) 查找原理、碰撞处理与哈希算法设计要点【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo哈希表是本仓库《Hello 算法》数据结构与算法课程中“哈希”一章的核心主题。本文基于俄文版章节总结 ru/docs/chapter_hashing/summary.md 整理成一篇可独立阅读的技术总览并结合 hash_map.md、hash_collision.md、hash_algorithm.md 三篇正文以及仓库内可运行的示例代码系统梳理哈希表为何能做到 $O(1)$ 查找、哈希碰撞为何不可避免、如何用链式地址与开放寻址化解碰撞以及工程实践中哈希算法需要满足哪些性质。读完本文你将能够完整复述“哈希表→哈希函数→哈希碰撞→扩容与负载因子→哈希算法设计”这一条知识主线并用仓库提供的多语言示例代码如 Python 的hash_map.py、hash_map_chaining.py验证每一个结论。一、核心结论速览哈希表为什么是 $O(1)$哈希表hash table也叫散列表其本质是建立起“键key”与“值value”之间的映射关系只要把key传入哈希表就能在 $O(1)$ 时间内取回对应的value。要理解这一结论需要先接受三个事实复杂度对照普通数组与链表在“查找”“删除”上都是 $O(n)$必须遍历只有“尾部追加”是 $O(1)$而哈希表的查找、插入、删除均为 $O(1)$。下表直接摘自正文 hash_map.md操作数组链表哈希表查找元素$O(n)$$O(n)$$O(1)$添加元素$O(1)$$O(1)$$O(1)$删除元素$O(n)$$O(n)$$O(1)$典型操作集合哈希表的常见操作包括——查询value、添加键值对、删除键值对以及遍历哈希表遍历键值对、只遍历键、只遍历值三种方式。这些代码在仓库中都有可运行的多语言示例例如 Python 版 hash_map.py 演示了hmap[key] value添加、hmap[key]查询、hmap.pop(key)删除以及.items()/.keys()/.values()三种遍历。一句口诀哈希表以“空间换时间”——它通常比数组、链表更快但代价是大量桶bucket处于空闲状态、内存利用率偏低详见后文 QA 中“为何比数组、链表快”的讨论。二、哈希函数key 到桶的映射1. 工作流程在哈希表中数组的每个空位称为一个桶bucket每个桶存放一对键值对。给定key后如何找到它的桶答案是哈希函数。哈希函数的作用是把“很大的输入空间”映射到“较小的输出空间”其计算过程分为两步用某个哈希算法hash()计算key的哈希值将哈希值对桶的数量即数组长度capacity取模得到桶下标index hash(key) % capacity正文用“学生证号 → 姓名”的例子做了直观说明设capacity 100、hash(key) key则哈希函数退化为key % 100。2. 哈希碰撞不可避免由于输入空间所有可能的key远大于输出空间数组下标“多个输入对应同一个输出”在理论上必然存在即哈希碰撞hash collision无法从原理上根除。还是以key % 100为例12836 % 100 36 20336 % 100 36两个不同的学生证号映射到了同一个桶就会产生错误查询结果。3. 极简实现的源码佐证仓库中的 array_hash_map.py 用 100 个桶的数组实现了一个最朴素的哈希表hash_func()返回key % 100get()/put()/remove()分别对应查询、插入覆盖、删除并将键值对封装为Pair类。它没有任何碰撞处理逻辑恰好可以用来观察“碰撞产生错误结果”的最坏形态。三、缓解碰撞的两条路线扩容与负载因子面对碰撞有两类手段改进哈希表内部结构让它在发生碰撞时仍能正确工作见第四节仅当碰撞严重时才扩容控制碰撞发生的概率。为什么扩容能减少碰撞因为哈希函数的最后一步通常是“对数组长度取模”。扩容使长度n改变同一key的桶下标随之改变原先挤在同一桶里的多个key可能被分散到不同桶中碰撞自然被削弱正文 hash_map.md 中用键值对(136, A)与(236, D)在扩容前后从冲突变不冲突的示意图说明这一点。但扩容的成本很高和数组扩容一样需要把全部键值对迁移到新表而且由于capacity变了每个键值对都要用哈希函数重新计算存储位置计算开销随之叠加。因此编程语言通常预先分配足够大的容量以避免频繁扩容。**负载因子load factor**是这里的关键指标定义为“哈希表中元素个数 ÷ 桶的数量”用于评估碰撞的严重程度也常被用作扩容的触发条件。以文档中给出的 Java 为例当负载因子超过 $0.75$ 时系统会把哈希表扩容为原来的 $2$ 倍。四、碰撞处理的两大流派1. 链式地址separate chaining链式地址把“单个元素”升级为“链表”发生冲突的键值对按链表节点形式挂在同一个桶下。查找经哈希函数定位到桶后遍历该链表、逐个比较key找到目标键值对添加定位到链表头后把新节点追加进链表删除遍历链表、定位目标节点后摘除。其代价一是链表指针带来的额外内存二是查找需要线性遍历链表。当链表过长时查找退化为 $O(n)$——此时可以把链表进一步改造成 AVL 树或红黑树把查找复杂度优化回 $O(\log n)$Java 的HashMap正是这一思路的工业实现。仓库中的 hash_map_chaining.py 给出了完整实现初始容量capacity 4负载因子阈值load_thres 2/3扩容倍率extend_ratio 2put()每次先检查load_factor() load_thres再决定是否调用extend()extend()中新建容量翻倍的桶数组并逐对重插所有键值对。这份代码是“扩容 链式地址”思想最直接的落地范本。2. 开放寻址open addressing开放寻址不引入额外数据结构而是通过“反复探测probing”寻找空桶。常见三种变体线性探测以固定步长通常为 1顺序向后探测。插入时遇到被占用的桶就向后走直到找到空桶查找时若发生碰撞同样按步长前进遇到空桶则说明元素不存在。二次探测探测距离取“尝试次数的平方”即 $1, 4, 9, \dots$。它比线性探测更能缓解“聚集”但因为平方增长过快可能无法覆盖整个哈希表——即使存在空桶也不一定探测得到。再哈希双散列准备多个哈希函数 $f_1(x), f_2(x), f_3(x), \dots$插入时依次尝试找到空位为止查找按同样顺序进行。它比线性探测更不易聚集但多个函数的计算带来额外开销。开放寻址有一个通病不能直接删除元素。直接置空会在数组中留下空位而线性探测查找遇到空位就会提前终止导致其后本应存在的元素被误判为“不存在”。业界解决方案是惰性删除lazy deletion不真正删除而是把该桶标记为特殊常量TOMBSTONE。None与TOMBSTONE都可用于放置新键值对但区别在于线性探测遇到TOMBSTONE时必须继续向后探测其后可能还有键值对。惰性删除的副作用是性能退化——每删除一次就多一个墓碑探测链条越来越长。优化的做法是在查找过程中记住第一个TOMBSTONE的位置找到目标元素后把目标与其交换让元素尽可能回到“理想探测起点”附近同时把整个数组当作环形结构处理越界后回到开头继续探测。仓库中 hash_map_open_addressing.py 正是这样一套“线性探测 惰性删除 环形数组”的完整实现。3. 不同语言的不同选择编程语言对哈希表的实现策略并不一致正文 hash_collision.md 举例说明了三种代表性选择Pythondict使用开放寻址探测时结合伪随机数JavaHashMap使用链式地址从 JDK 1.8 起当内部数组长度达到 64 且链表长度达到 8 时链表会转换为红黑树以维持查找性能Go同样使用链式地址但规定每个桶最多存放 8 对键值对溢出时挂接 overflow 桶当溢出桶过多时执行同规模的专门扩容。五、哈希算法决定碰撞概率的上游因素1. 三个基本目标链式地址和开放寻址都只能让哈希表“在碰撞发生后仍能工作”并不能降低碰撞发生的概率。真正决定键值对分布的是哈希函数——在容量capacity固定的情况下index hash(key) % capacity中的分布特性完全由hash()决定。因此哈希算法应满足确定性相同输入永远得到相同输出否则哈希表不可靠高效率哈希值计算要足够快计算成本越低哈希表的实用价值越高均匀分布尽量把键值对均匀摊到各桶分布越均匀碰撞概率越低。2. 加密场景的额外要求当哈希用于密码存储、数据完整性校验等安全场景时还必须满足更严格的性质单向性无法从哈希值反推输入的任何信息抗碰撞性极难找到两个不同输入共享同一哈希值雪崩效应输入微小变化应引起输出显著且不可预测的变化。需要注意“均匀分布”与“抗碰撞”是两个独立概念key % 100对随机输入可以分布得很均匀但它太简单容易被反向构造出碰撞输入无法承担安全职责。3. 几种朴素哈希算法正文与源码 simple_hash.py 给出四种入门级字符串哈希加法哈希累加所有字符的 ASCII 码乘法哈希每次把当前值乘以常数如 31再加下一个字符的 ASCII 码XOR 哈希用异或运算把各字符累积进哈希值旋转哈希每次累积前先对哈希值做循环移位如hash (hash 4) ^ (hash 28) ^ ord(c)。这四种算法都软弱可欺加法和 XOR 满足交换律因而加法哈希与 XOR 哈希无法区分“相同字符、不同排列”的字符串容易诱发碰撞甚至安全问题只能用于对安全性要求不高的场景。4. 为什么取模要用大素数细心观察会发现上述每个算法的最后一步都是对大素数 $1000000007$取模目的是把哈希值控制在合理范围内。为什么要强调素数结论是用大素数作模数能最大限度保证哈希值分布均匀因为素数与其他数没有公因子能削弱取余运算带来的周期性规律、降低碰撞。正文用算例对比了这一点。取合数 $9$ 作模数时它含有因子 $3$所有能被 $3$ 整除的key只会落到 $0, 3, 6$ 三个哈希值上周期性输入下必然聚集换成素数 $13$ 后key序列 ${0,3,6,9,12,15,\dots}$ 的哈希值变成 ${0,3,6,9,12,2,5,8,11,1,4,7,\dots}$分布立刻均匀起来。当然如果输入本身是均匀随机的合数模数影响不大可一旦输入存在周期性合数模数就很容易导致聚集。因此实践中习惯取较大的素数作为模数。5. 主流哈希算法一览工程上真正使用的是 MD5、SHA-1、SHA-2、SHA-3 这类把任意长度输入映射为定长哈希值的标准算法。正文 hash_algorithm.md 给出的对照如下MD5SHA-1SHA-2SHA-3诞生年份1992199520022008输出长度128 bit160 bit256/512 bit224/256/384/512 bit碰撞情况频繁频繁罕见罕见安全等级低已被成功攻破低已被成功攻破高高典型用途已过时仍偶用于数据完整性校验已过时加密货币交易校验、数字签名等可作 SHA-2 的替代一个容易被误解的表述哈希算法常在“取模”之外另有以自身结果直接参与运算的朴素场景但标准哈希算法并不局限于取模结构——它们通过内部轮函数把定长状态反复混淆扩散实现雪崩效应。6. 数据类型的哈希与“只可哈希不可变对象”语言的key可以是整数、浮点数、字符串等多种类型运行时通常为这些类型内置了哈希算法用于计算桶下标。以 Python 为例其内建hash()的行为示例代码见 built_in_hash.py整数与布尔值的哈希值等于其自身True为 1浮点数与字符串的哈希计算较复杂元组按元素逐个哈希后再合并成最终值对象默认按内存地址构造哈希值若重写哈希方法则可改为按内容计算。这里还有一个关键限制哈希表只允许把不可变对象用作key。若用列表这种可变对象当key一旦内容改变其哈希值也随之改变原本存入的value将永远无法再被找到。自定义对象如链表节点虽然字段可变却仍然可哈希——因为它的哈希基于内存地址地址不变哈希值就不变。此外Python 解释器每次启动都会为字符串哈希函数加入随机盐salt所以同一程序在不同控制台输出的哈希值不同这正是为了防御 HashDoS 类攻击。六、原章节 QA 精讲7 个高频疑问逐一拆解Q1哈希表何时退化到 $O(n)$当碰撞严重到一定程度时哈希表的时间复杂度就会退化到 $O(n)$。只要哈希函数设计良好、容量选择合理、冲突分布足够均匀通常可视为 $O(1)$。使用语言内置哈希表时一般直接按 $O(1)$ 对待。Q2为什么不直接用 $f(x) x$ 这种“零碰撞”哈希函数若 $f(x) x$每个元素对应唯一桶下标结构就退化成数组了。但输入空间通常远大于输出空间数组长度所以哈希函数最后一步必须对数组长度取模。也就是说哈希表的本质正是“把较大的状态空间映射进较小的空间并保持 $O(1)$ 查询”碰撞是这种压缩映射的必然代价。Q3哈希表底层是数组、链表、二叉树为什么反而比它们快有三个原因。其一哈希表是“以空间换时间”大量内存处于闲置时空效率此消彼长。其二它只在特定场景更快——若同一问题用数组或链表也能达到相同渐进复杂度通常这种直白的实现反而更快因为计算哈希本身要耗费时间相当于把常数项抬高了。其三哈希表的复杂度同样可能劣化比如链式地址下仍需在链表或红黑树中检索$O(n)$ 退化的风险始终存在。Q4再哈希是否有“不能直接删除”的缺点被标记删除的空间还能复用吗再哈希属于开放寻址所有开放寻址方法都有“不能直接删除、只能打删除标记”的通病。被标记为已删除的空间可以复用插入新元素做探测时若撞上这类标记位新元素可以直接占用它。这既保持了探测序列的连续性又维持了可接受的空间利用率。Q5线性探测在查找时为什么也会“碰到”碰撞查找时先用哈希函数定位桶与键值对若发现该位置的key与目标不一致——这就意味着发生了哈希碰撞。此时线性探测按预设步长继续向后找直到命中正确的键值对或确认查找失败为止。Q6为什么扩容能缓解碰撞哈希函数最后一步通常是对数组长度 $n$ 取模。扩容后 $n$ 变了同一key的下标可能随之改变原先挤在同一桶里的多个key扩容后可能被分摊到多个桶碰撞自然减弱。Q7既然要快速访问为何不直接用数组当key是小范围连续整数时直接用数组最简单高效。但若key是字符串等其他类型就需要哈希算法把key映射成数组下标、再用桶数组存储元素——这种结构才叫哈希表。七、如何动手验证与继续深入学习想观察“朴素数组哈希表 无碰撞处理”的最简形态运行 array_hash_map.py想看到链式地址与“负载因子超过 $2/3$ 自动扩容为 2 倍”的完整逻辑运行 hash_map_chaining.py想验证线性探测 惰性删除 环形数组的实现细节阅读 hash_map_open_addressing.py想亲手计算四种朴素哈希并对“大素数取模”获得直观感受运行 simple_hash.py。在《Hello 算法》仓库中俄文版哈希章节由四篇文档构成概念与基础操作见 hash_map.md两种碰撞处理方案详见 hash_collision.md哈希算法的目标、设计与常用算法分析见 hash_algorithm.md本章配套练习题位于 exercises.md正文多处配有可视化动画图。这些资源与本文配合阅读即可把“哈希表为何高效、碰撞为何存在、如何化解、算法如何设计”这条主线彻底打通。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考