本科生推翻姚期智40年前猜想！CS頂會論文重新整理雜湊表傳統認知

新智元報道

編輯：KingHZ

【新智元導讀】圖靈獎得主姚期智40年來公認正確的猜想，被推翻了！Andrew Krapivin和合作者一起提出的了全新雜湊演算法，突破了雜湊表搜尋效率的極限。相關論文已被計算機理論頂會FOCS 2024接受。而Krapivin提出關鍵思路時，還只是個本科生，甚至都不知道「姚期智猜想」。

因為證明了弱化版的「孿生素數猜想」，當年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。