【算法基础篇】（二十五）数据结构天花板！字符串哈希手把手教学：从原理到刷题，冲突率近乎为 0 的神仙算法

_OP_CHEN

发布于 2026-01-14 11:27:04

990

文章被收录于专栏：C++C++

前言

在编程世界里，字符串处理是绕不开的核心场景 —— 判断两个字符串是否相等、统计不同字符串的个数、快速查询子串是否匹配…… 这些需求看似简单，实则暗藏性能玄机。如果用暴力匹配，时间复杂度动辄 O (n*m)，面对大规模数据时直接原地 “翻车”。而今天要给大家安利的字符串哈希，堪称解决这类问题的 “核武器”—— 它能把字符串映射成整数，将字符串操作转化为高效的整数运算，时间复杂度直接降到 O (n) 预处理、O (1) 查询，冲突率低到可以忽略不计。不管你是算法入门的新手，还是正在备战面试的 “刷题人”，掌握字符串哈希都能让你在处理字符串问题时如虎添翼。这篇文章就从原理、实现、优化到实战，带你全方位吃透字符串哈希，看完直接上手刷题！

一、先搞懂：字符串哈希到底是什么？

在正式学习之前，我们先解决一个核心问题：字符串哈希究竟是个啥？

1.1 哈希的核心思想

哈希（Hash），简单来说就是 “映射”—— 把一个复杂的东西（比如字符串、大整数）通过某个规则，转换成一个简单的、固定长度的值（通常是整数）。这个转换规则就是哈希函数，转换后的值就是哈希值。

举个生活中的例子：我们给每个同学分配一个学号，通过学号就能快速找到对应的同学，而不用记住同学的全名、身高、体重等所有信息。这里的 “学号分配规则” 就是哈希函数，“学号” 就是哈希值。

1.2 字符串哈希的本质

字符串哈希，就是专门针对字符串设计的哈希方式 —— 将任意长度的字符串，通过哈希函数映射成一个整数。这样一来，我们判断两个字符串是否相等，就不用逐字符比较了，直接比较它们的哈希值即可；查询子串是否存在，也能通过哈希值快速判断。

比如字符串 “abc”，通过哈希函数可能映射成整数 123456，字符串 “abd” 映射成 123457，我们只要比较这两个整数，就能瞬间知道 “abc” 和 “abd” 是不同的字符串。

1.3 为什么需要字符串哈希？

可能有人会问：逐字符比较字符串也能解决问题，为什么非要用哈希？

我们用一组数据说话：

暴力逐字符比较两个长度为 m 的字符串：时间复杂度 O (m)
字符串哈希预处理：时间复杂度 O (n)（n 为字符串总长度）
哈希值比较：时间复杂度 O (1)
子串哈希查询：时间复杂度 O (1)

如果只是比较两个字符串，两者差距不大，但如果是以下场景，字符串哈希的优势就会被无限放大：

有 N 个字符串，统计不同字符串的个数（暴力需要 O (N^2m)，哈希只需 O (Nn + NlogN)）
一个长字符串，需要查询 M 次子串是否匹配（暴力需要 O (M*L)，哈希只需 O (n + M)，L 为查询子串长度）
处理超长字符串（比如长度 1e6），暴力会超时，哈希轻松应对

而且字符串哈希的冲突率极低，只要哈希函数设计合理，几乎不会出现 “不同字符串映射出相同哈希值” 的情况，可靠性拉满。

二、原理拆解：字符串哈希函数怎么设计？

字符串哈希的核心是哈希函数的设计 —— 设计得好，冲突率低、计算快；设计得不好，冲突频发，结果全错。

2.1 核心思路：把字符串当成 “p 进制数”

我们知道，十进制数 “123” 可以表示为：110² + 210¹ + 3*10⁰。字符串哈希的核心思路，就是把字符串看作一个 “p 进制数”，每个字符对应一个数字，然后计算这个 p 进制数的 “十进制值”（或其他进制值），这个值就是字符串的哈希值。

比如字符串 “abc”，假设 a=1，b=2，c=3，p=131（常用质数），那么：哈希值 = 1131² + 2131¹ + 3131⁰ = 117161 + 2*131 + 3 = 17161 + 262 + 3 = 17426

