題目要求

• 利用除留余數法為下列關鍵字集合的存儲設計hash函數，并畫出分別用開放尋址法和拉鏈法解決沖突得到的空間存儲狀態（散列因子取0.75）
  關鍵字集合：85，75，57，60，65，（你的8位學號相加值），98，74，89，12，5，46，97，13，69，52，92

實現思路

• 線性探測開放尋址法：
  1.調用哈希函數處理鍵得到哈希值，用值除以表的長度后取余數，從而確定表中的一個位置。
  2.如果該位置非空，則探測下一個位置，到達表最后一項時，折回表頭。
  3.如果回到原來哈希位置上時還未找到空閑位置，說明表已經填滿了。
  【附】注意發生沖突后的填入順序。

• 線性探測（形象表達法）：

簡單地講，也就是說，一間廁所，來了一個顧客就蹲其對應的位置，如果又來一個顧客，把廁所單間門拉開，一看里面有位童鞋正在用勁，那么怎么辦？很自然的，拉另一個單間的門，看看有人不，有的話就繼續找坑。當然了，一般來說，這個顧客不會按順序一個一個地拉廁所門，而是會去拉他認為有可能沒有被占用的單間的門，這可以通過聞味道，聽聲音來辨別，這就是尋址查找算法。如果找遍了所有廁所單間，看盡了所有人的光屁股，還是找不到坑，那么這座廁所就該擴容了。當然了，廁所擴容不會就只單單增加一個坑位，而是綜合考慮成本和保證不讓太多顧客拉到褲子里，會多增加幾個坑位，比如增加現有坑位的0.72倍。為什么是0.72呢，這是所長多年經營所得到的經驗值，為了讓自己的經驗發揚光大，需要出去演講，又不能太俗，總不能說“廁所坑位因子”吧，那就把把0.72叫做“裝填因子”或者“擴容因子”吧。目前很多產品使用0.72這個常數。

• 鏈式探查法（拉鏈法）：
  將哈希表看成是集合的表而不是各獨立單元的表。

每個單元中保存一個指針，指向與表中該位置相關的元素集合。

實現結果

• 線性探測法：（注意發生沖突后的填入順序，關鍵區域的填入順序已標出）
  

• 鏈式探查法：
  

關鍵問題

• 陳留余數法中如何確定H(key)中的key與哪個數取余？為什么？

• 解決方案 ：（查找資料）
  對于散列表長為 m 的散列函數公式為：f( key ) = key mod p ( p ≤ m )，若散列表表長為m，通常p為小于或等于表長（最好接近m)的最小質數或不包含小于20質因子的合數。這么做是因為如果 p 的約數越多，那么沖突的幾率就越大，這樣余數相同的數就會增加，從而使得散列表第一次處理數據時的利用率降低，從而增加了算法復雜度，以上是個人理解。下面舉一個查到的例子說明一下：

某散列表的長度為100，散列函數 H(k) = k%P ,則P通常情況下最好選擇哪個呢？
A、91 B、93 C、97 D、99

【解析】實踐證明，當P取小于哈希表長的最大質數時，產生的哈希函數較好。我選97，因為它是離長度值最近的最大質數。

• 至于為什么P應該這么選取，以下簡單的證明過程：（gcd表示最大公約數）

假設 p 是一個有較多約數的數，同時在數據中存在 key 滿足最大公約數 gcd(p,key) = d > 1 ，即有 p = a·d , key = b·d ,則有以下等式：key % p = key – p·[key/p] = key – p·[b/a] 。其中，[b / a]的取值范圍是不會超過[0，a-1]的正整數。也就是說，[b / a]的值只有a 種可能，而p 是一個預先確定的數。因此上式的值就只有a 種可能了（這顯然縮小了余數分布的范圍）。這樣，取 mod 運算之后的余數仍然在[0，p-1]內，但是它的取值僅限于等式可能取到的那些值，也就是說余數的分布變得不均勻了。容易看出，p 的約數越多，發生這種余數分布不均勻的情況就越頻繁，沖突的幾率越高。而素數的約數是最少的，因此我們選用大素數。所以 p應該最優選擇素數。

參考資料

• 哈希表線性探測開放尋址法與獨立表鏈地址法

• 開放尋址法解決散列沖突

• 哈希（Hash）相關