不完美世界中的完美哈希¶

标题：Perfect Hashing in an Imperfect World

日期：2024/06/06

作者：Joaquín M. López Muñoz

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

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

在开场时我说过这是我们的第八届会议。现在，有一个人参加了每一届会议并做了演讲，这个人就是Joaquin。所以他是Boost的长期贡献者，对我来说，他也是包括数据结构在内的许多领域的专家。所以Joaquin今天要讲的是哈希。完美哈希。完美！做到完美很重要。那么我就把时间交给Joaquin。Joaquin，非常感谢你再次为会议和C++社区做出贡献。谢谢。谢谢。

我们将要讨论完美哈希（perfect hashing）。首先，你们中有多少人知道常规哈希表是如何工作的？是的。大多数人都知道。所以你有一定数量的元素要插入到表中，还有一个哈希函数将每个元素映射成一个哈希值。通常是一个很大的整数，比如64位宽之类的。然后，你以某种方式将这些哈希值投影或缩减到一个所谓的桶数组（bucket array）的索引中。好的。元素数量除以桶数组的数量，我们称之为负载因子（load factor）。就是这样。这就是哈希表的工作原理。如果哈希函数表现相当好，那么元素将在桶数组中均匀分布。但很多时候。实际上我们会看到，大多数时候你会遇到冲突，即两个或更多元素被映射到同一个桶中。在示例中你可以看到。哦，抱歉。我该怎么切换… 好的。哦，它太小了，我几乎看不清。这里你看到有一个冲突。有两个元素被映射到了同一个桶里。

那么，完美哈希是关于什么的呢？完美哈希是一种令人愉快的情况，即你没有任何冲突。所以在这个例子中，你看到所有元素都被映射到了未被任何其他元素占用的桶中。而最小完美哈希（minimal perfect hashing）是更令人愉快的情况，即元素的数量正好等于桶的数量，也就是负载因子为一。因此所有的桶都有且只有一个元素。这就是最小完美哈希。这有多酷？这很酷。如果我们能得到它的话。

你可能会有直觉，认为你需要非常幸运才能拥有一个不产生冲突的哈希函数。事实上，你需要极其幸运。如果我们有n个元素和m个桶。这是一个公式，它基本上给出了随机选择的哈希函数不产生冲突（或称为无冲突）的概率。好的。让我们稍微分析一下这个公式告诉我们的关于这个东西的行为。如果桶的数量m趋向于无穷大，或者换句话说，如果你的桶数组非常巨大，那么哈希函数不产生冲突的概率基本上是一，因为你将非常少的元素映射到一个非常大的数组中，但这不实用。如果你有1000个元素，你需要一个有1000个元素，但你需要一个大小为100万的桶数组。这仍然只是一个奇闻，除非你只有非常非常少的元素。而当我们看到这个概率函数或公式在负载因子（元素数量除以桶的数量）固定为1时是如何工作的（这是最小完美哈希的情况）。你可以看到，随着n的增长，概率会非常迅速地以指数方式下降到零。图表也显示了在固定负载因子的不同值下，随着n的增长，存在相同的行为。你基本上可以看到它非常迅速地趋向于零，这似乎是显而易见的。这就是所谓的生日悖论，它基本上告诉你，如果你有一个哈希函数，你将会遇到冲突。

所以，对于最初的问题“你需要多幸运才能获得完美哈希”的答案是：极其幸运。你必须是宇宙历史上最幸运的人。所以这个故事的寓意是：完美哈希是不可能的，我的演讲到此结束。非常感谢。不，我们漏掉了什么。我的意思是，肯定有办法实现完美哈希，我将在下一张幻灯片中揭示这个技巧，或者说遗漏的技巧，或者说遗漏的信息。

一个小插曲。这个非常漂亮的雕塑是一位中国艺术家艾未未的作品。它永久陈列在我家乡卡塞雷斯（Cáceres）的埃尔加达瓦尔博物馆（Elgadalvear Museum）。所以下次你去卡塞雷斯时，别忘了去博物馆参观，或者也许给我发个消息，我们可以边参观博物馆边聊聊C++和艺术等等。

