Swiss Table 是什么

Swiss Table 是 Google 在 2017 年前后公开的一种高性能哈希表设计（最早用在 Abseil 库的 absl::flat_hash_map 里），本质上是开放地址法的一个工程变体：在经典的线性探测 / 二次探测之上，加入了按"组"批量比较的机制，充分利用 CPU 的 SIMD 指令与缓存局部性。基本的开链法、开放地址法概念见 开链法与开放地址法。

它已经被多个主流项目采纳：Rust 的 hashbrown（std::collections::HashMap 自 1.36 起的底层实现）就是 Google SwissTable 的 Rust 移植版；Go 1.24 内置的 map 也从桶+溢出桶的实现换成了基于 Swiss Table 思路的新实现（细节见 开链法与开放地址法#在-go-语言中的应用）。

核心设计

控制字节（control byte）

Swiss Table 给每个槽位（slot）配一个额外的 1 字节"控制字节"，不存实际数据，只存槽位的状态和一段哈希指纹：

  • 槽位状态：EMPTY（从未用过）、DELETED（曾经用过、已删除，即墓碑标记）、FULL（当前有效数据）。
  • 如果槽位是 FULL，控制字节里还会存一段哈希指纹，Abseil 里称为 h2，取的是 key 完整哈希值的低 7 位。

h1 和 h2：哈希值一分为二

Swiss Table 把 key 的哈希值拆成两部分：

  • h1：哈希值的剩余高位，用来计算这个 key 应该落在哪一个"组"（group），即决定探测起点，作用类似前文开放地址法里的 root = hash(key) % m。
  • h2：哈希值的低 7 位，存进控制字节，作为一个廉价的"预筛选"指纹。

分组批量比较

控制字节在内存中是连续排列的，按组打包（Abseil/hashbrown 里一组 16 个，Go 1.24 里一组 8 个，打包进一个 64 位控制字）。查找时：

  1. 用 h1 定位到起始组。
  2. 把待查 key 的 h2 和整组的控制字节一次性比较——Abseil/hashbrown 用 SIMD 指令（一条指令并行比较 16 个字节），Go 用位运算技巧在一个 64 位整数上模拟并行比较 8 个字节。这一步只是比较 1 字节的指纹，不用碰真正的 key 和 value，候选范围一下就从"组内 8~16 个槽位"收窄到"少数几个 h2 相同的槽位"。
  3. 对命中 h2 的少数候选槽位，再去比较完整的 key，确认真正相等。
  4. 如果整组都没有命中，且组内还有 EMPTY 槽位，说明当前 key 不存在，查找结束；否则说明当前组"满了"，探测下一个组（探测函数通常是二次探测的一种变体，保证能遍历完所有组）。

这套"先比 1 字节指纹、再比完整 key"的设计，把大部分不匹配的槽位在第一步就过滤掉了，减少了昂贵的 key 比较次数，也让内存访问更集中（一次性读一整组连续的控制字节），缓存命中率更高。

SIMD 具体带来了什么

如果去掉 SIMD，“分组比较"这一步会退化成一个逐字节比较的循环：拿 h2 和组内 8~16 个控制字节逐个比较，找出匹配的位置。SIMD 在这一步具体做了两件事：

  1. 把 N 次比较压缩成 1 条指令：把待查 key 的 h2 复制（broadcast）到一个和组等宽的向量寄存器里（比如 128 位寄存器里塞 16 份相同的 h2），再用一条向量比较指令（比如 x86 的 pcmpeqb）和整组控制字节逐字节比较，一次性得到一个"位掩码”，标出哪些位置的控制字节等于 h2。原本要写一个循环比较 8~16 次，现在是 1 条指令、1 次执行。
  2. 顺带判断要不要停止探测：同一批寄存器操作里，还可以再拿 EMPTY 这个哨兵值比一次，一次性知道这一组里有没有空槽位——如果有，说明目标 key 不存在，查找可以提前结束，不用再探测下一组。这个判断和第 1 点是同一批向量操作顺带做的，没有额外开销。

这两点合起来带来的实际收益是：大幅减少了要触碰真正 key/value 的次数。真正的 key 比较通常要解引用一个指针、访问一块不在当前缓存行里的内存（尤其是变长的 key，比如字符串），代价比比较 1 个字节的指纹高得多。没有 SIMD 的话，要么每个槽位都要老老实实地和目标 key 比较一次（代价最高），要么至少要写一个标量循环去过滤控制字节（虽然比直接比 key 便宜，但仍然是 N 次独立的比较指令、N 次条件跳转）。用了 SIMD 之后，整组的过滤在 CPU 层面变成一条指令、一次内存加载；对于哈希分布均匀、大多数探测会落空的场景（也就是大部分的查找/插入操作），可以把"平均要比较的完整 key 数量"降到接近 0 或 1，而不是组的大小（8~16）。

Go 的实现里没有用真正的向量硬件指令，而是用位运算在一个 64 位整数上模拟出等价效果（这个技巧一般叫 SWAR，SIMD Within A Register）：把 8 个控制字节打包进一个 64 位整数，通过几条普通的按位与、异或、减法指令，同样能一次性判断出 8 个字节里哪些等于目标值、哪些是 EMPTY，不需要专门的 SIMD 硬件支持，代价是不如真正的向量指令快，但比逐字节的标量循环还是快得多。

