在線性表中, 包括陣列和連結串列, 搜尋元素的時間複雜度為 O(n). 而雜湊表是搜尋友好的資料結構, 它可以將搜尋的時間複雜度降低到 \Omega(1). 雜湊表使用雜湊函數將值影射到雜湊表的具體位置. 如果元素為 k, 雜湊函數為 f, 在理想的情況下, 其在雜湊表的位置 p 滿足

p = f(k)

暫時假定雜湊表的每一個位置都至多只能夠存取一個元素, 為了搜尋元素為 k 的具體位置, 首先要計算函數 f(k) 的值, 再查看在雜湊表的 f(k) 處是否已有該值. 若有, 便找到了具體位置; 如果沒有, 則元素不存在於雜湊表中. 通過這樣的描述, 我們也可以想像在理想情況下 (不計入雜湊函數計算的時間複雜度), 雜湊表中查找、刪除和插入元素的時間複雜度為 \Theta(1)

但是, 如果元素的變化範圍過於大, 但元素的數量卻非常少, 那麼使用理想的雜湊表只會浪費空間, 為了維護那些空的元素也需要不少精力. 因此, 當元素的範圍太大時, 不能使用理想方法表示時, 就需要採用並不那麼理想的雜湊表和雜湊函數 : 雜湊表的位置數量可能比元素數量要少, 雜湊函數可能會將多個不同的元素放入到雜湊表的同一個位置

雜湊表中每一個位置稱為桶, 雜湊函數 f(k) 回傳的位置是桶的頭部位置. 桶的數量在數值上和雜湊表的大小是一樣的

雜湊函數具有多種 :

  • 線性函數 : f(k) = ak + b. 特別地, f(k) = k
  • 數值分析 : 設元素都以 r 為基數, 而雜湊表中可能出現的元素都已知. 那麼取元素中的部分數字作為雜湊位置
  • 平方取中 : 取元素值平方之後的中間數字作為雜湊位置. 通常, 在選定雜湊函數時不一定能夠知道元素的全部情況, 取其中的哪幾個數字也不一定合適. 而一個數平方之後的中間幾個數字和數值的每一個數字都相關. 由此使得隨機分佈的元素得到的雜湊值也是隨機分佈的. 取數字的數量和雜湊表的大小相關
  • 折疊 : 將元素分為長度相同的幾個部分 (最後一部分可以不同), 然後這幾個部分疊加並且捨棄進位, 最終得到的結果作為雜湊位置
  • 取亂數 : 不依賴於元素值本身, 而依賴於一個亂數產生器產生的亂數
  • 除留餘數 : f(k) = k \mod p. 其中, p 不應大於雜湊表的長度
  • 結合多種方法

上面說的方法在實際中已經基本見不到了, 只是為了方便大家學習雜湊表. 現在使用的雜湊演算法都比較複雜 :

  • cityhash
  • MurmurHash
  • MD5
  • SHA-1
  • ...

有一些雜湊演算法是可逆的, 有一些雜湊演算法是不可逆的. 不可逆的雜湊演算法在密碼領域使用比較多. 在 C++ 標準樣板程式庫中, unordered 系列容器都使用了雜湊演算法, libc++ 採用了 cityhash 和 Murmur2. 我在個人項目 data_structure 中採用了 cityhash 和 Murmur3

一個好的雜湊演算法應該同時兼顧到以下兩點 :

  • 不依賴於雜湊表的長度, 產生的雜湊值幾乎不會產生衝突, 即對不同的元素產生的雜湊值很少相同, 即使對於相似元素也是如此
  • 雜湊值的計算速度

對於不同的元素, 若雜湊函數同時產生同樣的雜湊位置, 此時就發生了衝突. 因為一個桶只能存取一個元素. 但是, 只要對應的桶足夠大, 那麼可以將產生相同雜湊值的元素全部裝下, 那麼就不會出現太大問題, 只是效率上稍有損失. 但是實際上, 這樣理想的桶很可能不存在, 即總會有元素無法裝下, 此時溢出就發生了. 因此, 結合好的雜湊函數或者雜湊演算法, 我們就要設計一個雜湊函式, 不但可以解決衝突問題, 還可以解決溢出問題

