Hash時取模一定要模質數嗎？

01-03

排除人為製造的數據外，對質數取模的優勢在哪裡呢？

看了一下幾個答案，都有不完全的部分。

首先來說假如關鍵字是隨機分布的，那麼無所謂一定要模質數。但在實際中往往關鍵字有某種規律，例如大量的等差數列，那麼公差和模數不互質的時候發生碰撞的概率會變大，而用質數就可以很大程度上迴避這個問題。

質數並不是唯一的準則，具體可以參考以下網站。

good hash table primes

Hash(N) = N % M

首先，我們要明白Hash的意義在於把一個大的集合A，映射到小的集合B。比如通過取余的方式進行Hash，集合A = {0, 1, …, M, M+1, …, 2*M, 2*M+1, …, 3*M, 3*M+1, …}就會被映射到集合B = {0, 1, 2, …, M - 1}。

然後，如果集合A的元素分布是{0, 1, 2, 3, 4, …}這樣的話，M取質數還是合數都可以，最後整個集合A會被均勻地映射到{0, 1, …, M-1}。

（例子）但是，很多情況下我們的元素分布是有非1步長的，比如集合A = {0, 6, 12, 18, 24, 30, 36, …}，這時候就出現問題了。當M取合數時，比如M = 10，我們來看看映射的情況。0-&>0, 6-&>6, 12-&>2, 18-&>8, 24-&>4, 30-&>0, 36-&>6, …。此時我們很容易發現，最後映射到了集合B = {0, 6, 2, 8, 4} = {0, 2, 4, 6, 8}，和我們理想中的{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}差距很大啊。

有問題我們就要去解決啊。我們回到代數形式上來看，在N與M最大公因數為1的情況下，N % M後可以得到的一系列的餘數r，而全體餘數r的集合R就是{0, 1, 2, …, M-1}。每個餘數r代表了一個N的集合，比如在上面的例子中餘數0代表了N的集合{0, 10, 20, 30, …}，這個集合就叫做「同餘類」。即餘數集合R中有M個餘數，每個餘數r代表一個同餘類。現在思路就很清晰了，我們最理想的方式就是將集合A映射到餘數集合R上，即B = R。

接下來我們討論一下為什麼有時候無法完全利用餘數集合R：

假設N = kn, M = km， N和M存在最大公因數k，此時可以將N % M = r轉化為公式N = Mq + r，即kn = kmq + r。其中q是商，r是餘數。「表面上」r的取值範圍是{0, 1, 2, …, M-1}（忽視了只有N與M最大公因數為1時，才能取整個餘數集合R的定理），一片和諧。但是可以對公式進行稍微的變換，n = mq + (r/k)，由於n和mq都是整數，則(r/k)也是整數。此時我們看一看到(r/k)的取值範圍是{0, 1, 2, …, M/k} = {0, 1, 2, …, m}。恢復到原式，也是就r的「實際」取值範圍是{0, k, 2*k, 3*k, …, m*k}，縮小了k倍。

一切都明了了，我們最後的目標就是保證N與M最大公因數為1。最簡單的方式就是直接取M為質數！

哈希演算法可能有很多種，其中可能會用到乘除法。如果鍵值比較大的話，可能要在計算過程中過中間結果取模。這樣問題就來了。

模素數的剩餘系除去 0 ，這個集合關於乘法構成群。這個很重要。只有群才能保證每個元素都有逆元，只有這樣，除法才是合法的。說的通俗一點，假設你要計算 (p / q) mod m，如果你想讓結果與 (p mod m) / (q mod m) 相等【註：後面的這個除法就是傳統意義的除法，是要對 p 求模 m 的逆元，也就是找到一個數 t，使得 (p * r) mod m = 1】，就必須令 m 為素數，否則逆元就求不出來。

想的可能有點多了，哈希演算法可能很少用到這麼複雜的計算吧？

請多批評。

舉個例子，對於除法哈希表（Division method）h(k)=k mod m