不仅仅是 rehash

标题：More than a rehash

日期：2023/05/22

作者：Joaquín M López

链接：https://www.youtube.com/watch?v=Rg8MZ5pJIJA

注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。

下一位演讲者是华金·洛佩斯（Joaquín López）。我想经过七届会议，唯一一位在这里演讲过七次的演讲者就是华金。所以，华金，再次感谢你来到这里。同时，也感谢你今年在 Boost 中的工作，尝试为容器提供新的解决方案并努力让它们更快。所以，嗯，我非常感兴趣。

好的，谢谢邀请我。好的，你们能听清楚我吗？我喜欢在讲台上走动，但我们麦克风有点问题，所以我会尽量待在讲台后面。但我倾向于走开，等等。所以如果你们听不清楚，请告诉我，好吗？

那么，我想和你们一起探索我们在 Boost 中开发的一个全新的 HashMap。名字叫 Boost Unordered FlatMap。这个容器使用了一些最先进的技术，这些技术并非由我们首创，但它也引入了一些新的概念、一些新的创新，我认为你们可能会觉得了解这些很有趣。所以，它不仅仅是现有技术的简单重做（rehash），好吗？

首先，我想说，在经历了漫长的四年之后，能再次在 CppCon 演讲，我感到非常高兴。我希望你们在 COVID 大流行期间过得还算顺利，对于那些经历了艰难时期或个人损失的人，我表示同情。

有一句老话说，每个人一生中都应该写一本书、种一棵树、生一个孩子。如果我们把这个说法翻译到 C++ 开发的世界，可以略带调侃地说，每一个名副其实的 C++ 开发者都应该至少为标准做一次贡献、写一个光线追踪器、以及设计和实现一个哈希表。

请举手，那些至少做过这三件事中一件的人。 好的，两件呢？ 好的，三件都做过？好的，那你们还有作业要做，对吧？我还没完成这三件事。

好的，之所以有这么多哈希表实现，原因之一是标准库提供的那一个出了名的慢。它之所以这么慢，是因为它是在 2004 年设计的。在那个时代，封闭寻址法（closed addressing）——这是 std::unordered_map 默认采用的技术——被认为足够健壮也足够快。但二十年后的今天，情况已非如此。

std::unordered_map API 的问题在于，它如此严重地依赖于使用封闭寻址法的假设，以至于你基本上无法用封闭寻址法以外的任何技术来实现 std::unordered_map。然而，开放寻址法（open addressing）在性能提升方面取得了重大进展。目前，在任何时候，用开放寻址法轻松击败 std::unordered_map 都是非常容易的。

所以，在 Boost 中，我们决定对此做点什么。一年前，Boost.Unordered 基本上只提供了一个完全符合标准的 std::unordered_map 实现。我们决定以某种方式扩展我们的产品，以便在继续提供那个容器的同时，也拥抱开放寻址技术，并尝试为我们的用户提供更快的东西，代价是稍微偏离一点标准。好吗？我们稍后在讨论中会了解到，为了提供这个容器，我们必须做出哪些妥协。

在 2022 年 3 月，我们制定了 Boost.Unordered 的开发计划。我们首先改进了现有的 Boost.Unordered Map。关于这个容器我们不会讲太多。然后在 2022 年 12 月，我们发布了 Boost.Unordered FlatMap，这就是我们今天演讲主要要讨论的开放寻址容器。几周前，我们发布了 Boost.Unordered Node Map，它类似于 Unordered FlatMap 的一个变体，通过牺牲性能来提供指针稳定性。如果一切顺利（从我内部看到的情况来看进展非常顺利），我们将在 2023 年 8 月发布一个名为 Concurrent Flat Map 的“猛兽”。我对这个小“猛兽”感到无比兴奋。我们会有一个关于它的预告。但今天演讲的主要焦点是 Boost.Unordered FlatMap。

