Hello 算法哈希表章节小结：从 O(1) 查询到冲突处理与哈希算法设计

本篇基于《Hello 算法》哈希表章节的小结文档 docs/chapter_hashing/summary.md，系统回顾哈希表的核心原理：哈希函数如何将键 key 映射为数组索引从而实现 $O(1)$ 查询、负载因子如何触发扩容、链式地址与开放寻址两种冲突处理机制的差异，以及哈希算法"确定性、高效率、均匀分布"的设计目标。读完本文，你可以完整掌握哈希表从简单实现、冲突缓解到标准哈希算法选型的知识体系，并结合仓库中的 Python 参考实现（codes/python/chapter_hashing/hash_map_chaining.py、codes/python/chapter_hashing/hash_map_open_addressing.py）验证每一处结论。

核心知识体系总览

小结将整章知识浓缩为以下要点，可作为复习清单：

1. 输入 key，哈希表能够在 $O(1)$ 时间内查询到 value，效率非常高；
2. 常见的哈希表操作包括查询、添加键值对、删除键值对和遍历哈希表；
3. 哈希函数将 key 映射为数组索引，从而访问对应桶并获取 value；
4. 两个不同的 key 经过哈希函数后可能得到相同的数组索引，导致查询结果出错，这一现象被称为哈希冲突；
5. 哈希表容量越大，哈希冲突的概率越低，因此可通过扩容缓解冲突；但与数组扩容类似，哈希表扩容的开销很大；
6. 负载因子定义为哈希表中元素数量除以桶数量，反映哈希冲突的严重程度，常用作触发扩容的条件；
7. 链式地址将单个元素转化为链表，把所有冲突元素存放在同一链表中；链表过长时会降低查询效率，可进一步将链表转换为红黑树来提升效率；
8. 开放寻址通过多次探测处理冲突：线性探测使用固定步长，缺点是不能删除元素且容易产生聚集；多次哈希使用多个哈希函数探测，更不易产生聚集，但多个哈希函数增加了计算量；
9. 不同编程语言采取了不同的哈希表实现，例如 Java 的 HashMap 使用链式地址，Python 的 dict 采用开放寻址；
10. 哈希算法应具备确定性、高效率、均匀分布的特点；在密码学场景中还应具备抗碰撞性和雪崩效应；
11. 哈希算法通常采用大质数作为模数，以最大化保证哈希值均匀分布、减少冲突；
12. 常见的标准哈希算法包括 MD5、SHA-1、SHA-2 和 SHA-3；MD5 常用于校验文件完整性，SHA-2 常用于安全应用与协议；
13. 编程语言通常为数据类型提供内置哈希算法用于计算桶索引；通常情况下，只有不可变对象是可哈希的。

各知识点的完整推导过程可参考本章的其余文档：hash_map.md（工作原理与扩容）、hash_collision.md（冲突处理）、hash_algorithm.md（算法设计）。

哈希函数：从 key 到桶索引的映射

哈希函数是哈希表的核心。其作用是将一个较大的输入空间（所有 key）映射到一个较小的输出空间（桶索引），计算过程分两步（参见 hash_map.md）：

1. 通过某种哈希算法 hash() 计算得到哈希值；
2. 将哈希值对桶数量（数组长度）capacity 取模，得到桶索引 index。

index = hash(key) % capacity

以 capacity = 100、hash(key) = key 为例，哈希函数即 key % 100。仓库中的参考实现正是这一思路的直接体现：hash_map_chaining.py 中哈希函数只有一行——

def hash_func(self, key: int) -> int:
    """哈希函数"""
    return key % self.capacity

更完整的简单哈希表（键值对封装为 Pair 类）见 array_hash_map.py，内置哈希值计算示例见 built_in_hash.py。

哈希冲突、负载因子与扩容

由于输入空间往往远大于输出空间，理论上一定存在"多个输入对应相同输出"的情况。例如 12836 % 100 = 36 与 20336 % 100 = 36，两个不同学号指向同一个桶，即发生哈希冲突。

缓解冲突最直接的手段是扩容：容量增大后取模的除数改变，原先落在同一个桶的多个 key 可能被重新分散到多个桶中。

但扩容与数组扩容类似，代价高昂：需要把所有键值对迁移到新表中，且 capacity 改变后每个 key 的存储位置都要重新计算。因此实践中采用**负载因子（load factor）**作为扩容触发条件，其定义为元素数量除以桶数量。例如 Java 中当负载因子超过 $0.75$ 时，系统会将哈希表扩容至原先的 $2$ 倍。

仓库的 Python 参考实现给出了可运行的参数配置（hash_map_chaining.py）：

