哈希表是计算机科学中的一种核心数据结构，它实现了许多语言中 Map（映射）类型的底层机制，Go 也不例外。

哈希表的概念由 Hans Peter Luhn 于 1953 年首次在 IBM 的一篇内部备忘录中 提出。他建议通过将项目放入“桶”（buckets）中，并在桶已满时使用链表处理溢出，来加速搜索。今天，我们称之为“链式哈希表”。

1954 年，Gene M. Amdahl、Elaine M. McGraw 和 Arthur L. Samuel 在编写 IBM 701 的程序时，首次使用了“开放寻址”方案。当一个桶已满时，新项目被放置在下一个空桶中。这个想法在 1957 年由 W. Wesley Peterson 在其论文 “Addressing for Random-Access Storage” 中进行了形式化和发表。今天，我们称之为“线性探测开放寻址哈希表”。

对于存在如此悠久历史的数据结构，人们很容易认为它们已经“完成”，即我们已经了解了关于它们的一切，并且无法再进行改进。事实并非如此！计算机科学研究在基础算法方面不断取得进步，这体现在算法复杂度的提升以及对现代 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 包含了对内置 Map 类型的一个全新实现，该实现基于 Swiss Table 设计。在这篇博文中，我们将探讨 Swiss Tables 如何改进传统的哈希表，以及将 Swiss Table 设计引入 Go Map 时所面临的一些独特挑战。

开放寻址哈希表

Swiss Tables 是一种开放寻址哈希表。让我们快速回顾一下基本开放寻址哈希表的工作原理。

在开放寻址哈希表中，所有条目都存储在一个单独的底层数组中。我们将数组中的每个位置称为一个槽（slot）。一个键所属的槽主要由哈希函数 `hash(key)` 决定。哈希函数将每个键映射到一个整数，同一个键总是映射到同一个整数，而不同的键理想情况下会遵循均匀的随机整数分布。开放寻址哈希表的关键特性是，它通过将键存储在底层数组的其他位置来解决冲突。因此，如果槽已满（发生冲突），则会使用探测序列（probe sequence）来检查其他槽，直到找到一个空槽。让我们通过一个示例哈希表来看看这是如何工作的。

示例

下面是一个 16 个槽的哈希表底层数组，以及每个槽中存储的键（如果有）。值未显示，因为它们与本示例无关。

要插入新键，我们使用哈希函数选择一个槽。由于只有 16 个槽，我们需要将键限制在此范围内，因此我们将使用 `hash(key) % 16` 作为目标槽。假设我们要插入键 `98`，且 `hash(98) % 16 = 7`。槽 7 是空的，所以我们直接将 98 插入此处。另一方面，假设我们要插入键 `25`，且 `hash(25) % 16 = 3`。槽 3 发生了冲突，因为它已经包含键 56。因此，我们不能在此插入。

我们使用探测序列来查找另一个槽。有许多著名的探测序列。最初且最直接的探测序列是线性探测，它按顺序尝试连续的槽。