對於一個雜湊函式來說, 除非雜湊表可以無限容納, 否則就難免產生溢出問題. 我們自然希望所有元素都能夠影射到雜湊表中, 產生的衝突和溢出的平均數量最少 :

  • 不均勻雜湊 : 假設某個雜湊表中存在 b 個桶, 其中 b > 1. 桶的範圍為 [0, b - 1]. 對於所有的元素 k, 都有 f(k) = i\ (i \in [0, b - 1]), 則雜湊函數 f 就不是一個均勻的雜湊函數. 因為它將所有的元素都影射入第 i 個桶中. 這樣的雜湊函數會使得我們設計的雜湊函式的衝突和溢出問題最大化
  • 均勻雜湊 : 函數 f(k) = k \mod b 對範圍 [0, r] 內的元素是均勻雜湊函數, 若且唯若對於一般的 r > 1b > 1, 部分桶中有 \left \lfloor \frac {r}{b} \right \rfloor 個元素, 部分桶中有 \left \lceil \frac {r}{b} \right \rceil 個元素. 其中, r 為正整數

如果要從元素範圍內均勻地選擇一組元素, 那麼就要用均勻雜湊函數. 但是在實際應用中, 理論上表現良好的雜湊函數可能不如人意. 因為實際應用中, 對於元素可能有多個要求或者關聯性. 例如有時候, 元素為整數, 我們希望有些性質的數佔優勢 (例如奇數佔優勢), 而不是均勻地. 因此, 有的雜湊函數表現好一些, 有一些雜湊函數表現不太好. 對於雜湊函數 f(k) = k \mod DD 的選擇問題, 有時候會產生比較好的雜湊函數, 有些時候不是. 但是只要 D > 1, 對於所有的 D, 均會產生均勻雜湊函數

假設 D 是偶數 : 當 k 為偶數的時候, f(k) 的值為偶數; 當 k 為奇數的時候, f(k) 的值為奇數. 如果你希望以偶數為主, 則大部分元素都會被影射到桶的序號為偶數的桶中. 此時, 選擇的 D 為奇數的話, 那麼得到的就不是令人滿意的雜湊函數. 反之亦然

不過, 當 D 比較小, 例如 D \in \left \{ 3, 5, 7 \right \}, 也不會產生好的雜湊函數. 考慮下列程式碼 :

#include <iostream>
#include <random>

using namespace std;
int main(int argc, char *argv[]) {
    random_device d {};
    uniform_int_distribution<> u;
    default_random_engine e(d());
    int zero {}, one {}, two {};
    for(auto i {0}; i < 20; ++i) {
        auto r {u(e)};
        switch(r % 3) {
            case 0:
                ++zero;
                break;
            case 1:
                ++one;
                break;
            case 2:
                ++two;
                break;
        }
        cout << r << "\t" << r % 3 << endl;     //D = 3
    }
    cout << zero << "\t" << one << "\t" << two << endl;
}
Output :

1486818898  1
2022942176 2
1202641839 0
702090123  0
1998379640 2
1887318869 2
2007192405 0
2114762568 0
1541207256 0
10752824   2
142911552  0
1095426363 0
2027232563 2
797487729  0
1293174916 1
955396019  2
1278739077 0
1068892341 0
351169558  1
1426648821 0
11 3  6

統計之後, 產生餘數為 0 的數總共有 11 個; 產生餘數為 1 的數共有 3 個; 產生餘數為 2 的數總共有 6 個. 顯然偶數佔優勢. 因此, 一般情況下, D = 3 時產生的雜湊函數不會令人滿意. 當要雜湊的元素數量增多的時候, 那些小的 D 同樣有這樣的問題. 因此, 要使得利用除留餘數這個方法產生一個較好的雜湊函數, D 應該是一個既不是偶數又不能被小奇數整除的數. 理想的 D 是一個素數. 當你不能用心算找到一個接近雜湊表的素數時, 應該儘量選擇不能被 219 之間的數整除的 D. 對於非整形的值, 可以將其轉型為整數之後或者影射為整數之後再使用雜湊函數即可

