control byte · SIMD · abseil / hashbrown

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

前几页的成本模型都在数「比较了几次 key」。现代 CPU 上这个口径已经不准了：一次整数比较约 1 个时钟周期，一次 L3 未命中的内存访问约 100 个以上。真正要省的是访存次数，尤其是那些落在不同 cache line 上的随机访问。

Swiss table 的做法是把「筛选」与「取值」拆开。筛选只读一张极紧凑的元数据数组，一个 cache line 装得下 64 个条目；只有筛选通过的候选才去碰真正的 key。abseil 的 flat_hash_map、Rust 的 hashbrown（自 1.36 起是标准库 HashMap 的实现）、Go 1.24 起的 map 都是这套布局。

1 · 一个 byte 装两件事

表被切成固定 16 个槽一组。每个槽对应一个 control byte，它取三种值之一：

control byte	含义
`0b1000_0000`	`EMPTY`，空槽
`0b1111_1110`	`DELETED`，墓碑
`0b0hhh_hhhh`	已占用，低 7 位是该 key 的指纹

散列值被切成两半：高位 h1 决定从哪一组开始探测，低 7 位 h2 就是存进 control byte 的指纹。最高位当作标志位——空槽与墓碑都是高位为 1，占用槽高位为 0，于是「这一组里有没有空槽」也能用同一条 SIMD 比较得出。

图 1-1 · 4 组共 64 槽的 control byte 数组。蓝底是指纹与 h2 相等的槽，绿底是完整比较后确认命中的那个。可换查找 key，注意扫过的槽位数与真正的完整比较次数之差。

查找一组的动作在 x86 上是三条指令：_mm_loadu_si128 把 16 个 control byte 装进一个 128 位寄存器，_mm_cmpeq_epi8 与广播成 16 份的 h2 逐字节比较，_mm_movemask_epi8 把结果压成一个 16 位掩码。之后只需对掩码里为 1 的位置去取真正的 key。没有 SSE2 的平台走 SWAR 回退——用 64 位整数的位运算一次处理 8 个字节，组大小相应改为 8。

2 · 指纹的位宽是一道算术题

7 位指纹意味着两个不同的 key 有 $1/128$ 的概率指纹相同。这个数字很容易被误读。

图 2-1 · 未命中查找的假匹配次数在五档负载下的实测与预测，下方另有与 linear probing 探测次数的对照。可勾选同时显示每槽口径的 1/128。

$1/128 = 0.0078$ 是每槽的口径，而一次查找要扫过一整组 16 个槽。实测（512 槽、4000 次未命中查找）：

负载 $\alpha$	每次查找的假匹配	预测值	扫过的组数
0.500	0.0630	0.0625	1.00
0.699	0.1033	0.1011	1.16
0.779	0.1729	0.1681	1.73
0.875	0.2444	0.2259	2.07

预测值取 $16 \cdot \alpha \cdot (\text{扫过的组数}) / 128$ ——扫过的槽位数乘占用率再除以 128。它与实测处处吻合到小数点后两位。 $\alpha = 0.78$ 时每次查找的假匹配是 0.17，比「1/128」这个数字高出二十多倍，原因只是口径不同：一个说的是一个槽，一个说的是一次查找扫过的二十几个槽。

指纹取 7 位而非更多，是因为 control byte 的第 8 位要留给状态标志。这个取舍换来的是元数据密度：8 位一个条目，一个 64 字节的 cache line 装得下 64 个槽的元数据。若把指纹加宽到 15 位，假匹配率降到 $1/32768$ ，但元数据密度减半、每次探测多读一条 cache line——省下的那点假匹配远不够付这笔账。

命中那一侧几乎不受负载影响：实测在 1.03 到 1.07 之间，也就是说找到一个 key 平均只需要碰一次真正的 key 数据。这才是这套布局的收益所在。

3 · 墓碑与「没有空槽」的组

删除仍然要留墓碑，理由和开放寻址 §3 一样——探测不能在删除位提前终止。但 Swiss table 有一个别处没有的优化：如果被删除的 key 所在的组里本来就有空槽，那么这个位置可以直接标成 EMPTY 而不是 DELETED。

理由是探测的终止条件：探测在「组内有空槽」时停止。既然这一组本来就有空槽、探测本来就会在这一组停下，那么再多一个空槽不会让任何 key 变得找不到。hashbrown 的 erase 正是这么判的：它数一遍该槽前后两个组窗口里的空槽，够多就写 EMPTY，否则才写 DELETED。这个优化让「删了很多之后表被墓碑塞满」的退化场景大幅缓解。

扩容的判据也因此要同时看两个数：占用槽数与「占用加墓碑」之和。hashbrown 的最大负载因子是 7/8，超过即扩容；若其中墓碑占比很高，扩容会选择原地重建（容量不变，只是把墓碑清掉）。

4 · 这套布局买到了什么

把三代实现放在一起对照，能看清优化的方向一直在变：

实现	冲突解决	每次查找的主要开销
`std::unordered_map`	链地址法，规范要求稳定的 bucket 迭代器	每个元素一次指针追逐，节点分散在堆上
Robin Hood（旧 Rust）	开放寻址，PSL 摊平	顺序访存，但每步要读真正的 key 来算 PSL
Swiss table	开放寻址，分组 + 指纹	一次元数据读（16 槽），平均一次 key 读

std::unordered_map 的性能上限被标准锁死了：规范要求 bucket 接口与引用稳定性，这实质上强制了链地址法，所以它无法改成开放寻址——abseil 才要另起一套。Robin Hood 的问题更微妙：它的提前终止依赖 PSL，而 PSL 要么额外存一个字节、要么现场用 key 的散列值重算，两条路都要碰 key 数据。Swiss table 的 control byte 同时解决了「筛选」与「终止条件」，且两者都只读元数据。

代价是这套布局对散列函数的高位质量要求更高——h1 取的是高位，h2 取的是低 7 位，两者必须互相独立。用一个只在低位有差异的弱散列，会同时毁掉分组与指纹。所以 hashbrown 默认配的是 SipHash-1-3，abseil 用的是 absl::Hash，都是过了 SMHasher 的实现。

5 · 参考文献

Kulukundis, M. (2017). Designing a fast, efficient, cache-friendly hash table, step by step. CppCon 2017.
abseil. Swiss Tables design notes. abseil.io/about/design/swisstables.
hashbrown. src/raw/mod.rs 中的 Group、find_inner 与 erase。
Go. internal/runtime/maps（Go 1.24 起的 Swiss table map 实现）与提案 golang/go#54766。