因?yàn)樽C明了弱化版的「孿生素?cái)?shù)猜想」，當(dāng)年58歲的張益唐一鳴驚人，蜚聲全球。

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

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

類似的故事，再次上演！

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

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

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

改變一生的邂逅

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

40年前的姚猜想被推翻

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

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

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

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

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

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

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

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

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

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

我們證明，即使不隨時(shí)間重新排序元素，也可以構(gòu)建哈希表，其期望搜索復(fù)雜度（包括攤銷（amortized）復(fù)雜度和最壞情況復(fù)雜度）遠(yuǎn)遠(yuǎn)優(yōu)于之前認(rèn)為可能實(shí)現(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)匀皇谴鎯?chǔ)數(shù)據(jù)的最有效方式之一?！?/span>

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

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

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

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

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

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

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

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

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

然而，Krapivin并沒有被這種傳統(tǒng)觀點(diǎn)所束縛，因?yàn)樗静恢肋@一猜想。

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

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

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

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

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

卡內(nèi)基梅隆大學(xué)的Guy Blelloch表示：「這個(gè)結(jié)果非常漂亮，因?yàn)樗鉀Q了一個(gè)經(jīng)典問題。」

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

常數(shù)查詢哈希表

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

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

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

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

Farach-Colton解釋道：「你會(huì)得到一個(gè)固定的數(shù)值，這只是一個(gè)常數(shù)，與哈希表的填充程度無關(guān)?！?/span>

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

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

Conway說道，團(tuán)隊(duì)的研究成果可能不會(huì)立即帶來實(shí)際應(yīng)用，但這并不重要?！父美斫膺@類數(shù)據(jù)結(jié)構(gòu)很重要。你無法預(yù)見這樣的研究何時(shí)會(huì)帶來突破，從而在實(shí)際應(yīng)用中取得更好的效果?！?/span>

主人公介紹

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