那么，完美哈希背后的技巧是什么？当你有一个常规的哈希表，常规的unordered_map之类的容器时，你是在尝试插入或删除元素之前就选定了哈希函数。所以你构造了哈希表，然后开始插入和删除元素，基本上就是这样。好的。所以正如我们已经看到的，哈希函数产生完美哈希的机会是零。完美哈希的技巧在于，我们要求在选定哈希函数之前预先知道输入元素。因此我们有机会在选定哈希函数或整个数据结构时足够聪明，以使其不产生冲突。所以这就是完美哈希的诀窍。完美哈希是关于预先知道输入元素，然后尝试构造一个没有冲突的哈希表。

有两种通用方法来尝试创建完美哈希表。其中之一基于文献中所谓的通用哈希函数。所以基本上，该算法或方法假设你有无限多的哈希函数，你可以尝试并选择其中的许多个，以某种方式组合它们，从而不产生冲突。另一种完美哈希的通用方法是创建一个专门为手头的输入集设计和定制的哈希函数。所以你将检查输入集，并确定如何构造一个对该输入集完美工作的哈希函数。对于其他元素或潜在的键，你并不真正关心。我的意思是，无论产生什么哈希值都可以。你只关心确保对于这些输入集，哈希函数会产生不同的哈希值。

那么，完美哈希表的优点、优势和缺点是什么呢？优点在于速度。你保证能在常数时间内完成查找，因为你不会有任何冲突。在哈希表的情况下，你知道，在病态情况下，你甚至会有线性行为。好的，这不会发生（在完美哈希中）。这是常数时间。而且它非常快，因为生成的代码分支更少。好的。例如，在最小完美哈希的情况下，你甚至会有更少的分支，因为你不需要检查桶是否被占用。桶已经被占用了。我的意思是，因为你的负载因子为一，每个桶正好有一个元素，等等。所以有很多机会可以为查找编写性能极高的代码。好的。所以这是完美哈希的最大优势，但它也伴随着许多缺点。

其一，表是不可变的（immutable）。正如我们已经看到的，一旦你将所有元素插入表中，你就不能再插入更多元素了。所以使用场景正是如此。如果我预先知道元素，我可以尝试构造一个完美哈希表。否则，你必须求助于常规容器。其二，构造时间会更长。所以将任何元素插入到一个unordered_map中，比插入到一个（如果你愿意这么称呼的）完美的unordered_map中要容易得多。所以你必须考虑到这一点。其三，也存在构造表失败的情况，因为理论上你是可能失败的。我的意思是，可能存在你找不到完美哈希函数的情况。这有点类似于在常规哈希表中使用行为不良的哈希函数时讨厌的病态行为。你会有线性查找时间等等。所以对于完美哈希表来说，等价的情况是构造过程放弃并失败。

所以这张幻灯片的要点是：完美哈希表不能替代常规哈希表。它适用于一个狭窄的使用场景空间，即你预先知道键，并且愿意接受采用完美哈希表所带来的缺点。

完美哈希表与常规哈希表相比有多快？我不想过多关注图中确切的数字，但蓝线是我稍后将讨论的一个概念验证（proof of concept）完美哈希表的相对性能。与之对比的是boost::unordered_set，这是一个相当快速的常规哈希集合（hash set）。这是针对整数和字符串，以及成功查找和不成功查找的不同组合。再次强调，我不想过多关注确切的数字，但其性能可能快两倍到四、五或六倍。好的。

那么，让我们进入演讲的一个难点部分。让我们谈谈一些流行的用于构造哈希表的算法。我们将简要回顾它们。我不想过多深入细节，但我希望你们能体会一下使用了哪些技术。

