本科生推翻姚期智40年前猜想！CS顶会论文刷新哈希表传统认知

新智元报道

编辑：KingHZ

【新智元导读】图灵奖得主姚期智40年来公认正确的猜想，被推翻了！Andrew Krapivin和合作者一起提出的了全新哈希算法，突破了哈希表搜索效率的极限。相关论文已被计算机理论顶会FOCS 2024接受。而Krapivin提出关键思路时，还只是个本科生，甚至都不知道「姚期智猜想」。

因为证明了弱化版的「孪生素数猜想」，当年58岁的张益唐一鸣惊人，蜚声全球。

据说，在证明发表之前，相关领域的顶尖数学家，召开了研讨会，讨论后失望的认为：目前的技术无法进一步推动「孪生素数猜想」取得实质性进展。

而当时，几乎在学术界「透明」的张益唐，甚至都不知道研讨会何时何地召开过。

类似的故事，再次上演！

不同的是，这一次发生在计算机理论领域，而做出主要发现时，主角还是个本科生！

同样的因为没接触相关「劝退」言论，没有成见，最终拓展了人类知识的边界。

本月10日，Quanta杂志报道了Andrew Krapivin如何颠覆CS理论，终结图灵奖得主姚期智在40年前提出的猜想。

改变一生的邂逅

2021年秋天，Rutgers大学的本科生Andrew Krapivin偶然读到了一篇论文，而这篇论文最终改变了他的一生。刚开始，他却并没有太在意这篇文章。但两年后，当他终于抽出时间细读（正如他所说，「只是为了好玩」），他的研究成果却引发了人们对计算机科学中一项广泛使用工具的全新思考。

Krapivin偶遇的论文是《Tiny Pointers》。

论文链接：https://arxiv.org/pdf/2111.12800

可以把「微指针」（Tiny Pointer）想象成类似指路牌的东西，可以把你引导到计算机内存中的某个信息或元素。

「微指针」（tiny pointer）是一种新的数据结构，用于压缩传统指针。在使用指针的许多场景中，微指针可以用来替代传统指针，消除几乎所有的空间开销。

Krapivin很快提出了一种可能的方法，进一步缩小微指针的大小，减少内存占用。然而，要实现这一目标，他需要更好的方式来组织指针所指向的数据。

他转向了常见的数据存储方法——哈希表。在不断实验的过程中，Krapivin意识到自己创造了一种全新的哈希表，

这种哈希表的工作速度比预期更快——用更少的时间和步骤就能找到特定的元素。

Andrew Krapivin并未刻意为之，却颠覆了计算机科学中研究最深入的工具之一——哈希表的传统认知。

哈希表可能是应用最广泛的数据结构之一：每次登录新账号，哈希表可能都要被调用一次。

哈希表算法主要有两部分构成：哈希算法和冲突处理算法。

哈希算法可以将计算机中的对象转变为长度固定的一串数字，叫做哈希值。利用哈希值，哈希表可以查询到真正需要的对象所在的「地址」，从而操作相关内容。

问题出现在，哈希值并不能保证唯一性：不同的对象可能会有相同的哈希值。

这就需要冲突处理算法，将同一哈希值的不同对象映射到不同的地址。

然而，随着哈希表中数据越来越多，冲突处理起来也越来越难。

新算法有望缓解这一问题: 开放地址法 (Open Addressing)--常见的冲突处理算法--这一次的复杂度达被证明并没有以前设想的大。

怪不得当时Krapivin的教授Martín Farach-Colton，会怀疑他提出的哈希表设计。

40年前的猜想被推翻

哈希表作为计算机科学中研究最深入的数据结构之一，Krapivin的突破听起来像神话，令人难以置信。

为了验证这一设计的可行性，Farach-Colton请来了他在《Tiny Pointers》论文中的长期合作者、卡内基梅隆大学的William Kuszmaul，共同审查这一发明。

然而，Kuszmaul的反应与Farach-Colton截然不同。

他记得当时对Krapivin说：「你不仅仅是发明了一个优良的哈希表。你实际上完全推翻了一个存在了40年的猜想！」

在2025年1月，Krapivin（现在是剑桥大学的研究生）、Farach-Colton（现在在纽约大学）和Kuszmaul在论文中共同证明，这种新的哈希表确实能够比以往认为可能的更快地找到元素。一举推翻了长期被认为正确的猜想。

论文链接：https://arxiv.org/pdf/2501.02305

实际上，在去年，相关研究在计算机理论界已引起关注。在领域Top2会议FOCS2024上，Krapivin已介绍过同名论文。

消息来源：https://focs.computer.org/2024/program/schedule/

在摘要中，他们认为新方法的期望搜索复杂度远远比之前大家所想的低：