我绝不是参与这项工作的唯一人员。有很多人在帮助推进 Boost.Unordered 的这个开发计划。官方指定的 Boost.Unordered 主要维护者是克里斯蒂安·马扎卡斯（Christian Mazakas）。彼得·迪莫夫（Peter Dimov）为这个库做出了关键贡献，特别是在哈希函数和哈希后处理（post mixing）方面。萨姆·达尔文（Sam Darwin）是我们的 IT DevOps CI 专家。多亏了他，我们能够在大量不同的编译器和平台上测试和基准测试我们的容器。马丁（Martin）和帕维尔（Pavel）贡献了很多反馈并测试了库的早期版本。所以，感谢他们所有人。一张幻灯片只能放这么多照片。在 Boost.Unordered Slack 群组里还有更多人。这是开放和公开的，所以如果你有兴趣对 Boost.Unordered 的发展方向发表意见，欢迎加入。

另外，让我提一下，这项工作是由 C++ 联盟（C++ Alliance）资助的，这是一个致力于改进 C++（特别是 Boost）的非营利组织。这是网站的 URL，如果你有兴趣可以看看。

那么，让我们深入探讨。哈希表本质上是将一堆元素插入到一个所谓的桶数组（bucket array）中的业务。我们通过一个哈希函数来实现这一点。理想情况下，哈希函数将每个不同的元素映射到一个不同的哈希值。通常，你无法获得 100% 的成功率，但如果哈希函数足够好，从概率上讲，哈希值将会不同。哈希值通常很大，比如 64 位。因此，为了将所有这些空间适配到小得多的桶数组中，你必须对哈希值进行某种缩减，比如通过某种取模函数或保留哈希值的低位比特等。这些你们基本上都知道。

哈希表的基本问题是，如果两个不同的元素被映射到同一个桶中会发生什么？这要么是因为哈希函数失败了并产生了相同的哈希值，要么是因为缩减过程导致两个哈希值最终落入了同一个桶。好的，这称为冲突（collision），希望你们都熟悉哈希表中的冲突是什么。

好的，封闭寻址法和开放寻址法的主要区别在于我们如何处理冲突。在封闭寻址法的情况下，我们为每个桶维护一个链表节点。好的，所以处理冲突是一个非常非常简单的任务。如果一个元素碰巧被映射到一个已经包含另一个元素的桶中，我只需分配一个新的节点，扩展链表，就完成了。非常简单，我认为这是实现起来非常容易的原因之一。

那么开放寻址法呢？开放寻址法的定义特征是，我最多只能在一个桶（在这个上下文中也称为槽/slot）中放一个元素。好的，所以槽和桶基本上是一回事。这有一些好处。我们稍后会看到这些好处是什么。但是冲突必须以其他方式解决。好的，如果我正在将一个元素映射到一个槽，而该槽已被占用，我唯一能做的就是尝试找到一个空的槽。好的，在这种情况下，我只是去下一个槽。下一个槽碰巧是空的。我就用它。完成了。完成了。这就是开放寻址法。

大多数关于开放寻址法的文献都在讨论如何定位可用槽。以及当我删除元素时该怎么做？这些是开放寻址法的两个关键方面。

让我们考虑这个我们称之为“不成功查找”（unsuccessful lookup）的小实验。我们试图在哈希表中定位一个不存在的元素。好的，在上面开放寻址法的情况下（指幻灯片）。嗯，过程的开始总是一样的。我获取这个元素的哈希值，然后定位这个元素对应的桶或槽。然后，既然这个元素在桶数组或槽数组中不存在，我必须遍历与该桶相关的所有不同节点，以确定确实没有一个是我要找的元素。

好的，让我们计算一下封闭寻址法和开放寻址法下检查的元素或节点的平均数量。好的，我们称之为平均探查长度（Average Probe Length - APL）。这是哈希表的一个重要统计指标。在演讲中我们会多次回到这个 APL 问题。

好的，所以你可以看到，在这个特定情况下，封闭寻址法的 APL 是 1.5。在开放寻址法的情况下（我说的是开放寻址法），实际上更高。为什么？因为你看到对于一次探查，长度可能高达 4。这是因为桶或槽在相互干扰。所以，如果某个桶或槽被占用，而我在它旁边的槽进行操作，那么它就会产生干扰，因为它们会成为更长探查序列的一部分。好的，这是封闭寻址法不会遭受的问题，因为桶之间完全不会相互干扰。这也意味着封闭寻址法哈希表使用的哈希函数不需要像开放寻址法那样高质量。

