1、问题分析 最近看到了哈希表的问题，网上也看到了一些解释，不过并没有讲的很清楚，正好顺便来探讨一下，如有不足之处，还请指出。
最简单的哈希算法可以用取模运算，模一般设置为素数，虽然很多书上讲使用素数能够减小冲突，但是并没有讲为什么会减小冲突，下面通过几个实例来说明一下。
2、实例分析2.1 取模选取模为6，7
6为合数，有因子1，2，3，6
7为素数，有因子1，7
我们看到，合数除了1与本身，还有其他的因子，所以我们考虑使用不同的因子来构造数列。
2.2 选取数列数列的选取很重要，之前看到有些文章将验证的数列间隔选为1，发现素数与合数并没有什么区别，这是因为素数与合数最大的区别不是间隔为1，我们首先看一下素数与合数的关键点：
素数只有两个因子，1和本身
合数至少有3个因子，1，本身，其他因子
素数与合数有公因子1
看到这里，我们可以做这样的一个假设，取模运算的冲突与因子相关，但是具体是如何相关呢，我们后面来实际验证一下，首先验证一下与因子相关；
数列1（因子2）：
1，3，5，7，9，11，13，15，17
数列2（因子2）：
2，4，6，8，10，12，14，16，18
数列3（因子3）：
1，4，7，10，13，16，19，22，25，28
数列4（因子6）：
1，7，13，19，25，31，37，43，49
数列5（因子7）：
1，8，15，22，29，36，43，50，57
上面我们根据6，7的因子，取了5个数列，数列1与数列2取因子2，分别用奇偶数表示，用来验证因子与取模运算是否是相关的；
然后再取后面的3个数列，验证另一个假设，数列的分布以因子为间隔。
2.3 检验
数列1 => 取模6
余数
0
1
2
3
4
5
哈希表
1
3
5
哈希表
7
9
11
哈希表
13
15
17
2是6的因子，数列1产生了冲突
上面我们通过取模运算，发现如果待存数据如果是以2为间隔的话，那么取模6就会有很多冲突，分布不均匀，0，2，4都没有存储，1，3，5冲突很多；
数列1 => 取模7
余数
0
1
2
3
4
5
6
哈希表
7
1
9
3
11
5
13
哈希表
15
17
19
2不是7的因子，数列1分布均匀
然后通过将模取为7，发现同样的数列1，这时候冲突减少，并且分布均匀，因为我们取的是奇数列，再使用偶数列验证是否是这样；
数列2 => 取模6
余数
0
1
2
3
4
5
哈希表
6
2
4
哈希表
12
8
10
哈希表
18
14
16
2为6的因子，分布不均匀
数列2 => 取模7
余数
0
1
2
3
4
5
6
哈希表
14
8
2
10
4
12
6
哈希表
16
18
2不是7的因子，分布均匀
通过上面的取模运算，我们发现，因子确实会影响数列的冲突，并且冲突的间隔就是因子大小，下面再通过其他数列，看一下是否是这样；
数列3 => 取模6
余数
0
1
2
3
4
5
哈希表
1
4
哈希表
7
10
哈希表
13
16
哈希表
19
22
哈希表
25
28
3是6的因子，分布不均匀
数列3 => 取模7
余数
0
1
2
3
4
5
6
哈希表
7
1
16
10
4
19
13
哈希表
28
22
25
3不是7的因子，分布均匀
数列4 => 取模6
余数
0
1
2
3
4
5
哈希表
1
哈希表
7
哈希表
13
哈希表
19
哈希表
25
哈希表
31
6是6的因子，分布不均匀，分部间隔为6
数列4 => 取模7
余数
0
1
2
3
4
5
6
哈希表
7
1
37
31
25
19
13
哈希表
49
43
6不是7的因子，分布均匀
数列5 => 取模6
余数
0
1
2
3
4
5
哈希表
36
1
8
15
22
29
哈希表
43
50
57
7不是6的因子，分布均匀
数列5 => 取模7
余数
0
1
2
3
4
5
6
哈希表
1
哈希表
8
哈希表
15
哈希表
22
哈希表
29
哈希表
36
哈希表
43
哈希表
50
哈希表
57
7是7的因子，分布不均匀，分布间隔为7
3、结论根据上面的结果，我们来分析一般性结论：
哈希表中的分布按照数列的间隔进行分隔，如果数列的间隔恰好整除模，也就是模的因子，那么就会哈希表的分布就会产生间隔，恰好是数列的间隔。
由此得到下面的结论：
如果有一个数列s，间隔为1，那么不管模数为几，都是均匀分布的，因为间隔为1是最小单位
如果一个数列s，间隔为模本身，那么在哈希表中的分布仅占有其中的一列，也就是处处冲突
数列的冲突分布间隔为因子大小，同样的随机数列，因子越多，冲突的可能性就越大
通过上面的分析，现在就很明确了，如果给我们随机的数列放到哈希表中，如何保障它能尽量减少冲突呢，就需要模的因子最少，而因子最少的就是素数了，这就是为什么哈希表取模为素数的原因了。
原文链接：https://blog.csdn.net/zhishengqianjun/article/details/79087525