原標題：本科生姚期智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的故事與張益唐證明孿生素數猜想的故事異曲同工，都體現了在科學研究中，打破常規思維，大膽探索的重要性。他們的成功激勵著更多年輕學者，勇于挑戰權威，探索未知的科學領域。

聯系作者

文章來源：新智元
作者微信：
作者簡介：智能+中國主平臺，致力于推動中國從互聯網+邁向智能+新紀元。重點關注人工智能、機器人等前沿領域發展，關注人機融合、人工智能和機器人對人類社會與文明進化的影響，領航中國新智能時代。