字符串 Rolling Hash 是什么？为什么能快速比较子串？
简化版
Rolling Hash 把字符串看成某个进制下的数字，并预处理前缀哈希。这样任意子串的哈希可以 O(1) 算出，用于快速比较子串、字符串匹配和去重。它有哈希碰撞风险，严谨场景要二次校验或双哈希。
详细版
字符串子串比较如果逐字符比较，长度为 m 就要 O(m)。Rolling Hash 通过前缀哈希把子串映射成数字。
常见公式：
H[i]表示前 i 个字符的哈希。H[i+1] = H[i] * base + value(s[i])。- 子串
[l, r)的哈希可由H[r] - H[l] * base^(r-l)得到。
这样比较两个等长子串时，可以先比较哈希。哈希相同不一定字符串相同，因为可能碰撞。
完整版教学
一、为什么子串比较会贵
如果要比较两个长度为 1000 的子串，朴素方法最坏要比较 1000 个字符。做很多次比较时，总成本会很高。
Rolling Hash 想把一段字符串压缩成一个数字签名：
"abc" -> hashValue比较数字比逐字符快。只要能快速得到任意子串的 hash，就能把大量子串比较加速。
二、字符串为什么可以看成进制数
可以把字符映射成数字，比如 a=1,b=2,c=3。字符串 "abc" 可以看成：
1 * base^2 + 2 * base^1 + 3这和十进制数字 123 类似，只是 base 不一定是 10。为了避免数字无限变大，实际常会对一个大模数取模。
hash = (hash * base + charValue) % modbase 和 mod 的选择会影响碰撞概率和实现稳定性。
三、前缀哈希如何 O(1) 取子串
定义 H[i] 为前 i 个字符的哈希。对于子串 [l, r)，可以用前缀差消掉前面的部分。
hash(l,r) = H[r] - H[l] * base^(r-l)例子：字符串 "abcd"，想取 "bc"，也就是 [1,3)。H[3] 包含 "abc"，减去 "a" 左移两位的贡献，就剩 "bc"。
预处理 H[] 和 basePow[] 后，每个子串哈希就是 O(1)。
四、Rolling 的含义是什么
Rolling 表示窗口滑动时可以快速更新哈希。比如固定长度 3 的窗口从 "abc" 滑到 "bcd"，可以去掉 a 的贡献，再加入 d。
old = hash("abc")
new = (old - value(a)*base^2) * base + value(d)这使它适合 Rabin-Karp 字符串匹配：文本窗口不断滑动，每个窗口快速算 hash，先和模式串 hash 比较。
五、哈希碰撞怎么处理
不同字符串可能有相同哈希。工程上常见处理方式有两种：哈希相同后再逐字符确认，或使用双哈希降低碰撞概率。
| 做法 | 优点 | 缺点 |
|---|---|---|
| 单哈希 | 快，实现简单 | 有碰撞风险 |
| 双哈希 | 碰撞概率更低 | 多一份计算 |
| 哈希后字符校验 | 正确性强 | 命中时要额外比较 |
如果是算法竞赛可以接受概率正确，生产安全敏感场景不能只靠单哈希判断相等。
六、和普通哈希表里的 hash 有什么关系
它们都把对象映射成数字，但 Rolling Hash 额外支持“由前缀快速推出子串哈希”。普通对象 hash 通常不要求这种可组合性。
记忆钩子：Rolling Hash 把字符串当数字，前缀哈希像前缀和；子串 hash 就是“总贡献减掉左边贡献”。
七、常见误区与追问
- 误区：哈希相同就说明子串一定相同。 可能碰撞，严谨场景要二次校验或双哈希。
- 误区：Rolling Hash 只能用于字符串匹配。 它也可用于子串去重、回文检测辅助、重复片段查找。
- 误区：base 和 mod 随便选都一样。 不好的参数会增加碰撞或分布问题。
- 追问：为什么要预处理 base 的幂？ 计算子串时需要
base^(r-l)抵消左侧贡献。 - 追问：复杂度是多少？ 预处理 O(n)，之后每次取子串 hash 是 O(1)。
八、加强记忆
Rolling Hash 的本质是“字符串版前缀和”，只是加法换成了带 base 的多项式。前缀哈希负责快速取任意片段，滑动更新负责快速移动窗口，碰撞风险则提醒你不能把 hash 当成绝对证明。