本科生顛覆姚期智40年前猜想！意外發現新型哈希表，數據搜索速度突破理論上限

明敏 發自 凹非寺

量子位 | 公眾號 QbitAI

姚期智40年前猜想被本科生意外顛覆！

00後本科生安德魯·克拉皮文（Andrew Krapivin，簡稱小克）發現了一種新型哈希表，數據搜索速度超過以往所有方法。

要知道，哈希表因為簡易快速高性能，被廣泛應用於計算機科學和編程中。

而這種新型哈希表在最壞情況下的查詢和插入時間與(log x) ²成正比，遠比之前認為的x快。

後者正是姚期智在1985年提出的猜想。

不僅如此，小克他們還發現非貪婪哈希表的平均查詢時間可以達到一個與哈希表x無關的恒定值，這一發現也完全出乎意料。

網民：這太瘋狂了！總是學生們實現了這些瘋狂的發現。

這一發現對於理解和改進數據結構至關重要。

一場意外的顛覆

哈希表（Hash table）是根據鍵而直接訪問在存儲器存儲位置的數據結構。

也就是說，它通過計算一個鍵值的函數，將所需查詢的數據映射到表中一個位置讓人來訪問，這加快了查找速度。這個映射函數被稱為哈希函數，存放記錄的數組稱作哈希表。

更通俗比喻，哈希表就好比一個很大的文件櫃，其中有很多個抽屜（槽）。每個抽屜可以存放一個文件（數據項）。但是，文件櫃很大，手動找文件肯定很麻煩。所以，你使用一個文件編號（哈希函數），它會告訴你應該把某個文件放到哪個抽屜里，或者當你要找某個文件時，告訴你該去哪個抽屜。

比如存放一個文件，文件名是「蘋果」，通過文件編號規則（哈希函數）得到一個數字，假設是 3，那麼就把「蘋果」文件放到文件櫃的第3個抽屜。

如果兩個文件（比如「蘋果」和「香蕉」）的編號規則（哈希函數）計算出來是一樣的（例如都被放到抽屜 3），那麼就會發生衝突。為了應對這個問題，哈希表採用了處理衝突的策略，比如在抽屜里放一個「文件夾」（鏈表）來存放所有衝突的文件，或者把文件放到下一個抽屜。

衡量哈希表已使用空間與總空間的比例，被稱為負載因子（Load Factor）。

負載因子(α)=存儲元素的數量/哈希表桶的數量=n/m

當負載因子較小時，哈希表的空桶多、衝突少，查找效率較高，但可能浪費內存。

當負載因子較高時，哈希表衝突增加，查找性能可能下降。

1985年，姚期智在論文《Uniform Hashing Is Optimal》中提出，在具有特定屬性的哈希表中，查找單個元素或空位的最佳方法是均勻探測（uniform probing），而且最壞情況的插入時間與x成正比。

即如果哈希表已經99%滿了，那麼需要查看100個不同位置，才能找到一個空位。

其中，x表示哈希表被填滿的距離。

當x=100時，表示哈希表已經被填充了99%，負載因子為0.99。當x=1000時，表示哈希表被填充了99.9%，負載因子為0.999。

這個猜想在2021年被撼動了，不過這一切其實是場意外。

當時正在羅格斯大學讀本科的小克讀了一篇名為《Tiny Pointers》的論文。

這篇論文提出了tiny pointer的概念，它能指向計算機內存中的一段信息或一個元素。

讀過論文後，小克意識到有一種方法可以進一步降低tiny pointer內存使用的方法。

為此，他需要使用哈希表來存儲tiny pointer指向的數據。

在這個過程中，他發現了一種工作速度更快的哈希表。

即最劣查詢和插入所需時間與（log x）²成正比，比之前姚期智論文中提出的x快得多。

最開始，小克的導師對這個新發現表示懷疑，畢竟哈希表從20世紀50年代誕生以來，已經被研究得很透徹了。

為了驗證這一發現是否正確，導師法拉·高爾頓（Farach-Colton）找到了卡內基梅隆大學的威廉姆·庫斯莫爾（William Kuszmaul）一起驗證。

結果就是庫斯莫爾發現，小克不僅發現了一個新的哈希表，更進一步推翻了40年前的猜想。

網民：「不知」反而可以擺脫傳統路徑

為什麼小克能輕鬆顛覆猜想呢？

因為他本來壓根不知道姚期智提出的猜想，也是一種無心插柳了。

有人因此感慨：創新的最佳方式總是要忽略以往的一些路徑。現在人們總是容易陷入前人的思維模式。

而且無獨有偶，有人表示一位醫學人員再次發現了復合梯形公式。

當然，能夠提出新哈希表，也是因為小克本身就很優秀。

他本科就讀於羅格斯大學，雙修數學和計算機科學。

他是近十年來羅格斯大學新布倫瑞克分校首位拿到劍橋研究生獎學金的學生。

接下來他將前往劍橋大學，攻讀計算機科學和哲學碩士學位。

他的老師法拉·高爾頓甚至說，小克是自己在羅格斯大學32年以來見過最優秀的本科生。

學習之外，他喜歡下象棋、攝影和詩歌，以及琢磨CPU、GPU、AI處理器等。

值得一提的是，小克的哥哥也是羅格斯大學畢業。

參考鏈接：

[1]https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/

[2]https://arxiv.org/pdf/2501.02305