1985 年，著名計算機科學(xué)家、圖靈獎得主姚期智提出了一個與哈希表有關(guān)的猜想。現(xiàn)在，40 年過去了，一名本科生卻成功推翻了這個猜想。而這項成就卻源自一個始于 2021 年秋的故事。

量子雜志近日報道了這個故事，機器之心編譯了該文章以饗讀者。

原文地址：https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/

2021 年秋季的某天，羅格斯大學(xué)的一位本科生 Andrew Krapivin 遇到了一篇論文，而這篇論文將改變他的一生。不過那時候，Krapivin 倒沒有多想。兩年之后，當(dāng)他終于有空細(xì)讀這篇論文時（他說當(dāng)時只是為了好玩），他還沒意識到：他的工作將讓人重新審視計算機科學(xué)領(lǐng)域一種被廣泛使用的工具。

這篇論文題為「Tiny Pointers」，即微型指針。這是一種類似箭頭的東西，指向的是計算機內(nèi)存中的一段信息或一個元素。Krapivin 很快就發(fā)現(xiàn)了一種有望進一步降低指針內(nèi)存使用量的方法。但首先，他需要一種更好的方法來組織指針指向的數(shù)據(jù)。

• 論文標(biāo)題：Tiny Pointers
• 論文地址：https://arxiv.org/pdf/2111.12800

他的方法是使用一種常用于存儲數(shù)據(jù)的方法，即哈希表（hash table）。在探索研究的過程中，Krapivin 最終發(fā)現(xiàn)了一種新的哈希表。并且這種新哈希表的工作速度更快 —— 用更少的時間和步數(shù)便能找到指定元素。

不過，Krapivin 之前的教授 Martín Farach-Colton 起初對這個新設(shè)計深感懷疑，畢竟哈希表似乎早已被人研究透了，很難再取得新進展。

但直覺上的看法并不一定總是對的。為了確認(rèn)這個新設(shè)計的有效性，F(xiàn)arach-Colton 邀請了卡內(nèi)基梅隆大學(xué)的 William Kuszmaul 檢查 Krapivin 的新發(fā)明。

Kuszmaul 深感振奮。他記得自己當(dāng)時對 Krapivin 說：「你不只是想出了一個很酷的哈希表，你實際上徹底推翻了一個已有 40 年的猜想！」

Andrew Krapivin 顛覆了人們對哈希表的普遍看法 —— 即便他一開始并沒有這樣的打算。哈希表是計算機科學(xué)中被研究得最透徹的工具之一。

本科生推翻存在 40 年的猜想

Krapivin 推翻的是著名計算機科學(xué)家、圖靈獎得主姚期智在 1985 年提出的一項研究。

他們的研究過程是這樣的。1 月份，劍橋大學(xué)研究生 Krapivin、任職于紐約大學(xué)的 Farach-Colton 以及 Kuszmaul 共同發(fā)表了一篇文章。

這篇文章重新探討了開放尋址哈希表（open-addressed hash table）的最優(yōu)搜索復(fù)雜度，以便在檢索時能以盡可能少的探測次數(shù)找到元素。文章提出了兩種新的哈希表插入策略 —— 彈性哈希（elastic hashing）和漏斗哈希（funnel hashing），并證明了，即使不隨時間重新排列元素，也可以構(gòu)建一種哈希表，其預(yù)期的搜索復(fù)雜度（無論是攤銷復(fù)雜度還是最壞情況）遠(yuǎn)超以往認(rèn)為可能的水平。

• 論文標(biāo)題：Optimal Bounds for Open Addressing Without Reordering
• 論文地址：https://arxiv.org/pdf/2501.02305

在論文摘要部分，他們強調(diào)了這項研究推翻了姚期智在其開創(chuàng)性論文《Uniform Hashing is Optimal》中留下的核心猜想，并給出了相關(guān)的下界證明。

眾所周知，哈希表在計算領(lǐng)域已變得無處不在，主要在于其簡單性和易用性。它通過將數(shù)據(jù)映射到一個固定大小的數(shù)組中，從而實現(xiàn)快速的插入、刪除和查詢操作。哈希表的核心思想是利用哈希函數(shù)（Hash Function）將數(shù)據(jù)的鍵（Key）轉(zhuǎn)換為數(shù)組的索引（Index），從而快速定位數(shù)據(jù)存儲的位置。

最早的哈希表可以追溯到 20 世紀(jì) 50 年代初，自那時起，計算機科學(xué)家一直在研究和使用它們。研究人員希望弄清楚這些操作的速度極限。例如，新的搜索或插入可能有多快？

