哈希是将一个序列映射到一段整数区间的函数。
通常要求对于两个随机的等长的不同序列，哈希函数得到的值（以下简称 Hash 值）不同。
更概括地说，Hash 函数满足：
- 序列相同时，Hash 值一定相同
- 序列不同时，Hash 值大概率不同；若两个长度相等的不同字符串 Hash 值相同，我们称这是“哈希碰撞”。
实现
考虑各种原因，OI 上使用的哈希函数通常这样实现：
对于字符串 \(S\)，记其前缀 \(S_{1\sim i}\) 的哈希值为 \(H_i\)。形式上记 \(H_0=0\)，则
\[H_i=H_{i-1}\times\mathtt{base}+S_{i} \]或者，有封闭形式：
\[H_{i}=\sum_{j=1}^{i}S_{j}\times\mathtt{base}^{i-j} \]容易发现，实际上是将序列视为一个以 \(\mathtt{base}\) 为进制的数。
为了控制值域，一般对一个大质数取模，或者让它自然溢出。
OI 界普遍认为取 \(\mathtt{base}\) 为 \(131\) 或 \(13331\) 难以在随机数据下发生哈希碰撞。
但是对着你的程序总是能构造数据卡掉你，见工具 anti-hash。
快速求子串哈希值
对于比对两个序列的子串的情形，我们可以预处理哈希值做到单次 \(O(1)\)。
参考定义，容易发现：
\[H_{i\sim j}=H_j-H_i\times\mathtt{base}^{j-i+1} \]预处理序列的前缀哈希值和 \(\mathtt{base}\) 的幂即可。
二维哈希
随便思考一个哈希方法是容易的，难点在如何快速求子矩阵的 Hash 值。
具体来说，对于矩阵 \(A\)，二维哈希的前缀矩阵定义为：
\[\begin{aligned} I_{i,j}&=\sum_{k=1}^{i}\left(\sum_{t=1}^{j}A_{k,j}\times\mathtt{base_1}^{j-t}\right)\times\mathtt{base_2}^{i-k}\\ &=\sum_{k=1}^{i}\sum_{t=1}^{j}A_{k,j}\times\mathtt{base_1}^{j-t}\times\mathtt{base_2}^{i-k} \end{aligned} \]则其子矩阵 \(A_{a\sim b,c\sim d}\) 的哈希值为
\[I_{a\sim b,c\sim d}=I_{b,d}-I_{b,c}\times\mathtt{base_1}^{c-d+1}-I_{a,d}\times\mathtt{base_2}^{b-a+1}+I_{a,c}\times\mathtt{base_1}^{c-d+1}\mathtt{base_2}^{b-a+1} \] 标签：Hash,times,base,哈希,mathtt,sim From： https://www.cnblogs.com/weily09/p/18327041/strHash