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

原标题：本科生姚期智40年前的猜想，哈希表的平均查询时间竟与填满程度无关
文章来源：人工智能学家
内容字数：12679字

本科生40年计算机科学猜想

本文报道了罗格斯大学本科生Andrew Krapivin图灵奖得主姚期智40年前提出的关于哈希表猜想的故事。这一突破源于Krapivin对一篇名为“Tiny Pointers”论文的研究，他意外地发现了一种更快、更有效的哈希表构建方法。

1. 哈希表与姚期智猜想

哈希表是计算机科学中广泛使用的用于存储和检索数据的工具。其效率取决于查找元素所需的时间，这与哈希表的填充程度密切相关。姚期智在1985年的论文《Uniform Hashing Is Optimal》中提出，对于特定类型的哈希表，在最坏情况下查找元素的时间与哈希表接近满的程度（用x表示）成正比。他认为，均匀探测是最佳的搜索方法。

2. Krapivin的突破

Krapivin在研究“Tiny Pointers”论文的过程中，无意中设计了一种新的哈希表，其搜索时间与(log x)²成正比，远小于x。这意味着即使哈希表接近满载，他的新哈希表也能以更快的速度查找元素。他与教授Martín Farach-Colton和卡内基梅隆大学的William Kuszmaul合作，验证了这一发现。

3. 猜想的证伪及更深层次的发现

Krapivin的工作直接了姚期智的猜想，证明了(log x)²是该类别哈希表的最佳界限。更令人惊讶的是，他们还证明了姚期智关于平均查询时间的结论对于非贪婪哈希表并不适用。他们发现，对于非贪婪哈希表，平均查询时间是一个常量，与哈希表的填充程度无关，这超出了之前的预期。

4. 研究意义与影响

Krapivin的发现不仅了一个长期存在的猜想，也为哈希表的研究带来了新的方向。虽然其直接应用尚不明确，但对数据结构的更深入理解，有助于未来计算机科学的创新和发展。计算机科学家们对这一成果给予了高度评价，认为它解决了经典问题，并可能在未来带来更多突破。

5. 结语

Krapivin的故事展现了意外发现的魅力和基础研究的重要性。一位本科生在无意中了著名学者的长期猜想，这不仅证明了科学探索的无限可能，也激励着更多人投身于计算机科学领域的探索与创新。

联系作者

文章来源：人工智能学家
作者微信：
作者简介：致力成为权威的人工智能科技媒体和前沿科技研究机构