删除：墓碑标记

开放地址法删除元素后不能直接清空槽位，否则会打断后续的探测路径，这个问题在 开链法与开放地址法#删除的处理 里已经讲过。Swiss Table 用的正是"删除标记"方案：删除时把控制字节置为 DELETED，探测时跳过 DELETED 继续往后找，插入时优先复用 DELETED 槽位。如果 DELETED 槽位积累过多，会拖慢探测效率，实现里通常会在扩容或达到一定比例时做一次整体 rehash，把 DELETED 清理掉。

和传统开放地址法的区别

Swiss Table 依然是开放地址法——只有一个数组，冲突时探测下一个位置，这点没变。它的改进点主要是两个：

  • 批量比较代替逐个比较：传统开放地址法探测时一次只看一个槽位；Swiss Table 一次看一整组（8 或 16 个），先用 1 字节指纹筛选，减少了要触碰的 key/value 数量。
  • 探测粒度从槽位变成了组：探测序列是在"组"之间跳，而不是在单个槽位之间跳，进一步提升了缓存局部性。

为什么是 2017 年才出现

CPU 早在 1996 年（Intel MMX）就支持 SIMD 了（详见 SIMD 指令与缓存局部性），但通用哈希表直到 2017 年前后才用上这个特性，中间隔了二十年。严格来说 Swiss Table 也不是"第一次"把 SIMD 用在哈希表上：2013~2015 年，Balkesen/Teubner 等人已经发表过用 SIMD 加速数据库 hash join 探测的论文，Polychroniou 等人也做过向量化的 Bloom filter 和哈希表探测，只是这些都是数据库内核里的专用实现，没有变成一个通用语言能直接拿来用的哈希表库。Swiss Table 真正的贡献是把这套思路做成了第一个通用、开箱即用的哈希表（absl::flat_hash_map）。

真正拖了二十年的原因，主要不是硬件问题：

  • 这是一个数据结构设计上的洞察，不是硬件能力问题。1996~2010 年代 SIMD 的主战场是音视频编解码、图形学、科学计算，这些场景天然是"一大堆同类型数字排成数组"，怎么用 SIMD 很直观。哈希表是指针追逐（pointer chasing）结构，key/value 大小不一、分散在内存各处，想用上 SIMD 得先想到把元数据（槽位状态 + 哈希指纹）拆出来，单独存成一个紧凑定长的字节数组——这是 Swiss Table 真正的创新点，SIMD 只是拿现成的指令用在这个新设计上。
  • 通用语言标准库有 API 契约上的枷锁。C++11 标准要求 std::unordered_map 提供指针/引用稳定性（元素插入后地址不变）和 O(1) 的迭代器自增，这两条几乎强制要求用链表式（chaining）的节点结构。Swiss Table 这种紧凑数组式的开放地址法天然做不到"指针永远不失效"，所以从设计上就无法把 std::unordered_map 直接改造成 Swiss Table，Google 只能另起一个 absl::flat_hash_map 放进 Abseil 库，而不是修 STL。
  • 要等 SIMD 变成"哪里都有、可以无脑依赖"的基线。1996 年的 MMX 只是可选特性，还要运行时检测 CPU 是否支持；直到 x86-64 把 SSE2 定为强制基线（约 2003~2004 年），通用库代码才能放心地无条件使用向量指令，不用写一堆运行时特性探测的分支逻辑。

为什么 Go 能在 1.24 换成 Swiss Table

容易联想到"Go 是新语言，没有历史包袱，所以能重新设计"，但这个说法只对了一半：Go 的内置 map 从 2012 年 Go 1.0 发布开始，用的一直是前文说的"桶 + 溢出桶"实现，直到 2024/2025 年（Go 1.24）才换成 Swiss Table——中间也用了十几年"旧设计"，并不是一开始就是 Swiss Table。它能换的关键不是"年轻"，而是 Go 从第一天起就做了两个具体的语言设计决策，提前给未来换实现留了自由度：

  • 禁止对 map 元素取地址：Go 规范明确规定 &m[key] 是编译错误，不允许拿到 map 内部某个 value 的指针。这一条从根上避免了 C++ std::unordered_map 那种"用户可能持有一个指向元素的裸指针，实现不能随便挪动内存"的约束，运行时可以自由地把数据搬来搬去。
  • 不保证遍历顺序：Go 的 map 遍历顺序从一开始就是未定义的，运行时还会故意随机化遍历起点，防止代码依赖某个具体顺序。这意味着换一套完全不同的内部布局，不会破坏任何文档承诺的行为。

另外 Go 只有一个官方实现，标准库由 Go 团队自己维护，不像 C++ 那样是 ISO 委员会标准、需要多个厂商的编译器/标准库长期保持 ABI 兼容——换实现纯粹是工程决策，不需要跨厂商达成一致。

不过"没有历史包袱"只是必要条件，不是充分条件：Java 的 HashMap 其实完全没有 C++ 那种指针稳定性问题（Java 里访问对象天生就是通过引用，不存在"取地址"的概念），但至今也没有换成 Swiss Table 类似的实现。这说明语言层面留没留自由度只是前提，最终换不换、什么时候换，还要看有没有人真正投入工程去做。

参考