Illustration: Nash Weerasekera for Quanta Magazine

本故事的原始版本 发表于 Quanta Magazine.

2021 年秋天的某个时候，Rutgers University 的本科生 Andrew Krapivin 遇到了一篇改变他人生的论文。当时，Krapivin 并没有多想。但两年后，当他最终抽出时间阅读这篇论文（正如他所说，“只是为了好玩”）时，他的努力将导致人们重新思考计算机科学中一种被广泛使用的工具。

这篇论文的标题“Tiny Pointers”指的是箭头状的实体，它可以将你引导到计算机内存中的一条信息或一个元素。 Krapivin 很快想出了一种潜在的方法，可以进一步缩小指针的尺寸，从而减少内存消耗。然而，为了实现这一点，他需要一种更好的方法来组织指针将指向的数据。

他求助于一种常见的数据存储方法，称为 hash table。但在他修补的过程中，Krapivin 意识到他发明了一种新型的 hash table，它的工作速度比预期的要快——花费更少的时间和更少的步骤来查找特定的元素。

Martín Farach-Colton 是“Tiny Pointers”论文的合著者，也是 Krapivin 在 Rutgers 的前教授，最初对 Krapivin 的新设计持怀疑态度。 Hash table 是计算机科学中研究最透彻的数据结构之一；这一进展听起来好得令人难以置信。但为了确保这一点，他请一位经常合作者（也是“Tiny Pointers”的合著者）、Carnegie Mellon University 的 William Kuszmaul 来检查一下他学生的发明。 Kuszmaul 的反应不同。“你不仅仅是提出了一个很酷的 hash table，”他回忆起对 Krapivin 说的话。“你实际上完全抹去了一个具有 40 年历史的猜想！”

在无意为之的情况下，Andrew Krapivin 颠覆了关于 hash table 的普遍看法，hash table 是计算机科学中研究得最好的工具之一。

Together, Krapivin (now a graduate student at the University of Cambridge), Farach-Colton (now at New York University), and Kuszmaul demonstrated in a January 2025 paper that this new hash table can indeed find elements faster than was considered possible. ln so doing, they had disproved a conjecture long held to be true.

纽约市 Cornell Tech 的 Alex Conway 说：“这是一篇重要的论文。” “Hash table 是我们拥有的最古老的数据结构之一。而且它们仍然是存储数据最有效的方式之一。” 他说，关于它们的工作原理，仍然存在一些悬而未决的问题。“这篇论文以令人惊讶的方式回答了其中的几个问题。”

Hash table 已经变得在计算中无处不在，部分原因是它们的简单性和易用性。它们旨在允许用户准确地执行三件事：“查询”（搜索）一个元素，删除一个元素，或将一个元素插入到一个空槽中。第一个 hash table 可以追溯到 1950 年代初期，此后计算机科学家一直在研究和使用它们。除其他外，研究人员希望找出其中一些操作的速度限制。例如，新的搜索或插入可能有多快？

Martín Farach-Colton 帮助 Krapivin 证明他的新 hash table 与一个长期存在的猜想相矛盾。

答案通常取决于在 hash table 中找到一个空位所需的时间。反过来，这通常取决于 hash table 有多满。完整度可以用总百分比来描述——这个表是 50% 满，那个表是 90% 满——但研究人员通常处理更满的表。因此，他们可能会使用一个整数（用 x 表示）来指定 hash table 离 100% 满有多近。如果 x 是 100，那么该表是 99% 满。如果 x 是 1,000，则该表是 99.9% 满。这种完整度的衡量标准提供了一种方便的方法来评估执行查询或插入等操作应该花费多长时间。

研究人员早就知道，对于某些常见的 hash table，进行最坏情况下的插入（例如，将一个项目放入最后一个剩余的空位）所需的预期时间与 x 成正比。 Kuszmaul 说：“如果你的 hash table 是 99% 满的，那么你必须查看大约 100 个不同的位置才能找到一个空闲的槽，这是有道理的。”

在 1985 年的一篇论文 中，计算机科学家 Andrew Yao （后来获得了 A.M. Turing Award）断言，在具有一组特定属性的 hash table 中，找到单个元素或空位的最佳方法是随机地浏览潜在的位置——这种方法被称为 uniform probing。他还指出，在最坏的情况下，当你正在搜索最后一个剩余的空位时，你永远不可能比 x 做得更好。 40 年来，大多数计算机科学家都认为 Yao 的猜想是正确的。

Krapivin 没有受到传统智慧的束缚，原因很简单，他对此一无所知。 “我在不知道 Yao 的猜想的情况下完成了这件事，”他说。他对 tiny pointers 的探索导致了一种新型的 hash table ——这种 hash table 不依赖于 uniform probing。而且对于这个新的 hash table，最坏情况下的查询和插入所需的时间与 (log x)2 成正比——比 x 快得多。这个结果直接与 Yao 的猜想相矛盾。 Farach-Colton 和 Kuszmaul 帮助 Krapivin 证明 (log x)2 是 Yao 撰写的那类流行的 hash table 的最佳、不可战胜的界限。

Carnegie Mellon 的 Guy Blelloch 说：“这个结果很棒，因为它解决了这样一个经典问题。”

滑铁卢大学的 Sepehr Assadi 说：“不仅仅是他们推翻了 [Yao 的猜想]，他们还找到了他的问题的最佳答案。” “我们可能还要再过 40 年才能知道正确的答案。”

Krapivin 在 Cambridge 大学的 King’s College Bridge 上。他的新 hash table 可以比研究人员想象的更快地查找和存储数据。

除了驳斥 Yao 的猜想之外，这篇新论文还包含许多人认为更令人惊讶的结果。它涉及一种相关但略有不同的情况：1985 年，Yao 不仅研究了查询的最坏情况时间，还研究了所有可能查询的平均时间。他证明，具有某些属性的 hash table ——包括那些被标记为“贪婪”的 hash table，这意味着必须将新元素放置在第一个可用的位置 ——永远无法实现比 log x 更好的平均时间。

Farach-Colton、Krapivin 和 Kuszmaul 想看看同样的限制是否也适用于非贪婪的 hash table。他们通过提供一个反例表明并非如此，这是一个非贪婪的 hash table，其平均查询时间比 log x 好得多。事实上，它根本不依赖于 x 。 Farach-Colton 说：“你会得到一个数字，一个只是常数并且不依赖于 hash table 有多满的数字。” 无论 hash table 的完整度如何，都可以实现恒定的平均查询时间，这一事实完全出乎意料 —— 即使是对作者自己也是如此。

Conway 说，该团队的结果可能不会立即导致任何应用，但这并不是全部。 “更好地理解这些类型的数据结构很重要。你不知道何时这样的结果会解锁一些东西，让你在实践中做得更好。”

原始故事 经 Simons Foundation 许可转载，Simons Foundation 是一个编辑上独立的出版物，其使命是通过报道数学以及物理和生命科学的研究进展和趋势来提高公众对科学的理解。