因此，在 `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 的设计也是一种开放寻址哈希表。让我们看看它如何改进传统的开放寻址哈希表。我们仍然有一个单独的底层数组用于存储，但我们将数组分成逻辑的组（groups），每组 8 个槽。（也可以使用更大的组大小。更多内容将在下面讨论。）

此外，每个组都有一个 64 位控制字（control word）用于存储元数据。控制字中的每个字节对应组中的一个槽。每个字节的值表示该槽是空、已删除还是在使用中。如果正在使用，则该字节包含该槽键的哈希值的最低 7 位（称为 `h2`）。

插入过程如下：

1. 计算 `hash(key)` 并将其分成两部分：高 57 位（称为 `h1`）和低 7 位（称为 `h2`）。
2. 高位（`h1`）用于选择要考虑的第一个组：在本例中为 `h1 % 2`，因为只有 2 个组。
3. 在一个组内，所有槽都有可能容纳该键。我们必须首先确定是否有槽已包含此键，在这种情况下，这是一个更新而不是新的插入。
4. 如果没有槽包含该键，那么我们寻找一个空槽来放置该键。
5. 如果没有空槽，则继续探测序列，搜索下一个组。

查找遵循相同的基本过程。如果在步骤 4 中找到一个空槽，那么我们就知道插入会使用该槽，并可以停止搜索。

步骤 3 是 Swiss Table 的神奇之处。我们需要检查组中的任何槽是否包含所需的键。朴素的做法是进行线性扫描并比较所有 8 个键。但是，控制字使我们能够更有效地做到这一点。每个字节包含该槽的哈希值（`h2`）的最低 7 位。如果我们确定控制字中的哪些字节包含我们正在寻找的 `h2`，我们将得到一组候选匹配项。

换句话说，我们想要在控制字内进行逐字节的相等性比较。例如，如果我们正在查找键 32，其中 `h2 = 89`，我们想要的操作如下所示。

这是SIMD硬件支持的操作，其中单个指令对较大值（向量）内的独立值执行并行操作。在这种情况下，当没有特殊 SIMD 硬件可用时，我们可以使用一组标准的算术和位运算来实现此操作。

结果是一组候选槽。`h2` 不匹配的槽不包含匹配的键，因此可以跳过。`h2` 匹配的槽是潜在匹配，但我们仍然必须检查整个键，因为存在冲突的可能性（使用 7 位哈希，冲突的概率为 1/128，仍然很低）。

这项操作非常强大，因为我们实际上同时并行地执行了探测序列的 8 个步骤。这通过减少我们需要执行的平均比较次数来加速查找和插入。这种对探测行为的改进使得 Abseil 和 Go 的实现都能提高 Swiss Table Map 相对于之前 Map 的最大负载因子，从而降低了平均内存占用。

Go 的挑战

Go 的内置 Map 类型有一些不寻常的特性，给采用新的 Map 设计带来了额外的挑战。其中有两个特别棘手。

增量式增长

当哈希表达到其最大负载因子时，它需要增长底层数组。通常这意味着下一次插入会将数组大小加倍，并将所有条目复制到新数组。想象一下插入一个包含 1GB 条目的 Map。大多数插入都非常快，但需要将 Map 从 1GB 增长到 2GB 的那次插入将需要复制 1GB 的条目，这将花费很长时间。

Go 经常用于对延迟敏感的服务器，因此我们不希望内置类型的操作对尾部延迟产生任意大的影响。相反，Go Map 是增量式增长的，这样每次插入的增长工作都有一个上限。这限制了单次 Map 插入的延迟影响。

不幸的是，Abseil (C++) Swiss Table 设计假定一次性增长，并且探测序列依赖于总组数，这使得拆分变得困难。

Go 的内置 Map 通过增加另一层间接性来解决此问题，将每个 Map 分成多个 Swiss Tables。每个 Map 由一个或多个独立表组成，这些表覆盖键空间的一部分，而不是由一个 Swiss Table 实现整个 Map。单个表最多存储 1024 个条目。哈希中可变数量的高位用于选择键所属的表。这是一种可扩展哈希的形式，其中使用的位数会随着区分表总数的需求而增加。

在插入过程中，如果单个表需要增长，它将一次性完成，但其他表不受影响。因此，单次插入的上限是增长一个 1024 个条目的表到两个 1024 个条目的表的延迟，复制 1024 个条目。

迭代期间的修改

许多哈希表设计，包括 Abseil 的 Swiss Tables，都禁止在迭代期间修改 Map。Go 语言规范明确允许在迭代期间进行修改，并具有以下语义：

• 如果在到达条目之前删除该条目，则不会生成该条目。
• 如果在到达条目之前更新该条目，则会生成更新后的值。
• 如果添加了新条目，则可能生成也可能不生成。

哈希表迭代的一种典型方法是简单地遍历底层数组，并按照它们在内存中的布局顺序生成值。这种方法不符合上述语义，最明显的原因是插入可能会导致 Map 增长，从而打乱内存布局。

通过让迭代器保持对其当前正在迭代的表的引用，我们可以避免增长期间的内存布局混乱的影响。如果该表在迭代期间增长，我们将继续使用旧版本的表，从而继续按照旧的内存布局顺序传递键。

这与上述语义是否兼容？增长后添加的新条目将完全被忽略，因为它们仅添加到增长后的表中，而不是旧表中。没关系，因为语义允许不生成新条目。但是，更新和删除会带来问题：使用旧表可能会生成过时或已删除的条目。

此边缘情况通过仅使用旧表来确定迭代顺序来解决。在实际返回条目之前，我们会查询增长后的表，以确定条目是否仍然存在，并获取最新值。

这涵盖了所有核心语义，尽管这里还遗漏了更多小的边缘情况。最终，Go Map 在迭代方面的灵活性使得迭代成为 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 挑战的解决方案相结合，构建了符合 Go 规范的 Swiss Table 实现：github.com/cockroachdb/swiss。Go 1.24 的内置 Map 实现很大程度上基于 Peter 的工作。感谢社区所有做出贡献的人！