Go 博客
使用 Swiss Tables 让 Go maps 更快
哈希表是计算机科学中的一个核心数据结构，它为包括 Go 在内的许多语言中的 map 类型提供了实现。
哈希表的概念于 1953 年由 Hans Peter Luhn 在 IBM 的一份内部备忘录中首次提出，该备忘录建议通过将项目放入“桶”中并在桶已包含项目时使用链表处理溢出来加快搜索。如今我们称之为使用链式法的哈希表。
1954 年，Gene M. Amdahl、Elaine M. McGraw 和 Arthur L. Samuel 在编程 IBM 701 时首次使用了“开放寻址”方案。当桶已包含项目时，新项目被放置在下一个空桶中。W. Wesley Peterson 在 1957 年的《随机存取存储器的寻址》中将这一想法正式化并发表。如今我们称之为使用线性探测的开放寻址哈希表。
对于已经存在这么长时间的数据结构，人们很容易认为它们已经“完成”了；认为我们已经了解了关于它们的一切，并且无法再改进了。这不是真的！计算机科学研究在基础算法方面不断取得进展，无论是在算法复杂度方面还是在利用现代 CPU 硬件方面。例如，Go 1.19 将 sort 包从传统的快速排序算法切换到模式挫败快速排序算法，这是一种由 Orson R. L. Peters 提出的新颖排序算法，于 2015 年首次描述。
就像排序算法一样，哈希表数据结构也在不断改进。2017 年，Google 的 Sam Benzaquen、Alkis Evlogimenos、Matt Kulukundis 和 Roman Perepelitsa 提出了一种新的 C++ 哈希表设计，被命名为“Swiss Tables”。2018 年，他们的实现在 Abseil C++ 库中开源。
Go 1.24 包含了一个基于 Swiss Table 设计的内置 map 类型全新实现。在这篇博客文章中，我们将探讨 Swiss Tables 相较于传统哈希表的改进之处，以及将 Swiss Table 设计引入 Go maps 所面临的一些独特挑战。
开放寻址哈希表
Swiss Tables 是一种开放寻址哈希表，所以让我们快速回顾一下基本的开放寻址哈希表是如何工作的。
在开放寻址哈希表中，所有项目都存储在单个支持数组中。我们将数组中的每个位置称为一个槽位（slot）。键所属的槽位主要由哈希函数（hash function） hash(key) 决定。哈希函数将每个键映射到一个整数，相同的键总是映射到相同的整数，而不同的键理想情况下遵循均匀随机的整数分布。开放寻址哈希表的决定性特征是它们通过将键存储在支持数组中的其他位置来解决冲突。因此，如果槽位已经满了（发生冲突（collision）），则使用探测序列（probe sequence）来考虑其他槽位，直到找到一个空槽位。让我们来看一个哈希表示例，看看它是如何工作的。
示例
您可以在下面看到一个 16 个槽位的哈希表支持数组，以及存储在每个槽位中的键（如果有）。此处不显示值，因为它们与此示例无关。
| 槽位 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 键 | 56 | 32 | 21 | 78 |
要插入新键，我们使用哈希函数选择一个槽位。由于只有 16 个槽位，我们需要限制在此范围内，因此我们将使用 hash(key) % 16 作为目标槽位。假设我们要插入键 98，并且 hash(98) % 16 = 7。槽位 7 是空的，所以我们直接将 98 插入那里。另一方面，假设我们要插入键 25，并且 hash(25) % 16 = 3。槽位 3 发生冲突，因为它已经包含键 56。因此我们无法在此处插入。
我们使用探测序列来寻找另一个槽位。有多种众所周知的探测序列。最初且最直接的探测序列是线性探测（linear probing），它只是按顺序尝试连续的槽位。
因此，在 hash(25) % 16 = 3 的示例中，由于槽位 3 被占用，我们将接下来考虑槽位 4，它也被占用。槽位 5 也是如此。最后，我们将到达空槽位 6，在那里存储键 25。
查找遵循相同的方法。对键 25 的查找将从槽位 3 开始，检查它是否包含键 25（不包含），然后继续线性探测，直到在槽位 6 中找到键 25。
此示例使用了具有 16 个槽位的支持数组。如果我们插入超过 16 个元素会发生什么？如果哈希表空间不足，它将增长，通常是通过将支持数组的大小加倍。所有现有条目都将重新插入到新的支持数组中。
开放寻址哈希表实际上不会等到支持数组完全满了才进行增长，因为随着数组变得更满，每个探测序列的平均长度会增加。在上面使用键 25 的示例中，我们必须探测 4 个不同的槽位才能找到一个空槽位。如果数组只有一个空槽位，最坏情况下的探测长度将是 O(n)。也就是说，您可能需要扫描整个数组。已用槽位的比例称为负载因子（load factor），大多数哈希表会定义一个最大负载因子（maximum load factor）（通常为 70-90%），达到此值时，它们将进行增长以避免非常满的哈希表产生的极长探测序列。
Swiss Table
Swiss Table 设计也是一种开放寻址哈希表。让我们看看它如何改进传统的开放寻址哈希表。我们仍然使用单个支持数组进行存储，但我们将把数组划分为每个包含 8 个槽位的逻辑组（group）。（也可以使用更大的组大小。更多内容见下文。）
此外，每个组都有一个 64 位的控制字（control word）用于元数据。控制字中的每个字节对应于组中的一个槽位。每个字节的值表示该槽位是空的、已删除的还是正在使用的。如果正在使用，该字节包含该槽位键的哈希值的低 7 位（称为 h2）。
| 组 0 | 组 1 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 槽位 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 键 | 56 | 32 | 21 | 78 | ||||||||||||
| 64 位控制字 0 | 64 位控制字 1 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 槽位 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| h2 | 23 | 89 | 50 | 47 | ||||||||||||
插入过程如下
- 计算
hash(key)并将哈希值分成两部分：高 57 位（称为h1）和低 7 位（称为h2）。 - 高位（
h1）用于选择第一个要考虑的组：在本例中为h1 % 2，因为只有 2 个组。 - 在一个组内，所有槽位都可以同样用于存储键。我们首先必须确定是否有任何槽位已经包含此键，如果包含，则这是更新而非新的插入。
- 如果没有槽位包含该键，则我们寻找一个空槽位来放置此键。
- 如果所有槽位都不为空，则我们通过搜索下一个组来继续探测序列。
查找遵循相同的基本过程。如果在步骤 4 中找到一个空槽位，那么我们就知道插入操作会使用这个槽位，可以停止搜索了。
步骤 3 是 Swiss Table 魔法发生的地方。我们需要检查组中的任何槽位是否包含所需的键。简单来说，我们可以直接进行线性扫描并比较所有 8 个键。然而，控制字使我们能够更高效地完成此操作。每个字节包含该槽位哈希值的低 7 位（h2）。如果我们确定控制字的哪些字节包含我们正在寻找的 h2，我们将得到一组候选匹配项。
换句话说，我们希望在控制字内进行逐字节的相等性比较。例如，如果我们要查找键 32，其中 h2 = 89，我们想要的操作如下所示。
| 测试字 | 89 | 89 | 89 | 89 | 89 | 89 | 89 | 89 |
| 比较 | == | == | == | == | == | == | == | == |
| 控制字 | 23 | 89 | 50 | - | - | - | - | - |
| 结果 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
这是一个由 SIMD 硬件支持的操作，其中一条指令对较大值（向量（vector））中的独立值执行并行操作。在这种情况下，当没有特殊的 SIMD 硬件时，我们可以使用一组标准的算术和位操作来实现此操作。
结果是一组候选槽位。h2 不匹配的槽位不包含匹配的键，因此可以跳过。h2 匹配的槽位是潜在的匹配项，但我们仍然必须检查完整的键，因为存在冲突的可能性（使用 7 位哈希，冲突概率为 1/128，仍然相当低）。
此操作非常强大，因为我们有效地一次并行执行了探测序列的 8 个步骤。这通过减少我们需要执行的平均比较次数来加快查找和插入的速度。这种对探测行为的改进使得 Abseil 和 Go 的实现都能提高 Swiss Table maps 的最大负载因子，相较于之前的 map，从而降低了平均内存占用。
Go 面临的挑战
Go 的内置 map 类型具有一些不寻常的特性，这对采用新的 map 设计带来了额外的挑战。其中有两个特别棘手。
增量增长
当哈希表达到其最大负载因子时，它需要增长支持数组。通常这意味着下一次插入会将数组大小加倍，并将所有条目复制到新数组中。想象一下向一个拥有 1GB 条目的 map 中插入。大多数插入操作都非常快，但需要将 map 从 1GB 增长到 2GB 的那次插入需要复制 1GB 的条目，这将花费很长时间。
Go 经常用于对延迟敏感的服务器，因此我们不希望内置类型的操作对尾部延迟产生任意大的影响。相反，Go maps 增量增长，这样每次插入都有其必须执行的增长工作量的上限。这限制了单个 map 插入的延迟影响。
不幸的是，Abseil (C++) Swiss Table 设计假设一次性增长，并且探测序列取决于总组数，这使得将其分解变得困难。
Go 的内置 map 通过将每个 map 分割成多个 Swiss Tables 来解决这个问题，增加了另一层间接性。每个 map 不是由单个 Swiss Table 实现整个 map，而是由一个或多个独立的表组成，每个表覆盖键空间的一个子集。单个表最多存储 1024 个条目。哈希值中可变数量的高位用于选择键属于哪个表。这是一种可扩展哈希（extendible hashing）的形式，其中使用的位数根据需要增加，以区分总表的数量。
在插入过程中，如果单个表需要增长，它会一次性完成，但其他表不受影响。因此，单次插入的上限是将一个 1024 条目表增长为两个 1024 条目表所需的延迟，即复制 1024 个条目。
迭代期间的修改
许多哈希表设计，包括 Abseil 的 Swiss Tables，禁止在迭代期间修改 map。Go 语言规范明确允许在迭代期间进行修改，并具有以下语义
- 如果在到达某个条目之前将其删除，该条目将不会被产生。
- 如果在到达某个条目之前对其进行更新，将产生更新后的值。
- 如果添加了新条目，则可能会或可能不会被产生。
哈希表迭代的一种典型方法是简单地遍历支持数组并按照它们在内存中的布局顺序产生值。这种方法与上述语义相悖，最显著的原因是插入可能会导致 map 增长，从而打乱内存布局。
我们可以通过让迭代器保持对其当前正在迭代的表的引用来避免增长期间打乱布局的影响。如果在迭代期间该表发生增长，我们将继续使用表的旧版本，因此继续按照旧内存布局的顺序提供键。
这与上述语义兼容吗？增长后添加的新条目将完全丢失，因为它们仅被添加到增长后的表，而不是旧表。这没问题，因为语义允许不产生新条目。然而，更新和删除是一个问题：使用旧表可能会产生过时或已删除的条目。
通过仅使用旧表来确定迭代顺序来解决这个边缘情况。在实际返回条目之前，我们会查阅增长后的表，以确定条目是否仍然存在，并检索最新值。
这涵盖了所有核心语义，尽管还有更多未在此处讨论的细小边缘情况。最终，Go maps 对迭代的宽松性导致迭代成为 Go map 实现中最复杂的部分。
未来工作
在微基准测试中，map 操作比 Go 1.23 快高达 60%。确切的性能提升因 map 操作和用途的多样性而差异很大，并且某些边缘情况相较于 Go 1.23 会有所退步。总体而言，在完整的应用程序基准测试中，我们发现 CPU 时间的几何平均改进约为 1.5%。
对于未来的 Go 版本，我们还有更多 map 改进想要研究。例如，我们或许能够提高不在 CPU 缓存中的 map 操作的局部性。
我们还可以进一步改进控制字比较。如上所述，我们有一个使用标准算术和位操作的可移植实现。然而，一些架构具有直接执行此类比较的 SIMD 指令。Go 1.24 已经对 amd64 使用了 8 字节 SIMD 指令，但我们可以将支持扩展到其他架构。更重要的是，虽然标准指令对最多 8 字节的字进行操作，但 SIMD 指令几乎总是支持至少 16 字节的字。这意味着我们可以将组大小增加到 16 个槽位，并并行执行 16 个哈希比较而不是 8 个。这将进一步减少查找所需的平均探测次数。
致谢
基于 Swiss Table 的 Go map 实现历时已久，并涉及众多贡献者。我要感谢 YunHao Zhang (@zhangyunhao116)、PJ Malloy (@thepudds) 和 @andy-wm-arthur 构建了 Go Swiss Table 实现的初始版本。Peter Mattis (@petermattis) 将这些想法与解决上述 Go 挑战的方案相结合，构建了 github.com/cockroachdb/swiss，一个符合 Go 规范的 Swiss Table 实现。Go 1.24 内置 map 实现很大程度上基于 Peter 的工作。感谢所有社区贡献者！