本文重新审视了数据结构中最简单的问题之一：将元素插入开放寻址哈希表，以便以后能够用尽可能少的探测操作来检索元素。 我们证明，即使不随时间重新排序元素，也可以构建哈希表，其期望搜索复杂度（包括摊销（amortized）复杂度和最坏情况复杂度）远远优于之前认为可能实现的结果。 由此，我们推翻了姚期智开创性论文《Uniform Hashing is Optimal》中的核心猜想。我们所有的结果都有相应的下界。

纽约市康奈尔大学科技校区（Cornell Tech）的Alex Conway表示：「这是一篇重要的论文。哈希表是我们拥有的最古老的数据结构之一，而且它们仍然是存储数据的最有效方式之一。」

然而，他表示关于它们如何工作的开放性问题仍然存在，这篇论文以令人惊讶的方式回答了其中几个问题。

哈希表在计算机领域已变得无处不在，这在一定程度上要归功于它们的简洁性和易用性。哈希表的设计允许用户执行三项基本操作：查询（搜索）、删除以及插入元素。最早的哈希表可追溯到1950年代初期，计算机科学家从那时起就一直在研究和使用它们。研究者们的一个目标是找出这些操作的速度限制。例如，新的搜索或插入操作最快能达到什么速度？

在哈希表中查找空位所需的时间，通常取决于哈希表的满载程度。满载程度可以用百分比来描述。例如，这个表是50%满的，那个表是90%满的。

但研究人员通常处理的是更高填充度的情况。因此，他们可能使用一个整数x来指定哈希表接近100%满的程度。如果x是100，那么表是99%满的。如果x是1,000，那么表是99.9%满的。这一填充度的衡量方式为评估查询或插入等操作所需时间提供了方便的标准。

研究人员早就知道，对于某些常见的哈希表，最坏情况下插入操作所需的时间——比如把某个元素放入最后剩余的空位——与x成正比。Kuszmaul说：「如果你的哈希表填充了99%，那么你可能需要检查大约100个位置才能找到一个空位。」

在1985年，姚期智（未来的图灵奖得主，清华「姚班之父」）在一篇论文中提出，对于具有特定属性的哈希表，查找一个元素或空位的最佳方法是随机遍历所有潜在位置，这种方法被称为均匀探测（uniform probing）。

他还指出，在最坏的情况下，查找最后一个空位时，所需时间永远不会优于x。

论文链接：https://dl.acm.org/doi/10.1145/3828.3836

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

然而，Krapivin并没有被这种传统观点所束缚，因为他根本不知道这一猜想。

他说：「做这个研究时，我并不知道姚期智的猜想」。

在Farach-Colton和Kuszmaul帮助下，Krapivin推翻了姚期智在40年前提出的猜想。

具体而言，全新的哈希表不依赖于均匀探测，而且就是姚期智所讨论的常见哈希表，但最优、不可超越的上限是(log x)²，而不是姚期智所猜想的x。

下图更直观的比较了两者复杂度，其中红色表示姚期智猜想的复杂度，蓝色表示新算法的复杂度。

而这一切都源于他偶然接触到的微指针论文。

卡内基梅隆大学的Guy Blelloch表示：「这个结果非常漂亮，因为它解决了一个经典问题。」

滑铁卢大学的Sepehr Assadi表示：「他们不仅仅是推翻了姚期智的猜想，他们还找到了问题的最佳答案。如果没有这个研究，我们可能还要等40年才能得到正确的答案。」

常数查询哈希表

除了推翻姚期智的猜想，这篇新论文还包含了更加令人惊讶的结果。

这与一个相关但稍有不同的情况有关：1985年，姚期智不仅研究了查询的最坏情况时间，还研究了所有可能查询的平均时间。他证明了：具有某些特性的哈希表——包括「贪婪」哈希表（即新元素必须放置在第一个可用位置的哈希表）——平均查询时间无法优于log x。

Farach-Colton、Krapivin和Kuszmaul想要验证这个限制是否同样适用于非贪心哈希表。

结果他们发现并不适用，并通过一个反例证明了这一点：他们构造了一个非贪心哈希表，其平均查询时间远远优于 log x，甚至完全不依赖于 x。

Farach-Colton解释道：「你会得到一个固定的数值，这只是一个常数，与哈希表的填充程度无关。」

也就是说，平均查询时间是恒定的，不受哈希表填充度的影响。

这一发现完全出乎意料，甚至连研究作者自己都感到惊讶。

Conway说道，团队的研究成果可能不会立即带来实际应用，但这并不重要。「更好理解这类数据结构很重要。你无法预见这样的研究何时会带来突破，从而在实际应用中取得更好的效果。」

主人公介绍

目前，Andrew Krapivin在剑桥大学攻读计算机科学硕士学位。之前，他在Rutgers大学荣誉学院（Honors College ）攻读数学和计算机科学的双学位。因上文报道的研究工作，先后获得美国Goldwater奖学金和剑桥大学的丘吉尔奖学金。

参考资料：

https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/