（本文作者張曉泉，清華大學(xué)經(jīng)管學(xué)院 Irwin and Joan Jacobs講席教授）

支撐現(xiàn)代技術(shù)幾十年的假設(shè)被推翻的情況并不常見，但最近一篇基于一名本科生及其兩位合著者的研究成果的論文卻做到了這一點(diǎn)。

該研究涉及哈希表，以及20世紀(jì)80年代研究成果的一個(gè)猜想。

一個(gè)長(zhǎng)達(dá)40年的猜想

哈希表自20世紀(jì)50年代就已存在，它是計(jì)算機(jī)科學(xué)中的基本數(shù)據(jù)結(jié)構(gòu)，也是數(shù)據(jù)庫(kù)、緩存系統(tǒng)、編譯器和網(wǎng)絡(luò)路由器等眾多應(yīng)用的重要構(gòu)建模塊。這些結(jié)構(gòu)在高效存儲(chǔ)和檢索數(shù)據(jù)方面表現(xiàn)出色，是現(xiàn)代計(jì)算不可或缺的一部分。

哈希表的數(shù)據(jù)結(jié)構(gòu)就像一個(gè)巨大的抽屜柜，數(shù)據(jù)被存放在某個(gè)抽屜中，并在需要時(shí)快速取出。問題在于，隨著哈希表被填滿，為新數(shù)據(jù)找到空位變得愈發(fā)困難，從而導(dǎo)致性能下降。

要理解這一點(diǎn)，首先要明白哈希表的填滿程度是如何衡量的。研究人員通常用一個(gè)整數(shù)x來表示哈希表接近100%滿的程度。

例如，如果x為100，則表示哈希表已滿99%，如果x為1000，則表示已滿99.9%。想象一個(gè)有1000個(gè)車位的停車場(chǎng)。x為100，說明990個(gè)車位已被占用，只有10個(gè)空著。這種衡量方式有助于評(píng)估諸如查詢或插入等操作所需的時(shí)間。

1985年，著名計(jì)算機(jī)科學(xué)家及圖靈獎(jiǎng)得主姚期智提出了一個(gè)猜想，該猜想對(duì)幾乎填滿的哈希表找到空位的速度設(shè)定了一個(gè)限制。

他認(rèn)為，對(duì)于某些常見的哈希表，最壞情況下的插入操作（填滿最后一個(gè)空位）的預(yù)期時(shí)間與“x”成正比。換句話說，在特定屬性的哈希表中，找到單個(gè)元素或空位的最佳方法是隨機(jī)遍歷潛在空位，這種方法叫做均勻探測(cè)（uniform probing）。

在停車場(chǎng)例子中，如果x為1000（停車場(chǎng)已滿99.9%），那么平均而言，找到那個(gè)唯一的空位會(huì)花費(fèi)相當(dāng)長(zhǎng)的時(shí)間。

姚期智的猜想表明，這種x與搜索時(shí)間之間的線性關(guān)系是此類插入操作的最佳速度。幾十年來，幾乎沒有人對(duì)此提出質(zhì)疑。

直到有人因?yàn)椴恢肋@一猜想，意外地實(shí)現(xiàn)了突破。

偶然地突破

這一突破源于一名叫做Andrew Krapivin的本科生偶然看到了一篇名為《Tiny Pointers》的論文，講的是一種旨在壓縮指針以減少內(nèi)存消耗的概念。

計(jì)算機(jī)系統(tǒng)中的傳統(tǒng)指針通常使用固定數(shù)量的位來表示內(nèi)存地址。然而，微型指針采用了一種巧妙的技術(shù)來減少所需的位數(shù)，從而節(jié)省內(nèi)存空間。這在Krapivin的創(chuàng)新中起著關(guān)鍵作用。

要理解微型指針的工作原理，可以設(shè)想多個(gè)用戶共享一個(gè)數(shù)據(jù)數(shù)組的情況。

每個(gè)用戶都可以請(qǐng)求數(shù)組中的一個(gè)位置，而微型指針用于跟蹤已分配的位置。微型指針并不直接存儲(chǔ)完整的內(nèi)存地址，而是利用知道哪個(gè)用戶“擁有”該指針以及數(shù)組的結(jié)構(gòu)，用更少的位來表示位置。

這就好比為一個(gè)特定位置設(shè)定了一個(gè)簡(jiǎn)化的代碼或昵稱，而這個(gè)代碼或昵稱只有在特定上下文中才有意義。

指針大小的縮減意味著顯著的內(nèi)存節(jié)省，尤其是在大量使用指針的應(yīng)用中。

為了進(jìn)一步探索內(nèi)存的優(yōu)化，Krapivin深入研究了哈希表，試圖找到一種更高效的方式來組織這些指針?biāo)赶虻臄?shù)據(jù)。

這一探索促使他開發(fā)出了一種新穎的哈希表設(shè)計(jì)，其性能超乎尋常，在數(shù)據(jù)查找和存儲(chǔ)方面展現(xiàn)出了前所未有的速度。

具體來說，Krapivin開發(fā)了一種采用開放尋址法的新型哈希表，將所有元素都直接存儲(chǔ)在哈希表本身中。這與分離鏈接法形成了鮮明對(duì)比，在分離鏈接法中，具有相同哈希鍵的元素存儲(chǔ)在一個(gè)鏈表中。

