给字符串做数字指纹——字符串哈希（滚动哈希）详解

这到底是个什么玩意？

你有没有遇到过这种情况：老师让你们从一大叠作业本里找出姓“李”的同学的本子。最笨的方法就是一本一本地看名字，一个字一个字地比，费时费力。但假如每个同学都有一个学号，你只需要扫一眼学号，就能立刻知道是不是他。字符串哈希（滚动哈希）就是干这个的——它把任何一串字符（比如名字、句子、密码）转换成一个整数，就像给每个字符串发了一个独一无二的学号。以后要比较两个字符串是否相等，直接比较它们的学号（哈希值）就行，速度飞快，就跟比较两个数字一样简单。

这个技术特别适合处理大量字符串比较的场景，比如在长文章里找某个单词、检查两段代码是否一样、或者判断两个文件是否相同。

哈希到底是什么？生活中的类比

“哈希”这个词听起来很神秘，其实它就是“映射”的意思。想象一下，学校给每个学生分配一个学号：张三 → 001，李四 → 002，王五 → 003。学号就是学生名字的“哈希值”。但学号是老师随便编的，而字符串哈希是用一个固定的数学规则算出来的。

更贴近计算机的例子是条形码：每种商品都有一个唯一的条形码数字，超市扫码枪扫一下，就知道是薯片还是可乐。条形码就是商品的哈希值。

在字符串哈希里，我们给每个字符（字母、数字、符号）也分配一个数字（比如ASCII码，A=65，B=66，空格=32），然后通过一个公式，把这些数字组合成一个更大的整数。这样，整个字符串就有了一个唯一的“数字指纹”。

滚动哈希的原理：把字符串看成数字

滚动哈希（Rolling Hash）也叫“多项式哈希”。它把字符串看作是一个base进制数（比如十进制、二十六进制）。每个字符就是一位数字，它的“权重”取决于它在字符串中的位置。

假设我们有字符串 s = "ABC"。我们选择 base = 131（一个常用的基数），模数 mod = 1e9+7。字符用ASCII码：A=65, B=66, C=67。

哈希值的计算公式是：

hash("ABC") = (65 * base^2 + 66 * base^1 + 67 * base^0) % mod

这就好比十进制数 312 = 3×10² + 1×10¹ + 2×10⁰。只不过我们的基数是131，而不是10。因为131比所有字符的ASCII码（最大127）都大，所以这个“进制数”不容易产生歧义。

为什么叫“滚动”？

因为当我们有一个长字符串时，经常需要滑动窗口比较子串。比如在"ABABAB"中找"ABA"，我们需要快速地算出每个长度为3的窗口的哈希值。如果每次都重新算一遍，很慢。滚动哈希有一个绝招：通过前缀哈希，能在O(1)时间内算出任意子串的哈希。就像坐滚轮滑梯一样，从一个位置“滚”到下一个位置，只需做一些加减乘除，不用从零开始。

前缀哈希：快速求任意子串的数字指纹

我们先计算整个字符串所有前缀的哈希。定义：

prefix[0] = 0
prefix[i] = (s[0]*base^(i-1) + s[1]*base^(i-2) + ... + s[i-1]*base^0) % mod

其中 prefix[i] 就是从开头到第 i-1 个字符（共 i 个字符）的哈希。注意下标：prefix[1] 是第一个字符的哈希，prefix[2] 是前两个字符的哈希，依此类推。

有了前缀哈希，想要得到子串 s[l..r]（从0开始，长度 len = r-l+1）的哈希，可以用这个公式：

hash(l, r) = prefix[r+1] - prefix[l] * base^len

然后取模，如果出现负数，加上模数。

这个公式的原理其实很简单：prefix[r+1] 包含了从0到r的所有字符，prefix[l] 包含了从0到l-1的所有字符。把 prefix[l] 向左移动 len 位（乘以 base^len），就相当于减去了开头那部分，剩下正好是子串。

举个例子：字符串 "HELLO"

我们手动算一下（假设 base=10, mod=1000000007，仅用于演示）：字符：H(72), E(69), L(76), L(76), O(79)

计算前缀：

prefix[1] = 72
prefix[2] = 72*10 + 69 = 789
prefix[3] = 789*10 + 76 = 7966
prefix[4] = 7966*10 + 76 = 79736
prefix[5] = 79736*10 + 79 = 797439

