跳转至

哈希表的大小为何是素数

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
哈希表 37
哈希表 43
哈希表 49

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,间隔为模本身,那么在哈希表中的分布仅占有其中的一列,也就是处处冲突

  • 数列的冲突分布间隔为因子大小,同样的随机数列,因子越多,冲突的可能性就越大

通过上面的分析,现在就很明确了,如果给我们随机的数列放到哈希表中,如何保障它能尽量减少冲突呢,就需要模的因子最少,而因子最少的就是素数了,这就是为什么哈希表取模为素数的原因了。