一、散列函数

散列函数即是将元素映射到对应槽位置的方法。 一个好的散列函数应该是尽可能的将元素均匀的散列到 m 个槽位中的一个。  

二、除法散列法

散列函数的实现有很多种，其中一种常见的散列函数即 除法散列法，h(k) = k mod m，通过取 k 除以 m 的余数，将关键字 k 映射到 m 个槽上。由于只需做一次除法操作，所以除法散列法是非常快的。 当我们使用除法散列法时，m 的选择很重要。《算法导论》一书中，建议我们使用一个不太接近 2 的整数幂的素数，作为 m 的选择。 那么在求模运算中为什么建议要使用素数呢？这是因为使用素数可以让元素取模后的值，更不容易发生冲撞。至于是为什么，我们在下面探讨。  

三、对素数取模的好处

前面说道，对素数取模，结果更不容易发生冲撞，即结果可以更均匀的散列到不同的槽位中。那么原理是怎么样的呢？ 合数和素数：合数即有两个以上的因数，素数（质数）即只有两个因数，分别为 1 和其本身。 如果对一个合数取模，那么对其某个因数取模，结果可能仍然一致。例如 10 对 8 取模，结果为 2，对 4 取模，结果也为 2。而我们对一个素数取模，由于素数只有 1 和其本身两个素数，即不可能出现上述情形。  

四、实例分析

1. 数列A：1，3，5，7，9，11，13，15

假设选取 8 取模，结果为： 余数 0 1 2 3 4 5 6 7 数值   1   3   5   7 数值   9   11   13   15 每个数间隔 2，2 是 8 的一个因数，容易发生冲突，不均匀分布。 假设选取 7 取模，结果为： 余数 0 1 2 3 4 5 6 数值 7 1 9 3 11 5 13 数值   15           每个数间隔 2，2 不是 7 的因数，均匀分布。  

2. 数列B：2，5，8，11，14，17，20，23

假设选取 8 取模，结果为： 余数 0 1 2 3 4 5 6 7 数值 8 17 2 11 20 5 14 7 数值               23 每个数间隔 3，3 不是 8 的因数，均匀分布。 假设选取 7 取模，结果为： 余数 0 1 2 3 4 5 6 数值 14 8 2 17 11 5 20 数值     23         每个数间隔 3，3 不是 7 的因数，均匀分布。

 

3. 总结

如果数列的间隔为 1，那么不管模数为几都会均匀分布。 如果间隔是模数的因数，则容易发生冲突，且模数的因数越多，冲突的可能性越大。 素数只有两个因数，所以可以保证发生冲突的可能性最小。 ​