2025/02/11 12:56

本科生推翻姚期智40年前的猜想，哈希表的平均查询时间竟与填满程度无关

1985 年，著名计算机科学家、图灵奖得主姚期智提出了一个与哈希表有关的猜想。现在，40 年过去了，一名本科生却成功推翻了这个猜想。而这项成就却源自一个始于 2021 年秋的故事。

量子杂志近日报道了这个故事，机器之心编译了该文章以飨读者。

原文地址：https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/

2021 年秋季的某天，罗格斯大学的一位本科生 Andrew Krapivin 遇到了一篇论文，而这篇论文将改变他的一生。不过那时候，Krapivin 倒没有多想。两年之后，当他终于有空细读这篇论文时（他说当时只是为了好玩），他还没意识到：他的工作将让人重新审视计算机科学领域一种被广泛使用的工具。

这篇论文题为「Tiny Pointers」，即微型指针。这是一种类似箭头的东西，指向的是计算机内存中的一段信息或一个元素。Krapivin 很快就发现了一种有望进一步降低指针内存使用量的方法。但首先，他需要一种更好的方法来组织指针指向的数据。

论文标题：Tiny Pointers
论文地址：https://arxiv.org/pdf/2111.12800

他的方法是使用一种常用于存储数据的方法，即哈希表（hash table）。在探索研究的过程中，Krapivin 最终发现了一种新的哈希表。并且这种新哈希表的工作速度更快 —— 用更少的时间和步数便能找到指定元素。

不过，Krapivin 之前的教授 Martín Farach-Colton 起初对这个新设计深感怀疑，毕竟哈希表似乎早已被人研究透了，很难再取得新进展。

但直觉上的看法并不一定总是对的。为了确认这个新设计的有效性，Farach-Colton 邀请了卡内基梅隆大学的 William Kuszmaul 检查 Krapivin 的新发明。

Kuszmaul 深感振奋。他记得自己当时对 Krapivin 说：「你不只是想出了一个很酷的哈希表，你实际上彻底推翻了一个已有 40 年的猜想！」

^{Andrew Krapivin 颠覆了人们对哈希表的普遍看法 —— 即便他一开始并没有这样的打算。哈希表是计算机科学中被研究得最透彻的工具之一。}

本科生推翻存在 40 年的猜想

Krapivin 推翻的是著名计算机科学家、图灵奖得主姚期智在 1985 年提出的一项研究。

他们的研究过程是这样的。1 月份，剑桥大学研究生 Krapivin、任职于纽约大学的 Farach-Colton 以及 Kuszmaul 共同发表了一篇文章。

这篇文章重新探讨了开放寻址哈希表（open-addressed hash table）的最优搜索复杂度，以便在检索时能以尽可能少的探测次数找到元素。文章提出了两种新的哈希表插入策略 —— 弹性哈希（elastic hashing）和漏斗哈希（funnel hashing），并证明了，即使不随时间重新排列元素，也可以构建一种哈希表，其预期的搜索复杂度（无论是摊销复杂度还是最坏情况）远超以往认为可能的水平。

论文标题：Optimal Bounds for Open Addressing Without Reordering
论文地址：https://arxiv.org/pdf/2501.02305

在论文摘要部分，他们强调了这项研究推翻了姚期智在其开创性论文《Uniform Hashing is Optimal》中留下的核心猜想，并给出了相关的下界证明。

众所周知，哈希表在计算领域已变得无处不在，主要在于其简单性和易用性。它通过将数据映射到一个固定大小的数组中，从而实现快速的插入、删除和查询操作。哈希表的核心思想是利用哈希函数（Hash Function）将数据的键（Key）转换为数组的索引（Index），从而快速定位数据存储的位置。

最早的哈希表可以追溯到 20 世纪 50 年代初，自那时起，计算机科学家一直在研究和使用它们。研究人员希望弄清楚这些操作的速度极限。例如，新的搜索或插入可能有多快？

^{Martín Farach-Colton 帮助 Krapivin 证明了新哈希表与一个长期存在的猜想相矛盾}