我们将要描述的第一个算法，是文献中最流行、最早出现的算法之一，叫做FKS（以三位匈牙利人的名字首字母命名，我记得他们是在1986年左右设计的）。过程如下：你有你的输入集（在这个例子中是12个元素），你首先使用某个哈希函数将其映射到一个常规哈希表中。这就是我们所说的主哈希表。在这个例子中，请注意我的负载因子甚至大于一。所以我肯定会有冲突。好的。这就是产生的主哈希映射。然后，我为每个桶关联一个二级哈希映射（secondary hash map），并将这些桶中的元素映射到这个二级哈希映射中。但这里的技巧或转折点是：二级哈希映射的大小是原始桶中元素数量的平方。如果你还记得，当我有一个大小是元素数量平方的桶数组时，那么我有50-50的机会（即50%的概率）让一个哈希函数无冲突地工作。所以我只需要尝试一些哈希函数，直到我中奖（hit the jackpot），我就得到了这个没有冲突的二级哈希表。好的。为此，我需要这种通用哈希函数。我需要有很多哈希函数来尝试。好的。这就是它的工作原理。它的美妙之处在于，我们生产出了没有冲突的哈希表，但桶的数量确实受到严格限制。它随着元素数量线性增长。所以我并没有达到我们之前讨论的那个二次方公式（N²桶）。我只需要分配大约3N个桶就够了（公式表明3N个桶就足够了）。所以这在我看来，无疑是美丽的。

让我们继续第二个算法，它是对第一个算法的改进，叫做HDC（H for Hash, D for Displace, C for Compress）。我把压缩部分放在括号里，因为我们不打算讨论那部分。这对于完美哈希表的一些使用场景很重要，当你在处理非常大的数据集等等时，需要压缩整个数据结构。我们不会讨论这个。所以让我们专注于哈希和位移（displace）部分。

该算法的工作原理，开始时和之前完全一样。你看到我说了一点哈希表，我会展示我接下来要做什么。所以让我们稍微处理一下哈希表。我可以在我的例子中做这个，然后我会展示我接下来要做什么。然后我会展示我要用哈希表做什么，而不是分配许多不同的二级哈希表或桶数组，我只创建一个，桶的数量如我所愿。在这个例子中，我将负载因子保持为一。它可以比一大一点。就是这样。

然后我做的是：我尝试使用一个随机选择的哈希函数和位移值（displacement），将所有元素映射到主桶数组的桶中。然后我尝试把所有元素放进去，当我成功时，就完成了。但直觉上，我不可能用这种方式成功，因为，我的意思是，我们已经看到了通过随机选择把事情做对的概率是多少。基本上是零。这里的技巧，再次强调，非常美妙，就是如果我从映射元素最多的桶开始，然后按降序进行，这个过程保证能在某个限度内、某个置信概率区间内工作等等。为什么？因为当我们映射元素最多的桶时，最终的桶数组基本上是空的。所以这很容易做到。随着桶越来越满，我需要映射的元素数量越来越少。当我处理到只有一个元素的桶时，我保证会成功，因为我只需要选择位移值，它基本上会去填满桶数组剩余的位置。所以如果你不相信我，你有理由不相信我。去看论文吧。有一个定理证明了这实际上是可行的。事实上，我们将要回顾的库就使用了这个方法。

我想回顾的最后一个算法，我称之为（因为我在文献中没找到特定的名字）最小覆盖。假设我们的关键元素是数字。像幻灯片上的12个数字。这是这些数字的二进制格式表示。你在那儿看到。好的。如果我能够提出一定数量的列，使得数字仅在这些列上过滤后，就能为所有元素产生不同的值，那么我就得到了我的哈希函数。因为我只需要分配一个桶数组，其元素数量是2的列数次幂。然后我用这个数字作为桶数组的索引。这有多酷？这也很酷。

这有一个问题。问题在于最小覆盖问题是NP难的（NP-hard），这意味着一个精确算法基本上是行不通的。这个算法的大多数实现基本上使用一种近似方法，它是线性时间，非常容易，基本上琐碎到可以写出来，并且能给出足够好的解。好的。但精确解，你是得不到的。另一个问题是，如果你增加一列，或者你需要另一列，桶数组的大小会翻倍（乘以2）。所以它非常依赖于这个最小覆盖有多“最小”。但除此之外，整个事情实现起来是微不足道的。在查找时，你只需要保留重要的列。然后你得到数字，使用掩码，压缩结果，也就是过滤出来的位，然后去桶数组。在x86架构中有一个叫做PEXT（Parallel Bits Extract）的CPU指令，就是专门做这个的。所以这非常非常快。我们将看到它有多快。好的。这些就是我想要和你们一起回顾的算法。

