前言 & 闲话

• 做哈希题时没打起十二分精神少用mod（亲验），建议unsigned long long

• 对于顺序不同的序列判断相同可以尝试考虑异或和相等，且异或可变性很多，性质也很多。

正文

字符串哈希/序列哈希

假设两个字符串为 $s$，长度分别为 $n$，以 $1$ 为起始下标。

哈希函数：

$$hashCode=\sum _{i=1}^n{s}_i\times bas{e}^{n-i}$$

设 $hs{h}_i$ 为字符串 $s$ 的前 $i$ 位的哈希值，利用前缀和的性质，则区间 $[l,r]$ 的哈希值是 $hs{h}_r-hs{h}_{l-1}\times bas{e}^{r-l+1}$。

---

二维矩阵哈希

很容易可以想到要分别从行和列入手。

设 $hs{h}_{i,j}$ 表示矩阵的左上角为 $(1,1)$，右下角为 $(i,j)$ 时的哈希值。

先从列开始 $hs{h}_{i,j}=hs{h}_{i,j-1}\times base1+a_{i,j}$，再从行开始，为了避免冲突，所以要用另一个 $base2$，则此刻转移为 $hs{h}_{i,j}=hs{h}_{i-1,j}\times base2+hs{h}_{i,j}$。

同样的，考虑如何得出大矩阵中的小矩阵的哈希值，发动大脑想象图，本人就不画了，设小矩阵是 $a$ 行 $b$ 列的，右下角在大矩阵中的位置是 $(i,j)$，那就套路了，这个小矩阵的哈希值是 $hs{h}_{i,j}-hs{h}_{i-a+1,j}\times bas{e}^a-hs{h}_{i,j-b+1}\times bas{e}^b+hs{h}_{i-a+1,j-b+1}\times bas{e}^a\times bas{e}^b$。

---

树上哈希

假设现在遍历到节点 $u$，左子树是 $l$，右子树是 $r$。

哈希转移式为：

$$hs{h}_u=hs{h}_l\times base1+hs{h}_r\times base2+a_i$$

---

拓展：异或哈希

引入

给定一个长度是 $n$ 的序列 $a$,在 $a$ 中选取一个区间 $[l,r]$，使得 $1,2,3,\dots ,r-l+1$ 在该区间恰好都出现一次，问序列 $a$ 中有多少个这样的区间。

分析

可以知道的是普通的哈希是固然不行的，因为顺序不同，每个位上 $base$ 的进制就不一样了。很巧妙的想到了异或和，因为相同集合的异或和是不变的，和顺序无关。

可是异或有个缺点，就是不同的数异或和可能相同，解决方案就是把每个数映射成随机大的数（哈希思想），设随机数的位数是 $m$，则冲突概率为 $\frac{n^2}{2^m}$，可以发现 $32$ 位的数冲突是很大的，那么尝试变成 $64$ 位呢，这个概率就变得非常小了，进而引出异或哈希。

小锦囊

随机数：

mt19937_64 rnd(time(0));