答案通常取决于在哈希表中找到一个空位所需的时间。而这通常又取决于哈希表的填充程度。

填充程度可以用百分比表示，比如 50% 或 90%，但在研究中，哈希表往往接近完全填满。

为了更精确地描述这种高填充状态，研究者们可能会使用一个整数（记作 x）来表示哈希表接近 100% 满的程度。如果 x 是 100，那么哈希表是 99% 满的；如果 x 是 1,000，那么哈希表是 99.9% 满的。

这种衡量填充程度的方法为评估执行查询或插入等操作所需的时间提供了一种便捷的方式。

此前，研究人员得出这样一个结论，对于某些常见的哈希表，执行最坏情况下插入操作所需的预期时间与 x 成正比。Kuszmaul 表示：「如果你的哈希表是 99% 满的，那么你需要查看大约 100 个不同的位置才能找到一个空闲槽位，这种情况是合理的。」

著名计算机科学家姚期智在这篇论文中提出，在具有特定属性的哈希表中，查找单个元素或空位的最佳方法是随机地遍历潜在的位置 —— 这种方法被称为均匀探测（uniform probing）。他还指出，在最坏的情况下（即寻找最后一个空闲位置时），你无法做得比 x 更好。

论文标题：Uniform Hashing Is Optimal
论文地址：https://dl.acm.org/doi/pdf/10.1145/3828.3836

40 年来，大多数计算机科学家都认为姚期智的猜想是正确的。

Krapivin 没有囿于传统的想法，原因很简单：他不知道这个传统的想法。他说：「我在不知道姚期智猜想的情况下做到了这一点。」这让 Tapline 联合创始人兼 CEO 不禁在 𝕏 上感叹说：「无知也是一种福气。」

Krapivin 在微型指针方面进行的探索最终得到了一种新的哈希表 —— 一种不依赖于均匀探测的哈希表。

对于这种新的哈希表，最坏情况查询和插入所需的时间与 (log x)² 成正比 —— 比 x 快得多。这个结果直接与姚期智的猜想相矛盾。Farach-Colton 和 Kuszmaul 帮助 Krapivin 证明了 (log x)² 是姚期智所写的常见哈希表类别的最佳、不可超越的界限。

卡内基梅隆大学的 Guy Blelloch 赞道：「这个结果非常美妙，因为它重新审视并解决了这样一个经典问题。」

滑铁卢大学的 Sepehr Assadi 表示：「他们不仅证否了 [姚期智猜想]，还找到了该问题的最佳答案。我们原本可能还要再等 40 年才能知道这个正确答案。」

^{Krapivin 在剑桥大学的国王学院桥上。他的新哈希表可以超出研究者预料的速度更快地查找和存储数据。}

除了证否姚期智的猜想外，这篇论文还包含许多更惊人的结果。这与一个相关但略有不同的情况有关：1985 年，姚期智不仅研究了查询的最坏情况时间，还研究了所有可能查询的平均时间。他证明：具有某些属性的哈希表（包括被标记为「贪婪」的哈希表，这意味着新元素必须放在第一个可用位置）的平均时间永远不会比 log x 好。

Farach-Colton、Krapivin 和 Kuszmaul 想看看对于非贪婪哈希表，这个限制是否同样适用。

最终，他们表明这个限制不适用。证明过程很简单，他们提供了一个反例，即一个平均查询时间远远好于 log x 的非贪婪哈希表。事实上，它根本与 x 无关。

Farach-Colton 说：「你会得到一个数值，而这个数值就是一个常量，与哈希表的填满程度没有关系。」也就是说，无论这个哈希表的填满程度如何，平均查询时间都是一个常量。

这一事实大出人们意料 —— 甚至连这几位作者自己也没有想到。

Conway 说，该团队得到的结果可能不会带来任何直接的应用，但这并不重要。「更好地理解这些类型的数据结构很重要。你不知道这样的结果何时会造就一些东西，从而让你创造更好的实践。」

工程