开放寻址法的这种效应称为主聚簇（primary clustering）。而主聚簇是你的开放寻址哈希表表现不佳的主要原因。所以你需要对抗它。好吗？

这些公式是成功查找和不成功查找的平均探查长度。这些公式最初是由唐纳德·克努特（Donald Knuth）推导出来的。这里唯一需要注意的是，α 是负载因子（load factor），是元素数量除以槽数量。

在所谓的线性探查（linear probing）情况下，即你基本上去下一个槽，然后再下一个，等等，以找到可用的槽。对于这种情况，随着负载因子趋近于 1，无论是成功查找还是不成功查找，平均探查长度都趋于无穷大。所以负载因子对于开放寻址表来说是一个非常关键的因素。你不可能在开放寻址表中拥有高达 1 的负载因子。而在封闭寻址法的情况下，你可以非常容易地将最大负载因子设置为 1 甚至更高。好吗？

为了最小化这个问题，我们可以使用其他一些探查技术。所以你在上面看到的是线性探查，但我们也可以使用二次探查（quadratic probing），即我们基本上以越来越大的步长去探查槽。这里的想法是，如果我们碰巧跳进了一个聚簇的中间，那么通过二次步长跳跃，我们能够更快地跳出这个聚簇。并且我们没有增加聚簇的总长度。明白了吗？好的。还有一些更复杂的探查机制，如双重哈希（double hashing）等，但就本次演讲的目的而言，这些就足够了。

开放寻址法的另一个问题是，如果我删除一个元素会发生什么？在第三个槽中，你看到我删除了一个元素，这个元素曾经是某个探查序列的一部分。明白吗？现在，如果我正在寻找最后一个元素，我的哈希表将会失败，因为我跳到第一个，然后另一个，再另一个，然后我跳到了一个空槽。算法会说，好吧，探查序列结束了。没有更多的元素需要探查了。好的。所以这不行。好的。这确实是个问题。

我们有大约两三种方法来解决开放寻址法的删除问题。一种非常著名且广泛使用的方法叫做“墓碑”（tombstones）。墓碑是一个特殊的标记，我把它放在被删除元素所在的槽里。所以当我在寻找一个元素时，如果碰巧跳到一个墓碑，我就知道探查序列必须继续下去。好的。然后我可以去下一个元素，再下一个。然后在我推进到完整的探查序列之后，如果我跳到一个真正空的槽，探查序列就完成了。好的。这就是墓碑。

墓碑的一个问题是，你们已经知道，哈希表的平均探查长度随着负载因子的增加而增加。但是有了墓碑，平均探查长度并不会减少。所以平均探查长度永远不会减少。这会导致哈希表性能的某些退化，直到你不得不重新哈希（rehash）表为止。好吗？还有一些其他机制。而 Boost.Unordered FlatMap 没有使用墓碑。它使用了其他东西。还有一些更复杂的算法，我称之为“重定位算法”（relocating algorithms），在这种算法中，你基本上在探查序列中不留空槽。这可以在删除时完成，就像这个例子中那样，也可以在插入时完成，目的是提高或改善哈希表的性能，比如尝试保持探查长度尽可能短，或者探查长度的方差尽可能小等等。

顺便说一句，你们可以随时打断我，因为我们要讲很多内容。我不想在中间把你们弄糊涂了。好的。所以如果有不清楚的地方，请举手。好的。

我们已经消化了关于封闭寻址和开放寻址的大量信息。我们现在可以勾勒一下市场上不同哈希表算法的分类或图表。好的。一方面，我们有封闭寻址。关于它没什么好说的，因为它简单至极。然后我们有开放寻址，有很多变种。有些人称之为“混合方法”（hybrid approaches），它们不完全像开放寻址，也不完全像封闭寻址，比如联合哈希（coalesced hashing）。顺便说一句，非常有趣的东西。

然后，如果我们专注于纯开放寻址哈希表，我们可以将它们分为重定位算法（relocating algorithms）和非重定位算法（non-relocating algorithms）。重定位算法有它们自己的问题。我认为它们不太适合像 C++ 容器这样的通用标准，不过我不会深入讨论这些。文献中有三种主要的重定位算法，称为布谷鸟哈希（Cuckoo Hashing）、跳房子哈希（Hopscotch Hashing）和罗宾汉哈希（Robin Hood Hashing）。如果你去维基百科或别的地方搜索，可以找到对它们的解释。