然后，在构造完美哈希表时，还有另一件事你必须考虑。那就是在什么时候构造它。有三个时间点你可能希望构造表：我称之为预处理时、编译时、运行时。

什么是预处理时？预处理时是指你有一个外部工具，一个程序。我们将看到其中一个，它接收输入集并生成专门为这个哈希表实现而生成的源代码。然后你使用这个工具，生成源代码，并将其编译或使用或包含到你的项目中。然后你就可以开始了。好的。

然后是编译时，它试图做同样的事情，但在编译时进行，通常使用constexpr魔法（magic）。好的。

还有运行时，它像一个常规哈希表一样工作，基本上你在运行时提供数据，在运行时构造表等等。

所有这些方法都有优点和缺点。

预处理时：这有点麻烦，因为你需要将一个生成工具包含到你的构建链（build chain）中，等等。但另一方面，它通常非常快。它不要求你拥有最新的C++标准。所以它有一些优点，也有一些缺点。
编译时：编译时。它需要较新的C++标准，因为正如你所知，constexpr能力在最新的标准中一直在升级。而且编译需要更长时间，因为这是C++，你知道的。
至于运行时，有时它是唯一的选择，因为即使你必须在构造表之前知道输入集，也可能在编译程序之前你不知道这些值，因为这些值可能是在运行时获取的。有时这是唯一的选择。即使不是唯一的选择，它也有一些优点。通常，你不需要最新的C++标准，因为这不需要那么强的constexpr能力。编译时间也会是可以接受的。好吧，你再次有一些优点和一些缺点。

我们将要回顾的库，有些是预处理时的，有些是编译时的，有些是运行时的。

我们将从Gperf开始，它可以说是完美哈希的黄金标准或基准。这是Douglas Smith在1989年写的，他也因编写了一个名为ACE的网络库而闻名。也许你们中有些人熟悉ACE。那些头发花白的人可能会知道那个库。嗯，这个人还发明了Gperf。这是一个预处理工具。你向这个工具提供一个规范或描述，包含将要放入这个完美哈希集合生成器的关键字或字符串。然后该工具为你生成C或C++代码。好的。它产生的唯一容器是一个集合。所以不是键值映射。只支持字符串的集合。所以它非常偏向于实现这类函数，比如判断一个给定字符串是否是某种语言的有效标识符，或者属于，我不知道，一些HTML实体集合之类的东西。事实上，GCC就在一些地方使用了Gperf，正是为了这个目的，在源代码中识别C++关键字等等。好的。他们使用的算法类似于最小覆盖。所以它的精神与我们描述的最小覆盖相同。你可以在这里看到为一个100个元素的哈希表生成的代码。好的。它是截断的，否则会很长。它创建了这个类perfect_hash，带有一个哈希函数和一个in_word_set函数，告诉你字符串是否属于该集合。哈希函数试图最小化在字符串中被检查的位置的数量。所以它就像一个最小覆盖的东西。它确保通过只检查这些位置，就能为输入集中的每个元素创建一个不同的值。它通过位置经过一个称为ASSO值的间接矩阵来实现，该矩阵映射到这个单词列表桶数组，在那里你可以看到这个东西并不是最小的，因为尽管大多数桶被占用，但存在空桶。所以这个算法不是最小完美哈希。它不必是。就是这样。所以这就是它的工作原理。而且它工作得很好。

我想评论的另一个库叫做Frozen。这是由Serge Guelton和其他一些人编写或维护的。它是一个编译时库，需要C++14，它提供集合和映射，看起来或多或少像你常规的unordered_set和unordered_map。当你在编译时构造这个东西时，通常你需要增加编译器允许的constexpr操作数量，因为限制会很快达到。只要你有10、12、20个元素，你就会达到那个阈值。所以你需要增加它。好的。它开箱即用地支持任何键类型，只要你为它提供了一个哈希函数。它为整数类型和冻结字符串（frozen strings）提供了开箱即用的支持，这些冻结字符串基本上就是string_view（字符串视图）。它们提供这个是为了兼容性原因，因为string_view只在C++17中才出现。但除此之外，它们基本上就是string_view。好的。他们使用的算法是我们之前回顾过的叫做HDC的那个。所以他们使用了它的一个变体。对于通用哈希函数，他们采用了一个接受一个值和一个种子的哈希函数。好的。所以通过改变种子，他们能够生成所需数量的哈希函数。所以这就是它的工作原理。好的。

