哈希算法

Published: July 06, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 多项式哈希
  • 哈希攻击
• 生日悖论
• 多次哈希
• 对64位整数的哈希
• 多重集合哈希
• 树哈希

多项式哈希

一般我们使用的哈希算法是多项式哈希。对于某个向量$(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$和$x$。我们考虑如何构造$f(x)$，使得$x_0$是它的一个根。实际上我们让$f(x)=x-x_0$即可。

第二种情况，固定的$m$，随机选择$x$，但是$m$是合数。这时候我们考虑$m$的最小素因子$p$，选择$f(x)=\frac{m}{p}x$。可以发现对于所有$p$的倍数，都是$f(x)$的根，考虑到$p\leq \sqrt{m}$，因此在$x$随机选择的情况下$f(x)=0$的概率不小于$\frac{1}{\sqrt{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 (high * 31L + low) % mod;
}

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

多重集合哈希

考虑计算多重集合的哈希值。我们有很多种方案，最简单的就是将多重集合中的元素进行排序后使用多项式哈希。但是这种方法有些大材小用了，而且必须引入排序的时间复杂度。

时间上多重集合哈希和一般的字符串哈希有着本质区别，前者不关心元素的排列顺序，而后者关心，换言之后者的哈希值中能夹带上顺序的信息，而前者的哈希值不需要带这部分额外的信息。

考虑选择一个素数$p$。之后我们为每个多重集合中的元素从$1$到$p-1$随机选择一个整数，表示它们的哈希值。之后我们定义一个多重集合中的哈希为它的所有元素的哈希值的和（模$p$意义下）。

我们考虑哈希冲突的概率。假设$A,B$是两个不同的多重集合，但是$h(A)\equiv h(B)$。记$C$表示$A$与$B$的交集，则$h(A-C)\equiv h(B-C)$。考虑任意一个仅在$A-C$中出现的元素$x$，记它的出现次数为$y$。则有$h(x)=\frac{1}{y}[h(B-C)-h(A-C-\left\{ x\right\}\times y]$（这里认为$y$的出现次数不超过$p$，且大于$0$）。由于$h(x)$可以等概率取$[1,p)$中的数，因此等式成立的概率为$\frac{1}{p-1}$。

题目1：考虑给定$n$多重集合，一开始的时候所有集合都是空集。之后处理$q$个请求，每个请求分为两类：

• 选中某个集合，向其中加入元素$x$
• 选中某个集合，删除其中的一个元素$x$（保证删除的元素存在）

要求在处理完每次请求后报告目前有多少个不同的多重集合。

多重集合哈希的裸题，维护$n$个集合的哈希值，之后每个操作对应某个哈希集合的哈希值的加减操作。

题目2：考虑一个整数序列$a_1,\ldots,a_n$，之后处理$q$个请求。

• 将$a_i$替换为$x$
• 给定两个区间，判断两个区间形成的两个多重集合是否相同。

把多重集合丢到区间查询结构上去即可。

树哈希

树哈希分成有根树哈希和无根树哈希，前者给定根，后者不给定。对于无根树哈希，考虑到每棵树最多只有两个重心，因此只需要对每个重心作为根进行考虑，即每个无根树都可以转换为最多两个有根树来处理。

树哈希的方式非常简单，对于一颗树，我们可以利用多重集合哈希的技术来完成。给定哈希函数$H$，考虑树根$r$，其下挂载的孩子为$c_1,c_2,\ldots,c_k$，且树的大小为$n$，则树的哈希值$h(r)$为$H(\sum_{i=1}^kh(c_i))$。

在不存在哈希碰撞的情况下，可以根据归纳法证明两个树相同，当且仅当它们的哈希值相同。