对于非重定位算法，我们基本上有两种技术。墓碑（Tombstones），我们已经讨论过了。然后还有一些东西，这个我在文献中没有找到，所以我编造了这个术语。我称之为“基于溢出”（overflow based）的算法。好的，我们将了解这个，实际上 Boost.Unordered FlatMap 有一个溢出机制，而不是墓碑机制。

到目前为止有什么问题吗？大家都跟上了吗？好的，所以你们可能会想，嗯，故事你们已经知道了，但你们可能会想，好吧，那么开放寻址法与封闭寻址法相比，究竟有什么好呢？因为封闭寻址法一方面有指针稳定性（pointer stability），因为节点是分配在它们自己的节点上的。所以如果我必须重新哈希表，指向节点的指针不会失效。而开放寻址法就不是这样了。封闭寻址法可以使用质量较差的哈希函数，因为我没有主聚簇问题。而且我可以将负载因子设置为 1 甚至更高。所以开放寻址法在各方面都更差。那我们为什么还对开放寻址法感兴趣呢？是的，没错。嗯，速度，性能。所以我们愿意牺牲或接受使用这些不稳定生物的风险，因为它们快得多。

我们不每个元素分配一个节点。这意味着我们只有一个大块分配（one allocation）。而且开放寻址哈希表具有非常非常好的缓存局部性（cache locality），极其好的缓存局部性。通常你跳到哈希函数告诉你要去的那个桶。如果你在那里没找到元素，它很可能就在附近。所以缓存局部性极好。而在封闭寻址法的情况下，你至少需要经过两个指针，可能更多。好吗？

那么开放寻址表比封闭寻址表好多少呢？这里只是一个例子。绿线是 Boost.Unordered Map，如果你把它与标准 std::unordered_map 的实现相比，它并不是一个慢的容器。蓝线是 Boost.Unordered FlatMap。容器是 int 到 int 的映射之类的。没关系。我只是要展示我们谈论的数量级。这张图是关于不成功查找的。我需要喝点水。抱歉。这张图是关于不成功查找的。这张是关于插入的。所以通常，你会得到比… 非常感谢（递水）。与封闭寻址法相比，开放寻址法的性能通常快 3 到 5 倍。这就是我们做这件事的原因。我们要速度。好吗？

然后，在处理开放寻址法时，我们还需要讨论最后一个要素。那就是 SIMD。你们都知道 SIMD 是什么。好的？我不需要提醒你们。好的。

有一个天才的想法。我想是谷歌最先提出的，即 SIMD 可以用来实现哈希表。好的？假设你有一堆元素，你将关联哈希值的一部分保存在一个所谓的元数据数组（metadata array）中。比如每个元素一个字节。比如哈希值的低字节之类的东西。好的？我正在尝试寻找一个元素，其缩减后的哈希值是 B0。好的？事实证明，使用 SIMD 操作，我基本上可以用几个 SIMD 操作创建一个重复 B0 的 16 字节数组。然后一次性与元数据数组进行比较，并获得一个匹配元素的掩码（mask）。好的？如果我有一个正向匹配（positive match），那意味着我必须真正去双重检查那个元素，以确认，好吧，就是这个吗？或者我可能不走运，因为缩减哈希值碰巧相同。但如果没有匹配，那么我完全确定元素不在那里。好的？所以我正在以一种非常非常高效的方式减少或过滤掉元素。

这个公式很重要，需要记住或稍微熟悉一下。这是在使用 SIMD 匹配时你会得到的平均误报（false positives）数量。好的？所以负载因子越高，你将得到的误报数量就越高。SIMD 寄存器中的组（group）越大，误报数量就越高。但是，误报的数量会随着你用于比较的缩减哈希值的大小呈指数级下降。所以如果你的缩减哈希值是一个字节，你会得到某个平均误报率。如果你用了两倍那么大，那么你的误报率将是原来的一半。明白了吗？好的。