對於一個雜湊函數, f(k) 的值是雜湊位置. 若這個位置已經存在了一個元素, 此時產生了一個衝突, 而解決這個衝突成為了目前主要討論的一個問題 :

  • 開放定位法 : g(k, i) = f(k) + i. 其中, g 是用於解決衝突的函數, f 是雜湊函數, i 是一個變數, 表示衝突次數, 滿足

    i = i(k)

    上述影射表示在 f(k) 的值之後, 下一個可用的空位. 若位置 f(k) 沒有被佔用, 則 i = 0; 若 f(k) 的位置已經有元素佔用, 且之後的 m 個位置也都被佔用, 則 i = m + 1

  • 非線性開放定位法 : 對於 g(k, i) = f(k) + i, 且 i 滿足

    i = i^{2}(k)

    甚至

    i = i^{3}(k)

    我們稱這樣的開放定位法是非線性的. 當 i = i^{2}(k) 時, 若發生衝突, 則將元素放入與 f(k) 值的雜湊位置間隔 i 的位置上 (若為空)

  • 偽隨機開放定位法 : g(k) = f(k) + r(k). 其中, r(k) = \begin {cases} 0 & {\text {不發生衝突}} \\ \text {random number} & {發生衝突} \end {cases}
  • 連結串列法 : 將衝突的元素放入一個連結串列中, 並且雜湊表本身是一個連結串列的陣列 :

  • 多次雜湊法 : f_{n}(k) = f(f_{n - 1}(k)). 定義 f_{0}(k) = f(k). 多次雜湊法是當衝突發生時, 對回傳的雜湊位置放入雜湊函數中, 並且一直重複這樣的步驟, 直到找到一個雜湊位置中沒有被元素佔用為止
  • 公共溢出區域法 : 建立公共溢出區域, 將發生衝突的物件放入其中

這些方法都會使得雜湊表的插入, 刪除和搜尋的時間複雜度增加, 但是至少不可能到達 O(n) 級別. 準確地說, 即我們開頭就提到的時間複雜度為 \Omega(1). 對於某一元素 k, 若 f(k) 的值對應的雜湊位置內的元素並不與 k 相等, 那麼就說明此處曾經發生過衝突. 對於開放定位法而言, 需要再移動 i 個位置才能被找到; 對於連結串列法, 需要不斷地向下搜尋; 對於多次雜湊法, 還需要進行多次雜湊; 對於公共溢出區域法, 那麼就進入公共溢出區域法

若要從雜湊表中刪除一個元素, 那麼就要考慮曾經衝突過的物件向前移動. 以開放定位法為例, 若位置 p 之後有三個元素曾經衝突, 則要將這三個元素向前移動. 否則, 再次搜尋的時候, 如果找到這個位置為空, 就會認為雜湊表不存在這個元素而停止搜尋. 對於多次雜湊法來說, 第 p_{n} 個位置滿足

p_{n} = f_{n}(k)

當某一個元素被移除的時候, 則 p_{n} 應該更新為

p_{n} = p_{n - 1} = f_{n - 1}(k)

因此, 我們更喜歡連結串列法. 在 C++ 標準樣板程式庫中的 unordered 系列容器都是以連結串列為低層的雜湊表

b 為雜湊表的長度, n 為雜湊表中元素的數量, 我們稱 \alpha = \frac {n}{b} 為雜湊表的載荷因素. 令 U_{n}S_{n} 分別表示在雜湊表中一次成功搜尋所需要探尋的桶數量和一次不成功搜尋所需要探尋的桶數量. 為了證明接下來的結論, 我們引入機率論中的一個引理 :

引理 1. 設事件 A 發生的機率為 p\ (0 < p < 1). 為了使得事件 A 發生, 獨立試驗的期望次數為 \frac {1}{p}

:

設事件 A_{i} = \left \{ \text {第}\ i\ \text {次試驗時, 事件}\ A\ \text {才發生} \right \}. 則第一次試驗就發生事件 A 的機率為 p; 第二次試驗時才發生事件 A 表示第一次試驗不發生事件 A 的條件下第二次試驗發生事件 A, 機率為 p(1 - p); ...; 第 n 次試驗才發生事件 A 的機率為 (1 - p)^{n - 1}p

