大數據文摘受權轉載自夕小瑤科技說

自計算機科學誕生之初，哈希表（Hash Table）便被奉為基石型數據結構，地位毋庸置疑 ～

哈希表的應用之廣泛，無需贅言。

從誕生至今，它一直是現代計算系統的基石，數據庫管理系統、網絡路由設備，乃至編程語言底層實現，無不依賴于哈希表。

然而，最近，哈希表最具影響力的猜想——姚期智四十年前提出的理論，竟被一名本科生意外顛覆！

1985 年，計算機科學泰斗、圖靈獎得主姚期智教授曾經在《Uniform Hashing is Optimal》論文中提出一個影響深遠的猜想：

在開放尋址哈希表中，均勻探測 (uniform probing) 通常被認為是解決沖突、定位目標元素或空槽位的最佳方法。 然而，在最壞情況下，當哈希表負載較高（負載系數為 x）時，查詢時間的下界將線性增長，與 x 成正比。 由此可見，對于特定類型的哈希表，在接近飽和狀態下，執行插入或查詢操作的平均時間復雜度會隨著負載系數（Load Factor，定義為已使用空間與總空間的比例，例如高達 99%、99.9% 甚至更高）的增加而顯著提升，每次操作都需要“探測”更多位置才能完成。。

姚期智老師的這一理論推斷在過去四十年間被廣泛接受，成為哈希表性能分析的經典范式。

但是本科生 Krapivin（克拉皮文）團隊的研究表明，對于非貪婪的哈希表，這個限制并不存在：

他們設計出一種非貪婪哈希表，其平均查詢時間竟然可以達到常數級別！也就是說，平均查詢時間不再受哈希表填充程度的影響，始終保持在一個極低的水平。

安德魯·克拉皮文（Andrew Krapivin），是一名羅格斯大學的 00 后本科生，在 2021 年秋季一次偶然的論文閱讀中，敏銳地捕捉到“微型指針”（Tiny Pointers）概念的潛在價值。

論文題目：Tiny Pointers 論文鏈接： https://arxiv.org/pdf/2111.12800

微型指針是一種類似箭頭的東西，指向的是計算機內存中的一段信息或一個元素。

計算機內存中存儲著各種各樣的數據，指針就像是內存中的“路標”，指引程序快速找到所需的數據。 它本質上是一個地址，指向數據在內存中的位置。

微型指針的目標是讓這些“路標”更小、更輕便。 就像把厚重的路標牌換成更簡潔的指示箭頭，微型指針用更少的內存空間來存儲地址信息，從而提升整體內存利用率。

克拉皮文從這篇論文中獲得啟發，他意識到，要讓更小的“路標”發揮更大的作用，需要一套全新的數據組織策略，才能更好地管理和利用這些“微型指針”所指向的數據。

如果指針可以變得更“微型”，那能否連帶著重新設計哈希表本身？

這個過程中，他意外地發明了一種運行速度更快的哈希表。 這種哈希表即使在最壞的情況下，查詢和插入數據也只需要(log )2 這么多的步驟，而根據之前圖靈獎得主姚期智的理論，這個步驟應該是，新哈希表快了很多！

最初，導師法拉赫-科爾頓（Martín Farach-Colton）對這個發現表示懷疑，因為哈希表是計算機科學里研究得最透徹的技術之一，突然出現這么大的進步，讓人難以置信。

為了確保萬無一失，導師請卡內基梅隆大學的威廉·庫茲馬爾（William Kuszmaul）幫忙驗證。

驗證結果令人驚喜，庫茲馬爾確認，克拉皮文不僅發明了一種新的哈希表，更重要的是，他推翻了一個持續了 40 年的計算機科學猜想-姚期智 40 前的理論推斷！

這個結果震驚了所有人。連研究團隊自己都一度不敢相信，反復驗證了無數次，才敢將其發表：

克拉皮文的論文中指出：

• 傳統認知中，開放尋址哈希表的最壞情況查詢和插入時間復雜度與負載系數 呈線性正比關系，即 O()。而他們的新提出的非貪心型的哈希表，即使在接近滿載的情況下，查詢和插入時間復雜度僅為O((log )2)，遠優于 姚期智教授之前推論的 O() 級別。

• 姚期智教授之前推斷“對于具有某些“貪婪”插入屬性的哈希表，其平均查詢時間存在 O(log ) 的理論下限”。而克拉皮文團隊通過引入非貪婪插入策略，推翻了這樣的限制條件。他們證明，他們所提出的新型哈希表能夠實現與負載系數 無關的常數級別平均查詢時間。

結語

哈希表作為計算機科學發展的活態見證者，其演進歷程深刻映射著計算范式的革新軌跡。

然而，克拉皮文的突破性研究昭示了一個被長期忽視的真理：即便在看似成熟的基礎算法領域，性能極限的邊界仍充滿未知可能。

這位年輕學者對經典哈希理論的顛覆性重構，不僅終結了歷時四十載的理論猜想，更重要的是重塑了學界對"計算最優性"（computational optimality）的認知框架 ～

當現代技術賦予我們更強大的分析工具時，克拉帕廷現象的啟示愈發清晰：那些被視為完美的經典算法，或許正等待著被重新解構。

正如計算科學家阿倫森所言："算法的終極可能性，永遠超越我們當前的想象力"。這種對未知的永恒探索，正是計算機科學最迷人的光芒。

GPU算力按需租用

A100/H100 GPU算力按需租用，

秒級計費，平均節省開支30%以上！

掃碼了解詳情?