本科生推翻姚期智40年前的猜想，哈希表的平均查询时间竟与填满程度无关

主要观点总结

本文介绍了罗格斯大学本科生Andrew Krapivin推翻了一项存在40年的计算机科学研究猜想的故事。这项研究涉及到哈希表的最优搜索复杂度，Krapivin提出了一种新的哈希表设计，其搜索速度超越了传统哈希表。这项成果源于他对微型指针的研究，最终得到了新的哈希表结构。这篇文章还详细阐述了计算机科学家姚期智在哈希表研究领域的贡献以及Krapivin等人对已有猜想的反驳。

关键观点总结

关键观点1: Andrew Krapivin推翻了一项存在40年的计算机科学研究猜想。

Krapivin对微型指针的研究导致了一种新型哈希表设计的发现，该哈希表工作速度更快。

关键观点2: 计算机科学家姚期智在哈希表研究领域做出了重要贡献。

姚期智提出了关于哈希表最优搜索复杂度的猜想，这一猜想被Krapivin等人的研究推翻。

关键观点3: Krapivin等人的研究涉及到哈希表的最优搜索复杂度。

他们提出了一种新的哈希表插入策略，证明了即便不随时间重新排列元素，也可以构建一种哈希表，其预期的搜索复杂度远超以往认为可能的水平。

关键观点4: Krapivin的成果源于他对微型指针的研究。

他的方法使用了一种常用于存储数据的方法，即哈希表。在探索研究的过程中，他发现了一种新哈希表，并证明了其优越性。

关键观点5: 该研究重新审视并解决了经典问题。

除了推翻姚期智的猜想外，该论文还包含许多更惊人的结果，例如非贪婪哈希表的平均查询时间与哈希表的填满程度无关。