原標題：本科生姚期智40年前猜想，證明哈希表查詢效率可達常數級別
文章來源：夕小瑤科技說
內容字數：3692字

哈希表：本科生顛覆四十年的計算機科學猜想

哈希表，作為計算機科學的基石數據結構，其重要性不言而喻。它廣泛應用于數據庫、網絡路由器以及編程語言底層實現等領域。然而，一項由羅格斯大學本科生Andrew Krapivin領導的研究，意外地顛覆了計算機科學泰斗、圖靈獎得主姚期智教授四十年前提出的一個重要猜想，引發了學術界的巨大震動。

1. 姚期智的猜想與均勻探測

1985年，姚期智教授在其論文《Uniform Hashing is Optimal》中提出一個猜想：在開放尋址哈希表中，均勻探測是解決沖突的最佳方法。然而，在負載系數較高的情況下，查詢時間的下界將線性增長，與負載系數x成正比。這意味著，當哈希表接近飽和時，插入和查詢操作的平均時間復雜度會顯著增加。

2. Krapivin的突破性發現

Krapivin在閱讀一篇關于“微型指針”（Tiny Pointers）的論文后受到啟發。他意識到，更小的指針可能需要全新的數據組織策略，從而重新設計哈希表。通過巧妙的設計，他發明了一種非貪婪哈希表，其平均查詢時間竟然達到了常數級別，不受哈希表填充程度的影響！這直接挑戰了姚期智教授的理論。

3. 非貪婪哈希表與時間復雜度

傳統開放尋址哈希表的最壞情況查詢和插入時間復雜度為O(x)，其中x為負載系數。而Krapivin團隊提出的非貪婪哈希表，即使在接近滿載的情況下，其時間復雜度僅為O((log x)2)，遠優于之前的O(x)。他們證明了，通過引入非貪婪插入策略，可以突破姚期智教授提出的O(log x)的理論下限，實現常數級別的平均查詢時間。

4. 學術界的驗證與震驚

Krapivin的導師和卡內基梅隆大學的專家對這一發現進行了嚴格驗證，最終確認了其正確性。這一結果震驚了學術界，因為哈希表是計算機科學領域研究最透徹的技術之一，如此重大的突破實屬罕見。 Krapivin的研究不僅了持續40年的猜想，更重塑了學界對計算最優性的認知。

5. 對未來研究的啟示

Krapivin的研究表明，即使在看似成熟的基礎算法領域，性能極限的邊界仍充滿未知的可能性。 他的突破性工作不僅終結了一個長達四十年的理論猜想，更重要的是，它提醒我們，那些被視為完美的經典算法，或許正等待著被重新解構和優化。這為未來的計算機科學研究指明了新的方向，也展現了年輕一代科研人員的創新活力。

聯系作者

文章來源：夕小瑤科技說
作者微信：
作者簡介：低負擔解碼AI世界，硬核也可愛！聚集35萬AI發燒友、開發者和從業者，廣泛覆蓋互聯網大廠中高管、AI公司創始人和機構投資人。一線作者來自清北、國內外頂級AI實驗室和大廠，兼備敏銳的行業嗅覺和洞察深度。商務合作：zym5189