¶前言
本文原文发表于《广达杂志》（Quanta Magazine）。
本文原文_发表于 《广达杂志》（Quanta Magazine）。_
2021 年秋天的某个时候，罗格斯大学 （Rutgers University） 的本科生安德鲁·克拉皮文 （Andrew Krapivin） 遇到了一篇改变他生活的论文。当时，克拉皮文并没有多想。但两年后，当他终于抽出时间阅读这篇论文时（用他的话说，“只是为了好玩”），他的努力将导致对计算机科学中广泛使用的工具的重新思考。
该论文的标题“Tiny Pointers”指的是箭头状实体，可以将您引导至计算机内存中的一条信息或元素。Krapivin 很快就想出了一种潜在的方法来进一步缩小指针，从而减少它们消耗的内存。但是，为了实现这一点，他需要一种更好的方法来组织指针将指向的数据。
他转向了一种称为哈希表的常用数据存储方法。但在修补过程中，Krapivin 意识到他发明了一种新型的哈希表，这种表的运行速度比预期的要快 — 查找特定元素所需的时间和步骤更少。
“Tiny Pointers”论文的合著者、Krapivin 在罗格斯大学的前教授 Martín Farach-Colton 最初对 Krapivin 的新设计持怀疑态度。哈希表是所有计算机科学中研究最深入的数据结构之一;这个预告听起来好得令人难以置信。但为了保险起见，他请了一位经常合作的人（也是《Tiny Pointers》的合著者），卡内基梅隆大学的威廉·库斯莫尔（William Kuszmaul）来看看他学生的发明。库斯莫尔有不同的反应。“你不只是想出了一个很酷的哈希表，”他记得对 Krapivin 说。“你居然彻底抹杀了一个 40 年前的猜想！”
Andrew Krapivin 没有打算这样做，它颠覆了围绕哈希表的常见思维，哈希表是计算机科学中研究得最多的工具之一。
照片：Phillip Ammon for Quanta Magazine
Krapivin（现在是剑桥大学的研究生）、Farach-Colton（现在在纽约大学）和 Kuszmaul 在 2025 年 1 月的一篇论文中一起证明，这种新的哈希表确实可以比人们认为的更快地找到元素。他们这样做，就反驳了一个长期以来被认为是正确的猜想。
“这是一篇重要的论文，”纽约市康奈尔理工学院的亚历克斯·康威（Alex Conway）说。“哈希表是我们拥有的最古老的数据结构之一。而且它们仍然是最有效的数据存储方式之一。然而，他说，关于它们如何运作仍然存在悬而未决的问题。“这篇论文以令人惊讶的方式回答了其中的几个问题。”
哈希表在计算中无处不在，部分原因是它们的简单性和易用性。它们旨在允许用户执行三项作：“查询”（搜索）元素、删除元素或将元素插入空槽。第一个哈希表可以追溯到 1950 年代初，从那时起，计算机科学家一直在研究和使用它们。除其他外，研究人员希望弄清楚其中一些作的速度限制。例如，新的搜索或插入可能有多快？
Martín Farach-Colton 帮助 Krapivin 证明他的新哈希表与一个长期存在的猜想相矛盾。
摄影：Andrew Farach-Colton
答案通常取决于在哈希表中查找空位所需的时间。反过来，这通常取决于哈希表的填充程度。充实度可以用总体百分比来描述——这个表格是 50%，那个表格是 90%——但研究人员经常处理更完整的表格。因此，他们可能会使用一个由 x 表示的整数来指定哈希表接近 100% 满的程度。如果 x 为 100，则表已满 99%。如果 x 为 1,000，则表已满 99.9%。这种填充度度量提供了一种便捷的方法来评估执行查询或插入等作需要多长时间。
研究人员早就知道，对于某些常见的哈希表，进行最差的可能插入（例如，将项目放入最后一个剩余的空位）所需的预期时间与 x 成正比。“如果你的哈希表已经满了 99%，”Kuszmaul 说，“那么你必须查看大约 100 个不同的位置才能找到一个空闲位置是有道理的。
在 1985 年的一篇论文中，后来获得 A.M. 图灵奖的计算机科学家 Andrew Yao 断言，在具有一组特定属性的哈希表中，查找单个元素或空点的最佳方法是随机遍历潜在点，这种方法称为统一探测。他还表示，在最坏的情况下，你正在寻找最后一个剩余的空位，你永远无法做得比 x 更好。40 年来，大多数计算机科学家都认为姚明的猜想是正确的。
克拉皮文并没有被传统智慧所阻碍，原因很简单，他没有意识到这一点。“我在不知道姚明的猜想的情况下做了这件事，”他说。他对微小指针的探索导致了一种新型的哈希表，一种不依赖于统一探测的哈希表。对于这个新的哈希表，最坏情况下的查询和插入所需的时间与 （log x）2 成正比，比 x 快得多。这个结果直接与姚的猜想相矛盾。Farach-Colton 和 Kuszmaul 帮助 Krapivin 证明 （log x）2 是 Yao 所写的流行哈希表类别的最佳、无敌的边界。
“这个结果很美，因为它解决并解决了这样一个经典问题，”卡内基梅隆大学的 Guy Blelloch 说。
“他们不仅反驳了[姚明的猜想]，还为他的问题找到了最好的答案，”滑铁卢大学（University of Waterloo）的塞佩尔·阿萨迪（Sepehr Assadi）说。“我们本可以再过 40 年才知道正确的答案。”
剑桥大学国王学院桥上的 Krapivin。他的新哈希表可以以前所未有的速度查找和存储数据。
照片：Phillip Ammon 为 Quanta 杂志拍摄
除了反驳姚明的猜想外，这篇新论文还包含了许多人认为更令人惊讶的结果。它与一个相关但略有不同的情况有关：在 1985 年，Yao 不仅研究了查询的最坏情况，还研究了所有可能的查询所花费的平均时间。他证明，具有某些属性的哈希表（包括那些标记为“贪婪”的哈希表，这意味着必须将新元素放置在第一个可用位置）永远无法实现比 log x 更好的平均时间。
Farach-Colton、Krapivin 和 Kuszmaul 想看看同样的限制是否也适用于非贪婪哈希表。他们通过提供一个反例来证明它没有，一个非贪婪哈希表，平均查询时间比 log x 好得多。事实上，它根本不依赖于 x。“你会得到一个数字，”Farach-Colton 说，“它只是一个常数，不取决于哈希表的填充程度。无论哈希表的填充度如何，您都可以实现恒定的平均查询时间，这一事实完全出乎意料，即使对作者自己也是如此。
Conway 说，该团队的结果可能不会立即导致任何申请，但这并不是最重要的。“更好地了解这类数据结构很重要。你不知道这样的结果什么时候会解锁一些让你在练习中做得更好的东西。
原文经 Quanta Magazine 许可转载，Quanta Magazine 是 Simons 基金会的独立编辑出版物 ，其使命是通过报道数学、物理和生命科学的研究发展和趋势来增强公众对科学的理解。