哈希学习笔记
FLY_lai
·
·
个人记录
【哈希】
哈希可以分成两块：哈希函数和哈希表。
哈希函数是一种对应关系，它可以把任意类型映射为一个不太大的整数。
例如字符串，我们可能希望在字符串上记录一些属性。但是字符串不能当下标，那我们就只能加个大常数用 map。
这时，哈希函数出场了！如果我们有一个哈希函数 h() 可以把一个字符串 str 映射到 h(str) 这个整数上。
对于这个哈希函数 h(x)，我们希望 h(x) 对于同样的 x 相等，对于不同的 x 一般不同。
因为 x 的取值范围一般比 h(x) 大，所以不同的 x 的 h(x) 相等是在所难免的。我们有两种方法处理这个问题：① 对相等的特殊处理。 ② 直接不管了，就直接把不同的 x 视为相同的。因为这样出问题的概率其实很小，如果刚好出 bug 算倒霉。
【字符串进制哈希】
把字符串视作一个 p 进制数。
例如 abcdahi 视作 p=31 进制数 (0123078)_{31}。h(abcdahi)=0\times 31^6+1\times 31^5+\dots+8\times 31^0.
但这样答案可能是很大很大的，所以有一个方法：设定一个数 md，对 md 取模。
【模板】字符串哈希
那我们为什么对进制哈希情有独钟？因为进制哈希带来了一些和进制整数类似的性质，很方便
比如我们现在处理出 s 所有前缀的 Hash 值。（进制哈希方便处理前缀）那我们要查询 s 的子段的 Hash 值就很方便，h(s[l\sim r])=h(s[0\sim r])-h(s[0\sim l-1])\times p^l.
而且两字符串拼接后的哈希值也能方便求出。
当然，哈希一般只判断是否相等，对于更复杂的信息，那就只能另寻他法了~
字符串前缀
注意是两个非空前缀。
基础想法：二重循环枚举两个前缀 + 一重循环判断是否是前缀，妥妥炸掉。
优化：先只用一重循环枚举一个前缀，第二个前缀位置可以二分（越大越好，越小越可行），判断是否是前缀可以哈希。
Radio Transmission
直接枚举前缀为循环节，然后枚举所有出现位置用哈希判断是否和循环节相等。
当枚举前缀长度 len=1，最差枚举 \dfrac{n}{1} 次。
当枚举前缀长度 len=2，最差枚举 \dfrac{n}{2} 次。
\dots
当枚举前缀长度 len=n，最差枚举 \dfrac{n}{n} 次。
总时间复杂度 O(n(1+\dfrac{1}{2}+\dots+\dfrac{1}{n})).
而当 n\le 10^6，后面的括号都不会超过 15，所以可以看作常数。
当然，也可以利用性质：如果 x 长度是前缀，那么前 n-x 个和后 n-x 个相等。少一重枚举循环节开始位置的循环。
ANT-Antisymmetry
判断 s 中的子段是否是回文串：
-
建立 s'=reverse(s)；
-
预处理出 s,s' 的前缀哈希；
-
如果一个子段在 s,s' 中的哈希值相等，就是回文子段。
这题里面类似处理：先全部取反，然后翻转。再在两个字符串里跑哈希。
但是 $O(n^2)$ 枚举子串不行，我们可以用类似上面的优化：一重循环枚举**对称轴** + 二分（越长越好，越短越可行）。
[Compress Words](https://www.luogu.com.cn/problem/CF1200E)
先对每个单词哈希。然后维护当前拼好的字符串的前缀哈希。
我们可以每次在拼上一个字符串时，前缀哈希递推——因为加字符只在末尾加。
查找最大匹配长度二分即可。
[企鹅QQ](https://www.luogu.com.cn/problem/P4503)
有点像[电子字典](https://www.luogu.com.cn/problem/P4503)？
**排序！！！**
先排序，这样我们只用找出所有段，段内任意两个都相差 $1$ 位。**注意如果 $a,b$ 差一，$b,c$ 差一，$a,c$ 不一定差一。所以我们要固定 $a,b,c$ 相差的位置，才能保证 $a,b,c$ 都是差一。**
判断两个串是否差一，用哈希尝试删去某一个位置的字符后是否相等。
具体实现时可以预处理出所有字符串删去某个位置后的 Hash 值，存在一个数组里。
然后一重循环枚举删去哪个位置，找出所有段：段内删去这个位置后都相等。
## 【哈希思想】
[解方程](https://www.luogu.com.cn/problem/P2312)
记给定多项式为 $p(x)$。
先有暴力思路：枚举 $O(nm)$，但是计算常数巨大。
我们可以改一改判断条件：$p(x)=0$ 我们认为只要 $p(x)\% md=0$ 就行。
我们把每个 $a_i$ 看作一个字符串，求出它模 $md$ 的 Hash 值，令 $a_i\leftarrow h(a_i)$。枚举解 $x$，就用正常的方法，对应的 $x^{?}$ 乘上已经变成 Hash 值的系数 $h(a_i)$。判断结果是否为 $0$。
还有一个专属于这种多项式题的优化：可以搞几个模数 $md_{1\sim 5}$，我们要求 $p(x)\%md_{1\sim5}=0$ 才看作是 $0$。另外，因为是多项式，所以 $p(x)\equiv p(x+md_1)\pmod md_1$。因此如果 $p(x)\%md_1$ 不行，那 $p(x+kmd_1)$ 也不行，打标记以后不枚举。
$n$ 次解最多只有 $n$ 个，这个优化效果显著。
[星战](https://www.luogu.com.cn/problem/P8819)
~~不可以，总司令~~
哈希的想法：把复杂数对应到简单数上。
那我们也可以**把复杂操作对应到简单操作上，维护复杂数对应到维护简单数上！**
**设点 $i$ 出边边权为 $v_i$（随机），维护边权和 $y$。**
$v[u]$ 是一条边的边权，$s[u]$ 是现在点 $u$ 的出边边权和，$T[u]$ 是初始时点 $u$ 的出边边权和。
① 删一条边，$y-=v[u],s[v]-=v[u]
② 删一个点，y-=s[i]
③ 恢复一条边，y+=v[u],s[v]+=v[u]
④ 加一个点，y+=(T[u]-s[u]),s[u]=T[u]
出错的概率怎么算？
假设随机数范围 t，查询次数 k。
单次不错 \dfrac{1}{t}，k 次不错概率 (1-\dfrac{1}{t})^k \approx 1 - \dfrac{k}{t}.
那么全部操作正确的概率，在我们随机数范围取 10^9 时就是 1-\frac{10^6}{10^9}\approx 99.9\%.
【哈希表】
可以用 Hash 值做索引，搞数组字典。
优点：O(1)，缺点：不能搞什么二分查找之类的，因为已经没有顺序了。
unordered_map 自己定义哈希函数模板：
struct my_hash {
long long operator()(const vector<int> &v) const {
long long res = 0, p = 131, md = 987656783;
for (auto i: v)
res = (res * p + i) % md;
return res;
}
};
unordered_map<vector<int>, int, my_hash> mp;
int main() {
vector<int> a(3, 5);
mp[a] = 5;
cout << mp[a];
return 0;
}
HDU3973
哈希可以通过长度和本身的哈希值，O(1) 合并！
这意味着我们可以用线段树维护！
而查询是否存在，可以用 unordered_map 建立一个以哈希值为索引，布尔类型的哈希表。