支撐現代技術幾十年的假設被推翻的情況並不常見，但最近一篇基於一名本科生及其兩位合著者的研究成果的論文卻做到了這一點。
該研究涉及雜湊表，以及20世紀80年代研究成果的一個猜想。
一個長達40年的猜想
雜湊表自 20 世紀 50 年代就已存在，它是計算機科學中的基本資料結構，也是資料庫、快取系統、編譯器和網路路由器等眾多應用的重要構建模組。這些結構在高效儲存和檢索資料方面表現出色，是現代計算不可或缺的一部分。
雜湊表的資料結構就像一個巨大的抽屜櫃，資料被存放在某個抽屜中，並在需要時快速取出。問題在於，隨著雜湊表被填滿，為新資料找到空位變得愈發困難，從而導致效能下降。
要理解這一點，首先要明白雜湊表的填滿程度是如何衡量的。研究人員通常用一個整數 x 來表示雜湊表接近100%滿的程度。
例如，如果x為100，則表示雜湊表已滿99%，如果x為1000，則表示已滿99.9%。想象一個有1000個車位的停車場。x為100，說明990個車位已被佔用，只有10個空著。這種衡量方式有助於評估諸如查詢或插入等操作所需的時間。
1985年，著名計算機科學家及圖靈獎得主姚期智提出了一個猜想，該猜想對幾乎填滿的雜湊表找到空位的速度設定了一個限制。
△姚期智
他認為，對於某些常見的雜湊表，最壞情況下的插入操作（填滿最後一個空位）的預期時間與“x”成正比。換句話說，在特定屬性的雜湊表中，找到單個元素或空位的最佳方法是隨機遍歷潛在空位，這種方法叫做均勻探測（uniform probing）。
在停車場例子中，如果x為1000（停車場已滿 99.9%），那麼平均而言，找到那個唯一的空位會花費相當長的時間。
姚期智的猜想表明，這種x與搜尋時間之間的線性關係是此類插入操作的最佳速度。幾十年來，幾乎沒有人對此提出質疑。
直到有人因為不知道這一猜想，意外地實現了突破。
偶然地突破
△Andrew Krapivin
這一突破源於一名叫做Andrew Krapivin的本科生偶然看到了一篇名為《Tiny Pointers》的論文，講的是一種旨在壓縮指標以減少記憶體消耗的概念。
計算機系統中的傳統指標通常使用固定數量的位來表示記憶體地址。然而，微型指標採用了一種巧妙的技術來減少所需的位數，從而節省記憶體空間。這在Krapivin的創新中起著關鍵作用。
要理解微型指標的工作原理，可以設想多個使用者共享一個數據陣列的情況。
每個使用者都可以請求陣列中的一個位置，而微型指標用於跟蹤已分配的位置。微型指標並不直接儲存完整的記憶體地址，而是利用知道哪個使用者“擁有”該指標以及陣列的結構，用更少的位來表示位置。
這就好比為一個特定位置設定了一個簡化的程式碼或暱稱，而這個程式碼或暱稱只有在特定上下文中才有意義。
指標大小的縮減意味著顯著的記憶體節省，尤其是在大量使用指標的應用中。
為了進一步探索記憶體的最佳化，Krapivin深入研究了雜湊表，試圖找到一種更高效的方式來組織這些指標所指向的資料。
這一探索促使他開發出了一種新穎的雜湊表設計，其效能超乎尋常，在資料查詢和儲存方面展現出了前所未有的速度。
具體來說，Krapivin開發了一種採用開放定址法的新型雜湊表，將所有元素都直接儲存在雜湊表本身中。這與分離連結法形成了鮮明對比，在分離連結法中，具有相同雜湊鍵的元素儲存在一個連結串列中。
與依賴統一探測不同，Krapivin的雜湊表採用了一種更復雜的策略，包括子陣列的使用以及特定的插入規則。
其基本思路是將雜湊表劃分為更小的子陣列，並使用一組規則來確定新元素的插入位置。這些規則優先考慮平衡元素在子陣列之間的分佈，這有助於最大限度地減少未來插入和搜尋所需的時間。這種“非貪婪”的方法，雖然早期插入的成本可能略高，但後期插入和搜尋的速度卻明顯加快，尤其是當雜湊表逐漸填滿時。
Krapivin的雜湊表實現了最壞情況下的查詢和插入時間與(log x)²成正比，比x要快得多。
這一突破最大的意義在於，Krapivin的研究並非只是漸進式的改進；而是從根本上挑戰了我們對於雜湊表如何設計和最佳化的理解。透過推翻姚氏猜想，他為資料結構和演算法的研究開闢了新的途徑，未來可能會帶來更高效的解決方案。
影響與應用
Krapivin的突破對利用雜湊表的各種應用具有深遠的影響。這一創新可能產生重大影響的一些關鍵領域包括：
資料庫：雜湊表在資料庫中被廣泛用於索引和檢索資料。Krapivin的發現可能會加快查詢處理速度，並提升資料庫的整體效能。
快取系統：快取依靠雜湊表來高效地儲存和檢索頻繁訪問的資料。Krapivin的雜湊錶帶來的速度提升可能會使網路瀏覽器、作業系統和內容分發網路的載入時間更快，從而改善使用者體驗。
編譯器：編譯器使用雜湊表進行符號表管理，這涉及儲存和檢索有關變數、函式和其他程式元素的資訊。更快的雜湊表有可能加快編譯過程，特別是對於大型程式而言。這在軟體開發中尤其有益，因為編譯時間可能是影響生產力的一個重要因素。
網路路由：雜湊表在網路路由器中用於高效轉發資料包。Krapivin的工作有助於加快路由決策並提升網路效能。在高流量網路中，採用更快雜湊表的路由器能夠更快地決定將資料包傳送到何處，從而降低延遲並提高整體網路速度。
密碼學：雜湊表被用於各種密碼學演算法中，例如用於數字簽名和安全通訊的演算法。更快的雜湊表所提供的效率提升有可能增強這些演算法的效能，從而加快加密和解密的過程。
儘管Krapivin的研究成果令人振奮，但要全面瞭解這一突破的範圍和潛力，還需要進一步的研究和驗證。研究人員目前正在探索這一發現的更廣泛影響，並研究其在不同領域的適用性。包括探索在其他資料結構和演算法中使用微型指標，以及針對特定應用最佳化Krapivin的雜湊表。
Krapivin的創新性研究，表明了科學研究有時候需要一種「無知」的探索精神與好奇心，所謂的「標準答案」或「正確解法」可能成為創新的桎梏，而「無畏」的探索反而能夠能刺破認知的繭房。正如愛因斯坦所言：“想象力比知識更重要。”
如今的AI行業也是如此，都在研究大語言模型，都知道尺度定律（Scaling Law）的存在，於是科技巨頭們專注於砸錢、堆晶片、比引數、拼算力，而DeepSeek另闢蹊徑實現彎道超車，雖然沒有完全顛覆尺度定律，但也說明了方法創新的重要性。
在遇到瓶頸或接近極限時，跳出路徑依賴，也許能找到新的解法。改變遊戲規則，才能提供另一種選項。
未來，當更多研究者敢於質疑“不可逾越”的極限時，我們或許會發現：那些曾被奉為圭臬的“真理”，不過是等待被重新整理的起點。