哈希表（hash table）是計算機科學中最基礎也最重要的數據結構之一，它的歷史可以追溯到 20 世紀 50 年代早期。哈希表的核心思想是通過一個哈希函數，將任意范圍的鍵值映射到一個固定大小的數組空間中。

圖丨一個作為哈希表的小型電話簿（來源：WikiPedia）

這種數據結構就像一個巨大的抽屜柜，每個數據都可以被迅速放入某個抽屜中，并在需要時快速取出。但當抽屜柜接近裝滿時，找到合適的空抽屜就變得越來越困難。

也就是說，當一個哈希表接近裝滿時（比如說已經占用了 99% 的空間），要在剩余空間中找到一個空位至少需要進行與填充率成正比的次數搜索。這就意味著，如果哈希表已經 99% 滿了，那么在最壞情況下，需要大約 100 次嘗試才能找到一個空位。這個理論限制就像物理學中的光速極限一樣，被認為是不可逾越的。

1985 年，圖靈獎得主姚期智在其具有里程碑意義的論文 Uniform Hashing is Optimal 中提出在具有特定屬性的哈希表中，隨機選擇抽屜的方法，即均勻探測（uniform probing）是最優的選擇。

圖丨相關論文（來源：Journal of the ACM）

近 40 年來，計算機科學家們普遍認為姚期智的這個猜想是正確的。這種共識不僅影響了數據庫系統的設計，也深刻影響了眾多依賴高效數據存儲的現代應用程序。然而，這個看似堅不可摧的理論堡壘，最近被一位年輕的本科生撼動了。

因為“無知”推翻 40 年來的猜想

這個突破性的發現源于一個看似偶然的機會。2021 年秋天，羅格斯大學的本科生 Andrew Krapivin 在瀏覽學術論文時，發現了一篇名為 Tiny Pointers 的文章。這篇論文探討了一種新型的數據指針技術，能夠大幅減少計算機內存的使用。那時候 Krapivin 并沒有想太多，但兩年后，當他真正開始深入研究這篇論文時，他意識到這里面隱藏著更多的可能性。

圖丨相關論文（來源：arXiv）

Tiny Pointers 這篇論文探討了一個看似簡單但意義深遠的問題：如何用更少的比特位來存儲計算機中的指針。傳統的指針需要 log n 個比特才能在 n 個位置中定位一個元素。但這篇論文提出了一個巧妙的思路：如果我們預先知道指針屬于哪個用戶，那么就可以利用這個額外信息來壓縮指針的大小。

正是這種壓縮指針的思路啟發了 Krapivin 對哈希表的新認識，在哈希表搜索過程中，我們其實也可以利用之前探測獲得的信息來指導后續的搜索。

相比之下，傳統方法則假設每次探測都是獨立的、均勻隨機的。而 Krapivin 沒有被這一種方式所束縛，其實也只是因為他并不知道這種方法。

他用 Tiny Pointers 進行的探索導致了一種新型的哈希表——一種不依賴于均勻探測的哈希表。對于這種新的哈希表，最壞情況下的查詢和插入所需的時間與 (log x)2 成正比——比 x 快得多。這一結果直接反駁了姚期智的猜想。

當 Krapivin 向他的前教授、Tiny Pointers 的共同作者 Martín Farach-Colton 展示這個設計時，后者最初顯得相當懷疑。這種謹慎是可以理解的：哈希表是計算機科學中研究最充分的數據結構之一，重大突破似乎不太可能。但當論文的另一位合作者、卡內基梅隆大學的 William Kuszmaul 仔細審視這項工作時，他意識到了其革命性意義。

“你并不是僅僅發明了一個新的哈希表，”Kuszmaul 對 Krapivin 說，“你實際上完全推翻了一個存在了 40 年的猜想！”

最終，他們共同合作，完成了這篇論文。

圖丨相關論文（來源：arXiv）

康奈爾理工學院的 Alex Conway 評價道：“這是一項開創性的工作。盡管哈希表已經有著悠久的歷史，但關于它們的工作原理，我們仍然有很多需要了解的地方。這篇論文以令人驚訝的方式回答了其中的幾個根本性問題。”

“彈性哈希”

要理解這項工作的開創性，我們需要先明確傳統哈希表面臨的根本性挑戰。

在傳統的開放尋址哈希表中，當我們需要插入一個新元素時，會按照某個預定義的探測序列逐個檢查位置，直到找到第一個空位。這種方法就被稱為“貪婪策略”，因為它總是急于接受第一個可用的位置。姚期智在 1985 年的論文中證明，在這種貪婪策略下，當哈希表接近滿載時（比如說留有δ比例的空位），最壞情況下需要 O(δ^-1) 次探測才能找到一個空位。并且他猜想這個界限對于任何貪婪策略都是最優的。

然而，Krapivin 的工作證明，如果我們愿意放棄貪婪策略，實際上可以獲得顯著更好的性能。研究提出了一種新的哈希表構造方法，命名為“彈性哈希”（Elastic Hashing），成功實現了均攤探測復雜度 O(1) 的最優解，同時使得最壞情況的探測復雜度降至 O(log δ?1)。這一研究不僅推翻姚期智的猜想，還在不依賴重排操作的前提下，首次證明了更優的探測復雜度下界。

就像 Tiny Pointers 通過利用額外的上下文信息來減少存儲開銷，彈性哈希通過收集更多的探測信息來做出更有效的放置決策。其核心思想是將整個哈希表劃分為多個子數組，并通過一種二元探測結構進行索引。

