字符串Hash
哈希是一个玄学的方法……最适骗分法
哈希，指将信息通过某种方式的缩减，映射到某一个值域上，从而表示这个信息。
如果有两个信息同时映射到了同一个位置，那么就会产生哈希冲突。
哈希冲突在哈希表中有两种处理方式：
链表
质数后移（向后移动质数位，知道找到一个空的地方为止）
但是，在OI中，哈希冲突恰恰是毒瘤出题人卡你正确性的方法……关键是我们不一定能够保证没有哈希冲突……QwQ
所以，哈希很玄学，慎用！
字符串哈希
一般来说，字符串哈希在OI中常用的公式是 $hash(str) = \sum_{i=1}^n base^{n-i} \times str_i$。
在生产环境中，可以有 time33, md5, sha256 等经典算法。但是这里用不到……
那么用这个公式有什么好处呢？
可以通过 $O(n)$ 的预处理，在 $O(1)$ 得出任意一个子串的哈希值
可以随意拼接两个字符串，在 $O(1)$ 内得出合并后的哈希，并在 $O(m)$ 时间内再处理
可以扩展到二维甚至更高
……
不扯了……讲实现了
由于我们需要映射到某一个值域上，所以，一般来说，我们取为 unsigned long long 可以表示的值域即可。（这样也有一些其他的好处，自然溢出避免了超慢的取模运算）
那么，我们以字符串 jeefy，base 取 13 为例：
| Text | Hash | Calc |
|---|---|---|
| j | 106 | $0 \times 13$ + 'j' |
| je | 1479 | $106 \times 13 +$ ’e' |
| jee | 19328 | $1479 \times 13$ + 'e' |
| jeef | 251366 | $19328 \times 13$ + 'f' |
| jeefy | 3267897 | $251366 \times 13$ + 'y' |
生成代码如下
我们考虑换一种表示法：
| Text | Calc |
|---|---|
| j | $13^0 + ord(j)$ |
| je | $13^1 \times ord(j) + 13^0 \times ord(e)$ |
| jee | $13^2 \times ord(j) + 13^1 \times ord(e) + 13^0 \times ord(e)$ |
| jeef | $13^3 \times ord(j) + 13^2 \times ord(e) + 13^1 \times ord(e) + 13^0 \times ord(f)$ |
| jeefy | $13^4 \times ord(j) + 13^3 \times ord(e) + 13^2 \times ord(e) + 13^1 \times ord(f) + 13^0 \times ord(y)$ |
想必，有了这个表之后，哈希拼接应该就很简单了吧。
$$Hash(T) = Hash(A) \times 13^{|B|} + Hash(B) $$
$|B|$ 指的是字符串的长度
我们可以预处理出 $base^i$
hashInt bofs[N] = {1}; // base_offset
for (int i = 1; i < N; ++i) bofs[i] = bofs[i - 1] * base;
那么两个计算如下
struct String {
string s;
hashInt ha;
}
String merge(String A, String B) {
String s = {A.s + B.s, A.ha * bofs[B.s.size()] + B.ha};
return s;
}
没有实际运行过程序，请自行斟酌
同理，如果我们需要字符串片段的哈希，我们可以通过合并的逆操作……
hashInt ha[N];
hashInt slice(int l, int r) { // [l, r]
return ha[r] - ha[l - 1] * bofs[r - l + 1];
}
那么，恭喜你，掌握了哈希的大部分用法了。
房卡小专题
总所周知，哈希是出题人特别喜欢卡的一种做法，所以，我们需要较少减少哈希冲突的可能。那么比较好的解决方法是双哈希。而双哈希指的是双模数和双底数，也就是说值域和 $base$ 都不一样。这种双保险的方法是很难被卡的。
练习题
没想到吧，同构也可以通过哈希来！
这道题可以用二维哈希
小知识
其实C++也是有内置的哈希函数的，参考std::hash - cppreference.com