除留余數法介紹
除留余數法此方法為最常用的構造散列函數方法。對于散列表長為m的散列函數公式為：
f( key ) = key mod p ( p ≤ m )
mod是取模（求余數）的意思。事實上，這方法不僅可以對關鍵字直接取模，也可在折疊、
平方取中后再取模。


一個例子
? 很顯然，本方法的關鍵就在于選擇合適的p, p如果選得不好，就可能會容易產生同義詞。
? 下面我們來舉個例子看看：
? 有一個關鍵字，它有12個記錄，現在我們要針對它設計一個散列表。如果采用除留余數法，
? 那么可以先嘗試將散列函數設計為f(key) = key mod 12的方法。比如29 mod 12 = 5，所以
? 它存儲在下標為5的位置。


? 不過這也是存在沖突的可能的，因為12 = 2×6 = 3×4。
? 如果關鍵字中有像18(3×6)、30(5×6)、42(7×6)等數字，它們的余數都為6，這就和78所對應
? 的下標位置沖突了。


如何合理選取p值


? 使用除留余數法的一個經驗是，若散列表表長為m，通常p為小于或等于表長（最好接近m)的最小質數或不包含小于20質因子的合數。


? 這句話怎么理解呢？要不這樣吧，
? 我再舉個例子：某散列表的長度為100，散列函數H(k)=k%P,則P通常情況下最好選擇哪個呢？
? A、91 B、93 C、97 D、99
?實踐證明，當P取小于哈希表長的最大質數時，產生的哈希函數較好。我選97，因為它是離長度值最近的最大質數。

總結

以上是生活随笔為你收集整理的除留余数法学习的全部內容，希望文章能夠幫你解決所遇到的問題。

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