现在想求子串 "ELL"（下标1到3，即E,L,L）： len = 3，base^3 = 1000 hash(1,3) = prefix[4] - prefix[1] * 1000 = 79736 - 721000 = 79736 - 72000 = 7736 直接算：E=69, L=76, L=76 → 69100 + 76*10 + 76 = 6900+760+76=7736 ✓

哈希冲突：有人“撞号”了怎么办？

就像世界上可能有两个人恰好同一天生日一样，两个不同的字符串也可能算出相同的哈希值。这叫做哈希冲突。冲突了怎么办？其实没关系，因为我们只要把概率降到非常低，就可以放心使用。常用办法有：

双哈希：用两个不同的模数（比如10^9+7和10^9+9）算两个哈希值，只有两个都相等才认为字符串相等。这样冲突概率几乎为0。
大模数自然溢出：在C++中，使用unsigned long long类型，让它自动溢出（相当于模2^64）。速度快，冲突概率也很低。
选择一个合适的基数和模数：基数最好大于字符集大小（比如131、13331），模数用大质数（10^9+7、10^9+9）。

对于中小学编程竞赛，一般用单哈希取大模数就足够了；如果想万无一失，用双哈希。

新手容易犯的几个错误（避坑指南）

忘记取模导致负数：公式 prefix[r+1] - prefix[l] * base^len 可能为负，一定要加上模数再取模。很多同学直接取模，负值取模在C++里还是负的，会出错。正确写法：(prefix[r+1] - prefix[l] * powBase[len] % mod + mod) % mod。
下标搞混了：prefix数组长度是 n+1，下标从0开始。prefix[i]是前i个字符的哈希（字符索引0到i-1）。求子串[l,r]时，记得用prefix[r+1] - prefix[l]。很多新手会写成prefix[r] - prefix[l-1]，如果l=0就出问题了。
没有预计算base的幂次：每次求子串哈希都重新计算base^len，会非常慢。应该提前算好 powBase[0..n]，用空间换时间。
基数选得太小：比如用26（小写字母集），但字符串可能包含大写字母、数字等，就会容易冲突。建议用131、13331这类大质数。
模数选得不合适：不要用2^32或2^64（自然溢出可以但注意风险），也不要选合数（容易找到冲突）。大质数如1e9+7、1e9+9是经典选择。

完整代码示例：不仅比较子串，还能查找所有匹配位置

下面我们用滚动哈希实现一个经典问题：在长字符串 text 中查找所有与模式串 pattern 相同的子串，并输出起始位置。

C++ 实现（含详细中文注释）

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class StringHash {
private:
    string s;
    int n;
    long long base, mod;              // 基数和模数
    vector<long long> prefix, powBase; // 前缀哈希数组，base幂次数组
public:
    // 构造函数：初始化字符串及相关数组
    StringHash(const string &str, long long b = 131, long long m = 1e9+7) 
        : s(str), base(b), mod(m) {
        n = s.size();
        prefix.resize(n + 1, 0);
        powBase.resize(n + 1, 1);
        // 预计算base的幂次
        for (int i = 1; i <= n; i++) {
            powBase[i] = powBase[i-1] * base % mod;
        }
        // 计算前缀哈希
        for (int i = 1; i <= n; i++) {
            prefix[i] = (prefix[i-1] * base + s[i-1]) % mod;
        }
    }
    // 获取子串哈希 [l, r] 左闭右闭，下标从0开始
    long long getHash(int l, int r) {
        if (l > r) return 0;
        long long value = (prefix[r+1] - prefix[l] * powBase[r-l+1] % mod + mod) % mod;
        return value;
    }
    // 判断两个子串是否相等
    bool equalSub(int l1, int r1, int l2, int r2) {
        if (r1 - l1 != r2 - l2) return false;
        return getHash(l1, r1) == getHash(l2, r2);
    }
};

// 扩展用法：在text中查找所有与pattern匹配的子串起始位置
vector<int> findAllMatches(const string &text, const string &pattern) {
    int n = text.size(), m = pattern.size();
    if (m == 0 || m > n) return {};
    StringHash textHash(text);
    StringHash patternHash(pattern);
    long long patternVal = patternHash.getHash(0, m-1);
    vector<int> result;
    for (int i = 0; i + m - 1 < n; i++) {
        if (textHash.getHash(i, i+m-1) == patternVal) {
            result.push_back(i);  // 记录匹配的起始位置
        }
    }
    return result;
}

