本科生挑战姚期智猜想，揭示哈希表查询时间与填满程度无关的惊人发现——数据结构优化的新突破

本科生颠覆40年哈希表猜想

1985年，著名计算机科学家、图灵奖得主姚期智提出了一个关于哈希表的重要猜想。如今，40年后，罗格斯大学的一名本科生Andrew Krapivin成功推翻了这个猜想。这项成就始于2021年秋季的一个偶然发现。

偶然的发现与突破

2021年秋季，Krapivin遇到了一篇题为《Tiny Pointers》的论文。起初，他只是出于兴趣阅读这篇论文，但很快他发现了一种有望进一步降低指针内存使用量的方法。为了实现这一目标，他开始探索如何更好地组织指针指向的数据，并最终选择使用哈希表（hash table）这种常用的数据结构。

新哈希表的诞生

在研究过程中，Krapivin发明了一种新的哈希表，其工作速度更快，能够在更短的时间和更少的步骤内找到指定元素。尽管他的教授Martín Farach-Colton最初对此表示怀疑，但经过卡内基梅隆大学的William Kuszmaul的验证后，他们意识到Krapivin不仅发明了一个高效的哈希表，还彻底推翻了姚期智提出的40年猜想。

推翻姚期智猜想

Krapivin的研究成果发表于2023年1月，文章重新探讨了开放寻址哈希表（open-addressed hash table）的最优搜索复杂度。通过提出两种新的哈希表插入策略——弹性哈希（elastic hashing）和漏斗哈希（funnel hashing），Krapivin证明了即使不随时间重新排列元素，也可以构建一种哈希表，其预期的搜索复杂度远超以往认为可能的水平。这直接反驳了姚期智在其开创性论文《Uniform Hashing is Optimal》中留下的核心猜想。

突破传统思维

Krapivin的成功在于他没有被传统的思维方式所束缚。他在不知晓姚期智猜想的情况下完成了这项研究，这也让许多专家感叹「无知也是一种福气」。Krapivin的新哈希表不仅推翻了姚期智的猜想，还找到了该问题的最佳答案，使得最坏情况查询和插入所需的时间与 (log x)² 成正比，远快于姚期智的x。

更多惊喜结果

除了推翻姚期智的猜想外，Krapivin的研究还带来了更多令人惊讶的结果。例如，他们证明了对于非贪婪哈希表，平均查询时间可以是一个常量，与哈希表的填满程度无关。这一发现大出人们意料，甚至作者自己也感到意外。

结论

Krapivin的研究不仅提升了我们对哈希表的理解，也为未来的数据结构优化提供了新的思路。虽然这些理论成果可能不会立即带来实际应用，但它们为未来的技术创新奠定了坚实的基础。

本文来源：