算法基础 -- 字符串哈希的原理与数值选定的剖析
字符串哈希的原理与数值选定的剖析
1. 什么是字符串哈希
字符串哈希（String Hashing）是一种用于快速比较字符串的技术，核心思想是：
将一个字符串
S
S
S 通过某种哈希函数转换为一个固定长度的整数（通常是一个较大的数模一个素数），然后用于字符串比较、搜索等场景。
应用场景：
- 字符串比较（例如，在字典或哈希表中查找字符串）
- 字符串去重（例如，检测重复子串）
- 子串匹配（例如，Rolling Hash 用于 Rabin-Karp 算法）
- 字符串相似性检测（例如，用于数据去重或查找相似文本）
2. 基本哈希函数：多项式哈希
最常用的字符串哈希方法是多项式哈希（Polynomial Hashing），公式如下：
H ( S ) = ( S 0 ⋅ P 0 + S 1 ⋅ P 1 + S 2 ⋅ P 2 + . . . + S n − 1 ⋅ P n − 1 ) m o d M H(S) = (S_0 \cdot P^0 + S_1 \cdot P^1 + S_2 \cdot P^2 + ... + S_{n-1} \cdot P^{n-1}) \mod M H(S)=(S0⋅P0+S1⋅P1+S2⋅P2+...+Sn−1⋅Pn−1)modM
其中：
- S i S_i Si 是字符串第 i i i 个字符的 ASCII 码值（或其他数值映射）
- P P P 是进制基数（Base）
- M M M 是取模素数（Modulus）
- n n n 是字符串长度
示例：
对于字符串 "abcd"，使用：
- P = 31 P = 31 P=31
- M = 1 0 9 + 7 M = 10^9+7 M=109+7 （一个大素数）
计算哈希值：
H
(
"
a
b
c
d
"
)
=
(
97
⋅
3
1
0
+
98
⋅
3
1
1
+
99
⋅
3
1
2
+
100
⋅
3
1
3
)
m
o
d
1
0
9
+
7
H("abcd") = (97 \cdot 31^0 + 98 \cdot 31^1 + 99 \cdot 31^2 + 100 \cdot 31^3) \mod 10^9+7
H("abcd")=(97⋅310+98⋅311+99⋅312+100⋅313)mod109+7
3. 进制基数 P P P 和模数 M M M 的选择原则
哈希算法的核心是选择合适的基数 P P P 和模数 M M M，以降低哈希冲突，提高计算效率。
(1) 进制基数 P P P 的选择
- 要求是一个质数（Prime Number）
- 质数能减少哈希碰撞，因为它们的因子较少，能让哈希值分布更均匀。
- 常见的选择有 31、37、53、101、131。
- 选择比字符集大小略大的质数
- 例如，ASCII 码字符（最大 127），可以选 31 或 37 作为 P P P。
- Unicode 字符（最大 65535），可以选 101、131。
(2) 模数 M M M 的选择
- 要求是一个大质数（通常接近
2
31
2^{31}
231 或
2
63
2^{63}
263）
- 避免哈希碰撞，提高安全性。
- 常见的取值：
- 1 0 9 + 7 10^9+7 109+7 （ 2 30 2^{30} 230 量级）
- 998244353 998244353 998244353（适用于模运算优化）
- 2 61 − 1 = 2305843009213693951 2^{61} - 1 = 2305843009213693951 261−1=2305843009213693951（更大范围，减少冲突）
- 避免与计算机整数溢出冲突
- 选择 1 0 9 + 7 10^9+7 109+7 之类的素数，可以确保 32-bit 系统不会溢出。
4. 滚动哈希（Rolling Hash）
在子串搜索（如 Rabin-Karp 算法）中，常常需要快速计算子串的哈希值。
朴素方法的时间复杂度是
O
(
n
m
)
O(nm)
O(nm)（其中
n
n
n 是文本长度，
m
m
m 是模式串长度），而滚动哈希能将其优化到
O
(
n
)
O(n)
O(n)。
滚动哈希公式（假设使用 P = 31 P=31 P=31 和 M = 1 0 9 + 7 M=10^9+7 M=109+7）：
给定字符串 “abcdef”，如果已知 “abc” 的哈希值 H ( " a b c " ) H("abc") H("abc")，计算 “bcd” 的哈希值：
H ( b c d ) = ( H ( a b c ) − S 0 ⋅ P 2 ) ⋅ P + S 3 m o d M H(bcd) = (H(abc) - S_0 \cdot P^2) \cdot P + S_3 \mod M H(bcd)=(H(abc)−S0⋅P2)⋅P+S3modM
实现：
long long rolling_hash(long long prev_hash, char out_char, char in_char, long long P, long long M, long long highest_pow) {
return ((prev_hash - (out_char * highest_pow) % M + M) * P + in_char) % M;
}
其中：
- p r e v _ h a s h prev\_hash prev_hash 是前一个子串的哈希值
- o u t _ c h a r out\_char out_char 是被移出的字符
- i n _ c h a r in\_char in_char 是新加入的字符
- h i g h e s t _ p o w highest\_pow highest_pow 是 P m − 1 P^{m-1} Pm−1（最高次幂预计算）
5. 哈希碰撞的处理
由于哈希函数不是 单射（Injective），不同的字符串可能映射到同一个哈希值，称为碰撞（Collision）。
(1) 使用多个哈希值（双哈希、多哈希）
- 采用不同的
P
P
P 和
M
M
M 计算多个哈希值，提高唯一性：
H 1 ( S ) = ( S 0 ⋅ 3 1 0 + S 1 ⋅ 3 1 1 + S 2 ⋅ 3 1 2 ) m o d 1 0 9 + 7 H_1(S) = (S_0 \cdot 31^0 + S_1 \cdot 31^1 + S_2 \cdot 31^2) \mod 10^9+7 H1(S)=(S0⋅310+S1⋅311+S2⋅312)mod109+7
H 2 ( S ) = ( S 0 ⋅ 3 7 0 + S 1 ⋅ 3 7 1 + S 2 ⋅ 3 7 2 ) m o d 998244353 H_2(S) = (S_0 \cdot 37^0 + S_1 \cdot 37^1 + S_2 \cdot 37^2) \mod 998244353 H2(S)=(S0⋅370+S1⋅371+S2⋅372)mod998244353 - 只有当 H 1 ( S ) H_1(S) H1(S) 和 H 2 ( S ) H_2(S) H2(S) 都相等，才认为字符串匹配。
(2) 选择更大的 M M M
- 2 61 − 1 2^{61}-1 261−1 这样的超大素数能减少碰撞的可能性。
(3) 使用拉比诺验算法（Rabin Test）
- 在哈希匹配后，使用额外的字符串比较来确认字符串是否完全相同。
6. 总结
- 多项式哈希 是最常用的字符串哈希方法，基于 P i P^i Pi 计算。
- P P P 选择质数（如 31, 37, 53），避免哈希碰撞。
- M M M 选择大质数（如 1 0 9 + 7 10^9+7 109+7），提高哈希分布的均匀性。
- 滚动哈希 让子串匹配更高效，时间复杂度从 O ( n m ) O(nm) O(nm) 降到 O ( n ) O(n) O(n)。
- 多哈希/大素数哈希 进一步减少哈希冲突。
7. 示例代码（C 实现）
#include <stdio.h>
#define P 31
#define M 1000000007
// 计算字符串的哈希值
unsigned long long compute_hash(const char *s) {
unsigned long long hash_value = 0;
unsigned long long p_pow = 1;
while (*s) {
hash_value = (hash_value + (*s - 'a' + 1) * p_pow) % M;
p_pow = (p_pow * P) % M;
s++;
}
return hash_value;
}
int main() {
const char *s = "hello";
printf("Hash Value: %llu\n", compute_hash(s));
return 0;
}
输出
Hash Value: 99162322
希望这篇讲解能让你彻底理解字符串哈希的原理与数值选定策略！如果有进一步的问题，欢迎继续讨论！