Martín Farach-Colton 幫助 Krapivin 證明了新哈希表與一個長期存在的猜想相矛盾

答案通常取決于在哈希表中找到一個空位所需的時間。而這通常又取決于哈希表的填充程度。

填充程度可以用百分比表示，比如 50% 或 90%，但在研究中，哈希表往往接近完全填滿。

為了更精確地描述這種高填充狀態(tài)，研究者們可能會使用一個整數(shù)（記作 x）來表示哈希表接近 100% 滿的程度。如果 x 是 100，那么哈希表是 99% 滿的；如果 x 是 1,000，那么哈希表是 99.9% 滿的。

這種衡量填充程度的方法為評估執(zhí)行查詢或插入等操作所需的時間提供了一種便捷的方式。

此前，研究人員得出這樣一個結(jié)論，對于某些常見的哈希表，執(zhí)行最壞情況下插入操作所需的預(yù)期時間與 x 成正比。Kuszmaul 表示：「如果你的哈希表是 99% 滿的，那么你需要查看大約 100 個不同的位置才能找到一個空閑槽位，這種情況是合理的。」

著名計算機科學(xué)家姚期智在這篇論文中提出，在具有特定屬性的哈希表中，查找單個元素或空位的最佳方法是隨機地遍歷潛在的位置 —— 這種方法被稱為均勻探測（uniform probing）。他還指出，在最壞的情況下（即尋找最后一個空閑位置時），你無法做得比 x 更好。

• 論文標(biāo)題：Uniform Hashing Is Optimal
• 論文地址：https://dl.acm.org/doi/pdf/10.1145/3828.3836

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

Krapivin 沒有囿于傳統(tǒng)的想法，原因很簡單：他不知道這個傳統(tǒng)的想法。他說：「我在不知道姚期智猜想的情況下做到了這一點?！惯@讓 Tapline 聯(lián)合創(chuàng)始人兼 CEO 不禁在 ?? 上感嘆說：「無知也是一種福氣。」

image.png

Krapivin 在微型指針方面進行的探索最終得到了一種新的哈希表 —— 一種不依賴于均勻探測的哈希表。

對于這種新的哈希表，最壞情況查詢和插入所需的時間與 (log x)2 成正比 —— 比 x 快得多。這個結(jié)果直接與姚期智的猜想相矛盾。Farach-Colton 和 Kuszmaul 幫助 Krapivin 證明了 (log x)2 是姚期智所寫的常見哈希表類別的最佳、不可超越的界限。

卡內(nèi)基梅隆大學(xué)的 Guy Blelloch 贊道：「這個結(jié)果非常美妙，因為它重新審視并解決了這樣一個經(jīng)典問題?！?/span>

滑鐵盧大學(xué)的 Sepehr Assadi 表示：「他們不僅證否了 [姚期智猜想]，還找到了該問題的最佳答案。我們原本可能還要再等 40 年才能知道這個正確答案?！?/span>

Krapivin 在劍橋大學(xué)的國王學(xué)院橋上。他的新哈希表可以超出研究者預(yù)料的速度更快地查找和存儲數(shù)據(jù)。

除了證否姚期智的猜想外，這篇論文還包含許多更驚人的結(jié)果。這與一個相關(guān)但略有不同的情況有關(guān)：1985 年，姚期智不僅研究了查詢的最壞情況時間，還研究了所有可能查詢的平均時間。他證明：具有某些屬性的哈希表（包括被標(biāo)記為「貪婪」的哈希表，這意味著新元素必須放在第一個可用位置）的平均時間永遠(yuǎn)不會比 log x 好。

Farach-Colton、Krapivin 和 Kuszmaul 想看看對于非貪婪哈希表，這個限制是否同樣適用。

最終，他們表明這個限制不適用。證明過程很簡單，他們提供了一個反例，即一個平均查詢時間遠(yuǎn)遠(yuǎn)好于 log x 的非貪婪哈希表。事實上，它根本與 x 無關(guān)。

Farach-Colton 說：「你會得到一個數(shù)值，而這個數(shù)值就是一個常量，與哈希表的填滿程度沒有關(guān)系?！挂簿褪钦f，無論這個哈希表的填滿程度如何，平均查詢時間都是一個常量。

這一事實大出人們意料 —— 甚至連這幾位作者自己也沒有想到。

Conway 說，該團隊得到的結(jié)果可能不會帶來任何直接的應(yīng)用，但這并不重要。「更好地理解這些類型的數(shù)據(jù)結(jié)構(gòu)很重要。你不知道這樣的結(jié)果何時會造就一些東西，從而讓你創(chuàng)造更好的實踐?！?/span>