我们现在可以理解 Boost.Unordered FlatMap 的布局或基本方法了。我喜欢这张图片。我放它没有特别原因。是让·科克托（Jean Cocteau）的画。我真的很喜欢。好的。这就是 Boost.Unordered FlatMap 的内部结构。好的？这个槽数组被分成 2 的 n 次方个组，每组 15 个元素（不是 16 个）。好的？好的。我们有一个元数据数组，其中每个组有 16 字节的元数据。其中 15 个字节基本上是关联元素的缩减哈希值。然后我们有一个字节的溢出字节（overflow byte）。好的？我们将理解… 或者我将解释这个东西是如何工作的。到目前为止好吗？好的。

缩减哈希值并不是一个完整的字节，因为我们需要保留一些值用于特殊标记，比如表示槽是空的，或者用于一个叫做哨兵（sentinel）的东西。我不会详细说明哨兵是什么。好的？所以我损失了 256 个值中的两个值，但剩下的可以用。当我不处理空槽或哨兵槽时，我使用剩下的值来尽可能多地获取关联槽中元素的哈希值信息。这意味着我每个元素存储了大约 7.9 位信息（实际是 log2(254) ≈ 7.99 位）。好的？那个溢出字节有什么用呢？

你在之前的幻灯片中看到，确定探查必须结束的一种方法是找到空槽。另一种方法是拥有一个溢出字节，为特定组发出信号。假设我正在寻找一个哈希值为 H 的值。确定我是否必须越过该组的一种方法是将该信息存储在溢出字节中。我在溢出字节中有 8 位。这意味着我可以将哈希值分为 8 类，比如取模 8，然后检查关联的位，它会告诉我对于这个哈希值，我是需要继续前进还是探查必须结束。这可能是整个实现中最棘手的部分。你们跟得上吗？理解了吗？是的。好的，很好。你们非常聪明。我花了几个月才弄明白这个。

所以，查找的一般算法是这样的。好的？我有 X。我计算哈希值。我定位组（group）。好的？我使用缩减哈希值对这 15 个元素进行 SIMD 匹配，然后我得到一个掩码（mask）。我遍历那些设置为 1 的位（bit），然后与这些元素（guys）进行比较，如果我找到了那个元素（guy），我就完成了。否则，我去检查溢出字节。我确定探查序列是否必须结束。如果探查序列必须结束（因为我没有溢出），那么元素就不在那里。否则，我继续处理下一个组，这个组是按二次方式探查的。但我们是按组级别（group level）进行二次探查，而不是按槽级别（slot level）。所以一次处理 15 个元素。

插入（Insertion）基本上也是一样的。好的？就这样。啊，不。关于 Unordered FlatMap 还有一件事需要知道。你们知道我们非常关注主聚簇（primary clustering）。所以我们想要一个通用的算法，一个可靠的（solid）容器，我们不希望用户因为他们的哈希函数很糟糕而悲惨地失败。所以我们正在采取一些措施来提高哈希函数的品质，通过做一个叫做后处理（post mixing）的事情。

在我们的例子中，这基本上是将哈希值乘以一个与斐波那契黄金分割常数相关的魔法常数（magic constant）进行扩展乘法（extended multiplication）。然后这个扩展乘法（180 位宽），我们进行某种折叠（folding）或类似操作。这就是我们最终得到的值。这基本上减少了哈希表中出现聚簇的可能性。

所以顶部的图是一个非常差、病态输入集（比如从 16 到 1000 万的整数）的比特概率分布。所以你可以看到空间基本上是空的，我们只在非常少的比特上有差异（variance）。如果我们做了后处理，那么我们就有了这个漂亮的分布，每个比特都同等可能，等等。好的。所以这就是后处理。我们… 这是一个可选退出的机制（opt-out mechanism）。如果你的哈希函数已经足够好，你可以设置一个特征（trait）并指示容器不要使用后处理，以获得最佳性能。