self.size = 0                          # 键值对数量
self.capacity = 4                      # 哈希表容量
self.load_thres = 2.0 / 3.0            # 触发扩容的负载因子阈值
self.extend_ratio = 2                  # 扩容倍数
self.buckets = [[] for _ in range(self.capacity)]  # 桶数组

对应的扩容逻辑（hash_map_chaining.py）暂存原表、将容量翻倍、重建桶数组后，把旧键值对逐个 put 回新表——由于 capacity 变化，每个键值对都会落到新的索引位置，这正是"扩容缓解冲突"的实现细节。

链式地址：冲突键值对挂到同一链表

链式地址（separate chaining）将每个桶扩展为一个链表（实现中常用动态数组简化代码），把所有发生冲突的键值对存放在同一链表中。其操作相应调整为：

• 查询元素：哈希函数得到桶索引后访问链表头节点，遍历链表对比 key 查找目标；
• 添加元素：先定位链表头节点，再将新节点添加到链表中；
• 删除元素：定位链表头后遍历链表找到目标节点并删除。

链式地址的局限：链表节点指针使空间开销增大，且需要线性遍历链表导致查询效率降低。因此当链表很长时，可将其转换为 AVL 树或红黑树，把查询时间复杂度优化至 $O(\log n)$。

结合 hash_map_chaining.py 的源码结构看，查询（get）先执行 index = self.hash_func(key) 定位桶，再对 bucket 线性扫描比对 pair.key；添加（put）在负载因子超过 load_thres 时先调用 extend()，若桶中已存在相同 key 则覆盖更新 val，否则追加至尾部并令 size += 1。

主流语言对链式地址的取舍各不相同：

• Java 采用链式地址，自 JDK 1.8 起，当 HashMap 内数组长度达到 64 且链表长度达到 8 时，链表会转换为红黑树以提升查找性能；
• Go 采用链式地址，每个桶最多存储 8 个键值对，超出则连接溢出桶；溢出桶过多时会执行一次特殊的等量扩容操作以确保性能；
• Python 则选择了开放寻址。

开放寻址：以多次探测代替附加结构

开放寻址（open addressing）不引入额外数据结构，而是通过多次探测处理冲突，探测方式主要包括线性探测、平方探测和多次哈希。

线性探测与聚集现象

线性探测采用固定步长（通常为 1）的线性搜索：

• 插入元素：哈希函数计算的桶若已有元素，则向后线性遍历直至找到空桶并插入；
• 查找元素：发生冲突时以相同步长向后遍历，找到目标即返回 value；遇到空桶则说明目标不存在，返回 None。

线性探测的主要缺点是容易产生聚集现象：数组中连续被占用的位置越长，发生哈希冲突的可能性越大，进而促使聚堆继续生长，形成恶性循环，最终劣化增删查改效率。

不能直接删除：懒删除与 TOMBSTONE

开放寻址中不能直接删除元素。若在数组中留下空桶 None，线性探测在该位置就会判定"元素不存在"而提前返回，导致该空桶之后的元素永远无法被访问到。

解决办法是懒删除（lazy deletion）：不真正移除元素，而是用常量 TOMBSTONE 标记该桶。None 和 TOMBSTONE 都可以放置新键值对，区别在于探测到 TOMBSTONE 时必须继续遍历，因为其下可能仍存在键值对。但懒删除会随 TOMBSTONE 增多而拖慢搜索速度，因此可进一步优化：记录探测过程中遇到的首个 TOMBSTONE 索引，找到目标元素后将其与该位置交换。这样每次查询或插入都会把元素移动至距离理想位置（探测起始点）更近的桶，从而优化查询效率。

仓库中 hash_map_open_addressing.py 完整实现了这一机制。核心方法 find_bucket（L34-L54）中可以看到三个关键细节：用 self.TOMBSTONE = Pair(-1, "-1") 表示删除标记（L24）；通过 first_tombstone 记录首个删除标记，命中目标后执行 buckets[first_tombstone] = buckets[index]; buckets[index] = TOMBSTONE 完成位置交换；索引推进采用 index = (index + 1) % self.capacity 将哈希表视为环形数组，越过尾部后回到头部继续遍历，以充分利用空间。删除操作 remove（L81-L88）也只是把命中桶替换为 TOMBSTONE 并 size -= 1。

注意：线性探测、平方探测和多次哈希等所有开放寻址方案都存在"不能直接删除元素"的问题，都需要依赖标记删除。

平方探测与多次哈希

