因為證明了弱化版的「孿生素數猜想」，當年58歲的張益唐一鳴驚人，蜚聲全球。

據說，在證明發表之前，相關領域的頂尖數學家，召開了研討會，討論后失望的認為：目前的技術無法進一步推動「孿生素數猜想」取得實質性進展。

而當時，幾乎在學術界「透明」的張益唐，甚至都不知道研討會何時何地召開過。

類似的故事，再次上演！

不同的是，這一次發生在計算機理論領域，而做出主要發現時，主角還是個本科生！

同樣的因為沒接觸相關「勸退」言論，沒有成見，最終拓展了人類知識的邊界。

本月10日，Quanta雜志報道了Andrew Krapivin如何顛覆CS理論，終結圖靈獎得主姚期智在40年前提出的猜想。

改變一生的邂逅

2021年秋天，Rutgers大學的本科生Andrew Krapivin偶然讀到了一篇論文，而這篇論文最終改變了他的一生。剛開始，他卻并沒有太在意這篇文章。但兩年后，當他終于抽出時間細讀（正如他所說，「只是為了好玩」），他的研究成果卻引發了人們對計算機科學中一項廣泛使用工具的全新思考。

Krapivin偶遇的論文是《Tiny Pointers》。

論文鏈接：https://arxiv.org/pdf/2111.12800

可以把「微指針」（Tiny Pointer）想象成類似指路牌的東西，可以把你引導到計算機內存中的某個信息或元素。

「微指針」（tiny pointer）是一種新的數據結構，用于壓縮傳統指針。在使用指針的許多場景中，微指針可以用來替代傳統指針，消除幾乎所有的空間開銷。

Krapivin很快提出了一種可能的方法，進一步縮小微指針的大小，減少內存占用。然而，要實現這一目標，他需要更好的方式來組織指針所指向的數據。

他轉向了常見的數據存儲方法——哈希表。在不斷實驗的過程中，Krapivin意識到自己創造了一種全新的哈希表，

這種哈希表的工作速度比預期更快——用更少的時間和步驟就能找到特定的元素。

Andrew Krapivin并未刻意為之，卻顛覆了計算機科學中研究最深入的工具之一——哈希表的傳統認知。

哈希表可能是應用最廣泛的數據結構之一：每次登錄新賬號，哈希表可能都要被調用一次。

哈希表算法主要有兩部分構成：哈希算法和沖突處理算法。

哈希算法可以將計算機中的對象轉變為長度固定的一串數字，叫做哈希值。利用哈希值，哈希表可以查詢到真正需要的對象所在的「地址」，從而操作相關內容。

問題出現在，哈希值并不能保證唯一性：不同的對象可能會有相同的哈希值。

這就需要沖突處理算法，將同一哈希值的不同對象映射到不同的地址。

然而，隨著哈希表中數據越來越多，沖突處理起來也越來越難。

新算法有望緩解這一問題: 開放地址法 (Open Addressing)--常見的沖突處理算法--這一次的復雜度達被證明并沒有以前設想的大。

怪不得當時Krapivin的教授Martín Farach-Colton，會懷疑他提出的哈希表設計。

40年前的姚猜想被推翻

哈希表作為計算機科學中研究最深入的數據結構之一，Krapivin的突破聽起來像神話，令人難以置信。

為了驗證這一設計的可行性，Farach-Colton請來了他在《Tiny Pointers》論文中的長期合作者、卡內基梅隆大學的William Kuszmaul，共同審查這一發明。

然而，Kuszmaul的反應與Farach-Colton截然不同。

他記得當時對Krapivin說：「你不僅僅是發明了一個優良的哈希表。你實際上完全推翻了一個存在了40年的猜想！」

在2025年1月，Krapivin（現在是劍橋大學的研究生）、Farach-Colton（現在在紐約大學）和Kuszmaul在論文中共同證明，這種新的哈希表確實能夠比以往認為可能的更快地找到元素。一舉推翻了長期被認為正確的猜想。

論文鏈接：https://arxiv.org/pdf/2501.02305

實際上，在去年，相關研究在計算機理論界已引起關注。在領域Top2會議FOCS2024上，Krapivin已介紹過同名論文。

消息來源：https://focs.computer.org/2024/program/schedule/

在摘要中，他們認為新方法的期望搜索復雜度遠遠比之前大家所想的低：

本文重新審視了數據結構中最簡單的問題之一：將元素插入開放尋址哈希表，以便以后能夠用盡可能少的探測操作來檢索元素。

我們證明，即使不隨時間重新排序元素，也可以構建哈希表，其期望搜索復雜度（包括攤銷（amortized）復雜度和最壞情況復雜度）遠遠優于之前認為可能實現的結果。