10分钟（提示时间快到了）。那么我们在性能方面表现如何呢？让我们把我们和 abseil（我不知道怎么发音，abseil）进行比较。比方说 abseil flat_hash_map，它被普遍认为是最快的哈希映射之一。这是谷歌的。好的。两个容器非常相似，但也有一些区别。

  • 我们每组元素数是 15。他们是 16 个元素每组。

  • 两者都进行组级别的二次探查（quadratic group level probing）。

  • 哈希映射（Hash mapping）在我们的情况下是在组级别进行的。所以我们定位一个组，而他们是定位槽（slots），然后他们的组是滑动或移动的。好的。

  • 两者在可用时都使用 SIMD 技术。

  • 缩减哈希值（Reduced hash），他们使用缩减哈希值的其他编码方式，结果是他们每个缩减哈希值只使用了 7 位有效载荷（payload）。而我们大约有 7.989 位（log2(254)≈7.99）。好的。

  • 他们通过空槽（empty slots）来做探查终止（prob termination），而我们使用这些溢出字节（overflow byte）。好的。

因此，元素在 Boost 哈希表和 abseil 哈希表中的分布是相当不同的，因为他们在做槽级别的映射（slot level mapping）。好的。所以这有利有弊。

如果我们看 Boost 这边，我们更缓存友好（cache friendly），因为我们的元素倾向于聚集在一起。但另一方面，在我们这里一个组满的概率更高，因为他们更均匀地分布空槽。好的。所以我们有这种权衡（trade off）。

通过一个模拟程序，我计算了不同负载因子下的三个重要指标：一个组满的概率、成功查找的平均探查长度（APL）和不成功查找的平均探查长度。我绘制的是 APL 减 1 的值，因为这样在图上看起来更好，但你们明白意思。

如我们所预测的，在我们这里一个组满的概率更高、更差，因为我们每组元素更少。而且我们有这种聚簇（clustering）问题。这导致在成功查找的情况下，我们的平均探查长度（APL）稍微差一些。但在不成功查找的情况下，我们的平均探查长度（APL）要好得多，因为我们使用了这种溢出机制，它能更好地区分不同的哈希值。

如果我们现在绘制实际的比较次数图，好的，我们看到在成功查找方面，我们稍微、稍微差一点。我们在查找时使用了更多比特用于缩减哈希，这意味着我们的误报（false positives）更少。所以即使我们稍微差一点，我们也在追赶。我们几乎一样。而在不成功查找方面，我们基本上比 abseil 的那些家伙好得多。

在真实性能方面，这是一个针对 int 到 int 映射等的合成基准测试。所以你可以看到，对于成功查找，我们表现大致相同，然后由于缓存效应（cache effects），在元素数量很大时表现更好。对于不成功查找，正如我们的统计分析所预测的，我们表现好得多。而且当负载因子非常高时我们表现更好，因为我们的曲线不那么尖峰（spiky）。好的。对于插入（insertion），它非常受不成功查找的支配，我们也表现更好。

所以这是 abseil。有一个叫马丁（Martin）的人。我已经提到过这个名字，马丁·利特纳-汉克尔（Martin Leitner-Hacker），他维护了一个非常著名的基准测试，包含许多不同的哈希映射和许多不同的哈希函数。我为他非常友好地为我运行的一个子集进行了选择，其中对于每个容器，我选择了该容器表现最好的哈希函数。这些是马丁设计的一系列不同的测试用例，从非常合成或非常人工化的东西（比如插入一堆东西）到更奇特的东西（比如模拟康威生命游戏）。好的。这些是数字。100 表示最好，其余结果按列归一化到 100。好的。

我们是最好的吗？我不会说我们是最好的。我不是销售人员。我们属于最快的行列。毫无疑问。内存使用是左边那一列。然后你可以查阅演示文稿并详细查看数据。正如预期的那样，std::unordered_map 差得多。但我们早就知道了。好的。而且外面有一些非常好的容器。所以并不是说，嗯，我不是那种竞争心态的人。我们正在尽力做到最好，但外面有一些非常值得尊敬的竞争对手，你们绝对应该尽可能多地检查它们。

假设我说服了你们，你们想尝试 Boost.Unordered FlatMap。嗯，你们需要安装 Boost 等等，但如果你们从 std::unordered_map 迁移过来，你们也必须做出一些妥协或有一些权衡（trade-offs）。