與依賴統(tǒng)一探測(cè)不同，Krapivin的哈希表采用了一種更復(fù)雜的策略，包括子數(shù)組的使用以及特定的插入規(guī)則。

其基本思路是將哈希表劃分為更小的子數(shù)組，并使用一組規(guī)則來確定新元素的插入位置。這些規(guī)則優(yōu)先考慮平衡元素在子數(shù)組之間的分布，這有助于最大限度地減少未來插入和搜索所需的時(shí)間。這種“非貪婪”的方法，雖然早期插入的成本可能略高，但后期插入和搜索的速度卻明顯加快，尤其是當(dāng)哈希表逐漸填滿時(shí)。

Krapivin的哈希表實(shí)現(xiàn)了最壞情況下的查詢和插入時(shí)間與(log x)²成正比，比x要快得多。

這一突破最大的意義在于，Krapivin的研究并非只是漸進(jìn)式的改進(jìn)；而是從根本上挑戰(zhàn)了我們對(duì)于哈希表如何設(shè)計(jì)和優(yōu)化的理解。通過推翻姚氏猜想，他為數(shù)據(jù)結(jié)構(gòu)和算法的研究開辟了新的途徑，未來可能會(huì)帶來更高效的解決方案。

影響與應(yīng)用

Krapivin的突破對(duì)利用哈希表的各種應(yīng)用具有深遠(yuǎn)的影響。這一創(chuàng)新可能產(chǎn)生重大影響的一些關(guān)鍵領(lǐng)域包括：

數(shù)據(jù)庫(kù)：哈希表在數(shù)據(jù)庫(kù)中被廣泛用于索引和檢索數(shù)據(jù)。Krapivin的發(fā)現(xiàn)可能會(huì)加快查詢處理速度，并提升數(shù)據(jù)庫(kù)的整體性能。

緩存系統(tǒng)：緩存依靠哈希表來高效地存儲(chǔ)和檢索頻繁訪問的數(shù)據(jù)。Krapivin的哈希表帶來的速度提升可能會(huì)使網(wǎng)絡(luò)瀏覽器、操作系統(tǒng)和內(nèi)容分發(fā)網(wǎng)絡(luò)的加載時(shí)間更快，從而改善用戶體驗(yàn)。

編譯器：編譯器使用哈希表進(jìn)行符號(hào)表管理，這涉及存儲(chǔ)和檢索有關(guān)變量、函數(shù)和其他程序元素的信息。更快的哈希表有可能加快編譯過程，特別是對(duì)于大型程序而言。這在軟件開發(fā)中尤其有益，因?yàn)榫幾g時(shí)間可能是影響生產(chǎn)力的一個(gè)重要因素。

網(wǎng)絡(luò)路由：哈希表在網(wǎng)絡(luò)路由器中用于高效轉(zhuǎn)發(fā)數(shù)據(jù)包。Krapivin的工作有助于加快路由決策并提升網(wǎng)絡(luò)性能。在高流量網(wǎng)絡(luò)中，采用更快哈希表的路由器能夠更快地決定將數(shù)據(jù)包發(fā)送到何處，從而降低延遲并提高整體網(wǎng)絡(luò)速度。

密碼學(xué)：哈希表被用于各種密碼學(xué)算法中，例如用于數(shù)字簽名和安全通信的算法。更快的哈希表所提供的效率提升有可能增強(qiáng)這些算法的性能，從而加快加密和解密的過程。

盡管Krapivin的研究成果令人振奮，但要全面了解這一突破的范圍和潛力，還需要進(jìn)一步的研究和驗(yàn)證。研究人員目前正在探索這一發(fā)現(xiàn)的更廣泛影響，并研究其在不同領(lǐng)域的適用性。包括探索在其他數(shù)據(jù)結(jié)構(gòu)和算法中使用微型指針，以及針對(duì)特定應(yīng)用優(yōu)化Krapivin的哈希表。

Krapivin的創(chuàng)新性研究，表明了科學(xué)研究有時(shí)候需要一種「無知」的探索精神與好奇心，所謂的「標(biāo)準(zhǔn)答案」或「正確解法」可能成為創(chuàng)新的桎梏，而「無畏」的探索反而能夠能刺破認(rèn)知的繭房。正如愛因斯坦所言：“想象力比知識(shí)更重要。”

如今的AI行業(yè)也是如此，都在研究大語言模型，都知道尺度定律（Scaling Law）的存在，于是科技巨頭們專注于砸錢、堆芯片、比參數(shù)、拼算力，而DeepSeek另辟蹊徑實(shí)現(xiàn)彎道超車，雖然沒有完全顛覆尺度定律，但也說明了方法創(chuàng)新的重要性。

在遇到瓶頸或接近極限時(shí)，跳出路徑依賴，也許能找到新的解法。改變游戲規(guī)則，才能提供另一種選項(xiàng)。

未來，當(dāng)更多研究者敢于質(zhì)疑“不可逾越”的極限時(shí)，我們或許會(huì)發(fā)現(xiàn)：那些曾被奉為圭臬的“真理”，不過是等待被刷新的起點(diǎn)。

本文僅代表作者觀點(diǎn)。