《Hello 算法》哈希章节总结：哈希表 O(1) 查找原理、碰撞处理与哈希算法设计要点-平芜编程栈

《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）处于空闲状态、内存利用率偏低（详见后文 Q&A 中“为何比数组、链表快”的讨论）。

操作	数组	链表	哈希表
查找元素	$O(n)$	$O(n)$	$O(1)$
添加元素	$O(1)$	$O(1)$	$O(1)$
删除元素	$O(n)$	$O(n)$	$O(1)$

二、哈希函数：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 % 100，get()/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 = 2；put()每次先检查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 举例说明了三种代表性选择：

Python：dict使用开放寻址，探测时结合伪随机数；
Java：HashMap使用链式地址；从 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 给出的对照如下：

MD5	SHA-1	SHA-2	SHA-3
诞生年份	1992	1995	2002	2008
输出长度	128 bit	160 bit	256/512 bit	224/256/384/512 bit
碰撞情况	频繁	频繁	罕见	罕见
安全等级	低，已被成功攻破	低，已被成功攻破	高	高
典型用途	已过时，仍偶用于数据完整性校验	已过时	加密货币交易校验、数字签名等	可作 SHA-2 的替代

一个容易被误解的表述：哈希算法常在“取模”之外，另有以自身结果直接参与运算的朴素场景，但标准哈希算法并不局限于取模结构——它们通过内部轮函数把定长状态反复混淆扩散，实现雪崩效应。

6. 数据类型的哈希与“只可哈希不可变对象”

语言的key可以是整数、浮点数、字符串等多种类型，运行时通常为这些类型内置了哈希算法用于计算桶下标。以 Python 为例，其内建hash()的行为（示例代码见 built_in_hash.py）：

整数与布尔值的哈希值等于其自身（True为 1）；
浮点数与字符串的哈希计算较复杂；
元组按元素逐个哈希后再合并成最终值；
对象默认按内存地址构造哈希值；若重写哈希方法，则可改为按内容计算。

这里还有一个关键限制：哈希表只允许把不可变对象用作key。若用列表这种可变对象当key，一旦内容改变，其哈希值也随之改变，原本存入的value将永远无法再被找到。自定义对象（如链表节点）虽然字段可变，却仍然可哈希——因为它的哈希基于内存地址，地址不变哈希值就不变。此外，Python 解释器每次启动都会为字符串哈希函数加入随机盐（salt），所以同一程序在不同控制台输出的哈希值不同，这正是为了防御 HashDoS 类攻击。

六、原章节 Q&A 精讲：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，正文多处配有可视化动画图。这些资源与本文配合阅读，即可把“哈希表为何高效、碰撞为何存在、如何化解、算法如何设计”这条主线彻底打通。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考