由此，我們推翻了姚期智開創性論文《Uniform Hashing is Optimal》中的核心猜想。我們所有的結果都有相應的下界。

40年前的猜想

紐約市康奈爾大學科技校區（Cornell Tech）的Alex Conway表示：「這是一篇重要的論文。哈希表是我們擁有的最古老的數據結構之一，而且它們仍然是存儲數據的最有效方式之一。」

然而，他表示關于它們如何工作的開放性問題仍然存在，這篇論文以令人驚訝的方式回答了其中幾個問題。

哈希表在計算機領域已變得無處不在，這在一定程度上要歸功于它們的簡潔性和易用性。哈希表的設計允許用戶執行三項基本操作：查詢（搜索）、刪除以及插入元素。最早的哈希表可追溯到1950年代初期，計算機科學家從那時起就一直在研究和使用它們。研究者們的一個目標是找出這些操作的速度限制。例如，新的搜索或插入操作最快能達到什么速度？

在哈希表中查找空位所需的時間，通常取決于哈希表的滿載程度。滿載程度可以用百分比來描述。例如，這個表是50%滿的，那個表是90%滿的。

但研究人員通常處理的是更高填充度的情況。因此，他們可能使用一個整數x來指定哈希表接近100%滿的程度。如果x是100，那么表是99%滿的。如果x是1,000，那么表是99.9%滿的。這一填充度的衡量方式為評估查詢或插入等操作所需時間提供了方便的標準。

研究人員早就知道，對于某些常見的哈希表，最壞情況下插入操作所需的時間——比如把某個元素放入最后剩余的空位——與x成正比。Kuszmaul說：「如果你的哈希表填充了99%，那么你可能需要檢查大約100個位置才能找到一個空位。」

在1985年，姚期智（未來的圖靈獎得主，清華「姚班之父」）在一篇論文中提出，對于具有特定屬性的哈希表，查找一個元素或空位的最佳方法是隨機遍歷所有潛在位置，這種方法被稱為均勻探測（uniform probing）。

他還指出，在最壞的情況下，查找最后一個空位時，所需時間永遠不會優于x。

論文鏈接：https://dl.acm.org/doi/10.1145/3828.3836

40年來，大多數計算機科學家都認為姚期智的猜想是對的。

然而，Krapivin并沒有被這種傳統觀點所束縛，因為他根本不知道這一猜想。

他說：「做這個研究時，我并不知道姚期智的猜想」。

在Farach-Colton和Kuszmaul幫助下，Krapivin推翻了姚期智在40年前提出的猜想。

具體而言，全新的哈希表不依賴于均勻探測，而且就是姚期智所討論的常見哈希表，但最優、不可超越的上限是(log x)2，而不是姚期智所猜想的x。

下圖更直觀的比較了兩者復雜度，其中紅色表示姚期智猜想的復雜度，藍色表示新算法的復雜度。

而這一切都源于他偶然接觸到的微指針論文。

卡內基梅隆大學的Guy Blelloch表示：「這個結果非常漂亮，因為它解決了一個經典問題。」

滑鐵盧大學的Sepehr Assadi表示：「他們不僅僅是推翻了姚期智的猜想，他們還找到了問題的最佳答案。如果沒有這個研究，我們可能還要等40年才能得到正確的答案。」

常數查詢哈希表

除了推翻姚期智的猜想，這篇新論文還包含了更加令人驚訝的結果。

這與一個相關但稍有不同的情況有關：1985年，姚期智不僅研究了查詢的最壞情況時間，還研究了所有可能查詢的平均時間。他證明了：具有某些特性的哈希表——包括「貪婪」哈希表（即新元素必須放置在第一個可用位置的哈希表）——平均查詢時間無法優于log x。

Farach-Colton、Krapivin和Kuszmaul想要驗證這個限制是否同樣適用于非貪心哈希表。

結果他們發現并不適用，并通過一個反例證明了這一點：他們構造了一個非貪心哈希表，其平均查詢時間遠遠優于 log x，甚至完全不依賴于 x。

Farach-Colton解釋道：「你會得到一個固定的數值，這只是一個常數，與哈希表的填充程度無關。」

也就是說，平均查詢時間是恒定的，不受哈希表填充度的影響。

這一發現完全出乎意料，甚至連研究作者自己都感到驚訝。

Conway說道，團隊的研究成果可能不會立即帶來實際應用，但這并不重要。「更好理解這類數據結構很重要。你無法預見這樣的研究何時會帶來突破，從而在實際應用中取得更好的效果。」

主人公介紹

目前，Andrew Krapivin在劍橋大學攻讀計算機科學碩士學位。之前，他在Rutgers大學榮譽學院（Honors College ）攻讀數學和計算機科學的雙學位。因上文報道的研究工作，先后獲得美國Goldwater獎學金和劍橋大學的丘吉爾獎學金。