Faster hash table Elastic Hashing and Funnel Hashing

Created in February 12, 2025

2025   ·   hash   algorithm   ·   self-learning

前言

哈希表（Hash Table）是一種極為重要的資料結構，廣泛應用於資料庫索引、快取系統、鍵值存儲（Key-Value Store） 等高效能場景。然而，當哈希表接近滿載時，開放位址哈希（Open Addressing）通常會面臨查詢與插入成本暴增的問題。

在 1985 年，計算機科學家 Andrew Yao 提出了一個經典猜想：「均勻探測（Uniform Probing）是最優的」。這意味著，在 無重排（No Reordering） 的情況下，最壞情況的期望探測次數應該是 \(O(\delta^{-1})\)，其中 \(\delta\) 代表哈希表的空閒比例（負載餘裕），例如當 \(\delta = 0.01\)時，表示哈希表已經填滿 99%，剩下 1% 的空位。

這個猜想影響了數十年來的哈希表設計，使得許多研究都接受了「當哈希表高負載時，查詢時間必然變慢」的現實。但這真的是無法突破的限制嗎？ 在這篇論文 Optimal Bounds for Open Addressing Without Reordering 中，作者 Martín Farach-Colton、Andrew Krapivin 和 William Kuszmaul 正式推翻了 Yao 的猜想！

他們提出了兩種創新的方法:

Elastic Hashing

透過非貪心插入（Non-Greedy Insertion） 和 層級化設計（Hierarchical Structure），將：

  • 攤銷查詢時間從 \(O(\log \delta^{-1})\) 降至 \(O(1)\)
  • 最壞查詢時間從 \(O(\delta^{-1})\) 降至 \(O(\log \delta^{-1})\)
  • 最壞插入時間從 \(O(\delta^{-1})\) 降至 \(O(\log \delta^{-1})\)

Funnel Hashing

Funnel Hashing 是目前最優的貪心開放位址哈希策略，透過 層級化設計(Hierarchical Structure) 和 區塊化存儲（Bucketized Storage），將：

  • 攤銷查詢時間從 \(O(\log \delta^{-1})\) 降至 \(O(\log \delta^{-1})\)
  • 最壞查詢時間從 \(O(\delta^{-1})\) 降至 \(O(\log \delta^{-1})\)
  • 最壞插入時間從 \(O(\delta^{-1})\) 降至 \(O(\log \delta^{-1})\)

Elastic Hashing

Elastic Hashing 的結構

Elastic Hashing 將哈希表分成多層（層數約為 \(O(\log n)\)），每一層的大小是 指數遞減 的。例如：

  • 層 \(A_1\)（最大層）：大小為 \(n\)。
  • 層 \(A_2\)：大小為 \(n/2\)。
  • 層 \(A_3\)：大小為 \(n/4\)。
  • 層 \(A_i\)：大小為 \(n/2^{i}\)。

這種結構確保：

  • 較大的層（靠前的層）可以容納更多元素，但也比較擁擠。
  • 較小的層（後面的層）有較多空間，但代價是較多的探測次數。

Elastic Hashing 的插入策略

Elastic Hashing 不貪心 地選擇第一個空位，而是：

先從較大的層（靠前的層）開始探測，但不是馬上插入，而是先記錄可能的插入位置。 如果這些探測都沒有找到可用位置，則往下一層繼續探測。 最終，根據已經探測過的資訊，選擇適合的位置插入。

具體步驟
假設要插入元素 \(x\)：

  1. 開始探測： 從第一層（\(A_1\)）的探測序列 \(h_1(x), h_1(x), h_1(x), \ldots\) 開始。

  2. 記錄探測過的位置： 如果前 \(f(\epsilon)\) 個探測都找到滿的槽位，就轉到下一層 \(A_2\)。 如果前 \(f(\epsilon)\) 個探測都找到滿的槽位，就轉到下一層 \(A_2\)。

在 \(A_2\) 執行類似的探測，直到找到一個空位。

  1. 決定插入位置： 如果上層有空位，插入靠前的層，減少未來查詢的探測次數。 如果上層沒有空位，插入下層（但此時已經有較多資訊來決定最佳插入位置）。

這種方式在插入時花費更多的探測，但換來的是更快的查詢時間，從而達到最優的攤銷探測次數。

為什麼這樣做能降低查詢時間？

Elastic Hashing 的核心思想是：

  • 插入時多花一些探測次數來確保元素分佈得更均勻。
  • 這樣當查詢時，元素更可能位於靠前的層（較少探測次數）。
  • 避免了傳統方法中，因為貪心插入導致未來查詢需要過多探測的問題。

這裡的關鍵是：查詢時間取決於「元素存放在哪一層」，而 Elastic Hashing 讓元素更可能存放在較少探測的層，從而降低查詢時間。

Elastic Hashing 的時間複雜度

  • 攤銷查詢時間： \(O(1)\)（最優）
    • 這意味著，對於大多數元素，平均只需要 \(O(1)\) 次探測就能找到。
  • 最壞查詢時間： \(O(\log \delta^{-1})\)
    • 這意味著，即使在最壞情況下，Elastic Hashing 仍然能保證比 Yao 猜測的 \(O(\delta^{-1})\) 更低的探測次數。
  • 最壞插入時間： \(O(\log \delta^{-1})\)

即使在最壞情況下，Elastic Hashing 仍然能保證比 Yao 猜測的 \(O(\delta^{-1})\) 更低的探測次數。

這使得它比傳統的均勻探測（Uniform Probing 更高效，特別是在負載接近滿載（ \(\delta\) 很小）時。

Funnel Hashing

Funnel Hashing 的結構