根據期望的定義, 有

\begin {aligned} E(n) &= \sum \limits_{i = 1}^{\infty}iP(A_{i}) \\ &= 1 \times p + 2 \times (1 - p)p + ... + n \times (1 - p)^{n - 1}p \end {aligned}

E_{n} = 1 \times p + 2 \times (1 - p)p + ... + n \times (1 - p)^{n - 1}p, 則有

E(n) = \lim \limits_{n \to \infty}E_{n}

(1 - p)E_{n} = p(1 - p) + 2(1 - p)^{2}p + ... + n(1 - p)^{n}p

E_{n} - (1 - p)E_{n} 可得

\begin {aligned} E_{n} - (1 - p)E_{n} &= E_{n} - E_{n} + pE_{n} = pE_{n} \\ &= p + 2(1 - p)p + n(1 - p)^{n - 1}p - \\ &\ \ \ \ \left ( p(1 - p) + 2(1 - p)^{2}p + ... + n(1 - p)^{n}p \right ) \\ &= p + (1 - p)p + (1 - p)^{2}p + ... + (1 - p)^{n - 1}p - n(1 - p)^{n}p \end {aligned}

則有

\begin {aligned} A_{n} &= 1 + \underbrace {(1 - p) + (1 - p)^{2} + ... + (1 - p)^{n - 1}}_{\text {等比數列}} - n(1 - p)^{n} \\ &= 1 + (1 - p)\frac {1 - (1 - p)^{n - 1}}{1 - (1 - p)} + n(1 - p)^{n} \\ &= 1 + (1 - p)\frac {1 - (1 - p)^{n - 1}}{p} + n(1 - p)^{n} \\ &= 1 + \frac {1 - p - (1 - p)^{n}}{p} + n(1 - p)^{n} \\ &= 1 + \frac {1}{p} - 1 - \frac {(1 - p)^{n}}{p} + n(1 - p)^{n} \\ &= \frac {1}{p} - \frac {(1 - p)^{n}}{p} + n(1 - p)^{n} \end {aligned}

由於 0 < 1 - p < 1, 故

\lim \limits_{n \to \infty} \frac {(1 - p)^{n}}{p} = 0

\begin {aligned} \lim \limits_{n \to \infty}n(1 - p)^{n} &= \lim \limits_{n \to \infty}na^{n}\ (\text {令}\ a = 1 - p, 0 < a < 1) \\ &= \lim \limits_{n \to \infty}nb^{-n}\ (\text {令}\ b = \frac {1}{a}, b > 1) \\ &= \lim \limits_{n \to \infty}\frac {n}{b^{n}} = 0 \end {aligned}

因此, E(n) = \lim \limits_{n \to \infty}E_{n} = \frac {1}{p}, 即為了使得事件 A 發生, 獨立試驗的期望次數為 \frac {1}{p}

\blacksquare

引理 2. 設函數 f(x) 在區間 [a, b] 上可積. 將區間 [a, b] 平分為 n 份, 在區間 \left [a + \frac {i}{n}(b - a), a + \frac {i + 1}{n}(b - 1) \right ] 上取 f \left (a + \frac {i}{n}(b - a) \right ) 作為函數值. 根據定積分的定義, 有

\displaystyle {\int_{a}^{b}f(x)dx = \lim \limits_{n \to \infty}\sum \limits_{i = 1}^{n}f \left (a + \frac {i}{n}(b - a) \right )\frac {b - a}{n}}

定理 1. 對於偽隨機開放定位法, 有 U_{n} \doteq \frac {1}{1 - \alpha}, S_{n} \doteq -\frac {1}{\alpha} \ln {(1 - \alpha)}

:

當載荷因素為 \alpha 時, 雜湊表內某一位置存在元素的機率為 \alpha, 不存在元素的機率為 1 - \alpha. 使用某個獨立隨機序列進行搜尋, 一次失敗的試驗是找到一個空的桶. 根據引理 1, 期望的搜尋次數為 \frac {1}{1 - \alpha}, 即

