快速学习 Go 1.24 的 Swiss Tables
小楼MrRoshi约 10 分钟上周，Go 发布了 1.24.0 版本，其中最重要的更新莫过于 map 的实现改成了 Swiss Tables，release note 中是这样描述的：
Several performance improvements to the runtime have decreased CPU overheads by 2–3% on average across a suite of representative benchmarks. Results may vary by application. These improvements include a new builtin map implementation based on Swiss Tables, more efficient memory allocation of small objects, and a new runtime-internal mutex implementation.
第一次听到 Swiss Tables，打算用大模型来快速学习一下，以下回答均来自 DeepSeek。
什么是 Swiss Tables
Swiss Tables 是一种高效的哈希表实现，最初由 Google 的 Abseil 库引入。它采用了先进的哈希表设计，具有以下特点：
开放寻址：Swiss Tables 使用开放寻址法（Open Addressing）来处理哈希冲突，这意味着所有键值对都存储在表中，而不是使用链表或树结构。 SIMD 优化：Swiss Tables 利用单指令多数据流（SIMD）指令来加速查找操作，这在现代CPU上非常高效。 元数据分离：Swiss Tables 将键值对和元数据（如哈希值的一部分）分开存储，这样可以更高效地进行查找和插入操作。
开放寻址的原理是什么
开放寻址是一种处理哈希冲突的方法，与链地址法（Chaining）不同，开放寻址将所有键值对都存储在哈希表本身，而不是使用链表或其他数据结构来存储冲突的键值对。当发生哈希冲突时，开放寻址会通过某种探测序列来寻找下一个可用的槽位（slot），直到找到空槽位为止。
开放寻址的步骤
计算哈希值：
对一个键（key）计算哈希值，得到一个初始的槽位索引：
index = hash(key) mod table_size
检查槽位：
如果该槽位为空，则直接插入键值对。 如果该槽位已被占用，则进入探测序列。
探测序列：
探测序列是一个固定的规则，用于决定如何寻找下一个槽位。常用的探测方法有：
线性探测：从当前槽位开始，依次检查下一个槽位。计算公式为：
index = (index+i) mod table_size
其中 i 是探测次数。
二次探测：使用二次函数来跳过多个槽位，减少聚集现象。计算公式为：
index = (index + c1 *i + c2 * i^2) mod table_size
c1 和 c2 是常数。
双重哈希：使用第二个哈希函数来计算步长。计算公式为：
index = (index + i * hash2(key)) mod table_size
其中 hash2 是第二个哈希函数。
插入或查找：
根据探测序列找到空槽位后，插入键值对。 查找时，按照同样的探测序列依次检查槽位，直到找到目标键或遇到空槽位（说明键不存在）。
开放寻址的优点
内存效率高：所有数据都存储在哈希表中，不需要额外的数据结构（如链表）来存储冲突的键值对。 缓存友好：由于数据连续存储，缓存命中率较高，访问速度更快。
开放寻址的缺点
聚集现象：如果哈希表过于填充，可能会导致聚集现象（Clustering），即大量的键集中在某个区域，导致探测序列变长，性能下降。 删除操作复杂：删除一个键值对时，不能直接置空槽位，否则会影响后续查找。通常采用“标记删除”的方法，但这会增加表的复杂度。
怎么解决开放寻址的聚集现象
聚集现象分为两种：
初级聚集（Primary Clustering）：线性探测导致的数据集中在某个区域。 次级聚集（Secondary Clustering）：不同键的探测路径重合导致的数据集中在某些路径上。
解决方法：
改进探测序列：
二次探测：使用二次函数跳过多个槽位，减少聚集现象。 双重哈希：使用第二个哈希函数计算步长，避免探测路径重合。
动态调整表大小：
当填充因子（Load Factor）超过一定阈值时（如0.7），对哈希表进行扩容（Rehashing）。扩容后重新分配所有键值对到新的更大的表中，从而减少聚集现象的发生。
使用更好的哈希函数：
选择高质量的哈希函数，使得键值在表中均匀分布，减少聚集的可能性。
怎么解决删除操作复杂问题
删除操作的复杂性在于删除一个键值对后，不能直接置空槽位，否则会导致后续查找时探测序列中断，无法找到目标键。
解决方法：
标记删除（Tombstone）
删除时不在物理上移除键值对，而是用特殊的标记（如“已删除”标记）代替。这样可以保留探测序列的完整性。
查找时：
遇到标记删除的槽位，继续探测。 遇到空槽位，说明键不存在。
插入时：
遇到标记删除的槽位，可以将新键值对插入到该槽位。
定期清理标记删除的槽位
当标记删除的槽位数量达到一定阈值时，触发一次重新整理哈希表（Rehashing），将所有有效键值对重新插入到新的表中，同时清除所有标记删除的槽位。
SIMD 优化是什么
SIMD（Single Instruction, Multiple Data，单指令多数据流） 是一种并行计算技术，允许在一条指令中同时对多个数据执行相同操作。现代 CPU 通常支持 SIMD 指令集（如 Intel 的 SSE、AVX，ARM 的 NEON 等），这些指令集可以显著加速数据密集型计算任务。
SIMD 的基本原理
单指令多数据： 传统指令是“单指令单数据”（SISD），即一条指令处理一个数据。 SIMD 指令则是“单指令多数据”，即一条指令可以同时处理多个数据。 向量化操作： SIMD 将一组数据打包为一个向量（Vector），然后对向量中的数据同时进行操作。 例如，使用一条 SIMD 指令可以对4个浮点数同时进行加法运算，而不是逐个处理。
SIMD 的应用场景
数学运算：矩阵乘法、向量加法、点积等数值计算任务可以明显受益于SIMD优化。 图像处理：图像滤波、像素操作等任务中，SIMD 可以同时处理多个像素。 哈希表查找：在哈希表（如 Swiss Tables）中，SIMD 可以同时检查多个槽位，快速判断哪些槽位是空的或匹配的，从而加速查找操作。 数据包处理：在网络编程中，SIMD 可以高效地处理大量数据包。
SIMD 在 Swiss Tables 中的优化
Swiss Tables 利用 SIMD 加速哈希表的核心操作（如插入、查找），以下是具体优化方式：
同时检查多个槽位：使用SIMD指令同时检查多个槽位的元数据（如哈希值的一部分），确定哪些槽位可能匹配目标键。
例如：
- 对8个槽位的元数据加载到 SIMD 寄存器。
- 使用一条指令同时比较这8个元数据与目标哈希值。
减少分支预测：SIMD 减少了逐一遍历槽位的需求，避免了分支预测失败的性能损失。
提高缓存利用率：SIMD 操作通常对连续的内存区域进行访问，充分利用 CPU缓存，减少内存访问延迟。
SIMD 优化的示例
假设有一个哈希表，我们需要查找某个键的位置。普通线性探测的伪代码如下：
for (int i = 0; i < table_size; i++) {
if (table[i] == target_key) {
return i;
}
}
使用 SIMD 优化后，可以同时对多个槽位进行检查：
__m128i target = _mm_set1_epi32(target_key);
for (int i = 0; i < table_size; i += 4) {
__m128i data = _mm_loadu_si128((__m128i*)&table[i]);
__m128i cmp = _mm_cmpeq_epi32(data, target);
int mask = _mm_movemask_epi8(cmp);
if (mask != 0) {
return i + __builtin_ctz(mask) / 4;
}
}
在该示例中：
_mm_set1_epi32：将目标键复制到SIMD寄存器的所有位置。 _mm_cmpeq_epi32：同时比较4个槽位的键与目标键。 _mm_movemask_epi8：将比较结果转换为掩码，快速确定匹配位置。
元数据分离是怎样提高性能的
元数据分离的实现
元数据的内容：
元数据主要包括哈希值的一部分（如哈希值的高位）和一些状态标记（例如槽位是否为空、是否被删除等）。 在 Swiss Tables 中，每个槽位的元数据通常是一个字节，存储了哈希值的部分信息。
元数据与键值对的存储分离：
元数据：存储在一个连续的内存区域（数组）中，结构紧凑，便于快速访问。 键值对：存储在另一个独立的内存区域（数组）中，每个槽位对应存储实际的键和值。
通过索引将元数据和对应的键值对关联起来。 例如，假设表大小为 N
Metadata: [M1, M2, M3, ..., MN]
Key-Value: [KV1, KV2, KV3, ..., KVN]
其中 Mi 是第 i 个槽位的元数据，KVi 是第 i 个槽位的键值对。
元数据分离为什么能提高性能
减少内存访问开销：
元数据通常比键值对小（如一个字节），存储在一个连续的内存区域中。这样可以充分利用 CPU 缓存的局部性，减少内存访问延迟。
在查找操作中，遍历元数据的速度远比遍历键值对要快，因为元数据占用更少的内存带宽。
SIMD 优化：
元数据存储在一个紧凑的数组中，很容易使用 SIMD 指令同时检查多个槽位的元数据。
例如，可以将 8 个字节的元数据加载到一个 SIMD 寄存器中，用一条指令同时检查哪些槽位匹配目标哈希值。
快速过滤不匹配的槽位：
在查找时，首先通过元数据快速过滤掉不匹配的槽位，避免频繁访问键值对。 这种方法可以减少不必要的内存访问，提高查找效率。 更高效的删除和插入：
在删除操作中，只需标记元数据为“已删除”，而无需实际移除键值对。 在插入操作中，可以通过元数据快速找到空槽位，而不需要检查整个键值对数组。
元数据分离的具体示例
假设有一个哈希表，存储了以下键值对，并且使用元数据分离的设计：
查找操作：
计算目标键的哈希值，提取高位（例如，目标键的哈希值高位是 0x12）。 使用 SIMD 指令扫描元数据数组，快速找到匹配的槽位（例如，槽位 0 匹配）。 仅对匹配的槽位访问键值对数组，进行精确匹配。
插入操作：
计算新键的哈希值，提取高位。 扫描元数据数组，找到第一个空槽位（例如，槽位 1）。 将元数据写入槽位 1，并将键值对存储到对应的键值对数组。
go 1.24.0 之前 map 用的是什么数据结构
在 Go 1.24.0 之前，Go 语言的 map 实现是基于 哈希表（Hash Table），但它的设计与 Swiss Tables 不同，采用的是传统的链地址法（Chaining）来处理哈希冲突。以下是 Go 1.24.0 之前 map 数据结构的详细信息：
哈希表的基本结构
Go 的 map 由以下几个核心组件组成：
桶（Bucket）：哈希表中的基本存储单元，每个桶可以存储多个键值对。 哈希函数：用于计算键的哈希值，确定键值对存储的位置。 链地址法（Chaining）：用于处理哈希冲突，每个桶内部使用链表（或类似结构）来存储冲突的键值对。
桶的设计
在 Go 1.24.0 之前的 map 实现中，每个桶是一个固定大小的结构体，内部包含：
键值对数组：每个桶可以存储 8 个键值对（key-value pairs）。 溢出指针：如果桶中的键值对数量超过 8 个，则使用溢出桶（Overflow Bucket）来存储额外的键值对，溢出桶通过链表链接。
例如，一个桶的结构如下：
type bmap struct {
tophash [8]uint8// 哈希值的高位，用于快速匹配
keys [8]Key // 键数组
values [8]Value // 值数组
overflow *bmap // 指向溢出桶
}
哈希冲突的处理
当两个键的哈希值映射到同一个桶时，Go 的 map 使用链地址法来处理冲突：
桶内查找： 首先检查桶的 tophash 数组，快速过滤掉不匹配的键。 如果 tophash 匹配，再检查实际的键值对。 溢出桶查找： 如果桶内的键值对数量超过 8 个，则通过 overflow 指针遍历溢出桶，直到找到匹配的键或遍历完所有溢出桶。
Go 1.24.0 之前 map 的缺点
尽管这种设计在大多数场景下表现良好，但也存在一些性能问题：
内存访问效率低：由于键值对和溢出桶的链表结构，查找时需要多次访问内存，导致缓存命中率较低。 哈希冲突处理不够高效：当哈希冲突较多时，链地址法会导致链表变长，查找性能下降。 动态扩容开销大：哈希表在扩容时需要重新分配所有键值对，开销较大。
为什么不采用 Java 的方案
在讨论 Go 为什么不采用 Java 的哈希表方案之前，我们先了解 Java 的哈希表实现（如 HashMap）的核心特点，然后再分析 Go 的选择原因。
Java 的哈希表方案：Chain Hashing
Java 的 HashMap 采用了 链地址法（Chain Hashing） 来处理哈希冲突。其核心设计如下：
桶结构：每个桶是一个链表或红黑树（在链表长度超过阈值时转换为红黑树），键值对存储在链表或树节点中。 哈希冲突处理：当哈希冲突发生时，将冲突的键值对存储在同一个桶的链表或树中。 动态扩容：当哈希表的负载因子（Load Factor）超过阈值时，触发扩容操作，重新分配所有键值对。
Go 为什么不采用 Java 的方案？
Go 是一种系统编程语言，设计目标之一是高效执行，尤其在高并发场景下性能要求更高。Java 的链地址法虽然简单可靠，但当哈希冲突较多时，链表的查找时间复杂度会退化为 O(n) 或 O(logn)
Go 语言的设计哲学是简单性和可预测性：
虽然红黑树可以优化查找性能（降至 O(logn)，但其实现复杂，插入和删除操作的维护成本较高。
Go 需要一种更轻量、更适合系统编程的哈希表实现。