滚动哈希（Rolling Hash）是一种 哈希函数，允许在 O(1) 时间内计算 相邻子串 的哈希值，而不需要重新遍历整个子串。它常用于字符串匹配、子串查找等问题，比如 Rabin-Karp 算法 就是基于滚动哈希的。
在说滚动哈希方法之前，先谈谈一般窗口内哈希值是如何计算的
例如对于字符串hello，那么哈希值是 h a s h C o d e ( h e l l o ) = ( h − a ) ∗ p o w ( 131 , 0 ) + ( e − a ) ∗ p o w ( 131 , 1 ) + ( l − a ) ∗ p o w ( 131 , 2 ) + ( l − a ) ∗ p o w ( 131 , 3 ) + ( o − a ) ∗ p o w ( 131 , 4 ) hashCode(hello)=(h-a)*pow(131, 0)+(e-a)*pow(131, 1)+(l-a)*pow(131, 2)+(l-a)*pow(131, 3)+(o-a)*pow(131,4) hashCode(hello)=(h−a)∗pow(131,0)+(e−a)∗pow(131,1)+(l−a)∗pow(131,2)+(l−a)∗pow(131,3)+(o−a)∗pow(131,4)
当然由于hash值可能会非常大，所以通常还会进行取模
其中，131 是一个常用的进制基数，a 是字符的起始偏移量（例如，‘a’ 可以为 97），pow(131, i) 表示基数的幂。由于哈希值可能会非常大，通常还会对其进行取模操作，常见的模数 MOD 可能是一个大质数，如 1000000007，用于避免溢出。
滚动哈希的核心概念是什么？
一言以蔽之，滚动哈希即利用前缀和思想简化求取窗口哈希值的方法
请看下面的代码
hashCode(l, r) = ((hash[r] - hash[l - 1] * pow(b, r - l + 1)) % p + p) % p
-
hash[r] - hash[l - 1] 实际上表示从位置 l 到位置 r 这段子串的哈希值，但直接这样做会有问题，因为哈希值是按位数的权重计算的，低位字符的影响会被高位字符的影响掩盖。所以，我们还需要做一个调整。
-
由于哈希是按字符的位权计算的，即字符在字符串中的位置越靠后，其在哈希值中的贡献越大（权重越大）。为了从整体哈希值中去除不需要的部分，需要用到一个幂 pow(b, r - l + 1)，其中 b 是基数，r - l + 1 是子串长度
-
哈希值很容易溢出，因此我们通常对其进行取模运算，这里使用了模数 p。
由于计算过程中可能会出现负数，我们需要确保取模后的值是非负的，因此加上了 + p，然后再对 p 取模。
完整的实现
const (B = 31 // 进制MOD = 1000000007 // 取模
)func rollingHash(s string, L int) []int {n := len(s)if n < L {return []int{} }hashes := make([]int, n-L+1)hash, power := 0, 1// 计算第一个子串的hash值for i := 0; i < L; i++ {hash = (hash*B + int(s[i]-'a'+1)) % MODif i < L-1 {power = (power * B) % MOD}}hashes[0] = hash// 滚动计算后续子串的hash值for i := 1; i <= n-L; i++ {// 使用滚动哈希公式计算新子串的哈希值hash = (hash - (int(s[i-1]-'a'+1) * power % MOD) + MOD) % MODhash = (hash * B + int(s[i+L-1]-'a'+1)) % MODhashes[i] = hash}return hashes
}
为什么需要滚动哈希？
- 文件对比：查找两个文件的相似部分
- 数据去重：发现重复的数据片段
- 文件分块：将文件分成小块进行存储