• 平方探测：冲突时跳过"探测次数的平方"的步数，即 $1, 4, 9, \dots$ 步。它通过跳跃更远距离来缓解聚集、使数据分布更均匀，但仍存在聚集现象，且可能无法探测到整个哈希表（即使有空桶也可能访问不到）。
• 多次哈希：使用多个哈希函数 $f_1(x), f_2(x), f_3(x), \dots$ 依次探测，插入时 $f_1$ 冲突则尝试 $f_2$，以此类推；查找时按相同顺序进行。相比线性探测更不易产生聚集，但多个哈希函数带来额外计算量。

哈希算法的设计目标与实现

链式地址和开放寻址只能保证哈希表在冲突时正常工作，却无法减少冲突的发生。若冲突过于频繁，链式地址哈希表在最差情况下所有键值对会落入同一桶，时间复杂度退化至 $O(n)$。键值对的分布由哈希算法 hash() 决定（capacity 固定时），因此降低冲突概率的关键在于哈希算法的设计。

设计目标

哈希算法应具备三个特点：

• 确定性：相同输入始终产生相同输出，确保哈希表可靠；
• 效率高：计算哈希值足够快，开销越小实用性越高；
• 均匀分布：键值对分布越均匀，冲突概率越低。

此外，哈希算法还用于密码存储、数据完整性检查等场景。密码学应用需要更高的安全特性：

• 单向性：无法通过哈希值反推输入数据的任何信息；
• 抗碰撞性：极难找到两个不同输入得到相同哈希值；
• 雪崩效应：输入的微小变化导致输出显著且不可预测的变化。

需要注意，"均匀分布"与"抗碰撞性"是独立概念：例如 key % 100 在随机输入下可以产生均匀分布，但后两位相同的 key 输出必然相同，极易从哈希值反推 key，因而不可用于密码学。

简单哈希算法与质数模数

仓库中 simple_hash.py 实现了四种常见简单哈希算法，均以大质数 1000000007 为模数：

def add_hash(key: str) -> int:
    """加法哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash += ord(c)
    return hash % modulus

def mul_hash(key: str) -> int:
    """乘法哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash = 31 * hash + ord(c)
    return hash % modulus

def xor_hash(key: str) -> int:
    """异或哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash ^= ord(c)
    return hash % modulus

def rot_hash(key: str) -> int:
    """旋转哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash = (hash << 4) ^ (hash >> 28) ^ ord(c)
    return hash % modulus

四种方式各有特点：加法哈希将各字符 ASCII 码累加；乘法哈希每轮乘常数 31 累积，利用乘法的不相关性；异或哈希通过异或累积；旋转哈希每次累积前对哈希值做"左移 4 位与右移 28 位异或"的旋转操作，避免高位信息丢失。

为什么强调使用大质数作为模数？结论是：使用大质数作为模数，可以最大化地保证哈希值均匀分布。质数不与其他数字存在公约数，能减少取模产生的周期性模式。以合数 $9$ 为例，它能被 3 整除，所有能被 3 整除的 key（等差数列 $0, 3, 6, 9, \dots$）只会被映射到 $0, 3, 6$ 三个哈希值；而将模数换为质数 $13$ 后，同样输入序列的输出变为 $0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, \dots$，均匀性明显提升。当然，如果 key 本身随机均匀分布，质数或合数模数都能输出均匀结果；但当 key 分布存在周期性时，对合数取模更容易聚集。

常见标准哈希算法

简单哈希算法都比较"脆弱"——例如加法和异或满足交换律，无法区分内容相同但顺序不同的字符串，可能加剧冲突并引发安全问题。实际中通常采用 MD5、SHA-1、SHA-2、SHA-3 等标准哈希算法，它们将任意长度的输入映射到恒定长度的哈希值：

	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

要点：MD5 和 SHA-1 已多次被成功攻击，被各类安全应用弃用（MD5 仍可用于数据完整性检查）；SHA-2 系列中的 SHA-256 是最安全的哈希算法之一，仍未出现成功的攻击案例；SHA-3 相较 SHA-2 实现开销更低、计算效率更高，但使用覆盖度不如 SHA-2。

数据结构的哈希值与可哈希性

编程语言通常为数据类型提供内置哈希算法，用于计算哈希表中的桶索引（Python 的 hash()、Java 的 hashCode()、C++ 的 std::hash 等，多语言示例见 hash_algorithm.md 与 built_in_hash.py）：

• 整数和布尔量的哈希值通常就是其本身（Java 中布尔 true 的哈希值为 1231 是例外）；
• 浮点数和字符串的哈希值计算较为复杂；
• 元组的哈希值是对每个元素分别哈希后组合而成的单一值；
• 对象的哈希值通常基于其内存地址生成，可通过重写哈希方法实现基于内容的哈希。

