哈希算法

Published: by Creative Commons Licence

  • Tags:

多项式哈希

一般我们使用的哈希算法是多项式哈希。对于某个向量$(a_0,\ldots,a_{n-1})$,其哈希值为:

\[poly(a)=\sum_{i=0}^{n-1}a_ix^i\]

其中$x$是一个选定的常数。很显然上面的计算结果是非常大的,为了保证计算和存储的效率,需要将结果模上一个数$m$。其中$m$需要选择一个素数,之后会提为什么。

上面的哈希算法有一个致命的问题,就是当$a$中所有元素都是$0$时,$poly(a)=0$一定成立。可以发现对于长度为$0,1,\ldots$的$0$向量,其哈希值一定是$0$,但是很显然这些长度不同的零向量是不同的。换言之,我们可以轻易找到一些值对我们的哈希算法进行碰撞攻击。

上面的问题的解决方式,就是在所有序列尾部加上一个$1$。即

\[poly(a)=x^n+\sum_{i=0}^{n-1}a_ix^i\]

这样我们就能成功地将长度信息也一同存进我们的哈希值中。

下面我们来估计一下碰撞的概率是多少。考虑一个与$a$不同的向量$b=(b_0,\ldots,b_{n-1})$。如果$a$和$b$拥有相同的哈希值,则一定有

\[\begin{aligned} poly(a)&=poly(b)\\ \Rightarrow x^n+\sum_{i=0}^{n-1}a_ix^i&=x^n+\sum_{i=0}^{n-1}\\ \Rightarrow \sum_{i=0}^{n-1}(a_i-b_i)x^i&=0\\ & \end{aligned}\]

现在考虑这样的问题,给定多项式$f(x)=\sum_{i=0}^{n-1}(a_i-b_i)x^i$,其中$f\neq 0$。当$f(x)=0$的时候,这时候$x$一定是$f$的一个零点。

这里我们需要了解到,当模素数$m$的前提下,$\mathbb{Z}_m$构成一个域。而对于$\mathbb{Z}_m[X]$上的非零$n-1$阶多项式,其最多仅有$n-1$个零点。

因此我们只需要在$0$到$m-1$之间随机取$x$,这时候$f(x)$为$0$的概率为$\frac{n-1}{m}$。换言之,我们在一开始的时候随机取$x$,就可以保证任意两个长度为$n$的不同向量,拥有相同的哈希值的概率为$\frac{n-1}{m}$。

生日悖论

一年有$m$天,一个班级里有$n$个学生,问里面至少有两个人有相同的生日的概率为多少。

我们可以通过计算任意两个学生生日不同的概率来计算我们想要的结果。其概率为:

\[\begin{aligned} &\frac{m(m-1)\cdots (m-n+1)}{m^n}\\ =&\prod_{i=0}^{n-1}\frac{m-i}{m}\\ =&\prod_{i=0}^{n-1}(1-\frac{i}{m}) \end{aligned}\]

这里我们需要注意到当$x$的绝对值足够小的时候,有$\ln (1+x)\sim x$。因此在$m$远大于$n$的前提下:

\[\begin{aligned} &\prod_{i=0}^{n-1}(1-\frac{i}{m})\\ =&e^{\ln\prod_{i=0}^{n-1}(1-\frac{i}{m})}\\ =&e^{\sum_{i=0}^{n-1}\ln(1-\frac{i}{m})}\\ \sim &e^{-\sum_{i=0}^{n-1}\frac{i}{m}}\\ =&e^{-\frac{(n-1)n}{2m}} \end{aligned}\]

要让概率碰撞的概率大于等于$p$,可以推出:

\[\begin{aligned} e^{-\frac{(n-1)n}{2m}}&\leq 1-p\\ (n-1)n&\geq -2m\ln(1-p)\\ \end{aligned}\]

稍微简化一下可以得出:

\[\sqrt{-2m\ln(1-p)}+1\geq n\geq \sqrt{-2m\ln(1-p)}\]

考虑移除其中的常数项,则有$n=O(\sqrt{m})$。

多重哈希

根据生日悖论,对于$n$个槽,向其中随机投$\sqrt{n}$个球,就有超过$50\%$的概率会发生碰撞。因此这就产生了一个问题,即使我们取模数为$m$,只需要$O(\sqrt{m})$个向量,就会产生至少一次的碰撞。

对于哈希表这种碰撞允许的情况,我们需要做的就是尽量分摊碰撞的位置,这时候是允许碰撞的。但是有的时候我们是不允许碰撞,比如我们直接用哈希值来表示一个对象进行判重。对于后面这种情况,这需要有$O(\sqrt{m})$个向量(这还是在向量极短的情况下,如果向量很长,则需要的向量数目会减少)就能保证高概率发生冲突。

并且需要注意$\sqrt{m}$一般也不是特别大的数值,比如当取$m=10^9+7$的时候,$\sqrt{m}\approx 31623$。

这里我们可以使用另外一个计数,为每个向量生成两个32位哈希值,并拼接为一个64位整数值。假设前一个哈希值碰撞概率为$p_1$,后一个哈希值碰撞概率为$p_2$,则64位整数碰撞的概率为$p_1p_2$。这个数一般足小。比如当$p_1=p_2=\frac{1}{10^9+7}$,则此时我们预计需要$10^9+7$个对象才会发生哈希碰撞。

对64位整数的哈希

一般哈希值都是32位整数(如果是自然溢出的话,可以使用64位整数,否则使用64位整数作为哈希值,在做乘法取模运算的时候需要使用$O(64)$的手动模拟的方法或一些其余黑科技)。

现在考虑一种情况,我们手头有$n$个对象的64位的哈希值,现在希望压缩到32位整数,该怎么做。

这样的压缩无疑会使得一些消息丢失,但是我们需要在意的是保证原本不同的64位整数值产生的32位整数依旧不同,原本相同的64位整数值产生的32位整数相同。

提几种做法,测试题目

1.直接采用系统自带的哈希算法:

public static int hashCode(long value) {
    return (int)(value ^ (value >>> 32));
}

WA在第5个测试样例。看来哈希效果不是很好。

2.使用http://xorshift.di.unimi.it/splitmix64.c中的哈希算法。

uint64_t next() {
	uint64_t z = (x += 0x9e3779b97f4a7c15);
	z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
	z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
	return z ^ (z >> 31);
}

WA在第49个测试样例。效果比较好,但是还是不够。

3.将64位整数拆分成两个32位整数,并进行哈希计算。

public int hash(long x) {
    long high = x >>> 32;
    long low = x & ((1L << 32) - 1);
    return mod.valueOf(high * 31L + low);
}

AC。效果看来非常好。其实这个是多重哈希的一个应用,将64位整数拆分成两个32位整数,并用多项式哈希的方式进行哈希,可以证明其发生冲突的概率为$\frac{2}{p}$,用双重哈希后可以进一步降低冲突的概率。