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

大数据文摘 · 公众号 · 大数据 · 2025-02-24 18:10

正文

大数据文摘受权转载自夕小瑶科技说

自计算机科学诞生之初，哈希表（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）的认知框架～

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

正文

结语

请到「今天看啥」查看全文