这样一来，每个字符串都能唯一对应一个整数（理论上）。

2.2 字符映射规则

在 C++ 中，字符本质上是 ASCII 码，所以我们可以直接用字符的 ASCII 码作为它对应的数字。比如：

'a' 的 ASCII 码是 97，对应数字 97
'A' 的 ASCII 码是 65，对应数字 65
'0' 的 ASCII 码是 48，对应数字 48

这样做的好处是不用手动给每个字符分配数字，直接用 ASCII 码即可，既方便又能避免字符冲突（大小写字母、数字的 ASCII 码都是不同的）。

2.3 为什么选择质数 p？

哈希函数中，p 是一个关键参数，通常选择质数，常用的有 131、13331、911 等。为什么选质数？

减少冲突：质数的因子只有 1 和它本身，能最大限度避免不同字符串因为进制的因子特性而映射出相同的哈希值。
分布均匀：质数进制能让哈希值的分布更均匀，进一步降低冲突概率。

经过实践验证，p=131 或 13331 时，冲突率最低，几乎可以忽略不计，所以我们后续的代码中，默认使用 p=13331（性能更优）。

2.4 哈希值溢出问题：利用 unsigned long long 自动取模

如果字符串很长，比如长度 1e6，那么 p 进制数会非常大，远远超过 64 位整数的存储范围，这时候就会出现溢出。

怎么解决？答案是利用 unsigned long long 的自动溢出特性。

在 C++ 中，unsigned long long 是无符号 64 位整数，取值范围是 0~2⁶⁴-1。当计算结果超过这个范围时，会自动对 2⁶⁴取模，相当于免费帮我们做了取模操作，既避免了溢出，又简化了代码。

这也是字符串哈希的一个小技巧 —— 不用手动写取模运算，直接用 unsigned long long 存储哈希值即可。

2.5 哈希冲突：如何处理？

虽然我们选择了质数 p，又用了 unsigned long long 自动取模，但理论上还是存在冲突的可能（不同字符串哈希值相同）。

怎么处理冲突？有两种方案：

双哈希验证：用两个不同的 p 值（比如 131 和 13331）和两个不同的模（比如 2⁶⁴和 1e9+7），对同一个字符串计算两个哈希值，只有当两个哈希值都相等时，才认为字符串相等。这种方式能把冲突率降到几乎为 0，但会增加一点代码量和计算时间。
实际应用中，单哈希（p=13331 + unsigned long long）已经足够应对绝大多数场景（包括算法竞赛），冲突率低到可以忽略，所以我们主要讲解单哈希的实现。

三、关键优化：前缀哈希数组（解决子串查询问题）

如果我们只需要比较整个字符串的哈希值，直接计算每个字符串的哈希值即可，但如果需要查询子串的哈希值（比如查询 “abcdef” 中 “cde” 的哈希值），直接计算子串的哈希值会很麻烦。

这时候就需要用到前缀哈希数组—— 通过预处理，存储字符串每个前缀的哈希值，然后利用前缀哈希值快速计算任意子串的哈希值。

3.1 前缀哈希数组的定义

假设我们有字符串 s，长度为 n，定义：

f [i]：表示字符串 s 的前 i 个字符组成的前缀的哈希值（s [1] s [2]...s [i]）
p [i]：表示 p 的 i 次方（用于后续计算子串哈希值）

注意：这里的字符串下标从 1 开始（方便前缀哈希的计算，避免处理 0 的情况）。

3.2 前缀哈希数组的计算

根据 p 进制的定义，前缀哈希数组的递推公式为：f [i] = f [i-1] * p + s [i]

解释：前 i 个字符的哈希值 = 前 i-1 个字符的哈希值 * p（相当于把前 i-1 个字符的 p 进制数左移一位，空出最后一位） + 第 i 个字符的 ASCII 码。

而 p [i] 的递推公式为：p [0] = 1（p 的 0 次方等于 1），p [i] = p [i-1] * p。

比如字符串 “abc”（下标 1~3）：

