当前位置：首页 > C++ > 正文

C++字符串哈希详解（从零开始掌握字符串哈希算法）

主机测评网
C++
2025-12-08
191

在C++编程中，字符串哈希是一种非常实用的技术，尤其在处理大量字符串匹配、判重或快速查找时能显著提升效率。本教程将带你从基础概念出发，一步步理解并实现C++字符串哈希算法，即使你是编程小白也能轻松上手！

什么是字符串哈希？

字符串哈希就是将一个任意长度的字符串通过某种哈希函数转换成一个固定长度的整数（通常是一个大整数）。这个整数可以作为该字符串的“指纹”，用于快速比较、存储或查找。

C++字符串哈希详解（从零开始掌握字符串哈希算法） C++字符串哈希字符串哈希算法 C++哈希函数字符串处理C++ 第1张

为什么需要字符串哈希？

想象一下，如果你要判断两个很长的字符串是否相等，直接逐字符比较的时间复杂度是 O(n)。但如果先计算它们的哈希值，再比较哈希值，时间复杂度就降到了 O(1)（忽略哈希冲突的情况）。这就是字符串处理C++中常用哈希的原因之一。

常见的字符串哈希算法

最经典且广泛使用的字符串哈希方法是多项式滚动哈希（Polynomial Rolling Hash），其公式如下：

hash(s) = (s[0] * p^0 + s[1] * p^1 + s[2] * p^2 + ... + s[n-1] * p^(n-1)) % mod

其中：

p 是一个质数（通常取 131、13331 等）
mod 是一个大质数（如 1e9+7 或 2^64）
s[i] 是字符串第 i 个字符的 ASCII 值

C++ 实现字符串哈希

下面是一个完整的 C++ 示例，展示如何为字符串计算哈希值：

#include <iostream>#include <string>using namespace std;typedef unsigned long long ULL; // 使用 unsigned long long 自动取模 2^64const ULL P = 131; // 哈希基数ULL stringHash(const string& s) {    ULL hash = 0;    for (char c : s) {        hash = hash * P + c;    }    return hash;}int main() {    string str1 = "hello";    string str2 = "world";    string str3 = "hello";    ULL h2 = stringHash(str1);    ULL h2 = stringHash(str2);    ULL h3 = stringHash(str3);    cout << "hash('hello') = " << h2 << endl;    cout << "hash('world') = " << h2 << endl;    cout << "hash('hello') again = " << h3 << endl;    if (h2 == h3) {        cout << "str1 和 str3 哈希值相同，可能是相同字符串！" << endl;    }    return 0;}

这段代码使用了 unsigned long long 类型，它会在溢出时自动对 2^64 取模，避免了手动取模的开销，同时保持了良好的分布性。