比如，键（Key）和值类型（T），在映射类型中，必须是可移动构造的（move constructible），而 std::unordered_map 则不需要，因为当你重新哈希表时，你必须将元素从一个槽数组重新定位到另一个。所以这是开放寻址法带来的必然要求。同样，我们没有指针稳定性（pointer stability）。如果你需要指针稳定性，你可以使用 Boost.Unordered Node Map，它在几周前已经可用。这会给你指针稳定性。如果这对你真的很重要，因为其代价是性能比 std::unordered_map 好，但比 Unordered FlatMap 差得多。好的。

begin() 不是常数时间（constant time）。我没有时间讨论这个。如果你们感兴趣，我可以在咖啡时间向你们解释为什么是这样。erase 迭代器不返回迭代器。这是出于性能原因。最大负载因子（maximum load factor）可以被改变。这在开放寻址表中很典型，因为你不希望用户乱动这个。这非常关键。如果你把最大负载因子设置得太接近 1，这东西会爆炸（blow up）。好的。而且没有桶 API（bucket API）。显然，没有提取节点（extract）函数，除非你使用 Boost.Unordered Node Map。嗯，看起来有很多注意事项（kvetch），等等。但除此之外，这是一个即插即用（drop-in）的替代品。所以基本上替换掉它然后享受吧。

还有一个预告，就是这个 Boost Concurrent Flat Map。它将在 2023 年 8 月发布。它基本上是一个并发 Flat Map，设计用于当你有多个线程向同一个哈希映射中插入东西或查找东西时使用。好的。我不会详细说明，但这是一个在非常简单的基准测试中与英特尔 TBB（INTEL-TBB）的比较。我们击败了他们（beating their pants off）。所以我对此非常兴奋。

结论。我们提供了一系列不同的容器，从完全符合标准、完全标准兼容的 Boost.Unordered Map，到最快的 Boost.Unordered Flat Map，以及介于两者之间的 Node Map。你们还有这个 Concurrent Flat Map 即将在今年发布。

所以，我希望你们或多或少理解了这东西是如何运作的，以及为什么我们在性能方面做得很好。如果你们尝试使用它，请记住，如果从 std::unordered_map 迁移过来，有一些注意事项需要考虑。请加入 cpplang.slack.com 上的 Boost.Unordered 群组。加入讨论。我们非常高兴有你们参与这项努力。

就这样。非常感谢大家。现在提问时间。哦。（掌声）我并不惊讶。谢谢这个非常有趣的话题和精彩的解释。谢谢。

观众提问 1: 我想问一下，当你解释探查（probing）以及为什么做二次探查（quadratic probing）时。也许我可以回到那里（幻灯片）。是的。在硬件预取器（hardware prefetcher）方面，你并没有帮助它，对吧？因为你没有采用恒定的步幅（constant stride）。那么这是否是一个考虑因素，以及你在基准测试中是否尝试过使用恒定步幅？

华金: 绝对是的。绝对是的。问题是，嗯，这是一个很好的问题。如果你是在槽级别（slot level）探查，那么二次探查会极大地伤害你，因为你说的原因。但我们是按组级别（group level）探查。通常，即使对于一个负载非常重的哈希表，我们也只检查一个组或两个组。永远不会超过这个。所以… 所以… 在探查长度更大的情况下预取器怎么样？是的，没错。所以，好吧，我们做二次探查只是为了它（for the sake of it）。是的。但事实证明，大多数时候，这并不重要。

观众 1: 这也回答了我的第二个问题。然后你展示了你在遍历掩码（mask），对吧？在你做完比较之后，里面可能有多个匹配项。你优化了遍历这些索引的方式吗？因为我也做过这方面的工作。我还实现了一个基于范围的循环来遍历它们，它只是通过位扫描（bit scan）内部函数（intrinsics）给出索引。我在使用内部函数来… 让我… 我总是希望能得到外界的帮助，但…

华金: 是的，这就是我问你是否想要（讨论）的原因。

观众 1: 为了得到最终的掩码，我们做了一些位操作内部函数。除此之外，我们就像… 查询下一个设置的位（next set bit），然后做一个掩码缩减（mask reduction）并一路走下去。

华金: 对，然后你遍历字段（fields）检查它们是否为真（true）。