在該模型中，哈希表被拆分為一系列大小指數遞減的子數組，例如 A?、A?、...、A_?log n?，其中 |A???| = |A?|/2 ± 1。這種層次結構為非貪婪探測提供了可能，使得插入操作可以優先在負載較低的區域進行，同時保證查找過程的高效性。研究者引入了一個特定的映射 φ(i,j)，使得二維探測序列 h?,? (x) 可以映射到一維探測序列 hφ(i,j)(x)，其中 φ(i,j) ≤ O(i·j2)。該映射的設計確保了在插入過程中，較早被訪問的探測位置能夠更高效地找到空槽，從而降低整體探測復雜度。

（來源：Quanta Magazine）

具體來說，彈性哈希采用分批次插入策略，以確保各個子數組的負載水平得到合理分配。首先，在初始批次 B?中，哈希表的第一個子數組 A? 被填充至約 75% 的負載。隨后，在后續的批次 B? 中，插入操作主要發生在 A?和 A??? 之間，確保每個子數組的負載保持在合理范圍內。

插入過程中，如果某個子數組仍有較多可用槽位（空位比例高于 δ/2），新元素將嘗試在該子數組內找到合適的位置。而當子數組接近滿載時，插入算法會自動轉向下一級子數組，以提高存儲效率。此外，在最壞情況下，即所有子數組的空位都非常有限時，算法會退回到均勻探測策略，但這種情況的概率極低，確保了整體復雜度的優化。

數學分析表明，該方法能夠顯著降低均攤探測復雜度和最壞情況探測復雜度。首先，在均攤探測復雜度方面，研究者證明了彈性哈希的平均探測次數為 O(1)，這意味著大多數操作只需要常數次探測就能完成。遠優于均勻探測的 O(log δ?1)。其根本原因在于，彈性哈希將大多數插入操作限制在負載較低的子數組中，使得多數元素能夠在少量探測后成功存儲。

其次，在最壞情況探測復雜度方面，研究表明在無重排的情況下，任何開放尋址哈希的最壞情況探測復雜度必須至少達到 Ω(log δ?1)，而彈性哈希實現了這一下界的最優匹配。

“漏斗哈希”

在彈性哈希方法的基礎上，研究者進一步提出了一種新的貪婪開放尋址（Open Addressing）策略，命名為“漏斗哈希”（Funnel Hashing）。通過構造一種層級結構的哈希表，該方法實現了最壞情況的期望探測復雜度 O(log2δ?1)，并且證明了這一界限的最優性。

漏斗哈希的基本思想是在哈希表中引入多級結構，使得元素在不同負載水平的區域之間進行分層存儲，從而降低高負載情況下的探測次數。具體而言，哈希表被劃分為多個層級，每一層內部進一步分為若干個等大小的子數組，所有子數組的大小按幾何級數遞減。假設哈希表的總容量為 n，研究者首先將其劃分為兩部分，其中一部分（記為A_α+1）的大小約為 δn，用于存儲最難插入的元素，而剩余部分（記為 A'）再細分為 α 個子數組 A?、A?、...、Aα。這些子數組的大小遞減關系滿足 |A???| ≈ 3|A?|/4，并且每個 A? 進一步劃分為若干個小塊，每個小塊的大小設定為 β，其中 β 取 O(logδ?1)。

在插入過程中，每個元素首先會嘗試插入最上層的子數組A?，如果失敗則依次嘗試 A?, A3,……直到成功找到空位或最終進入專門的存儲區 A_α+1。在每一層的插入嘗試中，元素會隨機選擇一個子塊，并依次掃描該子塊中的位置以尋找空槽。這種分層探測策略確保了大多數插入操作可以在前幾層完成，而僅有極少數插入會進入最底層的存儲區域。

數學分析表明，漏斗哈希的最壞情況期望探測復雜度為 O(log2δ?1)，顯著優于均勻探測的 O(δ?1)。其核心證明建立在以下幾個關鍵步驟之上。

首先，研究者證明了每個子數組在一定插入次數后都會達到接近飽和的狀態，即子數組內部空槽的數量受嚴格控制。這意味著即使在較高負載的情況下，仍然可以保證大多數插入操作在 O(logδ?1) 次探測內成功。其次，通過分析插入元素在不同層級上的分布，研究者證明了即使在最壞情況下，元素也只需經歷 O(log2δ?1) 次探測，即可找到一個可用的位置。此外，研究者還證明了這一界限的最優性，表明任何貪婪開放尋址哈希表都無法突破 Ω(log2δ?1) 的最壞情況探測復雜度。

除了在期望探測復雜度上的優化，漏斗哈希還具備良好的高概率最壞情況保證。研究者進一步證明，在絕大多數情況下（即以1-1/poly(n) 的概率），任意一個元素的最壞情況探測復雜度不會超過 O(log2δ?1 + log log n)。這意味著即使在極端負載的情況下，該方法仍然能夠保持較為穩定的性能，而不會出現大幅度退化的情況。

圖丨 Farach-Colton（來源：Andrew Farach-Colton）

總之，這一方法的提出不僅解答了姚期智在 1985 年提出的未解決問題，即最壞情況的期望探測復雜度是否可以低于 O(δ?1)，還證明了均勻探測在貪婪算法框架下并非最優。對于貪婪哈希表，最壞情況下的探測復雜度可以降低到 O(log2δ?1)，而對于非貪婪哈希表，平均查詢時間甚至可以完全獨立于負載因子 δ。

“這只是一個常數，與哈希表是否滿無關”，Farach-Colton 說。無論哈希表是否滿，查詢的平均時間都可以達到常數級別，這個發現甚至出乎研究者自己的意料。

即便目前該研究可能不會立即帶來工業界的應用，但理解數據結構的基礎理論非常重要，因為“你永遠不知道這樣的結果什么時候會解鎖某種新的突破，讓實際應用變得更加高效。”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