不用鏈接法，還有別的方法能處理碰撞嗎？捫心自問，我不敢問這個問題。鏈接法如此的自然、直接，以至于我不敢相信還有別的（甚至是更好的）方法。推動科技進步的人，永遠是那些敢于問出比外行更天真、更外行的問題，并且善于運用豐富的想象力找到新的可能性，而且有能力運用科學的方法實踐的人。
　　如果可以不用鏈表，把節省下來的鏈表的指針所占用的空間用作空槽，就可以減少碰撞的機會，提高查找速度。

使用開放尋址法處理碰撞

　　不用額外的鏈表，以及任何其它額外的數據結構，就只用一個數組，在發生碰撞的時候怎么辦呢？答案只能是，再找另一個空著的槽啦！這就是開放尋址法(open addressing)。但是這樣難道不是很不負責任的嗎？想象一下，有一趟對號入座的火車，假設它只有一節車廂，上來一位坐7號座位的旅客。過了一會兒，又上來一位旅客，他買到的是一張假票，也是7號座位，這時怎么辦呢？列車長想了想，讓拿假票的旅客去坐8號座位。過了一會兒，應該坐8號座位的旅客上來了，列車長對他說8號座位已經有人了，你去坐9號座位吧。哦？9號早就有人了？10號也有人了？那你去坐11號吧。可以想見，越到后來，當空座越來越少時，碰撞的幾率就越大，尋找空座愈發地費勁。但是，如果是火車的上座率只有50%或者更少的情況呢？也許真正坐8號座位的乘客永遠不會上車，那么讓拿假票的乘客坐8號座位就是一個很好的策略了。所以，這是一個空間換時間的游戲。玩好這個游戲的關鍵是，讓旅客分散地坐在車廂里。如何才能做到這一點呢？答案是，對于每位不同的旅客使用不同的探查序列。例如，對于旅客 A，探查座位 7，8，23，56……直到找到一個空位；對于旅客B，探查座位 25，66，77，1，3……直到找到一個空位。如果有 m 個座位，每位旅客可以使用 <0, 1, 2, ..., m-1> 的 m! 個排列中的一個。顯而易見，最好減少兩個旅客使用相同的探查序列的情況。也就是說，希望把每位旅客盡量分散地映射到 m! 種探查序列上。換句話說，理想狀態下，如果能夠讓每個上車的旅客，使用 m! 個探查序列中的任意一個的可能性是相同的，我們就說實現了一致散列。（這里沒有用“隨機”這個詞兒，因為實際是不可能隨機取一個探查序列的，因為在查找這名旅客時還要使用相同的探查序列）。
　　真正的一致散列是難以實現的，實踐中，常常采用它的一些近似方法。常用的產生探查序列的方法有：線性探查，二次探查，以及雙重探查。這些方法都不能實現一致散列，因為它們能產生的不同探查序列數都不超過 m² 個（一致散列要求有 m! 個探查序列）。在這三種方法中，雙重散列能產生的探查序列數最多，因而能給出最好的結果（注：.net framework 的 HashTable 就是使用的雙重散列法）。
　　在上一篇中，我們實現了一個函數 h(k)，它的任務是把數值 k 映射為一個數組（盡量分散）的地址。這次，我們使用開發尋找法，需要實現一個函數 h(k, i)，它的任務是把數值 k 映射為一個地址序列，序列的第一個地址是 h(k, 0)，第二個地址是 h(k, 1)……序列中的每個地址都要盡可能的分散。

線性探查

　　有這樣一個可以用 10 個槽保存 0～int.MatValue （但是不能處理碰撞）的 IntSet1:

public class IntSet1 {private object[] _values = new object[10];private int H(int value){return value % 10;}public void Add(int item){_values[H(item)] = item;}public void Remove(int item){_values[H(item)] = null;}public bool Contains(int item){if (_values[H(item)] == null)return false;elsereturn (int)_values[H(item)] == item;} }

