摘要訊息 : 是否存在一個搜尋時間複雜度能夠突破對數時間複雜度底線, 接近常數時間的資料結構呢?
0. 前言
在向量 (《【資料結構】向量 (順序表)》) 中進行二分搜尋 (《【演算法】二分搜尋法 (Binary Search)》) 的時間複雜度為 \Theta(\log {n}). 在跳躍列表 (《【資料結構】跳躍列表》) 中進行跳躍搜尋的時間複雜度也為 \Theta(\log {n}). 那麼我們不禁要問, 是否能夠突破 \Theta(\log {n}) 的底線, 讓搜尋的時間為 \Theta(1) 呢? 或者起碼可以接近 \Theta(1).
更新紀錄 :
- 2022 年 6 月 7 日進行第一次更新和修正.
1. 雜湊函數
定義 1. 設函數 h(x) 有能力將訊息 x 中的信息進行壓縮固定並重新建立一個值 v, 即 \displaystyle {v = h(x)}. 我們稱 h(x) 為雜湊函數 (hash function), v 為雜湊值 (hash value).
定義 2. 設雜湊函數函數 h(x) 對訊息 x 產生了雜湊值 v, 若存在某個 h^{-1}, 使得對於任意 x 都有 \displaystyle {x = h^{-1}(v)} 成立, 那麼我們稱雜湊函數 h(x) 是可逆的 (invertible), 且雜湊值 v 具有可逆性 (reversibility); 否則, 我們稱雜湊函數 h(x) 是不可逆的 (irreversible), 且雜湊值 v 具有加密性 (encryption).
一般來說, 雜湊函數的用途取決於其可逆性和雜湊值. 如果一個雜湊函數是不可逆的, 那麼它通常會被用於密碼加密, 例如 安全雜湊演算法 (通常稱其為 SHA) 和 MD5. 如果一個雜湊函數是可逆的, 那麼它通常會被用於資料壓縮. 例如對於一個很長的訊息 x, 如果能夠使得其長度在可控範圍之內, 那麼同一時間內可傳送的訊息量就會提升.
2. 雜湊表
定義 3. 設向量集合 \boldsymbol {\alpha} = \left \{ (\alpha_{1}^{1}, \alpha_{2}^{1}, ..., \alpha_{m_{1}}^{1}), (\alpha_{1}^{2}, \alpha_{2}^{2}, ..., \alpha_{m_{2}}^{2}), ...(\alpha_{1}^{n}, \alpha_{2}^{n}, ..., \alpha_{m_{n}}^{n}) \right \} 中任一向量 (\alpha_{1}^{p}, \alpha_{2}^{p}, ..., \alpha_{m_{p}}^{p}) 中的元素 \alpha_{i}^{p} 對於某一雜湊函數 f(k) 都滿足 \displaystyle {p = f(\alpha_{i}^{p})}, 則稱向量集合 \boldsymbol {\alpha} 為雜湊表 (hash table), 稱 \boldsymbol {\alpha} 中的任一向量 (\alpha_{1}^{p}, \alpha_{2}^{p}, ..., \alpha_{m_{p}}^{p}) 為桶 (bucket). 其中, p = 1, 2, ..., n, m_{p} 為第 p 個桶中元素的數量.
2.1 一些簡單的雜湊函數
雜湊表的雜湊函數可以很複雜, 也可以很簡單, 我們先介紹幾個非常簡單的雜湊函數 :
- 線性函數 : f(k) = ak + b. 特別地, f(k) = k;
- 數值分析 : 設元素都以 r 為基數, 而雜湊表中可能出現的元素都已知. 那麼取元素中的部分數字作為雜湊位置;
- 平方取中 : 取元素值平方之後的中間數字作為雜湊位置. 通常, 在選定雜湊函數時不一定能夠知道元素的全部情況, 取其中的哪幾個數字也不一定合適. 而一個數平方之後的中間幾個數字和數值的每一個數字都相關. 由此使得隨機分佈的元素得到的雜湊值也是隨機分佈的. 取數字的數量和雜湊表的大小相關;
- 折疊 : 將元素分為長度相同的幾個部分 (最後一部分可以不同), 然後這幾個部分疊加並且捨棄進位, 最終得到的結果作為雜湊位置;
- 取亂數 : 不依賴於元素值本身, 而依賴於一個亂數產生器產生的亂數;
- 除留餘數 : f(k) = k \mod p. 其中, p 不應大於雜湊表的長度;
- 結合多種方法多種方法的雜湊函數;
- ...
理論上雜湊表是沒有長度限制的, 最好的雜湊函數實際上就是 f(k) = k. 在這種情況下, 對於任意元素 k, 我們可以在 \Theta(1) 的常數時間內在雜湊表中找到這個元素. 但是實際上大家知道, 電腦的記憶體是有限的, 所以雜湊表並不能夠無限長, 這也就導致 f(k) = k 這樣的雜湊函數並沒有廣泛地被應用雜湊表. 而如果雜湊表很大, 但是元素寥寥無幾, 這樣的雜湊函數很容易導致大量的空間浪費.
2.2 較好的雜湊函數
準確來說, 上面介紹的簡單雜湊函數實際上已經用不到了, 這些雜湊函數可能只是為了方便大家學習雜湊表. 對於應用於雜湊表的雜湊函數, 我們對其可逆性並沒有太大要求. 因為雜湊表一般是用於搜尋的資料結構, 給出要搜尋的元素 k, 然後在雜湊表中找到其位置, 因此要求可逆性並沒有太大意義.
現在使用的雜湊演算法都比較複雜 :
- cityhash;
- Murmur 系列;
- MD5;
- SHA 系列;
- ...
這些雜湊函數我們不在本文中介紹. 在 C++ 標準樣板程式庫中, 無序容器的低層都採用了雜湊表. 那麼對於雜湊函數, libc++ 採用了 cityhash 和 Murmur2. 我在個人項目 data_structure 中採用了 cityhash 和 Murmur3.
一個好的雜湊演算法應該同時兼顧到以下兩點 :
- 不依賴於雜湊表的長度, 產生的雜湊值幾乎不會產生衝突, 即對不同的元素產生的雜湊值很少相同, 即使對於相似元素也是如此;
- 雜湊值的計算效率不能太低;
對於任意給定的值 k, 一個較好的雜湊函數 f(k) 回傳其在雜湊表中的位置, 這個位置如果幾乎不存在重複的話, 那麼定義 3 中的 m_{i} 取值可能就比較小. 極端地, 如果運氣比較好的話, 任意 m_{i} = 1, 那麼雜湊表就退化成了一個向量. 如果雜湊表低層使用的就是向量來儲存的話, 那麼我們也能在 \Theta(1) 的時間複雜度內找到這個元素. 然而, 如果雜湊值的計算非常複雜, 從而導致在計算 f(k) 的時候就用去了大量時間, 那麼在雜湊表中搜尋的效能可能還不如二分搜尋或者跳躍列表.
2.3 衝突處理
對於兩個不同的值 x_{1} 和 x_{2}, 不論再好的雜湊函數 f(k), 都有可能滿足 \displaystyle {f(x_{1}) = f(x_{2})} 成立. 因此, 我們有必要對衝突的情況進行處理, 畢竟雜湊表的長度並不能無限長. 其實根據定義 3, 我們已經可以看出, 我們可以使用向量的集合作為雜湊表的低層資料結構. 這樣, 存在衝突的元素或者相同的元素就會被放入同一個向量中. 不過, 我們肯定希望所有元素都能夠影射到雜湊表中, 產生的衝突和溢出的平均數量最少.
定義 4. 假設雜湊函數 f(k) 使得雜湊表所有桶中的元素數量相差不超過 r 個, 那麼我們稱雜湊函數 f(k) 產生了均勻雜湊 (uniform hashing); 否則稱雜湊函數 f(k) 產生了不均勻雜湊 (non-uniform hashing). 其中, r 為非負整數.
出人意料的是, 我們並不是總是選擇產生均勻雜湊的雜湊函數, 因為理論上表現良好的雜湊函數在實際應用中可能不如人意. 因為實際應用中, 對於元素可能有多個要求或者關聯性. 例如有時候, 元素為整數, 我們希望具有某些性質的數佔優勢 (例如奇數佔優勢), 而不是均勻地都佔優勢. 因此, 有的雜湊函數表現好一些, 有一些雜湊函數表現不太好. 對於雜湊函數 f(k) = k \mod D 中 D 的選擇問題, 有時候會產生比較好的雜湊函數, 有些時候不是. 但是只要 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;
}
/* 輸出 :
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 是一個素數. 當你不能用心算找到一個接近雜湊表的素數時, 應該儘量選擇不能被 2 到 19 之間的數整除的 D. 對於非整形的值, 可以將其轉型為整數之後或者影射為整數之後再使用雜湊函數即可.
當然, 定義 4 中我們使用的向量集合的方法並不是總是被大家所選擇. 有些人可能喜歡直接使用向量作為資料結構的低層, 那麼我們就不能把兩個元素放入同一個位置. 在這種情況下, 我們需要另闢蹊徑 :
- 開放定位法 : g(k, i) = f(k) + i. 其中, g 是用於解決衝突的函數, f 是雜湊函數, i 是一個變數, 表示衝突次數, 滿足 \displaystyle {i = i(k)}. 上述影射表示在 f(k) 的值之後, 下一個可用的空位. 若位置 f(k) 沒有被佔用, 則 i = 0; 若 f(k) 的位置已經有元素佔用, 且之後的 m 個位置也都被佔用, 則 i = m + 1;
- 非線性開放定位法 : 對於 g(k, i) = f(k) + i, 且 i 滿足 \displaystyle {i = i^{2}(k)}甚至 \displaystyle {i = i^{3}(k)}. 我們稱這樣的開放定位法是非線性的. 當 i = i^{2}(k) 時, 若發生衝突, 則將元素放入與 f(k) 值的雜湊位置間隔 i 的位置上 (若為空). 當然, 非線性函數還有很多, 它們都可以作為 i;
- 偽隨機開放定位法 : \displaystyle {g(k) = f(k) + r(k)}. 其中, r(k) = \begin {cases} 0 & {\text {不發生衝突}} \\ \text {random number} & {\text {發生衝突}}; \end {cases}
- 向量集合法 : 將衝突的元素放入一個向量中, 並且雜湊表本身是一個向量的集合. 這便是定義 4 中最顯然的表達;
- 連結串列法 : 將衝突的元素放入一個連結串列中, 並且雜湊表本身是一個連結串列的集合. 這也是定義 4 中表達的一種, 只是向量改用了連結串列, 一般是前向連結串列 (《【資料結構】前向連結串列》);
- 多次雜湊法 : \displaystyle {f_{n}(k) = f(f_{n - 1}(k))}, 並定義 f_{0}(k) = f(k). 多次雜湊法是當衝突發生時, 對回傳的雜湊位置放入雜湊函數中, 並且一直重複這樣的步驟, 直到找到一個雜湊位置中沒有被元素佔用為止;
- 公共溢出區域法 : 建立公共溢出區域, 將發生衝突的物件放入其中;
- ...
雖然這些方法都會使得雜湊表的插入移除和搜尋操作的複雜度有升高, 但是一般我們都會選取適合且複雜度提升在可接受範圍內的方法. 其中, 最常用的就是連結串列法. C++ 標準樣板程式庫的無序容器一般低層就是使用連結串列法的雜湊表. 在程式設計中, 連結串列法的雜湊表一般表現為前向連結串列的陣列.
2.4 插入, 移除與搜尋
在雜湊表中插入, 移除和搜尋實際上是對雜湊表低層資料結構的插入, 移除和搜尋. 以連結串列法為例, 在低層資料結構為前向連結串列的雜湊表中插入, 移除和搜尋, 實際上我們只多出了一步, 就是確定去哪一個桶中插入, 移除或者搜尋. 然而, 這一步是取決於雜湊函數的. 一般來說, 對於任意值 k, 我們會去 f(k) 這個前向連結串列中去插入 k, 移除 k 或者搜尋該桶中是否存在元素 k.
不過這裡要特別指出, 針對向量作為低層資料結構並且使用開放定位法, 非線性開放定位法和偽隨機開放定位法的雜湊表, 移除元素的時候我們還需要考慮重新安排位置. 如果我們曾經在雜湊表中插入 k_{1} 和 k_{2}, 而對於雜湊函數 f(k), 我們有 \displaystyle {f(k_{1}) = f(k_{2})}. 設 k_{1} 先被安排到雜湊表中, k_{2} 在 k_{1} 之後. 這樣在向雜湊表中插入 k_{2} 的時候就會產生衝突. 一旦從雜湊表中移除 k_{1} 之後, f(k_{1}) = f(k_{2}) 對應的位置就不存在元素了. 如果不把 k_{2} 安排到 f(k_{1}) 這個位置, 那麼在搜尋 k_{2} 的時候就會得到雜湊表中沒有 k_{2} 這個結果. 顯然, 這個結果不正確. 開放定位法, 非線性開放定位法和偽隨機開放定位法的重新安排元素操作是比較簡單的. 對於多次雜湊法來說, 第 p_{n} 個位置滿足 \displaystyle {p_{n} = f_{n}(k)}, 當某一個元素被移除的時候, 則 p_{n} 應該更新為 \displaystyle {p_{n} = p_{n - 1} = f_{n - 1}(k)}. 這也就是為什麼我們更加喜歡連結串列法, 因為它可以省去這步操作節省時間.
3. 載荷因素
定義 5. 設 b 為雜湊表中桶的數量, n 為雜湊表中元素的數量, 我們稱 \alpha = \frac {n}{b} 為雜湊表的載荷因素 (load factor).
為了簡便起見, 我們令 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.
根據期望的定義 (《【機率論】初等機率論——隨機變數及其特徵》第 2 節), 有 \displaystyle {\begin {aligned} \mathop {\mathrm {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}} 記 \mathop {\mathrm {E}}_{n} = 1 \times p + 2 \times (1 - p)p + ... + n \times (1 - p)^{n - 1}p, 則有 \displaystyle {\mathop {\mathrm {E}}(n) = \lim \limits_{n \to \infty}\mathop {\mathrm {E}}_{n}}. 而 \displaystyle {(1 - p)\mathop {\mathrm {E}}_{n} = p(1 - p) + 2(1 - p)^{2}p + ... + n(1 - p)^{n}p} 令 \mathop {\mathrm {E}}_{n} - (1 - p)\mathop {\mathrm {E}}_{n} 可得 \displaystyle {\begin {aligned} \mathop {\mathrm {E}}_{n} - (1 - p)\mathop {\mathrm {E}}_{n} &= \mathop {\mathrm {E}}_{n} - \mathop {\mathrm {E}}_{n} + p\mathop {\mathrm {E}}_{n} = p\mathop {\mathrm {E}}_{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}} 則有 \displaystyle {\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, 故有 \displaystyle {\lim \limits_{n \to \infty} \frac {(1 - p)^{n}}{p} = 0}. 且 \displaystyle {\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} \left (\text {令 } b = \frac {1}{a}, b > 1 \right ) \\ &= \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}, 即 \displaystyle {U_{n} \doteq \frac {1}{1 - \alpha}}.
\square
根據插入順序, 給雜湊表中的元素編號 : 1, 2, ..., n. 當插入第 i 個元素時, 首先通過一次不成功的搜尋找到一個空桶. 再將元素放入到桶中. 在插入第 i 個元素之前, 有 \displaystyle {\alpha = \frac {i - 1}{b}}. 其中, b 是雜湊表中桶的數量. 由 U_{n} 可知, 在搜尋第 i 個桶時, 搜尋桶的期望次數為 \frac {1}{1 - \frac {i - 1}{b}}. 若每個元素都有相同機率被插入, 則 \displaystyle {\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 )}}. 於是有 \displaystyle {\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)}.
\square
\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 ).
定理 5. 對於放開定位法和 0 < \alpha < 1, 有 U_{n} \doteq \frac {1}{1 - \alpha} 和 S_{n} \doteq -\frac {1}{\alpha} \ln {(1 - \alpha)}.
定理 6. 對於連結串列法, 有 U_{n} \doteq \frac {\alpha(\alpha + 3)}{2(\alpha + 1)} \doteq \alpha + \mathrm {e}^{-\alpha} 和 S_{n} \doteq 1 + \frac {\alpha}{2}.
證明 :若雜湊表中某個連結串列有 i 個結點, 一次不成功的搜尋必定會檢查 1, 2, ..., i 個結點. 也就是說, 總共要進行 i + 1 次搜尋 (最後一個結點的指向型標記沒有指向任何節點, 即為 \infty, 但是仍然要搜尋它). 若每種可能的機率都相同, 則一次不成功搜尋需要檢查的結點數為 \displaystyle {\frac {1}{i + 1}\left ( i + \sum \limits_{j = 1}^{j}j \right ) = \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, 從而得到 \displaystyle {U_{n} \doteq \frac {\alpha(\alpha + 3)}{2(\alpha + 1)} \doteq \alpha + \mathrm {e}^{-\alpha}}. 當 \alpha < 1 時, 由於連結串列捏的平均長度為 \alpha, 搜尋次數不可能比結點多, 因此 U_{n} \leq \alpha
\square
為了得到 S_{n}, 需要知道雜湊表中的 n 個標誌元素距離連結串列頭部結點的平均距離. 其中, 一個連結串列的標誌元素是連結串列中最大的元素, 之後所有插入連結串列中的元素都不會比它大. 為了計算距離, 不是一般性, 不妨假設各個元素在連結串列中是按照從小到大這樣的順序排列的. 當插入第 i 個標誌元素的時候, 其所在的連結串列的平均長度為 \frac {i - 1}{b}. 若插入的元素是標誌元素 (之後再插入連結串列的元素都不會比它更大), 那麼元素會在連結串列尾部插入, 因此需要檢查 1 + \frac {i - 1}{b}. 值得注意的是, 這個最大的元素插入之後, 它距離連結串列頭部結點的距離不會因為之後的插入而改變. 假定 n 個標誌元素中每一個被搜尋的機率都相同, 則有 \displaystyle {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}}.
\square
\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, 5 和 7 等的這樣的小奇數整除. 若能, 那麼就適當地加大 b, 然後取 D = b 就得到了一個合適的 D.
\blacksquare
另一種計算 D 的方式是根據雜湊表的可用空間的最大值來動態地確定 b 的最大值. 再取 D 為不大於 b 的最大整數, 而且要麼是素數, 要麼不能被 20 以內的數整除.
4. 實作
我自己用 C++ 實作了雜湊表 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/hash_table.hpp, 大家可以參考後自行實作. 另外, 我也實作了一些現代比較常用的雜湊函數可供大家參考 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/hash.hpp.
自創文章, 原著 : Jonny. 如若閣下需要轉發, 在已經授權的情況下請註明本文出處 :
