为什么求模运算要用素数(质数)—— 哈希表设计

在设计用除法来散射的哈希表时,我们都会用数值模哈希表大小,得到的余数来作为ID存入哈希表对应格子中。所有文章都表明要用一个较大的素数来作为哈希表的大小,也就是要模一个较大的素数。但为什么就是要用素数呢?简单分析一下可以看出玄机。

先看看如果用一个合数8作为哈希表大小,0-30在哈希表中的散射情况:

(表1)

mod8

再来看看用质数7作为哈希表大小,0-30在哈希表中的散射情况:

(表2)

mod7

我们都知道,合数8除了1和自身以外,还有2跟4这两个因数。观察表1的单独一列可以发现,这些在同一列的数,他们实际上就是上一个数+8,而查看2、4、6这三行我们发现,因为2 4 6 能被2(或4)整除,而在同一列上的数在+8以后一样满足可以被2(或4)整除的这一特性。例如4这一列,4、12、20、28,这些哈希映射在同一个格子里的数都是前一个数+8,然后他们都能被2和4整除,这样就导致他们之间有很强烈的关系,很容易发生哈希冲突。

再来看看表2,同样情况,同一列中的数都是由上一个数+7得到的,但因为7是一个素数,它除了1跟本身之外没有其他因数,所以在同一列的数里就找不到我们刚刚所说的那种特性。

而我们都知道,哈希表设计目的就是希望尽量的随机散射,不希望这些在同一列上的元素(也就是会冲突的元素)之间具有关系,所以我们都采用素数作为哈希表的大小,从而避免模数相同的数之间具备公共因数。

Bookmark the permalink.

6 Responses to 为什么求模运算要用素数(质数)—— 哈希表设计

  1. 山姆 says:

    请问,是不是素数越大,就会越好?

  2. 匿名 says:

    例如4这一列,4、12、20、28,这些哈希映射在同一个格子里的数都是前一个数+8,然后他们都能被2和4整除,这样就导致他们之间有很强烈的关系,很容易发生哈希冲突。
    为什么有强烈的关系,就容易发生冲突?

    • admin says:

      无法预期哈希表是存储什么样的数据的,如果这些数据是有关系(例如是2或4的倍数),然后又使用+8的哈希表格来存储就会很容易冲突。所以设计哈希表时应该尽量避免存在这些关系。

  3. 匿名 says:

    本文解释得还是有点绕, 那个例子让人一头雾水 。我的理解是:
    1. 如果哈希数据是均匀随机分布的,那么用质数和合数是没区别的。
    2. 但实际上哈希数据往往不是均匀分布的,比如存在很多等差数列(例如4,8,12,16…之类)。当用M取模时,M的任意一个因子k, 都存在等差数列,其模空间会缩小为M/k, 从而增加冲突概率。 例如用8取模时,其因子4存在等差数列4, 8, 12,16…,这个数列的余数空间是(4,0,4,0,..) 。因此,取质数是最安全的选择,因为它的因子最少。

匿名进行回复 取消回复

邮箱地址不会被公开。