現在想用開放尋址法處理碰撞，該怎么改造它？最簡單的方法是，如果發現 values[8] 已經被占用了，就看看 values[9] 是否空著，如果 values[9] 也被占用了，就看看 values[0] 是不是還空著。完整的描述是，先使用 H() 函數獲取 k 的第一個地址，如果這個地址已被占用，就探查下一個緊挨著的地址，如果還是不能用，就探查下一個緊挨著的地址，如果到達了數組的末尾，就卷繞到數組的開頭，如果探查了 m 次還是沒有找到空槽，就說明數組已經滿了，這就是線性探查（linear probing）。實現代碼是：

public class IntSet2 {private object[] _values = new object[10];private int H(int value){return value % 10;}private int LH(int value, int i){return (H(value) + i) % 10;}public void Add(int item){int i = 0; // 已經探查過的槽的數量do{int j = LH(item, i); // 想要探查的地址if (_values[j] == null){_values[j] = item;return;}else{i += 1;} } while (i <= 10);throw new Exception("集合溢出");}public bool Contains(int item){int i = 0; // 已經探查過的槽的數量int j = 0; // 想要探查的地址do{j = LH(item, i);if (_values[j] == null)return false;if ((int)_values[j] == item)return true;elsei += 1;} while (i <= 10);return false;}public void Remove(int item){// 有點不太好辦} }

　　在 Add() 函數中，先探查 LH(value, 0)，它等于 H(value)，如果發生了碰撞，就繼續探查 LH(value, 1)，它是 H(value) 的下一個地址，LH() 里面的 “... % 10”的意思是數組最后一個槽的下一個槽是第一個槽的意思。在 Contains() 函數里，使用和 Add() 函數一樣的探查序列，如果找到了 item 返回 true；如果遇到了 null，說明 item 不在數組中。
　　比較麻煩的是 Remove() 函數。不能簡單地把要刪除的槽設為 null，那樣會導致 Contains() 出錯。舉個例子，如果依次把 3，13，23 添加到 IntSet2 中，會執行 _values[3] = 3，_values[4] = 13，_values[5] = 23。然后，Remove(13) 執行 _values[4] = null。這時，再調用 Contains(23)，會依次檢查 _values[3]、_values[4]、_values[5] 直到找到 23 或遇到 null，由于 _values[4] 已經被設為 null 了，所以 Contains(23) 會返回 false。有一個解決此問題的方法是，在 Remove(23) 時把 _values[4] 設為一個特殊的值（例如 -1）而不是 null。這樣 Contains(23) 就不會在 _values[4] 那里因為遇到 null 而返回錯誤的 false 了。并且在 Add() 里，遇到 null 或 -1 都視為空槽，修改之后的代碼如下：

public class IntSet2 {private object[] _values = new object[10];private readonly int DELETED = -1;private int H(int value){return value % 10;}private int LH(int value, int i){return (H(value) + i) % 10;}public void Add(int item){int i = 0; // 已經探查過的槽的數量do{int j = LH(item, i); // 想要探查的地址if (_values[j] == null || (int)_values[j] == DELETED){_values[j] = item;return;}else{i += 1;} } while (i <= 10);throw new Exception("集合溢出");}public bool Contains(int item){int i = 0; // 已經探查過的槽的數量int j = 0; // 想要探查的地址do{j = LH(item, i);if (_values[j] == null)return false;if ((int)_values[j] == item)return true;elsei += 1;} while (i <= 10);return false;}public void Remove(int item){int i = 0; // 已經探查過的槽的數量int j = 0; // 想要探查的地址do{j = LH(item, i);if (_values[j] == null)return;if ((int)_values[j] == item){_values[j] = DELETED;return;}else{i += 1;}} while (i <= 10);} }

　　但是這種實現 Remove() 函數的方法有個很大的問題。想象一下，如果依次添加 0、1、2、3、4、5、6、7、8、9，然后再 Remove 0、1、2、3、4、5、6、7、8，這時再調用 Contains(0)，此函數會依次檢查 _values[0]、_values[1]..._values[9]，這是完全無法接受的！這個問題先放一放，我們在下一篇還會繼續討論解決這個問題的方法。
　　線性探查法雖然比較容易實現，但是它有一個叫做一次群集（primary clustering）的問題。就像本文開篇所討論的，如果 7、8、9 號座位已被占用，下一個上車的旅客，無論他的票是7號、8號還是9號，都會被安排去坐10號；下一個上車的旅客，無論他的票是7號、8號、9號還是10號，都會被安排去坐11號……如果有 i 個連續被占用的槽，下一個空槽被占用的概率就會是 (i + 1)/m，就像血栓一樣，一旦堵住，就會越堵越厲害。這樣，使用線性探查法，很容易產生一長串連續被占用的槽，導致 Contains() 函數速度變慢。
　　對于線性探查法，由于初始位置 LH(k, 0) = H(k) 確定了整個探查序列，所以只有 m 種不同的探查序列。

二次探查

　　可以在發生碰撞時，不像線性探查那樣探查下一個緊挨著的槽，而是多偏移一些，以此緩解一次群集的問題。二次探查（quadratic probing）讓這個偏移量依賴 i 的平方：
　　h(k, i) = (h'(k) + c1i + c2i²) mod m
其中，c1 和 c2 是不為0的常數。例如，如果取 c1 = c2 = 1，二次探查的散列函數為：

private int QH(int value, int i) {return (H(value) + i + i * i) % 10; }

對于數值 7，QH() 給出的探查序列是 7、9、3、9……由于初始位置 QH(k, 0) = H(k) 確定了整個探查序列，所以二次探查同樣只有 m 種不同的探查序列。通過讓下一個探查位置以 i 的平方偏移，不容易像線性探查那樣讓被占用的槽連成一片。但是，由于只要探查的初始位置相同，探查序列就會完全相同，所以會連成一小片、一小片的，這一性質導致一種程度較輕的群集現象，稱為二次群集（secondary clusering）。

雙重散列

　　造成線性探查法和二次探查法的群集現象的罪魁禍首是一旦初始探查位置相同，整個探查序列就相同。這樣，一旦出現碰撞，事情就會變得更糟。是什么造成一旦初始探查位置相同，整個探查序列就相同呢？是因為線性探查法和二次探查法都是讓后續的探查位置基于初始探查位置（即 H(k)）向后偏移幾個位置，而這個偏移量，不管是線性的還是二次的，都僅僅是 i 的函數，但是只有 k 是不同的對不對？所以必須想辦法讓偏移量是 k?的函數才行。以線性探查為例，要想辦法讓 LH(k, i) 是 k 和 i 的函數，而不是 H(k) 和 i 的函數。說干就干，我們試著把線性探查
H(k) = k % 10
LH(k, i) = (H(k) + i) % 10
改造一下，先試試把 k 乘到 i 上面去，即
H(k) = k % 10
LH(k, i) = (H(k) + i * k) % 10
這有效果嗎？很不幸，
LH(k, i) = (H(k) + i * k) % 10
?????????? = (H(k) + i * (k%10) % 10
?????????? = (H(k) + i * H(k)) % 10
?????????? = (H(k) * (1 + i)) % 10
結果 LH(k, i) 還是 H(k) 和 i 的函數。
再試試把 k 加到 i 上，即
H(k) = k % 10
LH(k, i) = (H(k) + i?+ k) % 10
這個怎么樣？
LH(k, i) = (H(k) + i?+ k) % 10
?????????? = (H(k) + i + k%10) % 10
?????????? = (H(k) + i + H(k)) % 10
?????????? = (2*H(k) + i) % 10
太不幸了，LH(k) 仍然是 H(k) 和 i 的函數。好像怎么折騰都不行，除非把 H(K) 變成乘法散列法，或者使用雙重散列(double hashing)法：
h(k, i) = (h1(k) + i*h2(k)) mod m
其中 h1(k) 和 h2(k) 是兩個不同的散列函數。例如可以讓
h1(k) = k mod 13
h2(k) = k mod 11
h(k, i) = (h1(k) + i*h2(k)) mod 10
這樣，h(7, i) 產生的探查序列是 7、4、1、8、5……
h(20, i) 產生的探查序列是 7、6、5、4、3……
這回終于達到了初始探查位置相同，但是后續探查位置不同的目標。
　　h2(k) 的設計很有講究，搞不好會無法探查到每個空槽。以剛剛實現的?h(k, i) 為例，h(6, i) 的探查序列是“6、2、8、4、0、6、2、8、4、0”，如果恰巧數組中的“6、2、8、4、0”這幾個位置都被占用了，將會導致程序在還有空槽的狀態下拋出“集合溢出”的異常。要避免這種情況，要求 h2(k) 與 m 必須互質。可以看一看如果 h2(k) 與 m 不是互質的話，為什么會有無法探查數組的所有的槽的后果。例如 h2(6)=6 與 10 有公約數2，把它們代入 h(k, i)：
h(6, i) = (h1(6) + i * h2(6)) mod 10
????????? = (6 + i * 6) mod 10
????????? = (6 + (i * 6) mod 10) mod 10
????????? = (6 + 2*((i*6) mod 5)) mod 10
由于 (i*6) mod 5) 只有 5 個不同的值，所以 h(6, i) 也只有 5 個值。而 h(16, i) = (3 + 5*((i*5) mod 2)) mod?10 只有2個值，真是太糟糕了。
　　要想讓 h2(k) 與 m 互質，有2種方法。一種方法是讓 m 為 2 的冪，并且設計一個總是產生奇數的 h2(k)，利用的是奇數和 2 的 m 次冪總是互質的原理。另一種方法是讓 m 為質數，并設計一個總是產生比 m 小的正整數的 h2(k)。可以這么實現后一種方法：首先使用上一篇實現的 GetPrime() 函數取得一個合適的質數作為 m，然后讓
h1(k) = k mod m
h2(k) = 1 + (k mod (m-1))
在 h2(k) 里之所以要把 (k mod (m-1))?加上個 1 是為了讓 h2(k) 永不為0。因為 h2(k) 為 0 會讓 i 不起作用，一旦正巧 h1(k) 產生碰撞就無法取得下一個空槽了。
這是一份完整的示例代碼，我們將會在下一篇繼續完善它：

public class IntSet4 {private object[] _values;private readonly int DELETED = -1;public IntSet4(int capacity){int size = GetPrime(capacity);_values = new object[size];}// 質數表private readonly int[] primes = {3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};// 判斷 candidate 是否是質數private bool IsPrime(int candidate){if ((candidate & 1) != 0) // 是奇數{int limit = (int)Math.Sqrt(candidate);for (int divisor = 3; divisor <= limit; divisor += 2) // divisor = 3、5、7...candidate的平方根{if ((candidate % divisor) == 0)return false;}return true;}return (candidate == 2); // 除了2，其它偶是全都不是質數}// 如果 min 是質數，返回 min；否則返回比 min 稍大的那個質數private int GetPrime(int min){// 從質數表中查找比 min 稍大的質數for (int i = 0; i < primes.Length; i++){int prime = primes[i];if (prime >= min) return prime;}// min 超過了質數表的范圍時，探查 min 之后的每一個奇數，直到發現下一個質數for (int i = (min | 1); i < Int32.MaxValue; i += 2){if (IsPrime(i))return i;}return min;}int H1(int value){return value % _values.Length;}int H2(int value){return 1 + (value % (_values.Length - 1));}int DH(int value, int i){return (H1(value) + i * H2(value)) % _values.Length;}public void Add(int item){int i = 0; // 已經探查過的槽的數量do{int j = DH(item, i); // 想要探查的地址if (_values[j] == null || (int)_values[j] == DELETED){_values[j] = item;return;}else{i += 1;}} while (i <= _values.Length);throw new Exception("集合溢出");}public bool Contains(int item){int i = 0; // 已經探查過的槽的數量int j = 0; // 想要探查的地址do{j = DH(item, i);if (_values[j] == null)return false;if ((int)_values[j] == item)return true;elsei += 1;} while (i <= _values.Length);return false;}public void Remove(int item){int i = 0; // 已經探查過的槽的數量int j = 0; // 想要探查的地址do{j = DH(item, i);if (_values[j] == null)return;if ((int)_values[j] == item){_values[j] = DELETED;return;}else{i += 1;}} while (i <= _values.Length);} }

　　除了鏈接法和開放尋址法，還有更好的方法嗎？人類永遠不會停止追問，本篇卻必須結束了。下一篇，我們將參考 .net framework 源代碼，討論實現散列表的一些重要的細節問題。

轉載于:https://www.cnblogs.com/1-2-3/archive/2010/10/12/hash-table-part2.html

總結

以上是生活随笔為你收集整理的白话算法(6) 散列表(Hash Table)从理论到实用（中）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。