本科生姚期智40年前猜想！CS顶会论文刷新哈希表传统认知

原标题：本科生姚期智40年前猜想！CS顶会论文刷新哈希表传统认知
文章来源：新智元
内容字数：7068字

本科生图灵奖得主40年猜想：哈希表效率新突破

本文讲述了Rutgers大学本科生Andrew Krapivin如何偶然间图灵奖得主姚期智40年前提出的关于哈希表搜索效率的猜想，以及这一发现对计算机科学领域的影响。

1. 偶然的发现与意外的突破

   2021年，Krapivin阅读了一篇关于“微指针”的论文，两年后出于兴趣深入研究。在探索如何进一步压缩微指针的过程中，他意外地设计了一种全新的哈希表，其搜索速度远超预期，最终了姚期智的猜想。

2. 哈希表与姚期智的猜想

   哈希表是计算机科学中应用最广泛的数据结构之一，用于快速查找数据。姚期智在1985年提出一个猜想：对于特定类型的哈希表，在最坏情况下，查找最后一个空位所需时间与哈希表填充程度成正比。这个猜想在学术界被广泛接受了40年。

3. Krapivin的创新与验证

   Krapivin设计的哈希表突破了姚期智猜想设定的上限，其期望搜索复杂度远低于之前的预期，证明了该猜想是错误的。他的导师和合作者William Kuszmaul意识到这一发现的重大意义，共同完成了论文的撰写和发表。

4. 研究成果及影响

   Krapivin等人的研究成果已在计算机理论顶级会议FOCS 2024上发表。该研究不仅了姚期智的猜想，还给出了问题的最佳答案，为哈希表的研究带来了新的突破。 他们的研究表明，平均查询时间可以是常数，与哈希表填充程度无关，这完全出乎意料。

5. Krapivin的背景及荣誉

   Krapivin在做出这一重大发现时还是一名本科生，对姚期智的猜想一无所知。 他的成功也印证了“无知者无畏”的道理。目前，Krapivin正在剑桥大学攻读计算机科学硕士学位，并获得了Goldwater奖学金和丘吉尔奖学金。

6. 学术界的评价

   学术界对Krapivin的研究成果给予了高度评价。专家们认为，这项研究不仅解决了经典问题，还可能在未来带来实际应用，进一步推动计算机科学的发展。

Krapivin的故事与张益唐证明孪生素数猜想的故事异曲同工，都体现了在科学研究中，打破常规思维，大胆探索的重要性。他们的成功激励着更多年轻学者，勇于挑战权威，探索未知的科学领域。

联系作者

文章来源：新智元
作者微信：
作者简介：智能+中国主平台，致力于推动中国从互联网+迈向智能+新纪元。重点关注人工智能、机器人等前沿领域发展，关注人机融合、人工智能和机器人对人类社会与文明进化的影响，领航中国新智能时代。