算法与数据结构 / 哈希表 · 从散列函数到渐进式 rehash 待审核 8 页

哈希表 · 从散列函数到渐进式 rehash

数组按下标取值是 O(1)，但下标必须是小整数。hash table 补上中间那一步：拿一个散列函数把任意 key 压成 32 位整数，再折算成数组下标，于是「按 key 取值」也降到平均 O(1)。整个数据结构的全部复杂度，都来自这一步折算不是双射——两个不同的 key 会算出同一个下标。

本系列分四条线。第一条是散列函数：什么叫「散得开」，为什么取低位会被对齐的地址打死，以及 hash flooding 这类拿碰撞当武器的攻击。第二条是冲突解决的两大流派，chaining 把同槽的 key 串成链，open addressing 让它们沿探测序列往后挪，后者的删除必须留墓碑、而 Robin Hood 变体能把探测距离摊平。第三条是规模：负载因子、成倍扩容的摊还代价，以及 Redis dict 用双表加 rehashidx 把一次性 rehash 拆成每次操作搬一格。第四条走向现代实现与分布式：Swiss table 的 control byte 让一条 SIMD 指令筛掉整组候选，cuckoo hashing 把查找钉死在两次访存，consistent hashing 与 jump hash 则解决「加一台机器要搬多少数据」。

每页都能改 key、单步执行，观察 hash 值如何折算成下标、探测路径怎么走、扩容时哪些格子被搬走。

地基：散列函数与两类冲突解决

key 到下标分两步：散列函数给出 32 位整数，折算规则把它压进 0..m-1。两步各有各的坑——散列函数可能把差异只留在低位，折算规则可能只看低位。冲突无法避免（mm 个槽装 n>mn > m 个 key 时必然发生），两大流派的分野是「同槽的 key 存在哪」：chaining 存在槽外的链上，open addressing 存在表内别的槽里。

hash function · avalanche · 折算

从 key 到下标：散列函数

key 到下标要走两步：散列函数给出 32 位整数，折算规则把它压进 0 到 m-1。两步的失效方式不同——散列函数可能把差异只留在低位，折算规则可能只读低位；两者叠在一起时表退化成一条链。

 separate chaining · 负载因子 · 树化

链地址法：把冲突挪到槽外

同槽的 key 串成一条链，槽只存链头指针。表可以装超过槽数的元素，删除只是摘一个节点；代价是每一跳都可能是一次 cache miss，而扩容治不了「hash 值真的相同」那种链。

 probing · 聚簇 · tombstone · Robin Hood

开放寻址：冲突就往后挪

同槽的 key 全存在表内，冲突时沿探测序列往后找空位。换来的是紧凑数组与顺序访存，代价是删除必须留墓碑、且 linear probing 会形成自我加强的聚簇。Robin Hood 变体不减少总探测量，只把它摊平。

两个流派的分工判据

chaining 与 open addressing 的选择，实践中很少取决于渐近复杂度——两者在负载因子受控时都是常数级。真正的判据有三条： 元素大小。open addressing 把 key 与 value 直接存在槽里，一个空槽也占一整个 entry 的空间；元素大时空表的浪费很可观，chaining 的空槽只是一个指针。 删除频率。open addressing 的删除要留墓碑（见 开放寻址 §4），墓碑会一直拉长探测路径直到下次 rehash；删除频繁的场景 chaining 更省心，Robin Hood 的 backward shift 是另一条出路。 访存局部性。chaining 的每一跳都是一次可能 cache miss 的指针追逐，open addressing 沿数组往后走，一个 cache line 能一次带回好几个槽。这一条在现代硬件上分量最重，也是 Swiss table 把它推到极致的动机。

散列函数与冲突解决 · 延伸阅读

探测方式与 Robin Hood

规模：负载因子与两种 rehash

表满了要换一张更大的。成倍扩容让 nn 次插入的总搬迁量保持在 O(n)O(n)，单次却可能搬走全部 key——摊还是好的，尾延迟不是。Redis dict 的答案是不搬：建好新表，让后续每次读写各搬一格，旧表在正常流量里自己排空。

load factor · 摊还 · 尾延迟

负载因子与成倍扩容

表满了要换一张更大的。成倍扩容让 n 次插入的总搬迁量停在 O(n)，摊还每次约 3 次写入；代价是这些搬迁全挤在少数几个点上，最贵的一次要搬走当前全部 key。

 dict.c · rehashidx · 尾延迟

渐进式 rehash：Redis 的双表

扩容时不搬 key，只建好新表并把游标置零，此后每次读写各搬一格。总搬迁量分毫不减，单次峰值从「全表」降到「一条链」。代价是两张表并存期间每次查找可能要查两遍。

摊还常数与尾延迟是两个指标

成倍扩容的摊还代价是 O(1)O(1)，这个结论没有问题，但它说的是总量。实测 10 万次插入、二倍扩容，总数组写入是 2.97n2.97n（见 负载因子与扩容 §3）；同一串插入里最贵的那一次要搬走 65536 个 key。摊还分析把这一次的代价平摊给了前面 6 万多次插入，可请求延迟不会自己平摊——第 65537 次插入的 p99.99 就是它。 这就是渐进式 rehash 存在的理由，也是它唯一的理由：它不降低总搬迁量（该搬的一个不少），只把这一坨代价切成 nn 份分摊到时间轴上。判断要不要它，看的是服务有没有尾延迟指标，而不是吞吐。

扩容与 Redis dict · 延伸阅读

  • redis/src/dict.c github.com 渐进式 rehash 的一手实现：dictRehash 的搬迁循环、dictRehashStep 的单步调用点、dict_can_resize 与 fork 期间的暂停逻辑。
  • Redis · Memory optimization redis.io 各类型的编码切换阈值与内存开销，含 dict 与紧凑编码之间的取舍。
  • 摊还分析讲义 · Brown CS cs.brown.edu 聚合法、记账法、势能法三种摊还分析手法，动态数组成倍扩容是其中的标准例题。

布局：为 cache line 与访存次数重做的两版实现

现代实现优化的不再是比较次数而是访存次数。Swiss table 把每个 key 的 7 位指纹单独存成一张紧凑的 control byte 数组，一次 SIMD 比较筛掉整组 16 个候选；cuckoo hashing 走另一条路，给每个 key 只留两处候选，查找恒为两次访存，代价是插入可能连锁踢出。

control byte · SIMD · abseil / hashbrown

Swiss table：一条指令筛掉一整组

把每个 key 的 7 位指纹单独存进一张紧凑的 control byte 数组，一条 SIMD 指令并行比较 16 个字节，得到一个候选位掩码。真正的 key 比较平均只发生一次，代价是极低的假匹配率。

 两次访存 · 踢出链 · 相变 0.5

cuckoo hashing：只给两处候选

每个 key 只允许落在两个位置之一，于是查找恒为两次访存，与负载因子无关。代价在插入侧：候选位置都被占时把原住户踢去它的另一处，链式接力；负载越过 0.5 就几乎必然成环。

现代布局 · 延伸阅读

分片：把同一套思路放大到一群机器

槽换成机器，问题就变成「加一台要搬多少数据」。取模分片的答案是几乎全部，consistent hashing 把它压到 1/(N+1)1/(N+1)，jump consistent hash 连环都不存、直接算出桶号。

环 · vnode · jump hash

一致性哈希：加一台机器要搬多少

槽换成机器，问题从「冲突怎么办」变成「集群规模变了要搬多少数据」。取模分片几乎全盘重排，环把它压到 1/(N+1)，jump consistent hash 连环都不存、直接算出桶号。

分片 · 延伸阅读