本科生推翻姚期智40年前猜想，证明哈希表查询效率可达常数级别

本科生推翻姚期智40年前猜想，证明哈希表查询效率可达常数级别

引用

腾讯

1.

https://new.qq.com/rain/a/20250224A04CXB00

自计算机科学诞生之初，哈希表（Hash Table）便被奉为基石型数据结构，地位毋庸置疑。

哈希表的应用之广泛，无需赘言。
从诞生至今，它一直是现代计算系统的基石，数据库管理系统、网络路由设备，乃至编程语言底层实现，无不依赖于哈希表。
然而，最近，哈希表最具影响力的猜想——姚期智四十年前提出的理论，竟被一名本科生意外颠覆！
1985 年，计算机科学泰斗、图灵奖得主姚期智教授曾经在《Uniform Hashing is Optimal》论文中提出一个影响深远的猜想：
在开放寻址哈希表中，均匀探测 (uniform probing) 通常被认为是解决冲突、定位目标元素或空槽位的最佳方法。
然而，在最坏情况下，当哈希表负载较高（负载系数为 x）时，查询时间的下界将线性增长，与 x 成正比。
由此可见，对于特定类型的哈希表，在接近饱和状态下，执行插入或查询操作的平均时间复杂度会随着负载系数（Load Factor，定义为已使用空间与总空间的比例，例如高达 99%、99.9% 甚至更高）的增加而显著提升，每次操作都需要“探测”更多位置才能完成。
姚期智老师的这一理论推断在过去四十年间被广泛接受，成为哈希表性能分析的经典范式。
但是本科生 Krapivin（克拉皮文）团队的研究表明，对于非贪婪的哈希表，这个限制并不存在：
他们设计出一种非贪婪哈希表，其平均查询时间竟然可以达到常数级别！也就是说，平均查询时间不再受哈希表填充程度的影响，始终保持在一个极低的水平。
安德鲁·克拉皮文（Andrew Krapivin），是一名罗格斯大学的 00 后本科生，在 2021 年秋季一次偶然的论文阅读中，敏锐地捕捉到“微型指针”（Tiny Pointers）概念的潜在价值。
论文题目：Tiny Pointers
论文链接：
https://arxiv.org/pdf/2111.12800
微型指针是一种类似箭头的东西，指向的是计算机内存中的一段信息或一个元素。
计算机内存中存储着各种各样的数据，指针就像是内存中的“路标”，指引程序快速找到所需的数据。 它本质上是一个地址，指向数据在内存中的位置。
微型指针的目标是让这些“路标”更小、更轻便。 就像把厚重的路标牌换成更简洁的指示箭头，微型指针用更少的内存空间来存储地址信息，从而提升整体内存利用率。
克拉皮文从这篇论文中获得启发，他意识到，要让更小的“路标”发挥更大的作用，需要一套全新的数据组织策略，才能更好地管理和利用这些“微型指针”所指向的数据。
如果指针可以变得更“微型”，那能否连带着重新设计哈希表本身？
这个过程中，他意外地发明了一种运行速度更快的哈希表。 这种哈希表即使在最坏的情况下，查询和插入数据也只需要(log 𝑥)² 这么多的步骤，而根据之前图灵奖得主姚期智的理论，这个步骤应该是𝑥，新哈希表快了很多！
最初，导师法拉赫-科尔顿（Martín Farach-Colton）对这个发现表示怀疑，因为哈希表是计算机科学里研究得最透彻的技术之一，突然出现这么大的进步，让人难以置信。
为了确保万无一失，导师请卡内基梅隆大学的威廉·库兹马尔（William Kuszmaul）帮忙验证。
验证结果令人惊喜，库兹马尔确认，克拉皮文不仅发明了一种新的哈希表，更重要的是，他推翻了一个持续了 40 年的计算机科学猜想-姚期智 40 前的理论推断！
这个结果震惊了所有人。连研究团队自己都一度不敢相信，反复验证了无数次，才敢将其发表：
克拉皮文的论文中指出：

传统认知中，开放寻址哈希表的最坏情况查询和插入时间复杂度与负载系数 𝑥 呈线性正比关系，即 O(𝑥)。而他们的新提出的非贪心型的哈希表，即使在接近满载的情况下，查询和插入时间复杂度仅为O((log 𝑥)²)，远优于 姚期智教授之前推论的 O(𝑥) 级别。

姚期智教授之前推断“对于具有某些“贪婪”插入属性的哈希表，其平均查询时间存在 O(log 𝑥) 的理论下限”。而克拉皮文团队通过引入非贪婪插入策略，推翻了这样的限制条件。 他们证明，他们所提出的新型哈希表能够实现与负载系数 𝑥 无关的常数级别平均查询时间。

结语

哈希表作为计算机科学发展的活态见证者，其演进历程深刻映射着计算范式的革新轨迹。
然而，克拉皮文的突破性研究昭示了一个被长期忽视的真理：即便在看似成熟的基础算法领域，性能极限的边界仍充满未知可能。
这位年轻学者对经典哈希理论的颠覆性重构，不仅终结了历时四十载的理论猜想，更重要的是重塑了学界对"计算最优性"（computational optimality）的认知框架。
当现代技术赋予我们更强大的分析工具时，克拉帕廷现象的启示愈发清晰：那些被视为完美的经典算法，或许正等待着被重新解构。
正如计算科学家阿伦森所言："算法的终极可能性，永远超越我们当前的想象力"。这种对未知的永恒探索，正是计算机科学最迷人的光芒。