 查找到分布式分片)
《系统架构师成长之路》第 5 期｜数据结构与算法：哈希表与一致性哈希——从 O(1) 查找到分布式分片
导读：前 4 期我们走完了"内存 → 传输 → 协议"，本期回到架构师最常挂在嘴边、却也最容易被低估的数据结构——哈希表。单机里它给你 O(1) 查找；到了分布式，
key % N的取模分片会在扩容瞬间引发缓存雪崩。本期先把 O(1) 的数学基础推一遍，再推导一致性哈希如何把"扩容影响"从 90% 压到 1/N。
一、哈希表：O(1) 从哪来
哈希表 = 哈希函数 + 一段连续数组（槽位）。插入/查找时：
插入 key：槽位 = hash(key) mod m，放入该槽（冲突则处理） 查找 key：槽位 = hash(key) mod m，到该槽找为什么平均 O(1)？关键在于"槽位数 m 与元素数 n 的比例"——定义装载因子：
α = n / m （元素数 / 槽位数）推导（链表法平均查找长度，逐步）：
- 若哈希均匀，每个槽平均挂 α 个元素（n 个元素均匀撒到 m 个槽：n/m = α）；
- 查找成功：目标元素所在链表，它排在链表中的平均位置 = 该链表长度的 1/2；
- 对目标元素所在链表，期望长度 = 1 + 该链表其他元素的期望数。其他 n−1 个元素落入"这一特定槽"的概率各为 1/m，故期望长度为：
1 + (n−1)/m ≈ 1 + α/2 （成功查找的平均比较次数）- 查找失败：需遍历完整个链表，平均比较次数 = 链表的期望长度 =1 + α；
- 只要 α 被控制在常数（如 0.75，Java HashMap 的扩容阈值），平均比较次数就是常数 →O(1)。
技巧：这里用的是"期望/平均"分析——哈希函数是否均匀决定了这个结论是否成立，所以哈希函数质量是哈希表性能的第一前提。
图5-3哈希表主体：hash(key) % m决定槽位，多个 key 落入同一槽时以链表串接；装载因子 α=n/m 控制链表平均长度。
冲突处理两大流派：
| 方案 | 思路 | 代价 |
|---|---|---|
| 链表法（chaining） | 冲突元素挂链表 | 指针开销，缓存不友好 |
| 开放寻址（open addressing） | 冲突后找下一个空槽（线性探测/二次探测） | 装载因子必须 < 1，删除需打标 |
工程实例：JavaHashMap用链表法，链表长度 ≥8 转红黑树（退化保护）；Redis 字典用链表法 + 渐进式 rehash（扩容不阻塞服务）。
二、分布式分片：key % N的致命伤
单机哈希要扩容怎么办？——取模分片：N 台节点，key放到hash(key) % N号节点。
推导（扩容为何雪崩，逐步）：
- 原 N=3：
key的归属 =hash(key) % 3； - 扩容到 N=4：归属变成
hash(key) % 4； - 一个 key 能留在原节点，必须同时满足：
hash(key) % 3 == 原节点，且 hash(key) % 4 == 原节点- 对均匀哈希，
hash(key) % 4 == hash(key) % 3只对约 1/4 的 key 成立（同余条件概率 ≈ 1/N）； - 结论：扩容 3→4 时，约 3/4 的 key 换了节点。若这些 key 是缓存键，扩容瞬间 3/4 的缓存失效，全部打回数据库 →缓存雪崩。
失效比例 ≈ 1 − 1/(N+1) = N/(N+1) （从 N 扩到 N+1）工程代价：取模分片扩容 = 全量重哈希 + 缓存穿透 + 数据库打爆。这也是"为什么不用取模"的经典答案。
三、一致性哈希：让扩容只影响 1/N
思路：把哈希空间组织成环（0 ~ 2³²−1 首尾相接），节点与 key 都哈希到环上：
key 归属 = 从 key 的位置出发，顺时针遇到的第一个节点图5-1一致性哈希环：节点 A/B/C/D 分布在环上，key 沿顺时针找归属；新增节点 X 只接管环上 X→D 之间的一小段。
推导（加节点影响比例，逐步）：
- 环总长 2³²，N 个节点均匀分布时，相邻节点间的平均弧长 = 2³²/N；
- 新增节点 X 落在环的随机位置，它只会接管从 X 逆时针到前一个节点这段弧上的 key；
- 这段弧的期望长度 = 相邻节点平均间距 = 2³²/N（均匀分布下任意落点与前驱间距期望 = 1/(N+1)·环长 ≈ 2³²/N）；
- 结论：加一个节点，只有约 1/(N+1) 的 key 迁移——相比取模的 N/(N+1)，影响比例反过来了。
取模分片扩容影响：N/(N+1) ≈ 全部失效 一致性哈希加节点影响：1/(N+1) ≈ 只有一小段迁移数据倾斜与虚拟节点：真实节点只有 N 个，环上位置随机，可能扎堆 → 负载不均。解法：每个物理节点在环上放k 个虚拟节点（如 k=160），把"一个节点"变成"160 个均匀撒点"，统计上负载更均衡（推导直觉：独立同分布样本越多，方差越小）。Redis Cluster、Cassandra、Memcached 客户端均采用该思想。
图5-2虚拟节点：物理节点 A/B 各映射到多个环上位置（A₁、A₂…B₁、B₂…），减少扎堆导致的负载不均。
四、架构视角：哈希在系统设计中的位置
| 场景 | 用到的哈希思想 |
|---|---|
| 缓存分片（Redis Cluster） | 一致性哈希 + 虚拟节点（16384 个 slot 的槽位设计） |
| 数据库分库分表 | 一致性哈希环或范围分片，扩容平滑 |
| 负载均衡（一致性哈希 LB） | 同一 client key 固定到同一后端，会话保持 |
| 去重/计数（Bloom Filter） | 多个哈希函数映射位数组 |
常见坑：① 哈希函数选得差（如直接取模字符串 hash 的偶分布）导致倾斜；② 虚拟节点 k 太小，热点 key 仍扎堆；③ 删除节点后没有数据迁移策略（如 rehash 窗口）会造成短暂 miss；④ 一致性哈希不解决"热点 key"（个别 key 访问量爆炸），需额外做热点检测与本地缓存。
小结
- 哈希表 O(1) 的前提是装载因子可控 + 哈希均匀：链表法成功查找期望 1+α/2 次比较；
- 取模分片扩容失效比例 = N/(N+1)，几乎全量重映射，是缓存雪崩的元凶；
- 一致性哈希把扩容影响压到 1/(N+1)：只有新节点与前驱之间的环段迁移；
- 虚拟节点（k≈160）把物理节点"打散"成均匀撒点，解决数据倾斜。
思考题
- Java HashMap 为什么在链表长度 ≥8 时转红黑树？用"最坏 O(n) vs 退化概率"推一下。
- Redis Cluster 用 16384 个固定 slot 而不是一致性哈希环，为什么？对比两者的扩容代价。
- 一致性哈希环上如果删掉一个节点，它的 key 全部迁移给下一个节点——如何避免下一个节点瞬间过载？
下期预告
第 6 期「设计原则与设计模式：SOLID——从面条代码到可维护架构」——用一次"订单系统重构"串起五个原则，推导依赖倒置如何让高层不依赖低层细节。
参考资料
- CLRS《算法导论》第 11 章（哈希表：链表法与开放寻址，装载因子分析）
- 一致性哈希论文：Karger et al., “Consistent Hashing and Random Trees”（1997）
- Redis Cluster 官方文档（slot 与哈希槽设计）
- 《Redis 设计与实现》黄健宏（渐进式 rehash、字典实现）
- 美团技术博客《Java HashMap 详解》（红黑树化阈值分析）
- Martin Kleppmann, “Designing Data-Intensive Applications” 第 6 章（分区：一致性哈希与倾斜）
