为何在散列表中除留余数法取模运算中，要尽量取素数

除留余数法

首先回顾一下什么是除留余数法。
当哈希函数产生哈希值较大，而存储值希望较小（如存储空间限制）时，可以采用模运算来限制在某个范围之内。

我们将运算值对p取余直接作为哈希值，p 一般取值小于等于哈希表长度 size 的最大质数。 选择优秀的 p 可以减少冲突的发生。

限制小于等于size是因为哈希值通常也是直接用于存储地址下标，从而不能超出存储空间长度。

下面给出一个常见的字符串hash实现（没有取质数）：

int hash(string& value) {
    int code = 0;
    for (size_t i= 0; i<value.length(); i++) {
        code = code * 256 + value[i] + 128;
    }
    return code%size;
}

考虑到避免长数据溢出问题，更常见的扩大适用版本应该是

int hash(string& value) {
    int code = 0;
    for (size_t i= 0; i<value.length(); i++) {
        code = (code * 256 + value[i] + 128)%size;
    }
    return code;
}

为何要尽量取素数

选取质数本质上只是一个优化，选取非质数其实并不会影响算法的正确性，
只会导致较差的hash算法在特定情况下会冲突概率变大，效率变差。

良好的hash函数（或者说如果取模本身是hash函数的一部分，那么就说hash函数抛去取模的部分），其实是无所谓模什么数的，但选取质数可以较好地抵抗不好的hash函数。

只要原hash方法是线性的变换，除数取合数的话，一旦数据是以合数的某个因子为间隔增长的，那么hash值只会是几个值不停的重复，冲突很严重，而素数就不会发生这种情况。

另一方面，即使哈希函数较差，但假如关键字是完全随机分布的，那么也无所谓一定要模质数的。但在实际中往往关键字有某种规律，例如大量的等差数列，那么公差和模数不互质的时候发生碰撞的概率会变大，而用质数就可以很大程度上回避这个问题。

综合，也就是这个优化方法产生效果的场合是：1.输入数据具有明显规律性（同余某个数）2. 哈希算法除去模数以外的部分对于这种输入数据表现差，冲突高。
而即使不满足这些条件，这个优化也不会降低效率，所以为了通用性，通常不管是否符合，我们都选取质数来模。

严格的数学推理与证明需要使用到数论知识，这里仅作简单的概念性说明。

下面详细说明。

哈希函数的重要特性，就是要尽量让输出n%m等概率，从而降低碰撞的频率。

理论上，若x的分布是平均的，那么m取值多少效果都一样好。假设x平均分布在[0, k * m]，那么f(x)就会平均分布于[0, m]。从排除哈希碰撞的角度看，这已经是最优的分布了。但理论归理论，实际上m最好还得是个质数，因为x的分布在实际应用中很难做到平均分布，这时候m的取值就至关重要。

首先不难看出m不能取2^t这种数，因为这样等同于把输入数据的高位截断了。如果恰好输入数据变化的只有高位（即2^a+b），那就会悲剧，所有的数据都会被分配到一个桶。比如m=256，257%256=1，513%256=1，769%256=1。

实际上，m不止在取2^t时会发生这种大量碰撞的糟糕情况。只要输入数据跟某一整数k同余（包含输入数据变化的只有高位的情况在内，k=2），而m与k的最大公因数越大，碰撞概率越大。

举例如m若取9（9并不是2^t），
输入数据4, 7, 10, 13, 16, 19, 22, 25 他们对于整数k=3同余1，
设中间哈希函数h(x)=5x-9，则他们的中间哈希值是11, 26, 41, 56, 71, 86, 101, 116, 他们对于整数k=3同余2，
则最终哈希值11%9=2， 26%9=8, 41%9=5, 56%9=2, 71%9=8, 86%9=5, 101%9=2, 116%9=8
m=9与k=3有公因数g=3。
可以看出最终哈希值分布在2, 5, 8，而并没有充分利用[0, 9)的结果空间，利用空间是公因数的倒数倍，即整个空间的1/3。

而要保证空间利用最大化，即哈希结果足够散，则需要使m与k的最大公因数g最小，即g=1，就要使m与k互质。
由于实际我们无法提前得知输入数据，从而无法得知k的取值，那么只需要将m取为质数，就可以保证m与k一定互质。

再次推广，即使输入数据不是跟某一整数n同余，但只要不是完全平均分布，那么这些数据的某个子集也会构成这种同余情况，从而一定程度上增多碰撞，通过取素数处理，也可以相应程度消除这种碰撞。
综合任意数据下的情况，输入数据集越接近这种同余情况，取素数这种处理方法的优化效果越明显。

---

另一种看到的数学说明如下：

Hash(N) = N % M首先，我们要明白Hash的意义在于把一个大的集合A，映射到小的集合B。比如通过取余的方式进行Hash，集合A = {0, 1, …, M, M+1, …, 2M, 2M+1, …, 3M, 3M+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} = {0, 1, 2, …, M/k}。恢复到原式，也是就r的“实际”取值范围是{0, k, 2k, 3k, …, m*k}，缩小了k倍。

一切都明了了，我们最后的目标就是保证N与M最大公因数为1。最简单的方式就是直接取M为质数！

---

质数并不是唯一的准则，质数的选取上还可以更加精细挑选来优化。见链接
good hash table primes

部分节选自知乎 @十一太保念技校，链接：https://www.zhihu.com/question/20806796/answer/21359160
部分节选自知乎 @林二xLINER，链接：https://www.zhihu.com/question/20806796/answer/159392465

Hash时取模一定要模质数吗？
哈希表中数组的容量为什么是质数
为何哈希函数取余法要避免2的幂?

Donate