本科生姚期智40年前的猜想，哈希表的平均查詢時間竟與填滿程度無關

原標題：本科生姚期智40年前的猜想，哈希表的平均查詢時間竟與填滿程度無關
文章來源：人工智能學家
內容字數：12679字

本科生40年計算機科學猜想

本文報道了羅格斯大學本科生Andrew Krapivin圖靈獎得主姚期智40年前提出的關于哈希表猜想的故事。這一突破源于Krapivin對一篇名為“Tiny Pointers”論文的研究，他意外地發現了一種更快、更有效的哈希表構建方法。

1. 哈希表與姚期智猜想

哈希表是計算機科學中廣泛使用的用于存儲和檢索數據的工具。其效率取決于查找元素所需的時間，這與哈希表的填充程度密切相關。姚期智在1985年的論文《Uniform Hashing Is Optimal》中提出，對于特定類型的哈希表，在最壞情況下查找元素的時間與哈希表接近滿的程度（用x表示）成正比。他認為，均勻探測是最佳的搜索方法。

2. Krapivin的突破

Krapivin在研究“Tiny Pointers”論文的過程中，無意中設計了一種新的哈希表，其搜索時間與(log x)2成正比，遠小于x。這意味著即使哈希表接近滿載，他的新哈希表也能以更快的速度查找元素。他與教授Martín Farach-Colton和卡內基梅隆大學的William Kuszmaul合作，驗證了這一發現。

3. 猜想的證偽及更深層次的發現

Krapivin的工作直接了姚期智的猜想，證明了(log x)2是該類別哈希表的最佳界限。更令人驚訝的是，他們還證明了姚期智關于平均查詢時間的結論對于非貪婪哈希表并不適用。他們發現，對于非貪婪哈希表，平均查詢時間是一個常量，與哈希表的填充程度無關，這超出了之前的預期。

4. 研究意義與影響

Krapivin的發現不僅了一個長期存在的猜想，也為哈希表的研究帶來了新的方向。雖然其直接應用尚不明確，但對數據結構的更深入理解，有助于未來計算機科學的創新和發展。計算機科學家們對這一成果給予了高度評價，認為它解決了經典問題，并可能在未來帶來更多突破。

5. 結語

Krapivin的故事展現了意外發現的魅力和基礎研究的重要性。一位本科生在無意中了著名學者的長期猜想，這不僅證明了科學探索的無限可能，也激勵著更多人投身于計算機科學領域的探索與創新。

聯系作者

文章來源：人工智能學家
作者微信：
作者簡介：致力成為權威的人工智能科技媒體和前沿科技研究機構