f[0] = 0
p[0] = 1
f[1] = f[0] * 13331 + 'a' = 0 * 13331 + 97 = 97
p[1] = p[0] * 13331 = 13331
f[2] = f[1] * 13331 + 'b' = 97 * 13331 + 98 = 1293107 + 98 = 1293205
p[2] = p[1] * 13331 = 13331 * 13331 = 177715561
f[3] = f[2] * 13331 + 'c' = 1293205 * 13331 + 99 = 17240715855 + 99 = 17240715954

3.3 子串哈希值的计算

有了前缀哈希数组 f 和 p 数组，我们如何计算子串 s [l...r]（从第 l 个字符到第 r 个字符）的哈希值？

我们可以把这个问题转化为 p 进制数的计算：

前 r 个字符的哈希值 f [r]，相当于 “前 l-1 个字符的哈希值 * p^(r-l+1) + 子串 s [l...r] 的哈希值”
因此，子串 s [l...r] 的哈希值 = f [r] - f [l-1] * p [r - l + 1]

举个例子：计算 “abcde” 中 “cde”（l=3，r=5）的哈希值：

f[5] = ap⁴ + bp³ + cp² + dp + e
f[2] = a*p + b
f[2] * p^(5-3+1) = (ap + b) * p³ = ap⁴ + b*p³
子串哈希值 = f [5] - f [2]p³ = cp² + d*p + e，正好是 “cde” 的哈希值

这个公式是字符串哈希的核心，一定要牢牢记住！

3.4 前缀哈希数组的初始化代码

我们把前缀哈希数组的初始化封装成一个函数，方便后续使用：

#include <iostream>
#include <string>
using namespace std;

typedef unsigned long long ULL; // 无符号64位整数，自动溢出取模
const int N = 1e6 + 10; // 字符串最大长度（根据题目调整）
const int P = 13331; // 进制数（质数）

ULL f[N]; // 前缀哈希数组
ULL p[N]; // p的i次方数组
string s; // 输入字符串

// 初始化前缀哈希数组和p数组
void init_hash() {
    int n = s.size();
    p[0] = 1;
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i-1] * P + s[i-1]; // s是0下标，所以s[i-1]对应第i个字符
        p[i] = p[i-1] * P;
    }
}

// 查询子串s[l...r]的哈希值（l和r是1-based下标）
ULL get_hash(int l, int r) {
    return f[r] - f[l-1] * p[r - l + 1];
}

注意：C++ 中的 string 是 0 下标开头的，而我们的前缀哈希数组是 1 下标开头的，所以在计算 f [i] 时，用 s [i-1] 获取第 i 个字符。

四、基础应用：3 个经典场景实战

学会了字符串哈希的原理和实现，我们来看看它的经典应用场景。

4.1 场景 1：统计不同字符串的个数

问题描述：给定 N 个字符串，统计其中不同字符串的个数。

解题思路：

对每个字符串计算哈希值（不需要前缀哈希，直接计算整个字符串的哈希值）
把所有哈希值存入一个数组，排序后去重
去重后的数组长度，就是不同字符串的个数

完整代码：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

typedef unsigned long long ULL;
const int P = 13331;
const int N = 1e4 + 10; // 字符串个数上限

ULL hash_array[N]; // 存储所有字符串的哈希值
int n; // 字符串个数

// 计算单个字符串的哈希值
ULL get_hash(string& s) {
    ULL res = 0;
    for (char ch : s) {
        res = res * P + ch;
    }
    return res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        hash_array[i] = get_hash(s);
    }
    // 排序后去重
    sort(hash_array, hash_array + n);
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (hash_array[i] != hash_array[i-1]) {
            cnt++;
        }
    }
    cout << "不同字符串的个数：" << cnt << endl;
    return 0;
}

测试用例：输入：5abcaaaaabcabcc12345

输出：不同字符串的个数：4

代码解释：

get_hash 函数：计算单个字符串的哈希值，遍历字符串的每个字符，按照 p 进制规则累加计算。
主函数：读取 N 个字符串，计算每个字符串的哈希值，存入数组，排序后去重统计个数。

4.2 场景 2：查询两个子串是否相等

问题描述：给定一个字符串 S，以及 M 次查询，每次查询给出两个区间 [l1, r1] 和 [l2, r2]，判断 S [l1..r1] 和 S [l2..r2] 是否相等。

解题思路：

