由于笔者不常使用哈希，且整理不够全面，本文只做启发。
哈希
寻找一个映射函数\(f\)把一个集合映射到一个有限集合，使得不同元素映射的值不同，相同元素的值相同。
我们希望这个函数能让我们快速判断两个字符串是否相同。
构造
字符串的哈希一般构造如下：
template<unsigned bas = 131, unsigned mod = 998244353>
struct HASH {
char s[MAXN]; int n;
ull f[MAXN], pw[MAXN];
void init(int _n) {
n = _n;
pw[0] = 1;
for (int i = 1; i <= n; ++i)
f[i] = (1ull * f[i - 1] * bas + s[i]) % mod,
pw[i] = 1ull * pw[i - 1] * bas % mod;
}
ull sub(int l, int r) {
return (f[r] - f[l - 1] * pw[r - l + 1] % mod + mod) % mod;
}
};
字符串的左边系数更大，因为这么构造能够轻易的去除字符串的任意子串的哈希值。
哈希碰撞
我们认为，映射函数\(f\)设计的足够好的时候，每个位置都是等概率被映射到的。那么哈希碰撞的概率就是\(\frac{n \times (n-1) /2}{mod}\)。即所有不同子串都映射到mod值域里。不推荐使用自然溢出的原因就是，\(f\)的映射不够优秀，导致某些位置容易被映射到。
不知道哪里听到的一句话
现在的出题人都默认卡单哈希
所以一般用双哈希来避免哈希碰撞。
unordered_map
unordered_map是通过哈希表来实现的。理论上复杂度应该是\(O(1)\)的，但不知道为什么，跑的经常没有map快。而且基数确定，经常被出题人卡。但是可以通过如下代码自定义哈希映射函数:
struct hashfunc {
template<typename T, typename U>
size_t operator() (const pair<T, U> &i) const {
return hash<T>()(i.first) ^ hash<U>()(i.second);
}
};
unordered_map< pair<int, int>, int , hashfunc > mp;
应用
哈希广泛应用于各种“乱搞”。
- 字符串匹配，判断\(S1\)是否是\(S2\)的子串
- 判断\(S\)字符串是否回文
求出\(S\)和\(S^R\)的哈希，判断是否相等。（R代表翻转） - 寻找\(S\)和\(T\)的lcp（最长公共前缀）
二分长度，哈希判断是否相等。
等等
其他的哈希映射方式 xor-hash
考虑这么一个问题：快速判断两个集合是否相等？（集合是无需的）
考虑一种满足交换律的运算作为哈希映射方式。就可以解决无需问题。
如：异或。
首先，我们把元素随机映射到mod值域内，降低哈希碰撞概率。然后异或起来就是哈希值。
for (int i = 1; i <= n; ++i)
f[i] = rnd() % mod;
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] ^ f[a[i]];
应用
- 判断一个序列内的元素是否出现偶数(\(k\)的倍数)次
异或起来为0，否则为非0。
\(k\)的倍数：手写一个$ k $进制xor，但是会多个log常数
例题：
- CF: 1175 F The Number of Subpermutations
- CF: 869 E. The Untended Antiquity
- CF: 1418 G. Three Occurrences
线段树 & 哈希
考虑以下问题：字符串\(S\)长度为\(|T|\)的子串是否和字符串\(T\)每个元素相对大小位置一样。
如：\(S = [1, 2, 5, 4, 6]\)，\(T = [2, 1, 5]\)，那么\(S[3,5]\)和\(T\)的相对大小位置一样。
哈希有很好的性质，只要知道这个字符的相对位置，就能算出这个字符对哈希的贡献。考虑开权值线段树。在\(pushup\)的时候重新构造字符串哈希，最后判断相等即可。
例题：
标签：map,映射,int,CF,哈希,字符串 From： https://www.cnblogs.com/Qing17/p/18316614