除留余数法

首先回顾一下什么是除留余数法。
当哈希函数产生哈希值较大,而存储值希望较小(如存储空间限制)时,可以采用模运算来限制在某个范围之内。

我们将运算值对p取余直接作为哈希值,p 一般取值小于等于哈希表长度 size 的最大质数。 选择优秀的 p 可以减少冲突的发生。

限制小于等于size是因为哈希值通常也是直接用于存储地址下标,从而不能超出存储空间长度。

下面给出一个常见的字符串hash实现(没有取质数):

1
2
3
4
5
6
7
int hash(string& value) {
int code = 0;
for (size_t i= 0; i<value.length(); i++) {
code = code * 256 + value[i] + 128;
}
return code%size;
}

考虑到避免长数据溢出问题,更常见的扩大适用版本应该是

1
2
3
4
5
6
7
int hash(string& value) {
int code = 0;
for (size_t i= 0; i<value.length(); i++) {
code = (code * 256 + value[i] + 128)%size;
}
return code;
}

为何要尽量取素数

选取质数本质上只是一个优化,选取非质数其实并不会影响算法的正确性,
只会导致较差的hash算法在特定情况下会冲突概率变大,效率变差。

良好的hash函数(或者说如果取模本身是hash函数的一部分,那么就说hash函数抛去取模的部分),其实是无所谓模什么数的,但选取质数可以较好地抵抗不好的hash函数。

只要原hash方法是线性的变换,除数取合数的话,一旦数据是以合数的某个因子为间隔增长的,那么hash值只会是几个值不停的重复,冲突很严重,而素数就不会发生这种情况。

另一方面,即使哈希函数较差,但假如关键字是完全随机分布的,那么也无所谓一定要模质数的。但在实际中往往关键字有某种规律,例如大量的等差数列,那么公差和模数不互质的时候发生碰撞的概率会变大,而用质数就可以很大程度上回避这个问题。

综合,也就是这个优化方法产生效果的场合是:1.输入数据具有明显规律性(同余某个数)2. 哈希算法除去模数以外的部分对于这种输入数据表现差,冲突高。
而即使不满足这些条件,这个优化也不会降低效率,所以为了通用性,通常不管是否符合,我们都选取质数来模。

严格的数学推理与证明需要使用到数论知识,这里仅作简单的概念性说明。

下面详细说明。

哈希函数的重要特性,就是要尽量让输出n%m等概率,从而降低碰撞的频率。

理论上,若x的分布是平均的,那么m取值多少效果都一样好。假设x平均分布在[0, k * m],那么f(x)就会平均分布于[0, m]。从排除哈希碰撞的角度看,这已经是最优的分布了。但理论归理论,实际上m最好还得是个质数,因为x的分布在实际应用中很难做到平均分布,这时候m的取值就至关重要。

首先不难看出m不能取2^t这种数,因为这样等同于把输入数据的高位截断了。如果恰好输入数据变化的只有高位(即2^a+b),那就会悲剧,所有的数据都会被分配到一个桶。比如m=256,257%256=1,513%256=1,769%256=1。

实际上,m不止在取2^t时会发生这种大量碰撞的糟糕情况。只要输入数据跟某一整数k同余(包含输入数据变化的只有高位的情况在内,k=2),而m与k的最大公因数越大,碰撞概率越大。

举例如m若取9(9并不是2^t),
输入数据4, 7, 10, 13, 16, 19, 22, 25 他们对于整数k=3同余1,
设中间哈希函数h(x)=5x-9,则他们的中间哈希值是11, 26, 41, 56, 71, 86, 101, 116, 他们对于整数k=3同余2,
则最终哈希值11%9=2, 26%9=8, 41%9=5, 56%9=2, 71%9=8, 86%9=5, 101%9=2, 116%9=8
m=9与k=3有公因数g=3。
可以看出最终哈希值分布在2, 5, 8,而并没有充分利用[0, 9)的结果空间,利用空间是公因数的倒数倍,即整个空间的1/3。

而要保证空间利用最大化,即哈希结果足够散,则需要使m与k的最大公因数g最小,即g=1,就要使m与k互质。
由于实际我们无法提前得知输入数据,从而无法得知k的取值,那么只需要将m取为质数,就可以保证m与k一定互质。

再次推广,即使输入数据不是跟某一整数n同余,但只要不是完全平均分布,那么这些数据的某个子集也会构成这种同余情况,从而一定程度上增多碰撞,通过取素数处理,也可以相应程度消除这种碰撞。
综合任意数据下的情况,输入数据集越接近这种同余情况,取素数这种处理方法的优化效果越明显。


另一种看到的数学说明如下:

Hash(N) = N % M首先,我们要明白Hash的意义在于把一个大的集合A,映射到小的集合B。比如通过取余的方式进行Hash,集合A = {0, 1, …, M, M+1, …, 2M, 2M+1, …, 3M, 3M+1, …}就会被映射到集合B = {0, 1, 2, …, M - 1}。

然后,如果集合A的元素分布是{0, 1, 2, 3, 4, …}这样的话,M取质数还是合数都可以,最后整个集合A会被均匀地映射到{0, 1, …, M-1}。

(例子)但是,很多情况下我们的元素分布是有非1步长的,比如集合A = {0, 6, 12, 18, 24, 30, 36, …},这时候就出现问题了。当M取合数时,比如M = 10,我们来看看映射的情况。0->0, 6->6, 12->2, 18->8, 24->4, 30->0, 36->6, …。此时我们很容易发现,最后映射到了集合B = {0, 6, 2, 8, 4} = {0, 2, 4, 6, 8},和我们理想中的{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}差距很大啊。

有问题我们就要去解决啊。我们回到代数形式上来看,在N与M最大公因数为1的情况下,N % M后可以得到的一系列的余数r,而全体余数r的集合R就是{0, 1, 2, …, M-1}。每个余数r代表了一个N的集合,比如在上面的例子中余数0代表了N的集合{0, 10, 20, 30, …},这个集合就叫做“同余类”。即余数集合R中有M个余数,每个余数r代表一个同余类。现在思路就很清晰了,我们最理想的方式就是将集合A映射到余数集合R上,即B = R。

接下来我们讨论一下为什么有时候无法完全利用余数集合R:

假设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, 2k, 3k, …, m*k},缩小了k倍。

一切都明了了,我们最后的目标就是保证N与M最大公因数为1。最简单的方式就是直接取M为质数!


质数并不是唯一的准则,质数的选取上还可以更加精细挑选来优化。见链接
good hash table primes

部分节选自知乎 @十一太保念技校,链接:https://www.zhihu.com/question/20806796/answer/21359160
部分节选自知乎 @林二xLINER,链接:https://www.zhihu.com/question/20806796/answer/159392465

Hash时取模一定要模质数吗?
哈希表中数组的容量为什么是质数
为何哈希函数取余法要避免2的幂?