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 开发的一种高效哈希表实现，利用 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 字节。
