一、散列表（哈希表）#
1. 概念引出#
編譯處理中對變量的管理：動態查找問題
- 利用查找樹進行？—— 兩個變量名（字符串）比較效率不高
- 將字符串轉換為數字，再處理？—— 即為散列查找的思想
已知的幾種查找方法： - 順序查找 O (N)
- 二分查找（靜態查找） O (log~2~N)
- 二叉搜索樹 O (h) h 為二叉查找樹的高度
- 平衡二叉樹 O (log~2~N)
問題：如何快速搜索到需要的關鍵詞？若關鍵詞不方便比較怎麼辦？#
查找的本質： 已知對象找位置
- 有序的安排對象：全序（完全有序，eg: 二分搜索）、半序（某些關鍵詞之間存在次序，eg: 查找樹）
- 直接 “算出” 對象位置：散列
散列基本工作#
- 計算位置：構造散列函數確定關鍵詞存儲位置
- 解決衝突：應用某種策略解決多個關鍵詞位置相同的問題
時間 复杂度#
時間複雜度幾乎是常量：O (1)，即查找時間與問題規模無關！
2. 散列查找#
（1）基本思想#
- 以關鍵字key為自變量，通過一個確定的函數 h （散列函數），計算出對應的函數值 h (key)，作為數據對象的存儲地址
- 可能不同的關鍵字會映射到同一個散列地址上，即 h (key~i~) = h (key~j~) (當 key~i~ ≠ key~j~)，稱為 “衝突 (Collision)” 。—— 需要某種衝突解決策略
不衝突的情況下，查找只需要根據散列函數算出地址查找
裝填因子#
裝填因子（Loading Factor）：設散列表空間大小為 m，填入表中元素個數為 n，則稱 α = n /m 為散列表的裝填因子
- 如上圖中的α = 11 / 17 ≈ 0.65
如果沒有溢出 則 T~ 查詢～= T~ 插入～= T~ 刪除～= O (1)
再散列#
- 當散列表元素過多（即裝填因子 α 過大）時，查找效率會下降
- 實用最大裝填因子一般取0.5 ≤ α ≤ 0.85
- 解決辦法是加倍擴大散列表，該過程叫做 “再散列(Rehashing)”
（2）散列函數的構造#
兩個因素#
一個 “好” 的散列函數一般應考慮以下兩個因素：
- 計算簡單，以便提高轉換速度
- 關鍵詞對應的地址空間分布均勻，以儘量減少衝突。
數字關鍵詞的散列函數構造#
① 直接定址法#
取關鍵詞的某個線性函數值為散列地址，即h(key) = a ×key + b (a、b 為常數)
② 除留餘數法（常用）#
散列函數為：h(key) = key mod p
eg：h(key) = key %17
一般為了盡可能使關鍵詞對應的地址空間分布均勻，p 取素數
③ 數字分析法#
通過分析數字關鍵字在各位上的變化情況，取比較隨機的位作為散列地址
④ 折疊法#
把關鍵詞分割成位數相同的幾個部分，然後疊加
⑤ 平方取中法#
字符關鍵詞的散列函數構造#
簡單的散列函數 ——ASCII 碼加合法#
對字符型關鍵詞 key 定義散列函數如下：h(key) = (Σkey[i]) mod TableSize
衝突嚴重！！
簡單的改進 —— 前 3 個字符移位法#
h(key) = (key[0] × 27^2^ + key[1] ×27 + key[2]) mod TableSize
仍然衝突、空間浪費
好的散列函數 —— 移位法#
設計關鍵詞的所有 n 個字符，且分布的很好
h(key) = ($\begin{matrix} \sum_{i=0}^{n-1}key[n-i-1] \times32^i \end{matrix}$) mod TableSize
代碼如下
typedef string DataType;//數據的類型
typedef int Index;//散列後的下標
//返回經散列函數計算後的下標
Index Hash(string Key, int TableSize) {
unsigned int h = 0; //散列函數值，初始化為0
int len = Key.length();
for(int i = 0; i < len; ++i)
h = (h << 5) + Key[i];
return h % TableSize;
}
（3）散列查找的衝突處理#
常用處理衝突的思路如下
- 換個位置 ——開放定址法
- 同一位置的衝突對象組織在一起 ——鏈地址法
開放定址法#
開放定址法 (Open Addressing)，一旦產生了衝突（該位置已有其他元素），則按某種規則去尋找另一空地址。其優點是散列表是一個數組，存儲效率高，隨機查找，缺點是散列表有 “聚集” 現象。在開放地址散列法中刪除操作需要很小心，只能 “懶惰刪除”，即需要增加一個刪除標記而不是真正的刪除，以便查找時不會 “斷鏈”。其空間可以在下次插入時重用。
- 若發生了第 i 次衝突，試探的下一個地址將增加 d~i~，基本公式是：h~i~(key) = (h(key) + d~i~) mode TableSize(1 ≤ i < TableSize)
- d~i~ 為多少決定了不同的解決衝突方案：線性探測 (d~i~ = i)、平方探測 (d~i~ = ± i^2^)、雙散列 (d~i~ = i*h~2~(key))。
① 線性探測法#
以增量序列 1，2，……，（TableSize - 1）循環試探下一個存儲地址。
② 平方探測法（二次探測）#
以增量序列 1^2^，-1^2^，2^2^，-2^2^，……，q^2^，-q^2^ 且 q ≤ | TableSize/2 | 循環試探下一個存儲地址。
平方探測是否能找得到所有空間？有定理如下：
- 如果散列表長度 TableSize 是某個4k+3（k 是正整數）形式的素數時，平方探測法就可以探查到整個散列表空間
//查找Key元素,這裡採用平方探測法處理衝突
Index Find(ptrHash H, DataType Key) {
Index nowp, newp;
int Cnum = 0;//記錄衝突次數
newp = nowp = Hash(Key, H->TableSize);
//若該位置的單元非空且不是要找的元素時發生衝突
while(H->Units[newp].flag != Empty && H->Units[newp].data != Key) {
++Cnum;//衝突增加一次
if(++Cnum % 2) {
newp = nowp + (Cnum+1)*(Cnum+1)/4;//增量為+i^2,i為(Cnum+1)/2
if(newp >= H->TableSize)
newp = newp % H->TableSize;
} else {
newp = nowp - Cnum*Cnum/4;//增量為-i^2,i為Cnum/2
while(newp < 0)
newp += H->TableSize;
}
}
return newp;//返回位置，該位置若為一個空單元的位置則表示找不到
}
③ 雙散列探測法#
d~i~ 為 i*h~2~(key)，h~2~(key) 是另一個散列函數，探測序列成 h~2~(key)，2h~2~(key)，3h~2~(key)……
- 對任意的 key，h~2~(key) ≠ 0！
- 探測序列還應該保證所有的散列存儲單元都應該能夠被探測到，選擇以下形式有良好的效果：h~2~(key) = p - (key mod p)
其中 p < TableSize，p、TableSize 都是素數
分離鏈接法#
分離鏈接法 (Separate Chaining)，將相應位置上衝突的所有關鍵詞存儲在一個單鏈表中。優點是關鍵字的刪除不需要 “懶惰刪除法” 從而沒有存儲垃圾，缺點是鏈表部分的存儲效率和查找效率都比較低。鏈表長度的不均勻會導致時間效率的嚴重下降
（4）散列查找的操作集（代碼）#
這裡給出字符串的散列查找，Hash 函數採用移位法，解決衝突採用開放定址法中的平方探測法，其他的在其基礎上更改即可
定義#
const int MaxSize = 100000;
typedef int Index;//散列後的下標
typedef string DataType;//散列單元中存放的元素類型
//散列單元狀態類型，分別對應：有合法元素、空單元、有已刪除元素
typedef enum {Legitimate, Empty, Deleted} EntryType;
struct HashNode { //散列表單元類型
DataType data; //存放元素
EntryType flag; //單元狀態
};
struct HashTable { //散列表類型
int TableSize; //表長
HashNode *Units; //存放散列單元的數組
};
typedef HashTable *ptrHash;
獲取素數#
返回大於 N 且不超過 MaxSize 的最小素數，用於保證散列表的最大長度為素數，儘可能使關鍵詞對應的地址空間分布均勻
//返回大於N且不超過MaxSize的最小素數，用於保證散列表的最大長度為素數
int NextPrime(int N) {
int i, p = (N%2) ? N+2 : N+1;//從大於N的下一個奇數p開始
while(p <= MaxSize) {
for(i = (int)sqrt(p); i >= 2; i--)
if(!(p % i)) break;//不是素數
if(i == 2) break;//for正常結束，是素數
else p += 2;//試探下一個奇數
}
return p;
}
創建空表#
創建一個長度大於 TableSize 的空表。（確保長度為素數）
ptrHash CreateTable(int TableSize) {
ptrHash H;
int i;
H = new HashTable;
H->TableSize = NextPrime(TableSize);
H->Units = new HashNode[H->TableSize];
for(int i = 0; i < H->TableSize; ++i)
H->Units[i].flag = Empty;
return H;
}
Hash 計算#
返回經散列函數計算後的下標 這裡關鍵字數據類型為 string, 採用移位法散列
Index Hash(DataType Key, int TableSize) {
unsigned int h = 0; //散列函數值，初始化為0
string str = Key.str;
int len = str.length();
for(int i = 0; i < len; ++i)
h = (h << 5) + str[i];
return h % TableSize;
}
查找操作#
查找 Key 元素，這裡採用平方探測法處理衝突，返回位置下標，該位置若為一個空單元的位置則表示找不到
Index Find(ptrHash H, DataType Key) {
Index nowp, newp;
int Cnum = 0;//記錄衝突次數
newp = nowp = Hash(Key, H->TableSize);
//若該位置的單元非空且不是要找的元素時發生衝突
while(H->Units[newp].flag != Empty && H->Units[newp].data != Key) {
++Cnum;//衝突增加一次
if(++Cnum % 2) {
newp = nowp + (Cnum+1)*(Cnum+1)/4;//增量為+i^2,i為(Cnum+1)/2
if(newp >= H->TableSize)
newp = newp % H->TableSize;
} else {
newp = nowp - Cnum*Cnum/4;//增量為-i^2,i為Cnum/2
while(newp < 0)
newp += H->TableSize;
}
}
return newp;//返回位置，該位置若為一個空單元的位置則表示找不到
}
插入操作#
將 Key 插入到表中，返回插入成功或失敗，失敗則說明該鍵值已存在
bool Insert(ptrHash H, DataType Key) {
Index p = Find(H, Key);
if(H->Units[p].flag != Legitimate) {//該位置可插入元素
H->Units[p].flag = Legitimate;
H->Units[p].data = Key;
//其他操作
return true;
} else {//該鍵值已存在
//其他操作
return false;
}
}
（5）性能分析#
散列表的查找效率通過以下因素分析：
- 成功平均查找長度（ASLs）
- 不成功平均查找長度（ASLu）
以線性探測法中的例題為例分析如下這個散列表的性能
- 其ASLs為查找表中關鍵詞的平均查找比較次數（即其衝突次數加 1）
ASLs = （1+7+1+1+2+1+4+2+4）/ 9 = 23 / 9 ≈ 2.56 - 其ASLu為不在散列表中的關鍵詞的平均查找比較次數（不成功）
一般方法：將不在散列表中的關鍵詞分若干類，如按其 H (key) 值分類的話，此處的 H (key) = key mod 11，分 11 類分析，ASLu 如下
ASLu = （3+2+1+2+1+1+1+9+8+7+6）/ 11 = 41 / 11 ≈ 3.73
關鍵詞的比較次數，取決於產生衝突的多少，而影響產生衝突多少有以下三個因素
- 散列函數是否均勻
- 處理衝突的方法
- 散列表的裝填因子 α
不同衝突處理方法和裝填因子對於效率的影響如下
① 線性探測法的查找性能#
② 平方探測法和雙散列探測法的查找性能#
當裝填因子 α<0.5 時，各種探測法的期望探測次數都不大，也比較接近，隨著 α 的增大，線性探測法的期望探測次數增加較快，不成功查找和插入操作的期望探測次數要比成功查找的期望探測次數要大。所以，合理的最大裝入因子應該不超過 0.85
③ 分離鏈接法的查找性能#
總結#
- 選擇合適的 h (key) 的話，散列法的查找效率期望是常數 O (1)，它幾乎與關鍵字的空間的大小 n 無關！也適合於關鍵字直接比較計算量大的問題
- 它是以較小的 α為前提，因此，散列方法是一個以空間換時間的方法
- 散列方法的存儲對關鍵字是隨機的，不便於順序查找關鍵字，也不適合於範圍查找，或最大值最小值查找。