主要内容为 Go 在1.24之后所采用的新的 Map 底层数据结构 SwissTable 的原理记录。

Go 在2025年2月11日发布了新版本1.24.0，里面比较重大的更新就是支持弱指针和将 map 的默认底层实现替换为 SwissTable。后者是这篇记录的主题，前者稍微记录一下：

1 弱指针（weak 包）

官方文档：https://pkg.go.dev/weak

弱指针（weak pointer），是一个存在了很久的概念。它是一种特殊的指针类型，它可以指向一个对象，但是不会增加该对象的引用计数，也不会阻止 GC 来回收该对象。如果弱指针指向的对象被 GC 回收，那么获取值会得到 nil。它的主要作用，一来是能够防止指针循环引用，从而使 GC 无法回收内存，继而导致内存泄漏；二来利用弱指针不会影响 GC 这一点，可以更好地手动控制对象的生命周期（个人认为后者作用会更明显）。

2 在 SwissTable 之前

map，或者叫哈希表（目标是读写时间复杂度O(1)的键值对存储结构），都是由两个部分构成：哈希函数，存储结构。虽然理想中的哈希函数，是应该不存在哈希碰撞，并且哈希值的每一位出现概率都是均等的。但是这毕竟是理想，现实里，存储结构也要面对哈希碰撞的问题。在 SwissTable 之前，解决哈希碰撞的存储结构方案有这么两种（也是八股常客）：

• 开放定址法：如果将存储结构看作一个数组，值存在数组上（权且管这个位置叫 slot），那么在发生哈希碰撞后，就会已存在的值的存储位置向后寻找（按寻找的方式，还有其他的方法。特别地，向后寻找的被称为线性探测法），直到能够找到存储的 slot。
• 链表法：仍然将存储结构看作一个数组。在发生哈希碰撞后，所有发生哈希碰撞的值会以链表的形式存在对应的 slot 上。

Go 在 SwissTable 之前，我认为 Map 使用的方式算是加强版的，混合了部分链表法思路的开放定址法，详见https://www.misaka19327.cc/post/104

3 SwissTable

SwissTable 首次被提出是在2017年的 CppCon 大会上，在2022年被字节提 issue，建议使用它作为 Map 的底层数据结构。

SwissTable 的核心思想仍然是改进线性探测法，只是将 slot 的关键信息提取出来作为元数据进行读写，比直接读取整个 slot 更快。

3.1 结构

SwissTable 的结构如图：

（对实际内存进行简化，看个意思）

SwissTable 主要由两部分构成：Control Bytes 和对应的 slots 数组。其中，Control Bytes 的每个字节都对应后面的一个 slot，字节内部存储的值，一个是指示 slot 的状态，另外就是在 slot 有值时，存储其 hash 得来的特征值。

图里没有写出来的有两部分，一个是 Group。它不是一个具体的结构，而是由8（不支持 simd 指令的平台）/16（支持 simd 指令的平台）个连续的控制字节组成。按图中所得，对键进行哈希后得到的哈希值，前57位的值（偏移量）就用来决定 slot 位置，而 slot 对应的控制字节的位置之后的7/15个控制字节就是一个 Group。

另外一个是，按照上面的说明，当决定 slot 位置定到了 Control Bytes 的尾部时，对应的控制字节之后的控制字节们的数量可能不足以支撑一个 Group。所以，Control Bytes 尾部也会复制头部的信息。

3.2 查

按照上面对 Group 概念的说明，可知一个键的哈希值是可以落到一个长为8/16的 Group 上的，之后就是怎么找到对应的 slot。如果不存在哈希碰撞，那皆大欢喜，第一个控制字节所对应的 slot 就是要找的值。如果存在哈希碰撞，按照线性探测法，应该是对 Group 中的每个控制字节所对应的 slot 都挨个取出来比较 key。但是 SwissTable 在这里做了优化。它利用了 simd 指令并行计算的特点，将特征值和16个控制字节同时进行比较，得到的16个字节再压缩为 uint32，直接取尾部0的数量，即可得到要找的 slot 的位置。如果当前 Group 没能找到值，那么会顺序移动到下一个 Group，再一次整体比较，直至找到对应值或到结束位。

（H2 即为特征值）

事实上，SwissTable 会首先过滤掉特征值不同的控制字节，再利用上述的方法快速找到要检查的 slot 位置。如果检查完第一个 slot 发现 key 不对，那么就可以将 uint32 的结果的检查完的 slot 所对应的1用位运算置零，再次计算尾随0的数量，即可找到下一个要检查的 slot。

增删的步骤基本上和查是差不多的，都是按这个方法定 Group，如果 Group 已满/没找到就顺延到下一个 Group，直到找到空 slot/目标键值对，写入数据/释放数据，并且修改对应的控制字节。

3.3 结束

我认为，SwissTable 能够和 Go 原来的 Map 拉开差距，主要有几个点：

1. SwissTable 利用这个 simd 指令，使得每次找数据的时候都是同时批量地找，比原来的 Map 在 bucket 里的 tophash 找快。并且用的是位运算，比等值比较快。当然，如果不支持 simd 指令，那么性能也会有所下降。
2. 内存紧凑，比起原来的 Map，同一哈希值下的 bucket 是链表组织（内存松散），能够提高缓存命中率（对 CPU 来说）。

Go runtime 下，原来的 map.go 变成了 map_swiss.go 和 map_noswiss.go，原来的实现还保留着，应该是可以通过 go build 的参数使用原来的底层结构。只是 map_swiss.go 没看懂，不好看源码了，主要是我找不到它的 linkname 链接的目标是谁。