一个年轻的计算机科学家和他的两位同事证明，在名为 Hash Table 的数据结构中进行搜索可以比之前认为的更快。

Image may contain Drawer Furniture and Cabinet

该故事的原始版本出现在 Quanta Magazine。

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

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

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

“Tiny Pointers”论文的合著者以及 Krapivin 在罗格斯大学的前教授 Martín Farach-Colton 最初对 Krapivin 的新设计持怀疑态度。 Hash Table 是计算机科学中研究最透彻的数据结构之一；这一进步听起来好得令人难以置信。但为了确保万无一失，他请一位经常合作者（以及“Tiny Pointers”的合著者）、卡内基梅隆大学的 William Kuszmaul 来检查他学生的发明。 Kuszmaul 的反应不同。“你不仅仅是提出了一个很棒的 Hash Table，”他回忆起对 Krapivin 说。“你实际上已经彻底推翻了一个有 40 年历史的猜想！”

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

如今，Krapivin（现在是剑桥大学的研究生）、Farach-Colton（现在在纽约大学）和 Kuszmaul 在 2025 年 1 月的一篇论文 中证明，这种新的 Hash Table 确实可以比先前认为的更快地找到元素。 这样做，他们推翻了一个长期以来被认为是正确的猜想。

康奈尔科技大学的 Alex Conway 说：“这是一篇重要的论文。” “Hash Table 是我们拥有的最古老的数据结构之一。而且它们仍然是存储数据的最有效方法之一。” 但他表示，关于它们如何运作，仍存在一些悬而未决的问题。“这篇论文以令人惊讶的方式回答了其中的几个问题。”

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

答案通常取决于在 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. 图灵奖）断言，在具有特定属性的一组 Hash Table 中，找到单个元素或空位的最佳方法是随机地遍历潜在的位置——这种方法被称为均匀探测。 他还指出，在最坏的情况下（你在搜索最后一个剩余的空位），你永远无法做得比 x 更好。 40 年来，大多数计算机科学家都认为 Yao 的猜想是正确的。

Krapivin 没有受到传统智慧的束缚，原因很简单，他不知道它。“我做这件事的时候并不知道姚的猜想，”他说。 他对 Tiny Pointers 的探索产生了一种新型 Hash Table——一种不依赖于均匀探测的 Hash Table。 对于这种新的 Hash Table，最坏情况查询和插入所需的时间与 (log x)2 成正比——远快于 x。 这个结果直接与姚的猜想相矛盾。 Farach-Colton 和 Kuszmaul 帮助 Krapivin 证明了 (log x)2 是姚所写的流行 Hash Table 类的最佳、无与伦比的界限。

卡内基梅隆大学的 Guy Blelloch 说：“这个结果很漂亮，因为它解决了这样一个经典问题。”

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

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

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

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

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