MPH是另一个有趣的库。我之所以在本次回顾中包含这个库有两个原因。其中一个原因是作者Chris Josiuk和我们在一起。Chris在哪里？嗨，Chris。所以如果我说错了什么，他可以纠正我。另一个原因是该库做出了一些有趣的设计决策，使其有别于我们在本次演讲中将看到的其他库。好的。所以这是一个编译时库，需要C++20（原文是30，应为20）。再次强调，你需要增加constexpr操作阈值限制。它不是提供一个容器，而是生成一个函数，该函数接受一个键值并返回一个映射值，归根结底，这基本上是同一回事。好的。所以它只支持整数类型和长度限制为64字节（原文是weight，应为bytes）的字符串。作为回报，它非常快。并且它支持多种算法。在我看来，最有趣的是最后一个，它基本上是使用PEXT指令的最小覆盖变体。好的。我们将看到它的表现如何。除此之外，它还有一些针对极端情况或某些特定情况的其他变体。

Boost呢？嗯，我们还没有一个完美的哈希容器。我正在努力研究我们是否应该拥有它。与此同时，我制作了一个概念验证的东西，叫做perfect_set，它是C++11的。它是运行时的，不是编译时的。编写一个仅运行时的东西有一些优势，因为我可以使用动态内存分配。这在编译时是无法使用的。好的。它使用HDC（原文是HEC，应为HDC）。与Frozen的主要区别在于：他们使用了一个通用哈希函数，通过提供不同的种子来获得不同的值。如果你还记得，我们在这里所做的是我们只对元素哈希一次。我们使用哈希值的低位（lower bits）用于主哈希表，高位（high bits）用于二级哈希表。所以我们试图最小化为一个元素计算哈希值的次数，以求更快。除此之外，它的工作方式基本上与Frozen相同。我也有它的一个constexpr友好版本。这是概念验证。我写这个东西只是为了更好地理解它的工作原理。希望在年内晚些时候，我能够将其变成一个对Boost的真正贡献。

那么，如果我们测量这些表的创建时间，我指的是不同的含义：

对于gperf，这是调用工具然后编译该工具生成的源代码所花费的时间。
对于constexpr容器，这是编译定义了该容器的源代码所花费的时间。
对于运行时容器，这是编译以及初始化或创建表所需的时间。

好的。所以gperf非常好。对于多达数千个元素，它保持在1秒以下。其余的则各有不同。好的。所以mph在100个元素时崩溃了。我们将看到为什么会这样。基本上是因为，在我看来，它并不是设计来处理那么多元素的。其余的，嗯，运行时版本的Frozen由于我无法解释的原因，在1000个元素时也失败了。而编译时版本的Frozen（这是红线），随着n的增长，性能非常差。这不是由于任何内在原因。这是Frozen中的一个bug。我必须报告回去。他们在使用一个快速排序算法，当桶数组大部分为空时，表现非常差。这就是我们出现这些峰值的原因。这是在桶数组增长到下一个2的幂时发生的。嗯，如果这个bug被修复了，那么用Frozen创建表的性能就会变得非常合理。

对于查找，再次强调，我不想过多关注图中的数字，因为你得到的数字在很大程度上取决于你的具体场景。但为了对性能的好坏程度有一个数量级的认识，这是查找的性能图。针对100个元素和1000个元素，以及使用HTML实体作为集合键的成功和不成功查找的不同组合。这是gperf、frozen、mph等。对于mph，我需要将元素集减少到60个，否则会崩溃。我还需要根据设计将字符串长度限制在8个字符，因为这是该库能接受的最大值。所以比较并不公平。但除此之外，它非常快。好的。其余的，有些更快，有些更慢。事情就是这样。无论如何，这些查找时间都比使用常规哈希表快得多。这是肯定的。

