1 简介

编程语言Go 1.24 中引入了 Swiss Table 作为 map 数据类型的新底层实现，这是 Go 语言发展中的一个重要改进。

这个实现借鉴了现代编程语言（如 C++ 和 Rust）中的哈希表优化技术，尤其是来自 Google 的 SwissTable 实现（在 C++ 的 absl::flat_hash_map 和 Rust 的 HashMap 中应用）。

这次更改提升了性能、减少了内存使用，并提高了并发场景下的稳定性。

2 Swiss Table 实现概述

Swiss Table 的核心思想是在 数据局部性 和 高效探测策略 上做了深度优化。

• 1.1 基本设计理念：

控制字节（control byte）数组：

每个桶都使用一个 control byte 来标记其状态（空、已删除、哈希前缀等）。

控制字节被紧凑地存储在一块连续内存中，从而实现高效 SIMD 操作和缓存友好。

SIMD 扫描优化：

借助 SIMD 指令可以在一次操作中并行比较多个控制字节，大大加快查找速度（Go 目前未直接使用 SIMD，但内存布局与 SIMD 优化兼容）。

桶内小数组（bucketized）结构：

每个 bucket 内部容纳多个键值对（Go 默认是 8 个），结合开地址法的探测策略提高缓存命中率。

删除标记与再散列避免链化（tombstones）：

删除元素后保留控制字节标记，避免破坏查找路径，延迟清理。

• 1.2 相比旧实现（Go <1.24）

  特性 Go 旧 map 实现（before 1.24） Go 1.24 Swiss Table 实现
  探测策略 链表式桶链 + 位图分配（hmap） 开放地址探测 + 控制字节数组
  空间局部性 较差，访问多次内存 高，连续探测（bucket & control）
  删除操作 直接移除 使用 tombstone 标记
  SIMD 支持 无 内存布局对 SIMD 友好
  性能（特别是查找） 中等 显著提升
  并发修改时稳定性 容易退化 更强健的迭代器语义

3 与 Python 的 dict 实现的根本差异

Python 的 dict（自 3.6 之后）也采用了现代哈希表的设计，但其原理和目标与 Go 有所不同。

• Python dict 的关键设计点（基于 CPython 3.6+）

分离键值数组 + 索引表（split table）：

索引表中只存储 key/value 对应的偏移，而真正的键值存储在另一个数组中。

这样便于共享 key 值（尤其用于类属性 dict）。

探测方式：open addressing + perturbation：

使用“扰动（perturbation）”机制进行开放地址线性探测，确保避免聚集。

保序（insertion order）保证：

从 3.6 开始，Python 保证 dict 中键值对插入顺序。

借助 compacting 索引表保持顺序，结合引用计数优化性能。

缓存性能较低，但适合灵活动态对象模型。

4 小结

核心对比（Swiss Table vs Python dict）

特性/设计点			Go 1.24 Swiss Table 实现			Python dict 实现
控制字节			有（紧凑连续）						无（索引表中使用空槽标记）
探测方式			开地址探测 + 			Grouped Probing	开地址探测 + PERTURB shift
保序					无						有（自 Python 3.6+）
内存结构			紧凑连续的 buckets 和控制数组			分离索引表 + entries 表
删除策略			使用 tombstone 标记				删除后 compaction
并发适应性			更强健迭代器行为			不适用于多线程直接共享
实现目标			高性能通用哈希表			灵活性 + 插入顺序兼容性

Go 1.24 的 Swiss Table 实现是一次面向性能和现代硬件特性的重大升级：

对于大多数典型负载，它提供更快的查找、更小的内存占用。

借助对缓存和指令流水的理解（如控制字节、线性探测、SIMD 支持），Go map 结构已经跻身顶级语言中最优的哈希表实现之一。

与 Python dict 相比，Go map 更强调性能与结构稳定性，而 Python 的 dict 更强调灵活性与兼容性（尤其是对象模型的支持）。