Bilibili 同步视频

干货版《算法导论》08：哈希——重构集合数据结构的速度魔法

在数据结构的浩瀚世界里，集合（Set） 始终是绕不开的核心基石🌍。我们不执着于元素的外部序列顺序，只执念于按 Key 精准定位：这个键是否存在？能否快速插入？能否高效删除？

此前我们探索过两种经典实现：

• 无序数组：查找靠线性扫描，时间复杂度 O(n)，数据量稍大便慢如蜗牛🐌

• 有序结构+二分查找：查找优化至 O(log n)，构建开销却高达 O(n log n)

看似 O(log n) 已是最优解，但真的无法突破吗？

log₂(10⁹)≈30，这个数字看似微小，可在高并发、高频访问的场景下，30 倍的对数开销依旧是性能瓶颈🚫。我们真正渴望的，是O(1) 常数级的极致速度——一步直达，零冗余损耗。

今天，我们就沿着比较模型下界 → 直接寻址的理想与缺憾 → 哈希压缩 + 链式冲突解决的路径，揭开哈希打破速度极限的底层逻辑💡。

---

🔎 一、比较模型：藏在查找背后的「下界枷锁」

首先，我们要明确比较模型的核心规则：

所有存储元素都是「黑盒」📦，唯一能区分元素的方式只有两两比较（>、<、=、≥、≤），每次比较仅输出 True/False 二元结果。

在这个模型中，任何查找算法都能被抽象为一棵**决策树（Decision Tree）**🌳：

• 内部节点 = 一次关键比较

• 分支走向 = 比较结果

• 叶子节点 = 算法终止（找到目标 / 判定不存在）

一棵正确的查找决策树，必须满足两个条件：

1. 能返回 n 个存储元素中任意一个的位置

2. 能明确返回「目标不存在」

这意味着决策树的叶子节点数量 ≥ n+1。

而二叉树的最小高度由叶子数决定，推导可得：

最小高度 h ≥ ⌈log₂(n+1)⌉ − 1 = Ω(log n)

这就是比较模型的查找下界：

✅ 结论：仅依靠比较操作，查找的最坏时间复杂度不可能快过 O(log n)。

想要挣脱这个枷锁，必须跳出比较模型，拥抱 RAM 模型的终极能力——**内存随机访问（Random Access）**🚀。

---

🎯 二、直接寻址数组：O(1) 乌托邦，却困于空间爆炸

跳出比较模型后，最简单的方案就是直接寻址数组（Direct Access Array），这是最纯粹的 O(1) 实现：

核心原理

键 Key 直接作为数组下标，即 h(Key) = Key，元素精准存储在 table[Key] 位置。

极致性能

• 查找 find(Key)：O(1)，直接读取对应下标

• 插入 insert(Key)：O(1)，直接写入对应下标

• 删除 delete(Key)：O(1)，直接清空对应下标

完美契合集合的语义，无冲突、无分支，纯常数时间操作✨。

致命缺陷：空间爆炸💥

我们定义两个核心变量：

• n：实际存储的元素个数

• U：键的全集大小（如 9 位学号，U=10⁹）

当 U ≫ n 时，直接寻址的弊端暴露无遗：

1. 需要开辟长度为 U 的数组，空间利用率极低

2. 绝大多数下标位置空置，造成指数级空间浪费

3. 连续遍历、迭代操作效率崩盘

直接寻址仅适用于键范围小、数据密集的场景，无法适配真实世界的复杂需求。

---

🔑 三、哈希登场：把「大宇宙」压缩进「小盒子」

我们的目标清晰明确：

保留随机访问的 O(1) 速度，同时将空间复杂度压至 O(n)。

解法就是哈希函数 h(Key)：

将庞大的键空间 U，压缩映射到更小的范围 [0, m−1]，其中 m≈n。

形式化定义

h: U → {0,1,…,m−1}

鸽巢原理：冲突是哈希的「必然宿命」

因为 U ≫ m，根据鸽巢原理，必然存在不同的 Key₁≠Key₂，使得：

h(Key₁) = h(Key₂)

这就是**哈希冲突（Collision）**⚠️。

冲突无法避免，我们能做的，是优雅、高效地处理冲突。

---

⛓️ 四、链式哈希：最易懂、最实用的冲突解法

哈希冲突的主流解决方案有两种：

1. 开放寻址（Open Addressing）：在原数组中寻找空位（Python 字典底层实现），分析复杂、易出现聚集问题

2. 链式哈希（Chaining）：每个数组槽位挂载一条链表/动态数组，冲突元素直接追加到链上

链式哈希逻辑极简、分析清晰、工程易实现，是入门哈希的最佳选择👇。

核心工作流程

1. 通过哈希函数 h(Key) 计算桶下标 i

2. 第 i 个桶对应一条「存储链」

3. 查找/插入/删除仅在当前链上线性扫描

只要哈希函数足够均匀，链长期望为常数，整体操作依旧保持 O(1) 复杂度🌟。

---

✨ 五、哈希的本质：重新定义集合操作的极限

我们用一张对比表，看清数据结构的进化之路：

结构类型	查找	插入	删除	空间复杂度	适用模型
无序数组	O(n)	O(1)	O(n)	O(n)	通用模型
有序+二分	O(log n)	O(n)	O(n)	O(n)	比较模型
直接寻址	O(1)	O(1)	O(1)	O(U)	RAM 模型
链式哈希	期望 O(1)	期望 O(1)	期望 O(1)	O(n)	RAM 模型
哈希的底层智慧，是用哈希函数做「空间-速度」的完美平衡⚖️：

• 继承随机访问的极速特性

• 把空间从 O(U) 压缩至 O(n)

• 用均匀分布将冲突控制在常数级

它彻底打破了比较模型 O(log n) 的下界枷锁，用极简设计实现了均摊 O(1) 的集合操作，成为编程语言字典、缓存系统、数据库索引、分布式哈希表的底层灵魂💻。

当我们在代码中轻松使用 dict、HashMap 时，每一次「瞬间查找」的背后，都是决策树下界、随机访问、哈希压缩、冲突解决的完美协作⚡️。

这，就是哈希的魔法；这，就是数据结构的浪漫✨。