Hash时取模为什么要模质数

2019-04-13 14:03发布

  首先来说假如关键字是随机分布的,那么无所谓一定要模质数。但在实际中往往关键字有某种规律,例如大量的等差数列,那么公差和模数不互质的时候发生碰撞的概率会变大,而用质数就可以很大程度上回避这个问题。
  考虑模是合数的情况:假设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, 2*k, 3*k, …, m*k},缩小了k倍。
  可以明显看出,在模和关键字有公因数的情况下,模后取值范围减少,冲突概率增加,尤其是关键字是等差数列。而模为质数就不会出现这种情况。