U_{n} \doteq \frac {1}{1 - \alpha}

根據插入順序, 給雜湊表中的元素編號 : 1, 2, ..., n. 當插入第 i 個元素時, 首先通過一次不成功的搜尋找到一個空桶. 再將元素放入到桶中. 在插入第 i 個元素之前, 有

\alpha = \frac {i - 1}{b}

其中, b 是雜湊表長度. 由 U_{n} 可知, 在搜尋第 i 個桶時, 搜尋桶的期望次數為 \frac {1}{1 - \frac {i - 1}{b}}. 若每個元素都有相同機率被插入, 則

\begin {aligned} S_{n} &= \frac {1}{n}\sum \limits_{i = 1}^{n}\frac {1}{1 - \frac {i - 1}{b}} \\ &= \frac {1}{n}\sum \limits_{i = 0}^{n - 1}\frac {1}{1 - \frac {i}{b}} \\ &= \frac {1}{n} \left ( 1 + \sum \limits_{n = 1}^{n - 1}\frac {1}{1 - \frac {i}{b}} + \frac {1}{1 - \frac {n}{b}} - \frac {1}{1 - \frac {n}{b}} \right ) \\ &= \frac {1}{n} \left ( 1 + \sum \limits_{i = 1}^{n}\frac {1}{1 - \frac {i}{b}} - \frac {1}{1 - \frac {n}{b}} \right ) \end {aligned}

f(x) = \frac {1}{1 - \frac {x}{b}}. 將區間 [0, n] 內的 f(x) 平分為 n 份, 則每份區間的長度為 1, 並在區間 [i, i + 1] 上取 f(i) 作為函數值, 則根據引理 2, 當 n \to \infty 時, 有

\displaystyle {\lim \limits_{n \to \infty}\sum \limits_{i = 1}^{n}\frac {1}{1 - \frac {i}{b}} = \int_{0}^{n}\frac {1}{1 - \frac {x}{b}}dx = -\frac {b}{n}\ln {\left |-\frac {n}{b} + 1 \right |} = -\frac {b}{n}\ln {\left (1 - \frac {n}{b} \right )}}

綜上所述, 有

\begin {aligned} S_{n} &= \frac {1}{n} \left ( 1 + \sum \limits_{i = 1}^{n}\frac {1}{1 - \frac {i}{b}} - \frac {1}{1 - \frac {n}{b}} \right ) \\ &= \frac {1}{n} - \frac {1}{\alpha}\ln {(1 - \alpha)} - \frac {1}{1 + \frac {n}{b}} \end {aligned}

n 充分大時, 便有 S_{n} \doteq -\frac {1}{\alpha} \ln {(1 - \alpha)}

\blacksquare

定理 2. 對於非線性二次開放定位法, 有 U_{n} \doteq \frac {1}{1 - \alpha}, S_{n} \doteq -\frac {1}{\alpha} \ln {(1 - \alpha)}

定理 3. 對於多次雜湊法, 有 U_{n} \doteq \frac {1}{1 - \alpha}, S_{n} \doteq -\frac {1}{\alpha} \ln {(1 - \alpha)}

定理 4. 對於放開定位法, 有 U_{n} \doteq \frac {1}{2}\left ( 1 + \frac {1}{(1 - \alpha)^{2}} \right ), S_{n} \doteq \frac {1}{2}\left ( 1 + \frac {1}{(1 - \alpha)} \right )

定理 4. 對於放開定位法和 0 < \alpha < 1, 有 U_{n} \doteq \frac {1}{1 - \alpha}, S_{n} \doteq -\frac {1}{\alpha} \ln {(1 - \alpha)}

定理 5. 對於連結串列法, 有 U_{n} \doteq \frac {\alpha(\alpha + 3)}{2(\alpha + 1)} \doteq \alpha + e^{-\alpha}, S_{n} \doteq 1 + \frac {\alpha}{2}

:

若雜湊表中某個連結串列有 i 個結點, 一次不成功的搜尋必定會檢查 1, 2, ..., i 個結點. 也就是說, 總共要進行 i + 1 次搜尋 (最後一個結點為 nullptr, 仍然要搜尋它). 若每種可能的機率都相同, 則一次不成功搜尋需要檢查的結點數為