在编译时构造容器（任何容器）都伴随着一些挑战。这也适用于完美哈希表。基本上有两种方式来设计这类容器的接口。

第一种：表的类型取决于元素的类型和元素的数量。你在构造编译时容器时需要知道元素的数量。好的。
第二种：容器的类型取决于整个输入集的所有不同键。所以这就像是第二种方法。MPH采用了第二种方法，这也是我选择它的原因之一。好的。

每种设计或每个接口决策都有其优点和缺点。好的。对于基于通用哈希函数的方法，第一种可能就足够了。但是当你使用工程化的哈希函数，比如使用最小覆盖时，采用第二种接口可能更有意义。但是那样你就需要所谓的结构性字符串（structural strings）。你需要特殊的类字符串对象，因为常规字符串或字符串视图不能用作你的容器的非类型模板参数。然后生成的符号长度将会非常巨大。这就是为什么你不能超过100个元素或几十个元素的原因。好的。还有一个关于constexpr的问题，这是由constexpr的定义方式所固有的。当你的容器的尺寸或占用空间（footprint）——我指的不仅仅是大小，还包括与容器相关的数据结构的大小——是输入大小的函数，即N的函数时，你没有问题。但是当大小取决于输入本身时，例如，对于某些输入，我可能需要更大的表；而对于其他一些输入，我可能需要更小的表。那么constexpr的工作方式要求你对与数据结构相关的计算执行两次。一次是为了获取大小，然后你需要分配一个静态存储持续期数组之类的东西。第二次你再去填充或构建（populate）数据结构。你无法绕过它。你必须那样做。如果你问我，这很痛苦（a pain in the ass）。好的。

我要结束这个演讲了。演讲的最后一部分将聚焦于一些适合完美哈希的用例。好的。我们已经看到了一些。比如第一个，转换表或关键字检测。这就像是完美哈希表的典型用例。你有一些预先知道的关键字或字符串集合。你想尽可能快地判断某个输入字符串是否属于该集合。好的。另一个用例是你很少更新表。就像你创建它之后，可能再更新一两次。但你读取（read）很多很多次。一个典型的用例是JSON对象。你从某个文件获取JSON对象。然后你多次查询这个JSON对象。好的。所以这将是一个非常适合完美哈希的案例。另一个用例是我们昨天看到的，Jean-Louis Leroy的库jump to。他使用完美哈希作为虚拟方法等的分派表（dispatch table）。所以这个分派表只在程序开始时创建一次，或者如果动态库被加载了，可能再创建一次。但除此之外，它是固定的。因此，为了尽可能加速那里的查找，使用完美哈希是有意义的。好的。

另一个用例是更快的switch语句。我们将重点讨论这个来结束演讲。另一个我们不讨论的用例是数据库索引。我们不讨论它，因为这需要我们之前讨论过的压缩部分。当我们在处理数百万、数千万或数亿元素的数据集时。好的。这有点超出本次演讲的范围了。

那么，让我们看看如何改进我们的switch语句。好的。这是一个例子，我有一个函数foog，它接收一个输入值x，x可能取任何值。但如果值在0到4之间，那么我们在一个外部变量y上执行一些操作。所以如果x是0，那么y乘以2。如果是1，我们加上7，依此类推。好的。你可以在那里看到汇编代码。这段代码非常好，因为它只有两个分支。这个分支是确定x是否在0到4之间。这是一个跳转表，根据x的值，我们执行相关的操作。这些是操作。所以这很容易阅读。好的。那么，如果这些非常连续的数值，我们让它们分散一点会怎么样呢？

好的。所以不是0,1,2,3,4，而是这些值。然后，编译器再次认为值得保持跳转表方法。它基本上扩展了跳转表，并为switch中未覆盖的情况（如1或4,5,6等）插入什么都不做的操作（do nothing operations）。好的。但如果我们让数值更稀疏，编译器就放弃了。在这种情况下，它决定跳转表不再有效。它基本上是在对x的不同值进行二分查找。所以它首先与31比较。如果小于32，它就转到那部分。否则，它转到那部分。所以这有多达四个分支。我们能做得比这更好吗？是的，我们可以使用完美哈希来做得更好。

