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

原标题：本科生姚期智40年前猜想，证明哈希表查询效率可达常数级别
文章来源：夕小瑶科技说
内容字数：3692字

哈希表：本科生颠覆四十年的计算机科学猜想

哈希表，作为计算机科学的基石数据结构，其重要性不言而喻。它广泛应用于数据库、网络路由器以及编程语言底层实现等领域。然而，一项由罗格斯大学本科生Andrew Krapivin领导的研究，意外地颠覆了计算机科学泰斗、图灵奖得主姚期智教授四十年前提出的一个重要猜想，引发了学术界的巨大震动。

1. 姚期智的猜想与均匀探测

1985年，姚期智教授在其论文《Uniform Hashing is Optimal》中提出一个猜想：在开放寻址哈希表中，均匀探测是解决冲突的最佳方法。然而，在负载系数较高的情况下，查询时间的下界将线性增长，与负载系数x成正比。这意味着，当哈希表接近饱和时，插入和查询操作的平均时间复杂度会显著增加。

2. Krapivin的突破性发现

Krapivin在阅读一篇关于“微型指针”（Tiny Pointers）的论文后受到启发。他意识到，更小的指针可能需要全新的数据组织策略，从而重新设计哈希表。通过巧妙的设计，他发明了一种非贪婪哈希表，其平均查询时间竟然达到了常数级别，不受哈希表填充程度的影响！这直接挑战了姚期智教授的理论。

3. 非贪婪哈希表与时间复杂度

传统开放寻址哈希表的最坏情况查询和插入时间复杂度为O(x)，其中x为负载系数。而Krapivin团队提出的非贪婪哈希表，即使在接近满载的情况下，其时间复杂度仅为O((log x)²)，远优于之前的O(x)。他们证明了，通过引入非贪婪插入策略，可以突破姚期智教授提出的O(log x)的理论下限，实现常数级别的平均查询时间。

4. 学术界的验证与震惊

Krapivin的导师和卡内基梅隆大学的专家对这一发现进行了严格验证，最终确认了其正确性。这一结果震惊了学术界，因为哈希表是计算机科学领域研究最透彻的技术之一，如此重大的突破实属罕见。 Krapivin的研究不仅了持续40年的猜想，更重塑了学界对计算最优性的认知。

5. 对未来研究的启示

Krapivin的研究表明，即使在看似成熟的基础算法领域，性能极限的边界仍充满未知的可能性。 他的突破性工作不仅终结了一个长达四十年的理论猜想，更重要的是，它提醒我们，那些被视为完美的经典算法，或许正等待着被重新解构和优化。这为未来的计算机科学研究指明了新的方向，也展现了年轻一代科研人员的创新活力。

联系作者

文章来源：夕小瑶科技说
作者微信：
作者简介：低负担解码AI世界，硬核也可爱！聚集35万AI发烧友、开发者和从业者，广泛覆盖互联网大厂中高管、AI公司创始人和机构投资人。一线作者来自清北、国内外顶级AI实验室和大厂，兼备敏锐的行业嗅觉和洞察深度。商务合作：zym5189