\frac {1}{i + 1}(i + \sum \limits_{j = 1}^{j}j) = \frac {1}{i + 1} \left (i + \frac {i(i + 1)}{2} \right ) = \frac {i(i + 3)}{2(i + 1)}

其中, i \geq 1. 當 i = 0 時, 無需檢查結點. 假定連結串列的平均長度為

\alpha = \frac {n}{b}

其中, n 為雜湊表中持有的元素, b 為雜湊表長度. 當 \alpha \geq 1 時, 可以用 \alpha 來替代 i, 從而得到

U_{n} \doteq \frac {\alpha(\alpha + 3)}{2(\alpha + 1)} \doteq \alpha + e^{-\alpha}

\alpha < 1 時, 由於連結串列捏的平均長度為 \alpha, 搜尋次數不可能比結點多, 因此 U_{n} \leq \alpha

為了得到 S_{n}, 需要知道雜湊表中的 n 個標誌元素距離連結串列頭部結點的平均距離. 其中, 一個連結串列的標誌元素是連結串列中最大的元素, 之後所有插入連結串列中的元素都不會比它大. 為了計算距離, 不是一般性, 不妨假設各個元素在連結串列中是按照從小到大這樣的順序排列的. 當插入第 i 個標誌元素的時候, 其所在的連結串列的平均長度為 \frac {i - 1}{b}. 若插入的元素是標誌元素 (之後再插入連結串列的元素都不會比它更大), 那麼元素會在連結串列尾部插入, 因此需要檢查 1 + \frac {i - 1}{b}. 值得注意的是, 這個最大的元素插入之後, 它距離連結串列頭部結點的距離不會因為之後的插入而改變. 假定 n 個標誌元素中每一個被搜尋的機率都相同, 則有

S_{n} = \frac {1}{n}\sum \limits_{i = 1}^{n}\left (1 + \frac {i - 1}{b} \right ) = 1 + \frac {n - 1}{2b} \doteq 1 + \frac {\alpha}{2}

\blacksquare

結合這幾個定理, 就需要查看的桶的數量而言, 線性搜尋的性能並不如隨機搜尋. 但是我們一般不採用隨機搜尋, 因為

  • 亂數產生器產生一個亂數所需要的時間可能遠比搜尋時間要長
  • 隨機搜尋並非線性的, 存取時可能需要多次存取記憶體而非快取

現在還有最後一個問題, 就是對於雜湊函數 f(k) = k \mod D, 如何選取一個比較好的 D. 我們首先確定, 對於成功的搜尋和不成功的搜尋而言, 什麼樣的性能才可以可以接受的. 使用 U_{n}S_{n} 可以確定 \alpha 的最大值. 根據 n 的值 (或者是關於它的一個估計值 g = g(\alpha)) 和 \alpha 的計算值, 可以確定 b 的最小可接受的值

例題 1. 使用某一雜湊函數, 一次成功搜尋中平均搜尋的桶的數量為 U_{n}, 一次不成功搜尋中平均搜尋的桶的數量為 S_{n}. 雜湊表可容納 b 個元素, 要求 U_{n} \leq m, S_{n} \leq n

:

U_{n} 的公式可得 \alpha \leq \alpha_{1}, 由 S_{n} 的公式可以得到 \alpha \leq \alpha_{2}. 由此, \alpha \leq \min \left \{ \alpha_{1}, \alpha_{2}\right \}. b 的最小值為 \left \lceil \frac {b}{\alpha} \right \rceil. 再考慮 b 是否可以被 3, 57 等的這樣的小奇數整除. 若能, 那麼就適當地加大 b, 然後取 D = b 就得到了一個合適的 D

\blacksquare

另一種計算 D 的方式是根據雜湊表的可用空間的最大值來動態地確定 b 的最大值. 再取 D 為不大於 b 的最大整數, 而且要麼是素數, 要麼不能被 20 以內的數整除

資料結構 hash_table : GitHub 點擊直達

資料結構 hash function : GitHub 點擊直達