Swiss Table：Google 的 SIMD 加速哈希表
内容提要
Google 的 Swiss Table 是一种高效的哈希表实现，利用 SIMD 指令实现 16 路并行探测，性能比传统的 std::unordered_map 快 2 倍以上。它通过控制字节优化内存访问，减少缓存未命中率，提升查找效率，并采用开放寻址策略，解决了链式哈希的内存开销和性能瓶颈问题。
关键要点
-
Google 的 Swiss Table 是一种高效的哈希表实现，利用 SIMD 指令实现 16 路并行探测，性能比传统的 std::unordered_map 快 2 倍以上。
-
Swiss Table 通过控制字节优化内存访问，减少缓存未命中率，提升查找效率。
-
采用开放寻址策略，解决了链式哈希的内存开销和性能瓶颈问题。
-
传统的 std::unordered_map 由于标准接口约束，导致结构性问题，性能较差。
-
Swiss Table 的设计通过将元素匹配判断从逐个比较变为 SIMD 批量筛选，显著提高了查找速度。
-
控制字节的设计使得状态检查和哈希匹配可以在一次 SIMD 加载中完成，极大提高了效率。
-
Swiss Table 使用三角探测策略，确保探测序列不会在 group 之间循环，优化了查找过程。
-
在高负载因子下，Swiss Table 仍能保持良好的查找性能，平均每次查找只需探测 1-2 个 group。
-
Swiss Table 的内存效率极高，每个元素的实际内存开销仅为约 18.3 字节。
-
Swiss Table 的设计理念是顺应现代 CPU 的特性，充分利用 SIMD 和缓存机制，提升性能。
延伸解读
Swiss Table 的设计动机
Swiss Table 的设计源于 Google 对其 C++ 服务中 std::unordered_map 性能瓶颈的深入分析。尽管 1% 的 CPU 时间看似不多，但在 Google 的规模下，这意味着数以万计的 CPU 核心在进行哈希表查找。通过优化哈希表的实现，Swiss Table 不仅提高了查找速度，还降低了内存占用，展现了对现代 CPU 特性的深刻理解。
内存效率与性能的平衡
Swiss Table 的内存效率极高，每个元素的实际内存开销约为 18.3 字节，相比于 std::unordered_map 的 48 字节，显著降低了内存使用。这种设计使得在高负载因子下，Swiss Table 仍能保持良好的查找性能，平均每次查找只需探测 1-2 个 group，体现了在性能与内存使用之间的有效平衡。
与传统哈希表的比较
与传统的 std::unordered_map 相比，Swiss Table 通过开放寻址和 SIMD 指令实现了更高的查找效率。传统哈希表由于链式哈希的结构性问题，导致内存访问延迟和性能瓶颈，而 Swiss Table 的设计则有效避免了这些问题，尤其在高负载情况下，展现出更优的性能表现。
延伸问答
Swiss Table 是什么？
Swiss Table 是 Google 开发的一种高效哈希表实现，利用 SIMD 指令实现 16 路并行探测，性能比传统的 std::unordered_map 快 2 倍以上。
Swiss Table 如何优化内存访问？
Swiss Table 通过控制字节优化内存访问，减少缓存未命中率，从而提升查找效率。
Swiss Table 的查找性能如何？
在高负载因子下，Swiss Table 平均每次查找只需探测 1-2 个 group，查找速度显著提高。
Swiss Table 采用了什么探测策略？
Swiss Table 使用三角探测策略，确保探测序列不会在 group 之间循环，优化了查找过程。
Swiss Table 如何处理删除操作？
Swiss Table 将删除的槽位标记为 DELETED（tombstone），以避免截断其他元素的探测序列。
Swiss Table 的内存效率如何？
Swiss Table 的内存效率极高，每个元素的实际内存开销仅为约 18.3 字节。
