板：P3370 【模板】字符串哈希
复杂度：O(n)
用途：将一串字符串映射到一个数
怎么写？
选取一个较小质数 p 选取一个较大质数 mod1
将字符串转换成一个 p 进制在 mod1 定义下的数
常见模数：1e9+7（但很容易被卡）
不太容易被卡的模数：19260817 123456791
写法如下：
哈希冲突
根据哈希的写法 我们不难发现 相同的字符串的 hash 值一定相等
但 hash 值相等的字符串一定相同吗？ 其实不然
事实上 是有可能存在两个不同字符串转换后的 hash 值相同的情况 我们将其称之为哈希冲突
这里给出结论 若字符串的长度为 \(n\) 则模数若不超过 \(n^2\) 就很容易发生哈希冲突
那么如何避免 hash 冲突呢？
1.unsigned long long
unsigned long long 的数据范围为 \(0-2^{64}\) 当取值大于 \(2^{64}\) 时会自动溢出 相当于是自动对 \(2^{64}\) 取模
缺点：有概率会被丧心病狂的出题人卡
2.双哈希
顾名思义 就是准备两个模数 做两遍哈希
优点：我们认为是无法被 hack 的
缺点：常数巨大 取模和除法运算又很慢 有可能慢到 TLE
3.哈希表
优点：安全
缺点：我不会写 写起来有点麻烦
4.unordered_map
有点：写起来非常方便
缺点：STL...懂得都懂
同时 哈希还支持查询子串的 hash 值
需要 O(n) 的复杂度 O(1) 查询
首先我们要开一个数组 把之前每一步的 ch 记录下来
我们以十进制数为例 观察如何查询中间一段数字的值
如这段：123456789 我们要查询第 3 位至第 7 位 即34567
我们已知每一段前缀的 hash 值 不难发现我们要用到 hash[2] = 12 与 hash[7] = 1234567
然后我们发现 $34567 = 1234567 - 12 * 10^5 $
根据这个式子 我们可以推广出 \(hash[l,r] = ha[r] - ha[l-1] * ch[r-l+1]\)
具体代码如下：
