在计算机科学的漫长发展历程中，一些经典理论和猜想犹如基石，构建起整个学科的大厦。然而，近期一位本科生的研究成果却如同一颗投入平静湖面的巨石，激起千层浪。罗格斯大学本科生 Andrew Krapivin 成功推翻了图灵奖得主姚期智 40 年前提出的与哈希表相关的猜想，这一突破性进展不仅改写了计算机科学的理论认知，更让人们对年轻一代科研人员的创新潜力有了全新的认识。

故事始于 2021 年秋季，当时 Andrew Krapivin 偶然邂逅了一篇名为《Tiny Pointers》（微型指针）的论文。彼时，他或许并未意识到这篇论文将成为他学术生涯的转折点。直到两年后，当他有空深入研读这篇论文时，一个大胆的想法在他脑海中逐渐成型。论文中的微型指针概念激发了 Krapivin 的灵感，他发现了一种有望进一步降低指针内存使用量的方法。但在此之前，他需要找到一种更优的方式来组织指针指向的数据，而哈希表成为了他探索的方向。

哈希表，作为计算机科学中被广泛应用且研究透彻的工具，自 20 世纪 50 年代初诞生以来，一直是计算机科学家研究的重点。其核心原理是利用哈希函数将数据的键转换为数组的索引，从而实现快速的数据插入、删除和查询操作。在漫长的研究进程中，科学家们一直在探寻哈希表操作速度的极限，例如新的搜索或插入操作究竟能有多快。

1985 年，著名计算机科学家姚期智在其开创性论文《Uniform Hashing is Optimal》中提出了一个重要猜想。他认为，在具有特定属性的哈希表中，查找单个元素或空位的最佳方法是随机地遍历潜在的位置，即均匀探测。并且，在最坏情况下（比如寻找最后一个空闲位置时），所需时间与哈希表接近 100% 满的程度（用整数 x 表示）成正比，无法超越 x。这一猜想在过去 40 年里被大多数计算机科学家奉为圭臬。

然而，Krapivin 在对哈希表的深入探索中，凭借着自己独特的思维和创新的方法，设计出了一种全新的哈希表。这种新哈希表在查询和插入操作上展现出了惊人的速度。对于新哈希表，最坏情况查询和插入所需的时间与 (log x)2 成正比，远远快于传统认知中的 x。这一结果直接与姚期智的猜想相矛盾。

起初，Krapivin 的教授 Martín Farach-Colton 对这个新设计持怀疑态度，毕竟哈希表领域早已被众多科研人员深入研究，想要取得新的突破实属不易。为了验证新设计的有效性，Farach-Colton 邀请了卡内基梅隆大学的 William Kuszmaul 对 Krapivin 的发明进行检查。Kuszmaul 在仔细研究后，兴奋地告知 Krapivin，他不仅设计出了一个出色的哈希表，更重要的是，他推翻了一个存在了 40 年的猜想。

今年 1 月，剑桥大学研究生 Krapivin、任职于纽约大学的 Farach-Colton 以及 Kuszmaul 共同发表了一篇文章。在这篇文章中，他们重新探讨了开放寻址哈希表的最优搜索复杂度，提出了两种新的哈希表插入策略 —— 弹性哈希（elastic hashing）和漏斗哈希（funnel hashing）。他们证明，即使不随时间重新排列元素，也能构建出一种哈希表，其预期的搜索复杂度（无论是摊销复杂度还是最坏情况）远超以往人们认为可能的水平。在论文摘要部分，他们明确强调了这项研究推翻了姚期智在其论文中留下的核心猜想，并给出了相关的下界证明。

除了推翻姚期智关于最坏情况查询时间的猜想，他们的研究还在平均查询时间方面取得了令人瞩目的成果。1985 年，姚期智研究发现，具有某些属性（包括被标记为 “贪婪” 的哈希表，即新元素必须放在第一个可用位置）的哈希表，其平均查询时间永远不会比 log x 好。而 Krapivin 等人通过研究发现，对于非贪婪哈希表，这一限制并不适用。他们提供了一个反例，即一个平均查询时间远远好于 log x 的非贪婪哈希表，且这个平均查询时间与哈希表的填满程度 x 无关，无论哈希表的填满程度如何，平均查询时间都是一个常量。这一结果不仅出乎其他研究人员的意料，甚至连论文的几位作者自己都未曾想到。

这一突破性研究成果得到了业内专家的高度评价。卡内基梅隆大学的 Guy Blelloch 称赞这个结果非常美妙，因为它重新审视并解决了这样一个经典问题。滑铁卢大学的 Sepehr Assadi 表示，他们不仅证否了姚期智猜想，还找到了该问题的最佳答案，原本可能还要再等 40 年才能知道这个正确答案。虽然目前该团队得到的结果可能不会带来直接的应用，但正如专家 Conway 所说，更好地理解这些类型的数据结构非常重要，这样的结果或许在未来的某个时刻会为创造更好的实践奠定基础。

Andrew Krapivin 的成功并非偶然，他凭借着对科研的热爱和执着，在不被传统思维束缚的情况下，勇于探索未知。他的经历也激励着更多年轻的科研人员，在追求真理的道路上，要保持好奇心和创新精神，敢于挑战权威。相信在未来，随着科研的不断深入，这一突破性成果将在计算机科学领域引发更多的思考和研究，推动整个学科不断向前发展。