哈希简单解说

这个哈希确实是啊。

这里不说各种冲突什么东西的证明，因为作者不会，看不懂。

你说说是谁把钢琴和弦乐放一块去的，我怎么飞起来了。

哈希

下面的定义都是不严谨的，这里仅是我的通俗解释。

哈希的基本原理是：把一个判断需要很多时间或空间资源的元素或者状态，通过某种函数变成一个特殊的值或者是什么易于比较的东西，来大大节约判断花销。

比较重要的一点是，我们可以比较快速的维护出各个状态的哈希值。这通常需要一些数据结构辅助或者是利用一些运算符的运算性质。

下文解说的都是把什么东西变成值的哈希。

这里把这个东西 \(S\) 变成值的函数称为哈希函数 \(H(S)\)。

当然，我们不能保证 \(H(S)\) 一定会对两个不同的 \(S\) 输出不同的结果。我们称这种情况为“碰撞”。稍微想一下就可以发现，既然输入数据长度不固定，而输出的哈希值是一个用 unsigned int 或 unsigned long long 存的数，这意味着哈希值是一个有限集合，而输入数据则可以是无穷多个，那么建立一对一关系明显是不现实的。所以“碰撞”是必然会发生的。

我们的工作就是去设计一个有着尽量小可能发生碰撞的哈希函数来做题。

序列哈希

最开始应该是从字符串哈希开始学的。

序列哈希的重要性质与单模哈希

我们定义一有序序列 \(a_1,a_2,\cdots,a_n\) 的哈希函数为

\[H(n)=\left ( \sum_{i=1}^n a_i \cdot base^{n-1} \right ) \bmod M \]

其中 \(base\) 是一个特殊选择的质数，\(M\) 是一个很大的质数模数。常取 \(base=31,M=10^9+7\)。

你问为什么要这样取？因为大家发现这样产生碰撞的可能性很小。也就是经验之谈。

\(H\) 显然可以递推，也就是：

\[H(i)=\left ( H(i-1)\times base +s_i \right ) \bmod M \]

这个哈希函数有不少优点：

可拆性

我们可以通过进行前缀哈希在 \(O(n)\) 的时间内对 \(a\) 预处理，并在 \(O(1)\) 时间内得到 \(a\) 任何一个子串的哈希值。

考虑一个新序列 \(s\)，我们从 \(1\) 到 \(n\) 处理前缀哈希，计入数组 \(H(n)\) 中，也即是：

\[H(i) = (s_1 \cdot base^{n-1} + s_2 \cdot base^{n-2} + \cdots + s_i \cdot base^{0}) \bmod M \]

对于一个子串 \(s_{l,r}\)，其哈希值为：

\[H(s_{l,r}) = (H(r) - H(l-1) \cdot base^{r-l+1}) \bmod M \]

怎么推的

假设我们要求解区间 \([l,r]\) 的哈希值，有下面两个式子，下面省略一下 \(\bmod \ M\)：

\[H(r) = s_1 \cdot base^{0} + s_2 \cdot base^{1} + \cdots + s_r \cdot base^{r-1} \]

\[H(l-1) = s_1 \cdot base^{0} + s_2 \cdot base^{1} + \cdots + s_{l-1} \cdot base^{l-2} \]

如果把 \(H(l-1)\) 乘上 \(base^{\,r-l+1}\)，它就会对齐到 \(H(r)\) 的高位：

\[H(l-1) \cdot base^{\,r-l+1} = s_1 \cdot base^{r-l+1-1} + \cdots + s_{l-1} \cdot base^{r-1} \]

此时：

\[H(r) - H(l-1)\cdot base^{\,r-l+1} \]

就只剩下：

\[s_l \cdot base^{0} + s_{l+1} \cdot base^{1} + \cdots + s_r \cdot base^{r-l} \]

于是：

\[H(s_{l,r}) = (H(r) - H(l-1) \cdot base^{r-l+1}) \bmod M \]

可并性

我们可以在知道序列 \(a,b\) 的长度及其哈希值时，在两者生成哈希值的 \(base,M\) 均相同的前提下，得到拼接后的序列 \(a+b\) 或 \(b+a\) 的哈希值。

拼接串 \(a+b\) 的哈希值为：

\[H(a+b) = H(a) + H(b) \cdot base^{|A|} \bmod M \]

其中 \(|a|\) 为序列 \(a\) 的长度。

怎么推的

设有两个子串：

• \(A = s[l_1 \dots r_1]\)，长度 \(|A| = r_1-l_1+1\)，哈希为 \(Hash(A)\)
• \(B = s[l_2 \dots r_2]\)，长度 \(|B| = r_2-l_2+1\)，哈希为 \(Hash(B)\)

目标：计算拼接串 \(C = A+B\) 的哈希。

---

\[H(A) = s_{l_1} \cdot base^0 + s_{l_1+1}\cdot base^1 + \cdots + s_{r_1}\cdot base^{|A|-1} \]

\[H(B) = s_{l_2} \cdot base^0 + s_{l_2+1}\cdot base^1 + \cdots + s_{r_2}\cdot base^{|B|-1} \]

拼接串 \(C = A+B\) 的哈希为：

\[H(C) = H(A) + H(B) \cdot base^{|A|} \bmod M \]

/n

由上面的合并性质，我们注意到一个序列的哈希值是可以动态维护的，使用树状数组或线段树均可。

性质说完了，你可能注意到我们上面的哈希值都对一个固定的 \(M\) 取模，我们称这样的哈希为单模哈希，这种哈希比较容易被 hack，下面说点更牛的。但好像赛场上写这种也就够了？

双模哈希

如名字，我们选择两个不同的大模数 \(M_1, M_2\)，分别计算哈希：

\[H_1(s) = \left(\sum_{i=1}^n s_i \cdot base^{\,n-i}\right) \bmod M_1 \]

\[H_2(s) = \left(\sum_{i=1}^n s_i \cdot base^{\,n-i}\right) \bmod M_2 \]

最终哈希值为一个二元组：

\[\left(H_1(s), H_2(s)\right) \]

只有当两个模数下都发生碰撞时才会误判，冲突概率大约是原来的平方级下降，总而言之就是更不容易被卡了！

当然你也可以用两个不同的 \(base\) 对一个相同的 \(M\) 取模算出来两个哈希值，也有相同的效果。

如果你不嫌麻烦，三模及以上的哈希也是可以的。

自然溢出哈希

我们直接让所有存储哈希值的变量为 unsigned int 或 unsigned long long 类型，这样在计算时相当于随时都对着 \(2^{32}\) 或 \(2^{64}\) 取模。

可以说比较好写一些？但由于取模的是个偶数，被卡的可能性也比较大。

字符串哈希

就是把上述理论中的序列换成字符串而已啦。

因为每个字符都有一个自己的 ASCII 码，于是和序列哈希是一模一样的。

例题

ABC331F

是线段树维护区间哈希值的例题。

还没有代码。

[CF???]

我咋就记住这俩题了。

集合哈希与多重集合哈希

简单的树哈希

今晚上写不完了（恼