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

據(jù)說，在證明發(fā)表之前，相關(guān)領(lǐng)域的頂尖數(shù)學(xué)家，召開了研討會，討論后失望的認(rèn)為：目前的技術(shù)無法進(jìn)一步推動「孿生素數(shù)猜想」取得實質(zhì)性進(jìn)展。

而當(dāng)時，幾乎在學(xué)術(shù)界「透明」的張益唐，甚至都不知道研討會何時何地召開過。

類似的故事，再次上演！

不同的是，這一次發(fā)生在計算機(jī)理論領(lǐng)域，而做出主要發(fā)現(xiàn)時，主角還是個本科生！

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

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

改變一生的邂逅

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

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

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

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

「微指針」（tiny pointer）是一種新的數(shù)據(jù)結(jié)構(gòu)，用于壓縮傳統(tǒng)指針。在使用指針的許多場景中，微指針可以用來替代傳統(tǒng)指針，消除幾乎所有的空間開銷。

Krapivin很快提出了一種可能的方法，進(jìn)一步縮小微指針的大小，減少內(nèi)存占用。然而，要實現(xiàn)這一目標(biāo)，他需要更好的方式來組織指針?biāo)赶虻臄?shù)據(jù)。

他轉(zhuǎn)向了常見的數(shù)據(jù)存儲方法——哈希表。在不斷實驗的過程中，Krapivin意識到自己創(chuàng)造了一種全新的哈希表，

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

Andrew Krapivin并未刻意為之，卻顛覆了計算機(jī)科學(xué)中研究最深入的工具之一——哈希表的傳統(tǒng)認(rèn)知。

哈希表可能是應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一：每次登錄新賬號，哈希表可能都要被調(diào)用一次。

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

哈希算法可以將計算機(jī)中的對象轉(zhuǎn)變?yōu)殚L度固定的一串?dāng)?shù)字，叫做哈希值。利用哈希值，哈希表可以查詢到真正需要的對象所在的「地址」，從而操作相關(guān)內(nèi)容。

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

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

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

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

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

40年前的姚猜想被推翻

哈希表作為計算機(jī)科學(xué)中研究最深入的數(shù)據(jù)結(jié)構(gòu)之一，Krapivin的突破聽起來像神話，令人難以置信。

為了驗證這一設(shè)計的可行性，F(xiàn)arach-Colton請來了他在《Tiny Pointers》論文中的長期合作者、卡內(nèi)基梅隆大學(xué)的William Kuszmaul，共同審查這一發(fā)明。

然而，Kuszmaul的反應(yīng)與Farach-Colton截然不同。

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

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

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

實際上，在去年，相關(guān)研究在計算機(jī)理論界已引起關(guān)注。在領(lǐng)域Top2會議FOCS2024上，Krapivin已介紹過同名論文。

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

在摘要中，他們認(rèn)為新方法的期望搜索復(fù)雜度遠(yuǎn)遠(yuǎn)比之前大家所想的低：

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

我們證明，即使不隨時間重新排序元素，也可以構(gòu)建哈希表，其期望搜索復(fù)雜度（包括攤銷（amortized）復(fù)雜度和最壞情況復(fù)雜度）遠(yuǎn)遠(yuǎn)優(yōu)于之前認(rèn)為可能實現(xiàn)的結(jié)果。

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

40年前的猜想

紐約市康奈爾大學(xué)科技校區(qū)（Cornell Tech）的Alex Conway表示：「這是一篇重要的論文。哈希表是我們擁有的最古老的數(shù)據(jù)結(jié)構(gòu)之一，而且它們?nèi)匀皇谴鎯?shù)據(jù)的最有效方式之一。」

然而，他表示關(guān)于它們?nèi)绾喂ぷ鞯拈_放性問題仍然存在，這篇論文以令人驚訝的方式回答了其中幾個問題。

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

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

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

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

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

他還指出，在最壞的情況下，查找最后一個空位時，所需時間永遠(yuǎn)不會優(yōu)于x。

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

40年來，大多數(shù)計算機(jī)科學(xué)家都認(rèn)為姚期智的猜想是對的。

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

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

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

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

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

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

卡內(nèi)基梅隆大學(xué)的Guy Blelloch表示：「這個結(jié)果非常漂亮，因為它解決了一個經(jīng)典問題。」

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

常數(shù)查詢哈希表

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

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

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

結(jié)果他們發(fā)現(xiàn)并不適用，并通過一個反例證明了這一點：他們構(gòu)造了一個非貪心哈希表，其平均查詢時間遠(yuǎn)遠(yuǎn)優(yōu)于 log x，甚至完全不依賴于 x。

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

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

這一發(fā)現(xiàn)完全出乎意料，甚至連研究作者自己都感到驚訝。

Conway說道，團(tuán)隊的研究成果可能不會立即帶來實際應(yīng)用，但這并不重要。「更好理解這類數(shù)據(jù)結(jié)構(gòu)很重要。你無法預(yù)見這樣的研究何時會帶來突破，從而在實際應(yīng)用中取得更好的效果。」

主人公介紹

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