SwissTable 比 std::unordered_map 快一个数量级，核心是它用一条 SIMD 指令同时比 16 个槽的 7-bit 指纹

“hash map 慢是因为 hash 函数不够好”——这句话被说了十年，但它是错的。你可以把 hash 函数从std::hash换成 wyhash、xxHash、甚至用密码学级的 SipHash，std::unordered_map的 find 延迟不会有数量级变化。瓶颈不在 hash 的质量，在 hash 之后的事：每次查找至少追两个指针（桶数组→链表节点→key），每个指针都是一次几乎必然的 cache miss。abseil 的flat_hash_map换了一种做法。它把每个槽的 hash 值拆出高 7 位，存进一个独立的、连续的控制字节数组（control bytes）。查找时，先用一条 SSE2 指令_mm_cmpeq_epi8把目标指纹广播到 128-bit 寄存器里，和 16 个控制字节同时比较——一次 SIMD 操作过滤 16 个槽，只有指纹匹配的槽（期望不到 0.11 个）才会去碰真正的 key。Matt Kulukundis 在 CppCon 2017 公开这个设计后，Google 在整个代码库里把unordered_map替换成flat_hash_map，取得了可测量的全舰队 CPU 使用率下降。此后 Rust 标准库（hashbrown, 2019）、Boost.Unordered（2022）、Go 1.24（2025）先后采用同一设计。这篇文章拆开这个设计的每一层：从unordered_map的内存布局讲起，到控制字节的位编码、SIMD 探测循环、三角数步长的数论证明、tombstone 的代价，最后讲