像这里这样。所以这是一个非常非常微小的最小完美哈希表，它将你之前看到的数值（10, 21, 32等）映射到值0,1,2,3,4和5。意思是该值不在集合中。好的。我们不在x上做switch，而是在x的完美哈希函数值上做switch。所以switch的值是0,1,…5。任何大于5的情况都是不可达的。我们可以告诉编译器它是不可达的。编译器将利用这个信息。生成的代码只有两个分支。好的。这有多酷？嗯，你必须非常小心。一旦你开始做这些微优化，如果你改变一点点东西，那么整个事情可能就毁了等等。但它表明，对于这些微用例（micro-use cases），完美哈希也是有意义的。好的。

那么字符串呢？如你所知，你不能在字符串上做switch。所以如果输入值不是整数值而是字符串，那么你唯一能做的就是做一系列if检查。好的。这是生成的代码。编译器非常聪明，因为它判断出所有针对字符串的检查长度都是1。它首先验证输入值的长度是否为1。如果长度不是1，那么我们就完成了。不需要采取任何动作。如果输入值长度为1，那么与不同值的比较只在这个字符上进行。所以即使这不是最优的，或者我们可以做得更好，编译器在这里已经极其明智、极其聪明了。好的。我们怎样才能做得更好？我们可以通过拥有一个完美哈希函数将其转换为真正的switch，这个函数基本上像之前处理数字那样处理字符串。当字符串是”0”到”4”时，它返回一个整数值0到4。否则，它返回5。嗯，不是5。在这种情况下，它也可以返回任何非0-4的值。好的。生成的switch像这样。我们已经从最坏情况下多达6个分支减少到这里平均情况下3个分支。好的。所以这是完美哈希的一个很好的应用。

那么，结论。所以从这个完美哈希演讲中得出的关键见解和要点是：完美哈希不是常规哈希的替代品。当你预先知道关键元素时，你可以尝试用它来加速查找。如果你知道它们，那么你可以尝试一下，因为你处于一个非常注重性能的场景或类似的情况。

有两种算法或宽泛的方法来实现完美哈希：基于通用哈希函数或基于工程化的哈希函数。你将要使用的工具可能遵循三种不同的方法：它必须在预处理时、编译时还是运行时使用。

GPERF是一个非常棒的工具。即使它非常非常古老，我认为它很难被超越。好的。而constexpr构造完美哈希表以及一般的容器仍然不尽如人意。我的意思是，constexpr存在一些限制，使得做这种事情有点困难。其中之一是我们不能在constexpr中分配动态内存。换句话说，我们可以做，但当constexpr函数结束时，所有分配的内存必须被释放。好的。委员会正在讨论一些提案，旨在增加constexpr的能力，以便可以完成非瞬时或持久的动态内存分配。这对于创建编译时数据结构将非常非常有用。

我们正在继续研究是否应该为Boost提供或制作一个完美哈希容器。所以如果你对这个讨论感兴趣，请加入我们的cpplang.slack.com。基本上就是这样了。谢谢。

谢谢。谢谢。谢谢。非常感谢。

（掌声）

那么，提问。谢谢。谢谢。谢谢你的演讲。谢谢。我想知道关于运行时的用例，你尝试使用通用哈希函数。在那种情况下，你是否还必须为后备场景编写代码，即它无法创建？然后你必须用常规哈希表来编程？后备情况？在哈希函数无法找到唯一值的情况下？我不这么认为。我的意思是，提供后备情况的问题在于，它会影响常规情况下的查找性能。因为你必须检查我是否处于后备情况。好的。好的。所以在我见过的所有情况下，你基本上假设事情会成功。否则你就抛出一个异常。这是个问题。但这并不比在常规哈希容器中遇到病态哈希函数的问题更大。因为即使你不会得到异常，你的查找时间也会糟糕到让你的程序卡住。所以你必须考虑，我的意思是，可能有些直觉或类似上帝的感觉认为抛出异常更好，因为我无法创建哈希表。但如果你理性地思考，我不太确定哪个更糟。好的。非常感谢。不客气。还有问题吗？

看起来人们想要咖啡了。是的。

谢谢。谢谢。