本科生“不小心”推翻图灵奖得主清华姚期智教授40年猜想：事关哈希表

　　你可能觉得哈希表技术很成熟了吧？毕竟用了这么多年。但最近发生了一件挺让人惊讶的事情：一位本科生，和两位教授合作，竟然挑战并突破了计算机科学界对哈希表长达40年的一个经典猜想。这可不是一个小小的优化，而是在理论层面上的重要突破

　　故事的主角叫Andrew Krapivin，当时还是罗格斯大学的本科生。他在2021年接触到一篇关于“微型指针”（Tiny Pointers）的论文，当时只是粗略浏览了一下。两年后，他重新翻出这篇论文，想“随便看看”，结果就看到了新思路

　　“微型指针”简单来说，就是一种指向计算机内存中数据的快捷方式。Krapivin当时的想法是，能不能进一步缩小指针的体积，更节省内存？为了实现这个目标，他需要一种更有效的数据组织方法，于是他开始研究哈希表

　　哈希表，作为一种非常基础且常用的数据结构，大家应该都不陌生。它的核心操作就是三个：查询（查找数据）、删除（删除数据）、插入（添加数据）。从上世纪50年代诞生以来，哈希表一直是计算机科学领域的重要工具

　　在研究过程中，Krapivin意外地发现，他似乎设计出了一种新型的哈希表。这种新哈希表在查找数据时，速度更快，效率更高！这让他感到非常兴奋

　　一开始，他的导师Martín Farach-Colton教授（也是“微型指针”论文的作者之一）也有些保留。毕竟哈希表研究这么多年了，还能有什么颠覆性的创新吗？但为了严谨起见，教授邀请了另一位专家，卡内基梅隆大学的William Kuszmaul教授（同样是“微型指针”论文的合作者）来评估

　　结果，Kuszmaul教授的反馈出乎意料：“你不仅仅是做出了一个很棒的哈希表，你实际上是推翻了一个存在了40年的猜想！”

　　40年的猜想？这到底是怎么回事呢？

　　这就不得不提到计算机科学领域的泰斗级人物——图灵奖得住，清华大学教授姚期智教授。1985年，姚期智教授提出了一个关于特定类型哈希表的猜想：

　　对于这类哈希表，要找到目标元素或空位，最佳策略是随机探测（uniform probing）。而且，在最坏的情况下，比如查找最后一个空位，查询时间的下限就是x（x 代表哈希表的“满”程度，x越大，表格越接近满载）

　　这个猜想提出后，长期以来被认为是哈希表性能的理论极限

　　然而，Krapivin在进行研究时，并没有受到这个经典猜想的束缚，或许正是这种“初生牛犊不怕虎”的精神，让他跳出了固有框架。他设计的新型哈希表，没有采用传统的随机探测方法。结果令人惊讶，在最坏情况下，其查询和插入的时间复杂度竟然降到了(log x)²！

　　(log x)² 相比于 x，这是一个巨大的性能提升。这直接与姚期智教授的猜想相悖。更进一步，Krapivin和两位教授合作，在今年1月发表的论文中证明，对于姚期智教授描述的那类哈希表，(log x)² 实际上已经是性能的理论最优解了！这意味着，他们不仅推翻了旧的猜想，还找到了新的速度上限

　　康奈尔理工学院的 Alex Conway 评价说：“这篇论文非常重要，哈希表是最基础的数据结构之一，但我们对它的理解仍然不够深入。这项研究以出人意料的方式，解答了其中一些关键问题。”

　　卡内基梅隆大学的 Guy Blelloch 也认为：“这个成果非常漂亮，它解决了一个非常经典的问题。”

　　滑铁卢大学的 Sepehr Assadi 甚至表示：“我们可能还需要再过40年才能找到正确的答案。” 可见这个成果的重要性

　　更令人意外的发现

　　除了在最坏情况下的性能突破，研究团队还在平均查询时间方面取得了惊人的发现。姚期智教授在1985年还证明，对于“贪婪”哈希表（新元素必须插入到第一个遇到的空位），平均查询时间的下限是log x

　　但是，Krapivin团队的研究表明，对于非贪婪的哈希表，这个限制并不存在！他们设计出一种非贪婪哈希表，其平均查询时间竟然可以达到常数级别！也就是说，平均查询时间不再受哈希表填充程度的影响，始终保持在一个极低的水平。这个发现完全出乎意料，甚至让研究者自己都感到惊讶

　　这项研究的意义

　　虽然这项研究目前可能还没有直接的应用落地。但正如 Conway 所说：“更深入地理解这些基础数据结构至关重要。我们不知道何时这样的理论突破会带来实践上的飞跃。”

　　基础研究的价值在于其长远的潜力。哈希表作为计算机科学的基石，任何理论上的进步，都可能为未来的技术创新打开新的大门。特别是在大数据和人工智能时代，高效的数据处理能力至关重要。更快速的哈希表，意味着更高效的算法，更强大的AI，以及更流畅的用户体验

　　总结一下这次的突破：

　　•本科生 Andrew Krapivin “无意中” 挑战了哈希表领域一个40年的经典猜想。

　　•新型哈希表在最坏情况下的查询和插入速度达到 (log x)²，突破了原有猜想的 x 速度限制。

　　•非贪婪哈希表实现了常数级别的平均查询时间，这是一个非常出乎意料的发现。

　　•这项研究是理论计算机科学的重要进展，未来可能对人工智能、大数据等领域产生深远影响。

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