Funnel Hashing 將哈希表劃分為多層，每層大小指數遞減，並使用 「區塊化的 Bucket 結構」 來組織插入：

  1. 分層設計（Hierarchical Layers）

    • 哈希表被分成 \(( \alpha )\) 層，每層大小遞減：
      • 第 1 層 \(A_1\)：最大，大小為 \(n\)
      • 第 2 層 \(A_2\)：大小約為 \(n/2\)
      • 第 \(i\) 層 \(A_i\)：大小約為 \(n/2^i\)
    • 每層又被劃分為更小的「區塊」（Buckets），每個區塊大小為 \(\beta = O(\log \delta^{-1})\)。

  2. 多層 Bucket 管理（Bucketized Storage）

    • 每層 \(A_i\) 被進一步劃分為 \(n/\beta\) 個小區塊 \(A_{i,j}\)，每個大小為 \(\beta\)。
    • 插入時，優先嘗試插入較高層的區塊，若該區塊已滿，則往下一層尋找。

  3. 特殊存儲區 \(A_{\alpha+1}\)

    • 這是一個保險區域（Fallback Region），用來處理無法在前面層級找到插入位置的情況。
    • 這個區域採用 均勻探測（Uniform Probing）+ 雙重選擇（Two-choice Hashing） 來確保插入時間不會過高。

這樣的設計可以確保：

  • 高頻查詢的元素大多數都留在較高層，降低查詢時間
  • 低頻插入的元素才會被推向較低層，降低最壞情況的探測次數

Funnel Hashing 的插入策略

當一個新元素 \(x\) 需要插入時，它會按照 Funnel 的方式逐層嘗試插入：

  1. 從 \(A*1\) 層開始，嘗試插入某個隨機選擇的 Bucket \(A*{1,j}\)：

    • 如果該 Bucket 還有空位，則直接插入，結束。
    • 如果該 Bucket 已滿，則繼續到 \(A_2\) 層進行相同的嘗試。

  2. 如果所有前 \(\alpha\) 層的 Bucket 都已滿，則將元素插入 \(A\_{\alpha+1}\)（特殊存儲區）。

這種策略確保：

  • 大部分插入都能在較高層找到位置，降低未來查詢的探測次數。
  • 只有少數插入才會進入低層或特殊存儲區，避免極端情況。

Funnel Hashing 如何改進最壞查詢時間？

Funnel Hashing 改進查詢時間的核心機制是：

  1. 多層結構確保較高層的元素更容易被查詢到

    • 常見的元素會存放在較高層（靠近頂端的區塊）。
    • 這樣，查詢時大多數情況下只需要查找少量區塊即可找到。

  2. Bucket 結構讓查詢更高效

    • 每個區塊的大小 \(\beta\) 為 \(O(\log \delta^{-1})\)，這樣即使查詢需要檢查多層，總探測次數仍然控制在 \(O(\log^2 \delta^{-1})\)。

  3. 特殊存儲區 \(A_{\alpha+1}\) 確保最壞查詢時間受控

    • 這個區域的負載受到嚴格限制，避免了標準均勻探測中可能出現的高密度碰撞問題。

這些機制確保了 Funnel Hashing 能將最壞查詢時間從 \(O(\delta^{-1})\) 降至 \(O(\log^2 \delta^{-1})\)。

Funnel Hashing 的時間複雜度

  • 攤銷查詢時間： \(O(\log \delta^{-1})\)
  • 最壞查詢時間： \(O(\log \delta^{-1})\)
  • 最壞插入時間： \(O(\log \delta^{-1})\)

這代表 Funnel Hashing 是目前最優的貪心開放位址哈希策略！

Funnel Hashing vs Elastic Hashing

特性 Funnel Hashing Elastic Hashing
類型 貪心（Greedy） 非貪心（Non-Greedy）
攤銷查詢時間 \(O(\log \delta^{-1})\) \(O(1)\)
最壞查詢時間 \(O(\log^2 \delta^{-1})\) \(O(\log \delta^{-1})\)
攤銷插入時間 \(O(\log \delta^{-1})\) \(O(1)\)
最壞插入時間 \(O(\log^2 \delta^{-1})\) \(O(\log \delta^{-1})\)
  • Elastic Hashing 最適合低查詢延遲的應用（如快取系統、資料庫索引）。
  • Funnel Hashing 是目前最優的貪心策略，適合需要貪心插入的場景。

總結

以下是各種方法的時間複雜度比較：

方法 攤銷插入時間 最壞插入時間 攤銷查詢時間 最壞查詢時間
均勻探測（Uniform Probing） \(O(1)\) \(O(\delta^{-1})\) \(O(\log \delta^{-1})\) \(O(\delta^{-1})\)
Elastic Hashing \(O(1)\) \(O(\log \delta^{-1})\) \(O(1)\) \(O(\log \delta^{-1})\)
Funnel Hashing \(O(1)\) \(O(\log \delta^{-1})\) \(O(\log \delta^{-1})\) \(O(\log \delta^{-1})\)

我們看到：

  • Elastic Hashing 透過非貪心插入，成功將查詢時間降至 \(O(1)\)，並顯著降低最壞探測次數，突破 Yao 猜想。
  • Funnel Hashing 則作為最優的貪心策略，確保在無重排的情況下，仍能顯著降低最壞查詢與插入時間，適用於高負載場景。

這些方法不僅在理論上具有重大突破，更在實務應用上開啟了新的可能性，特別適合：

  • 快取系統（如 Redis、Memcached）
  • 高效能資料庫索引
  • 分散式哈希表（DHT）
  • 大型 Key-Value 存儲系統

隨著資料量的增長與系統負載的提升，如何設計更高效、更穩定的哈希表將成為關鍵議題。

附錄

Optimal Bounds for Open Addressing Without Reordering