初始化前缀哈希数组 f 和 p 数组
对于每次查询，计算两个子串的哈希值
如果两个哈希值相等，则子串相等；否则不相等

完整代码：

#include <iostream>
#include <string>
using namespace std;

typedef unsigned long long ULL;
const int N = 1e6 + 10;
const int P = 13331;

ULL f[N]; // 前缀哈希数组
ULL p[N]; // p的i次方数组
string s;
int m; // 查询次数

// 初始化前缀哈希和p数组
void init_hash() {
    int n = s.size();
    p[0] = 1;
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i-1] * P + s[i-1];
        p[i] = p[i-1] * P;
    }
}

// 查询子串[l..r]的哈希值（1-based）
ULL get_hash(int l, int r) {
    return f[r] - f[l-1] * p[r - l + 1];
}

int main() {
    cin >> s >> m;
    init_hash();
    while (m--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        // 计算两个子串的哈希值
        ULL h1 = get_hash(l1, r1);
        ULL h2 = get_hash(l2, r2);
        if (h1 == h2) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

测试用例：输入：aabbaabb31 3 5 71 3 6 81 2 1 2

输出：YesNoYes

代码解释：

init_hash 函数：初始化前缀哈希数组 f 和 p 数组，注意字符串是 0 下标，前缀哈希是 1 下标。
get_hash 函数：根据公式计算子串哈希值。
主函数：读取字符串和查询次数，每次查询计算两个子串的哈希值并比较。

4.3 场景 3：判断字符串是否为回文串（扩展应用）

问题描述：给定一个字符串 S，判断它是否为回文串（正读和反读都一样）。

解题思路：

计算原字符串的前缀哈希值 f1
计算反转字符串的前缀哈希值 f2
原字符串的哈希值 = 反转字符串的哈希值，则原字符串是回文串

或者更严谨地：原字符串的子串 S [l..r] 的哈希值，等于反转字符串的子串 S'[n-r+1..n-l+1] 的哈希值（n 为字符串长度），则 S [l..r] 是回文串。

完整代码：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

typedef unsigned long long ULL;
const int N = 1e6 + 10;
const int P = 13331;

ULL f1[N]; // 原字符串的前缀哈希
ULL f2[N]; // 反转字符串的前缀哈希
ULL p[N];
string s, rev_s;
int n;

// 初始化哈希数组
void init_hash() {
    p[0] = 1;
    // 原字符串的前缀哈希
    for (int i = 1; i <= n; i++) {
        f1[i] = f1[i-1] * P + s[i-1];
        p[i] = p[i-1] * P;
    }
    // 反转字符串的前缀哈希
    for (int i = 1; i <= n; i++) {
        f2[i] = f2[i-1] * P + rev_s[i-1];
    }
}

// 获取原字符串子串[l..r]的哈希值（1-based）
ULL get_hash1(int l, int r) {
    return f1[r] - f1[l-1] * p[r - l + 1];
}

// 获取反转字符串子串[l..r]的哈希值（1-based）
ULL get_hash2(int l, int r) {
    return f2[r] - f2[l-1] * p[r - l + 1];
}

// 判断原字符串是否为回文串
bool is_palindrome() {
    // 原字符串的哈希值应该等于反转字符串的哈希值
    return get_hash1(1, n) == get_hash2(1, n);
}

// 判断原字符串子串[l..r]是否为回文串
bool is_sub_palindrome(int l, int r) {
    // 反转字符串中对应的子串是[n-r+1 .. n-l+1]
    int rev_l = n - r + 1;
    int rev_r = n - l + 1;
    return get_hash1(l, r) == get_hash2(rev_l, rev_r);
}

int main() {
    cin >> s;
    n = s.size();
    rev_s = s;
    reverse(rev_s.begin(), rev_s.end()); // 反转字符串
    init_hash();
    
    // 判断整个字符串是否为回文串
    if (is_palindrome()) {
        cout << "整个字符串是回文串" << endl;
    } else {
        cout << "整个字符串不是回文串" << endl;
    }
    
    // 测试子串是否为回文串
    int l, r;
    cin >> l >> r;
    if (is_sub_palindrome(l, r)) {
        cout << "子串[" << l << "," << r << "]是回文串" << endl;
    } else {
        cout << "子串[" << l << "," << r << "]不是回文串" << endl;
    }
    
    return 0;
}

测试用例：输入：abba2 3

输出：整个字符串是回文串子串 [2,3] 是回文串

代码解释：

反转字符串后，原字符串的回文子串对应反转字符串的相同哈希值子串。
通过比较原字符串子串和反转字符串对应子串的哈希值，判断是否为回文串。

五、进阶实战：洛谷经典题目刷题

理论学得差不多了，我们来刷两道洛谷的经典题目，巩固一下知识点。

5.1 题目 1：洛谷 P3370 【模板】字符串哈希

题目链接：https://www.luogu.com.cn/problem/P3370

题目描述：给定 N 个字符串，请求出 N 个字符串中共有多少个不同的字符串。

解题思路：和我们之前讲的 “统计不同字符串的个数” 完全一致，直接套用代码即可。

AC 代码：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

typedef unsigned long long ULL;
const int P = 13331;
const int N = 1e4 + 10;

ULL a[N];
int n;

ULL get_hash(string& s) {
    ULL res = 0;
    for (char ch : s) {
        res = res * P + ch;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); // 加速输入输出
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        a[i] = get_hash(s);
    }
    sort(a, a + n);
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i-1]) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

