哈希表（hash table）是計算機(jī)科學(xué)中最基礎(chǔ)也最重要的數(shù)據(jù)結(jié)構(gòu)之一，它的歷史可以追溯到 20 世紀(jì) 50 年代早期。哈希表的核心思想是通過一個哈希函數(shù)，將任意范圍的鍵值映射到一個固定大小的數(shù)組空間中。
這種數(shù)據(jù)結(jié)構(gòu)就像一個巨大的抽屜柜，每個數(shù)據(jù)都可以被迅速放入某個抽屜中，并在需要時快速取出。但當(dāng)抽屜柜接近裝滿時，找到合適的空抽屜就變得越來越困難。
也就是說，當(dāng)一個哈希表接近裝滿時（比如說已經(jīng)占用了 99% 的空間），要在剩余空間中找到一個空位至少需要進(jìn)行與填充率成正比的次數(shù)搜索。這就意味著，如果哈希表已經(jīng) 99% 滿了，那么在最壞情況下，需要大約 100 次嘗試才能找到一個空位。這個理論限制就像物理學(xué)中的光速極限一樣，被認(rèn)為是不可逾越的。
1985 年，圖靈獎得主姚期智在其具有里程碑意義的論文 Uniform Hashing is Optimal 中提出在具有特定屬性的哈希表中，隨機(jī)選擇抽屜的方法，即均勻探測（uniform probing）是最優(yōu)的選擇。
近 40 年來，計算機(jī)科學(xué)家們普遍認(rèn)為姚期智的這個猜想是正確的。這種共識不僅影響了數(shù)據(jù)庫系統(tǒng)的設(shè)計，也深刻影響了眾多依賴高效數(shù)據(jù)存儲的現(xiàn)代應(yīng)用程序。然而，這個看似堅不可摧的理論堡壘，最近被一位年輕的本科生撼動了。
因?yàn)椤盁o知”推翻 40 年來的猜想
這個突破性的發(fā)現(xiàn)源于一個看似偶然的機(jī)會。2021 年秋天，羅格斯大學(xué)的本科生 Andrew Krapivin 在瀏覽學(xué)術(shù)論文時，發(fā)現(xiàn)了一篇名為 Tiny Pointers 的文章。這篇論文探討了一種新型的數(shù)據(jù)指針技術(shù)，能夠大幅減少計算機(jī)內(nèi)存的使用。那時候 Krapivin 并沒有想太多，但兩年后，當(dāng)他真正開始深入研究這篇論文時，他意識到這里面隱藏著更多的可能性。
Tiny Pointers 這篇論文探討了一個看似簡單但意義深遠(yuǎn)的問題：如何用更少的比特位來存儲計算機(jī)中的指針。傳統(tǒng)的指針需要 log n 個比特才能在 n 個位置中定位一個元素。但這篇論文提出了一個巧妙的思路：如果我們預(yù)先知道指針屬于哪個用戶，那么就可以利用這個額外信息來壓縮指針的大小。
正是這種壓縮指針的思路啟發(fā)了 Krapivin 對哈希表的新認(rèn)識，在哈希表搜索過程中，我們其實(shí)也可以利用之前探測獲得的信息來指導(dǎo)后續(xù)的搜索。
相比之下，傳統(tǒng)方法則假設(shè)每次探測都是獨(dú)立的、均勻隨機(jī)的。而 Krapivin 沒有被這一種方式所束縛，其實(shí)也只是因?yàn)樗⒉恢肋@種方法。
他用 Tiny Pointers 進(jìn)行的探索導(dǎo)致了一種新型的哈希表——一種不依賴于均勻探測的哈希表。對于這種新的哈希表，最壞情況下的查詢和插入所需的時間與 (log x)2 成正比——比 x 快得多。這一結(jié)果直接反駁了姚期智的猜想。
當(dāng) Krapivin 向他的前教授、Tiny Pointers 的共同作者 Martín Farach-Colton 展示這個設(shè)計時，后者最初顯得相當(dāng)懷疑。這種謹(jǐn)慎是可以理解的：哈希表是計算機(jī)科學(xué)中研究最充分的數(shù)據(jù)結(jié)構(gòu)之一，重大突破似乎不太可能。但當(dāng)論文的另一位合作者、卡內(nèi)基梅隆大學(xué)的 William Kuszmaul 仔細(xì)審視這項(xiàng)工作時，他意識到了其革命性意義。
“你并不是僅僅發(fā)明了一個新的哈希表，”Kuszmaul 對 Krapivin 說，“你實(shí)際上完全推翻了一個存在了 40 年的猜想！”
最終，他們共同合作，完成了這篇論文。
康奈爾理工學(xué)院的 Alex Conway 評價道：“這是一項(xiàng)開創(chuàng)性的工作。盡管哈希表已經(jīng)有著悠久的歷史，但關(guān)于它們的工作原理，我們?nèi)匀挥泻芏嘈枰私獾牡胤?。這篇論文以令人驚訝的方式回答了其中的幾個根本性問題?！?/p>
“彈性哈?！?/strong>
要理解這項(xiàng)工作的開創(chuàng)性，我們需要先明確傳統(tǒng)哈希表面臨的根本性挑戰(zhàn)。
在傳統(tǒng)的開放尋址哈希表中，當(dāng)我們需要插入一個新元素時，會按照某個預(yù)定義的探測序列逐個檢查位置，直到找到第一個空位。這種方法就被稱為“貪婪策略”，因?yàn)樗偸羌庇诮邮艿谝粋€可用的位置。姚期智在 1985 年的論文中證明，在這種貪婪策略下，當(dāng)哈希表接近滿載時（比如說留有δ比例的空位），最壞情況下需要 O(δ^-1) 次探測才能找到一個空位。并且他猜想這個界限對于任何貪婪策略都是最優(yōu)的。
然而，Krapivin 的工作證明，如果我們愿意放棄貪婪策略，實(shí)際上可以獲得顯著更好的性能。研究提出了一種新的哈希表構(gòu)造方法，命名為“彈性哈希”（Elastic Hashing），成功實(shí)現(xiàn)了均攤探測復(fù)雜度 O(1) 的最優(yōu)解，同時使得最壞情況的探測復(fù)雜度降至 O(log δ?1)。這一研究不僅推翻姚期智的猜想，還在不依賴重排操作的前提下，首次證明了更優(yōu)的探測復(fù)雜度下界。
就像 Tiny Pointers 通過利用額外的上下文信息來減少存儲開銷，彈性哈希通過收集更多的探測信息來做出更有效的放置決策。其核心思想是將整個哈希表劃分為多個子數(shù)組，并通過一種二元探測結(jié)構(gòu)進(jìn)行索引。
在該模型中，哈希表被拆分為一系列大小指數(shù)遞減的子數(shù)組，例如 A?、A?、...、A_?log n?，其中 |A???| = |A?|/2 ± 1。這種層次結(jié)構(gòu)為非貪婪探測提供了可能，使得插入操作可以優(yōu)先在負(fù)載較低的區(qū)域進(jìn)行，同時保證查找過程的高效性。研究者引入了一個特定的映射 φ(i,j)，使得二維探測序列 h?,? (x) 可以映射到一維探測序列 hφ(i,j)(x)，其中 φ(i,j) ≤ O(i·j2)。該映射的設(shè)計確保了在插入過程中，較早被訪問的探測位置能夠更高效地找到空槽，從而降低整體探測復(fù)雜度。
具體來說，彈性哈希采用分批次插入策略，以確保各個子數(shù)組的負(fù)載水平得到合理分配。首先，在初始批次 B?中，哈希表的第一個子數(shù)組 A? 被填充至約 75% 的負(fù)載。隨后，在后續(xù)的批次 B? 中，插入操作主要發(fā)生在 A?和 A??? 之間，確保每個子數(shù)組的負(fù)載保持在合理范圍內(nèi)。
插入過程中，如果某個子數(shù)組仍有較多可用槽位（空位比例高于 δ/2），新元素將嘗試在該子數(shù)組內(nèi)找到合適的位置。而當(dāng)子數(shù)組接近滿載時，插入算法會自動轉(zhuǎn)向下一級子數(shù)組，以提高存儲效率。此外，在最壞情況下，即所有子數(shù)組的空位都非常有限時，算法會退回到均勻探測策略，但這種情況的概率極低，確保了整體復(fù)雜度的優(yōu)化。
數(shù)學(xué)分析表明，該方法能夠顯著降低均攤探測復(fù)雜度和最壞情況探測復(fù)雜度。首先，在均攤探測復(fù)雜度方面，研究者證明了彈性哈希的平均探測次數(shù)為 O(1)，這意味著大多數(shù)操作只需要常數(shù)次探測就能完成。遠(yuǎn)優(yōu)于均勻探測的 O(log δ?1)。其根本原因在于，彈性哈希將大多數(shù)插入操作限制在負(fù)載較低的子數(shù)組中，使得多數(shù)元素能夠在少量探測后成功存儲。
其次，在最壞情況探測復(fù)雜度方面，研究表明在無重排的情況下，任何開放尋址哈希的最壞情況探測復(fù)雜度必須至少達(dá)到 Ω(log δ?1)，而彈性哈希實(shí)現(xiàn)了這一下界的最優(yōu)匹配。
“漏斗哈?！?/strong>
在彈性哈希方法的基礎(chǔ)上，研究者進(jìn)一步提出了一種新的貪婪開放尋址（Open Addressing）策略，命名為“漏斗哈希”（Funnel Hashing）。通過構(gòu)造一種層級結(jié)構(gòu)的哈希表，該方法實(shí)現(xiàn)了最壞情況的期望探測復(fù)雜度 O(log2δ?1)，并且證明了這一界限的最優(yōu)性。
漏斗哈希的基本思想是在哈希表中引入多級結(jié)構(gòu)，使得元素在不同負(fù)載水平的區(qū)域之間進(jìn)行分層存儲，從而降低高負(fù)載情況下的探測次數(shù)。具體而言，哈希表被劃分為多個層級，每一層內(nèi)部進(jìn)一步分為若干個等大小的子數(shù)組，所有子數(shù)組的大小按幾何級數(shù)遞減。假設(shè)哈希表的總?cè)萘繛?n，研究者首先將其劃分為兩部分，其中一部分（記為A_α+1）的大小約為 δn，用于存儲最難插入的元素，而剩余部分（記為 A'）再細(xì)分為 α 個子數(shù)組 A?、A?、...、Aα。這些子數(shù)組的大小遞減關(guān)系滿足 |A???| ≈ 3|A?|/4，并且每個 A? 進(jìn)一步劃分為若干個小塊，每個小塊的大小設(shè)定為 β，其中 β 取 O(logδ?1)。
在插入過程中，每個元素首先會嘗試插入最上層的子數(shù)組A?，如果失敗則依次嘗試 A?, A3,……直到成功找到空位或最終進(jìn)入專門的存儲區(qū) A_α+1。在每一層的插入嘗試中，元素會隨機(jī)選擇一個子塊，并依次掃描該子塊中的位置以尋找空槽。這種分層探測策略確保了大多數(shù)插入操作可以在前幾層完成，而僅有極少數(shù)插入會進(jìn)入最底層的存儲區(qū)域。
數(shù)學(xué)分析表明，漏斗哈希的最壞情況期望探測復(fù)雜度為 O(log2δ?1)，顯著優(yōu)于均勻探測的 O(δ?1)。其核心證明建立在以下幾個關(guān)鍵步驟之上。
首先，研究者證明了每個子數(shù)組在一定插入次數(shù)后都會達(dá)到接近飽和的狀態(tài)，即子數(shù)組內(nèi)部空槽的數(shù)量受嚴(yán)格控制。這意味著即使在較高負(fù)載的情況下，仍然可以保證大多數(shù)插入操作在 O(logδ?1) 次探測內(nèi)成功。其次，通過分析插入元素在不同層級上的分布，研究者證明了即使在最壞情況下，元素也只需經(jīng)歷 O(log2δ?1) 次探測，即可找到一個可用的位置。此外，研究者還證明了這一界限的最優(yōu)性，表明任何貪婪開放尋址哈希表都無法突破 Ω(log2δ?1) 的最壞情況探測復(fù)雜度。
除了在期望探測復(fù)雜度上的優(yōu)化，漏斗哈希還具備良好的高概率最壞情況保證。研究者進(jìn)一步證明，在絕大多數(shù)情況下（即以1-1/poly(n) 的概率），任意一個元素的最壞情況探測復(fù)雜度不會超過 O(log2δ?1 + log log n)。這意味著即使在極端負(fù)載的情況下，該方法仍然能夠保持較為穩(wěn)定的性能，而不會出現(xiàn)大幅度退化的情況。
總之，這一方法的提出不僅解答了姚期智在 1985 年提出的未解決問題，即最壞情況的期望探測復(fù)雜度是否可以低于 O(δ?1)，還證明了均勻探測在貪婪算法框架下并非最優(yōu)。對于貪婪哈希表，最壞情況下的探測復(fù)雜度可以降低到 O(log2δ?1)，而對于非貪婪哈希表，平均查詢時間甚至可以完全獨(dú)立于負(fù)載因子 δ。
“這只是一個常數(shù)，與哈希表是否滿無關(guān)”，F(xiàn)arach-Colton 說。無論哈希表是否滿，查詢的平均時間都可以達(dá)到常數(shù)級別，這個發(fā)現(xiàn)甚至出乎研究者自己的意料。
即便目前該研究可能不會立即帶來工業(yè)界的應(yīng)用，但理解數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)理論非常重要，因?yàn)椤澳阌肋h(yuǎn)不知道這樣的結(jié)果什么時候會解鎖某種新的突破，讓實(shí)際應(yīng)用變得更加高效。”Conway 表示。
參考資料：
1.https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/
2.https://doi.org/10.1145/3828.3836
3.https://arxiv.org/abs/2501.02305
4.https://arxiv.org/abs/2111.12800
熱門跟貼