Cpp

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 位控制字）。查找时： ...