观众 1: 是的，没错。所以，我做的实现是，基本上你可以把它变成一个位域（bit field），对吧？然后你可以做一个位扫描（bit scan），它会直接给你下一个索引。但我们可以私下再谈。

华金: 是的，当然。你有我的邮箱，或者我们可以在咖啡时间聊聊。

观众 1: 谢谢。

华金: 还有问题吗？哇。

观众提问 2: 你可能知道在 C++23 中，我们将有 flat_map 和 flat_set 容器。是的。它们将有效地接受不同的… 不同的模板参数。所以，我有一个问题是，对于无序容器（unordered containers）来说，拥有这种参数是否有意义？如果没有，是否可以有更好的名字，里面不包含 “flat”？因为你在预告中也提到了你将会有 concurrent_flat_map，这完全把命名搞乱了…

华金: 好问题，因为我们在内部就如何命名容器有过争执，而这个 “flat” 的事情正好有相同的… 所以我们无法解决这类问题。至于 flat_set 和 flat_map，它们基本上如你所知是一个向量（vector），上面实现了有序树结构（ordered tree-based structure）。好的。std::flat_map 做的一件有趣而我们没有做的事情是，键和值可以保存在单独的数组（separate arrays）中。我们没有那样做。所以这是我想探索的事情。除此之外，它们是完全不同的东西，人们可能会对 “flat” 这个名字有点困惑。是的。所以，抱歉。你知道，像 abseil 把他们的容器命名为 flat_map。所以我们有点喜欢那个多一点。是的。提到 concurrent_flat_map，它是有序的还是无序的？

观众 2: 无序的（Unordered）。

华金: 它和你已经看到的容器布局相同，但在上面加了一些并发机制。

华金: 还有问题吗？

观众提问 3: 首先，恭喜 Boost 又添一个容器。里面有很多了。好的。我的问题与 Concurrent Flat Map 有关。我只是想知道同步（synchronization）方面。你打算开发什么样的同步机制？或者你还没有？

华金: 不，不。是的，是的。我们有一些锁（locking）。它不是绝对无锁（lock-free）的东西。所以想法是我们有两级锁（two levels of locking）。一个类似于容器级别（container level），另一个是组级别（group level）。好的。我们设计的布局的好处在于，开放寻址法只有非常少的活动部件（moving parts）。所以实现基本无锁的查找（lookup）非常容易。好的。很多操作可以在最小化锁定的情况下完成，并且结果证明了这一点。所以这是这个容器背后的秘密或魔法酱（magic sauce）。但是，我们有锁。我们在内部锁定时使用了一些带重试的自旋锁（retried spin locks）。如果你对它感兴趣的话。好的。代码是开放的。你可以联系我，你可以看看。

观众 3: 好的。完美。谢谢。

观众提问 4: 非常，非常有趣的演讲。我只是，只是想问一件事，关于删除（deletion）在… 如果有很多删除操作，会损害性能吗？我的意思是，这是一种理论上的练习，但我想知道这个问题。这是否是你们探索过的一个问题？

华金: 是的，这是个问题。嗯，如果你碰巧在一个典型的开放寻址表中有很多插入和删除操作，平均探查长度（average probe length）将会无限制地增加。好的。一些容器做的，我们也做，abseil 也完全做同样的事情是，我们跟踪平均探查长度是如何增加的。一旦达到某个限制，我们就重新哈希（rehash）表，即使最大负载因子还没有达到。我内部称之为漂移（drift）和反漂移（anti-drift）机制。abseil 的家伙们称之为别的名字。但如果你有一个非重定位（non-relocating）的开放寻址哈希表，你的平均探查长度会随着时间的推移而退化。如果你做大量的插入和删除，这是无法避免的。好的。

观众提问 5: 你描述的溢出机制，它需要读取两个字节，它们总是在同一个缓存行（cache line）上吗？

华金: 我假设你是指溢出字节？它是一个字节。它在缓存行中，因为它与其他缩减哈希值一起位于同一个 16 字节块（work）中。所以，是的。

观众 5: 所以那是在 64 字节行上。是的。基本上是免费的。

华金: 是的。谢谢。

华金: 还有问题吗？好吧，你们可以在咖啡休息时间问更多问题。

非常感谢，华金。谢谢。谢谢。