注意：因为 N 可能达到 1e4，每个字符串长度可能达到 1e3，所以用 ios::sync_with_stdio (false); 和 cin.tie (0); 加速输入输出，避免超时。

5.2 题目 2：洛谷 P10468 兔子与兔子

题目链接：https://www.luogu.com.cn/problem/P10468

题目描述：给定一个 DNA 字符串 S，有 m 次询问，每次询问两个区间 [l1, r1] 和 [l2, r2]，判断这两个区间的 DNA 序列是否相同。

解题思路：前缀哈希数组 + 子串哈希查询，直接套用场景 2 的代码。

AC 代码：

#include <iostream>
#include <string>
using namespace std;

typedef unsigned long long ULL;
const int N = 1e6 + 10;
const int P = 13331;

ULL f[N], p[N];
string s;
int m;

void init_hash() {
    int n = s.size();
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i-1] * P + s[i-1];
        p[i] = p[i-1] * P;
    }
}

ULL get_hash(int l, int r) {
    return f[r] - f[l-1] * p[r - l + 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s >> m;
    init_hash();
    while (m--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        ULL h1 = get_hash(l1, r1);
        ULL h2 = get_hash(l2, r2);
        cout << (h1 == h2 ? "Yes" : "No") << endl;
    }
    return 0;
}

注意：字符串长度可能达到 1e6，所以数组大小要设置为 1e6+10，避免数组越界。

六、常见问题与注意事项

在使用字符串哈希时，容易出现一些细节问题，这里总结一下：

6.1 下标问题

前缀哈希数组 f 是 1 下标开头，而 C++ 的 string 是 0 下标开头，计算 f [i] 时要用 s [i-1]。
子串查询时，l 和 r 是 1-based 的，要确保输入的 l 和 r 在合法范围内（1<=l<=r<=n）。

6.2 数组大小

字符串长度可能达到 1e6 甚至更大，所以 f 数组和 p 数组的大小要足够大（比如 1e6+10、1e7+10），避免数组越界。
如果是多组测试数据，要注意数组的初始化，避免上一组数据的残留影响当前组。

6.3 输入输出加速

当字符串长度或查询次数较大时（比如 1e5、1e6），一定要用 ios::sync_with_stdio (false); 和 cin.tie (0); 加速输入输出，否则会超时。

6.4 哈希冲突处理

如果题目要求极高的准确性，可以使用双哈希（两个不同的 p 值和模），比如 p1=131，p2=13331，模 1=2^64，模 2=1e9+7，只有两个哈希值都相等时才认为字符串相等。

双哈希的 get_hash 函数示例：

typedef unsigned long long ULL;
const int P1 = 131;
const int P2 = 13331;
const int MOD = 1e9 + 7;

pair<ULL, int> get_hash(string& s) {
    ULL h1 = 0;
    int h2 = 0;
    for (char ch : s) {
        h1 = h1 * P1 + ch;
        h2 = (1LL * h2 * P2 + ch) % MOD;
    }
    return {h1, h2};
}