在许多编程语言中，只有不可变对象才可作为哈希表的 key：若把列表（动态数组）作为 key，其内容变化时哈希值随之改变，就无法查询到原先的 value。而自定义对象（如链表节点）虽然成员可变，但由于哈希值基于内存地址生成，地址不变则哈希值不变，因此依然可哈希。

另外值得注意：不同控制台中运行同一程序，输出的字符串哈希值可能不同。这是因为 Python 解释器每次启动时都会为字符串哈希函数加入一个随机盐（salt）值，用于有效防止 HashDoS 攻击，提升哈希算法的安全性。

高频问题解析

以下 Q&A 完整继承自小结文档 summary.md，并对照源码加以说明。

Q1：哈希表的时间复杂度在什么情况下是 $O(n)$ ？

当哈希冲突比较严重时，哈希表的时间复杂度会退化至 $O(n)$。当哈希函数设计得较好、容量设置合理、冲突比较平均时，时间复杂度是 $O(1)$。使用编程语言内置哈希表时，通常认为时间复杂度是 $O(1)$。从源码结构看，hash_map_chaining.py 中 get 的最坏路径正是对单个桶内列表的完整遍历。

Q2：为什么不使用哈希函数 $f(x) = x$？这样就不会有冲突了。

在 $f(x) = x$ 下每个元素对应唯一桶索引，这与数组等价。然而输入空间通常远大于输出空间（数组长度），因此哈希函数的最后一步往往是对数组长度取模。换句话说，哈希表的目标是将一个较大的状态空间映射到一个较小的空间，并提供 $O(1)$ 的查询效率。

Q3：哈希表底层实现是数组、链表、二叉树，为什么效率可以比它们更高？

首先，哈希表是用空间换时间——相当一部分内存未被使用。其次，它只是在特定使用场景下时间效率变高：若某功能能以相同时间复杂度用数组或链表实现，通常比哈希表更快，因为哈希函数计算有额外开销，常数项更大。最后，哈希表的时间复杂度可能发生劣化，例如链式地址中在链表或红黑树上查找，仍有退化至 $O(n)$ 的风险。

Q4：多次哈希有不能直接删除元素的缺陷吗？标记为已删除的空间还能再次使用吗？

多次哈希是开放寻址的一种，开放寻址法都有不能直接删除元素的缺陷，需要通过标记删除。标记为已删除的空间可以再次使用：插入新元素时若哈希函数找到标记为已删除的位置，该位置即可被新元素占用。这样做既能保持探测序列不变，又能保证空间使用率——hash_map_open_addressing.py 中 get 将 None 与 TOMBSTONE 统一视为"空桶"即体现了这一点。

Q5：为什么在线性探测中，查找元素的时候会出现哈希冲突？

查找时通过哈希函数找到对应的桶和键值对，若发现 key 不匹配，就代表发生了哈希冲突。因此线性探测会按预设计步长依次向下查找，直到找到正确的键值对或无法找到为止。

Q6：为什么哈希表扩容能够缓解哈希冲突？

哈希函数的最后一步往往是对数组长度 $n$ 取模，使输出值落在数组索引范围内。扩容后 $n$ 发生变化，key 对应的索引也随之改变：原先落在同一个桶的多个 key，扩容后可能被分配到多个桶中，冲突就此缓解。这对应 hash_map_chaining.py 中 extend 重新计算所有索引的行为。

Q7：如果为了高效的存取，直接使用数组不就好了吗？

当 key 是连续的小范围整数时，直接用数组即可，简单高效。但当 key 是其他类型（例如字符串）时，就需要借助哈希函数将 key 映射为数组索引，再通过桶数组存储元素——这样的结构就是哈希表。

小结与延伸阅读

哈希表以"哈希函数 + 桶数组"的结构实现了 $O(1)$ 级别的增删查；冲突不可避免，但可以通过扩容（受负载因子触发）、链式地址、开放寻址等机制控制其影响；而冲突频率本身则由哈希算法的均匀分布能力决定，标准算法 MD5/SHA-2/SHA-3 则进一步覆盖了安全领域的需求。继续深入可阅读本章源码实现：

• hash_map.py：各语言内置哈希表的标准操作与遍历示例；
• array_hash_map.py：单数组简单哈希表与 Pair 键值对定义；
• hash_map_chaining.py：链式地址 + 负载因子扩容；
• hash_map_open_addressing.py：开放寻址 + 懒删除 + 环状探测；
• simple_hash.py：加法/乘法/异或/旋转四种简单哈希算法；
• built_in_hash.py：内置哈希值计算示例。