int main() {
    string text = "ABABAB";
    string pattern = "ABA";
    StringHash sh(text);
    // 测试：比较子串"ABA" (0-2) 和 "BAB" (1-3)
    cout << "子串[0,2]哈希: " << sh.getHash(0,2) << endl;
    cout << "子串[1,3]哈希: " << sh.getHash(1,3) << endl;
    cout << "子串[0,2]和[1,3]相等? " << (sh.equalSub(0,2,1,3) ? "是" : "否") << endl;
    // 查找所有"ABA"出现的位置
    vector<int> matches = findAllMatches(text, pattern);
    cout << "模式串 \"" << pattern << "\" 在 \"" << text << "\" 中出现的位置: ";
    for (int pos : matches) cout << pos << " ";
    cout << endl;
    return 0;
}

运行结果：

子串[0,2]哈希: 1310720
子串[1,3]哈希: 1310720
子串[0,2]和[1,3]相等? 是
模式串 "ABA" 在 "ABABAB" 中出现的位置: 0 2 4

Python 实现

class StringHash:
    def __init__(self, s, base=131, mod=10**9+7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod
        self.prefix = [0] * (self.n + 1)  # 前缀哈希数组，长度n+1
        self.powBase = [1] * (self.n + 1) # base的幂次数组
        # 预计算base的幂次
        for i in range(1, self.n + 1):
            self.powBase[i] = (self.powBase[i-1] * base) % mod
        # 计算前缀哈希
        for i in range(1, self.n + 1):
            # ord(s[i-1]) 取字符的ASCII码
            self.prefix[i] = (self.prefix[i-1] * base + ord(s[i-1])) % mod

    def get_hash(self, l, r):
        """获取子串哈希 [l, r] 左闭右闭"""
        if l > r:
            return 0
        # 公式：prefix[r+1] - prefix[l] * base^(r-l+1)
        value = (self.prefix[r+1] - self.prefix[l] * self.powBase[r-l+1]) % self.mod
        return value

    def equal_sub(self, l1, r1, l2, r2):
        """判断两个子串是否相等"""
        if r1 - l1 != r2 - l2:
            return False
        return self.get_hash(l1, r1) == self.get_hash(l2, r2)

# 扩展：在text中查找所有与pattern匹配的子串起始位置
def find_all_matches(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    text_hash = StringHash(text)
    pattern_hash = StringHash(pattern)
    pattern_val = pattern_hash.get_hash(0, m-1)
    result = []
    for i in range(n - m + 1):
        if text_hash.get_hash(i, i+m-1) == pattern_val:
            result.append(i)
    return result

# 测试
text = "ABABAB"
pattern = "ABA"
sh = StringHash(text)
print("子串[0,2]哈希:", sh.get_hash(0,2))
print("子串[1,3]哈希:", sh.get_hash(1,3))
print("子串[0,2]和[1,3]相等?", sh.equal_sub(0,2,1,3))
matches = find_all_matches(text, pattern)
print(f"模式串 \"{pattern}\" 在 \"{text}\" 中出现的位置: {matches}")

实际应用场景（学了能干什么？）

子串匹配：在长文章中查找某个单词的所有出现位置，比逐字符比较快很多。
检测重复子串：判断一段文字中是否有重复的句子（比如查重系统）。
回文判断：快速判断一个子串是不是回文（正反哈希值相同）。
文件校验：计算大文件的哈希值，比较两个文件是否一致。
密码存储：网站不会存你的明文密码，而是存哈希值，登录时比对哈希（当然用的是更安全的哈希算法）。

总结与拓展

要点	说明
核心思想	把字符串看作base进制数，通过多项式计算哈希值
滚动哈希	利用前缀哈希O(1)求任意子串哈希
冲突处理	双哈希、大模数、自然溢出
常用参数	base=131/13331，mod=1e9+7/1e9+9
注意	下标别搞错，取模避免负数

掌握了字符串哈希，你就可以快速解决很多字符串问题。如果想学更高级的算法，可以进一步了解：

KMP算法：另一种高效子串匹配方法，不依赖哈希，没有冲突。
后缀数组：处理更多字符串问题的利器（如最长公共子串）。
Rabin-Karp算法：基于滚动哈希的子串匹配，就是我们刚才实现的。

滚动哈希就像一把万能钥匙，用好了能打开很多大门。现在，你可以试着用它来解决一个实际问题：比如，检查你写的作文里有没有连续重复的句子！

字符串哈希（滚动哈希）：给字符串做数字指纹