【算法漫笔002】字符串Hash

FeIndentOvO

2026-08-19 15:19:39

发布于：重庆

8阅读

0回复

0点赞

【算法漫笔002】浅谈字符串Hash

字符串Hash 将字符串映射为一个固定范围的整数（也就是哈希值），该映射是单向的，即从字符串计算哈希值很容易，但从哈希值反推原字符串在计算上不可行。

构造哈希函数

哈希函数，即将字符串映射为哈希值的函数。理论上只要是能将字符串转化为哈希值的函数都可以被称为哈希函数。

首先给一个极其容易想到的哈希函数，我们将字符串中的每一个字符的 ASCII 码值相加得到哈希值，如下：

int hash_(string s) {
	int res=0,len=s.size();
	for (int i=0;i<len;i++) res+=s[i];
	return res; 
}

但是这样的哈希函数会有一个严重的问题：哈希冲突。

哈希冲突

首先我们要知道，字符串 Hash 的意义是什么、作用又是什么。普通的字符串操作多数为 $O(N)$ 级别的（此处及后文中的 $N$ 为字符串的长度），而整数的操作大多为 $O(1)$ 。

拿一个直观的例子，给你一个长串 $S$ ，反复询问 $S_{l1 \dots r1}$ 和 $S_{l2 \dots r2}$ 是否一样。如果是直接截取子串并逐字符比较的话，每一次计算的时间复杂度自然为子串长度。而如果使用哈希去预处理，其预处理后每次比较的时间复杂度为常数级。

但这不代表字符串Hash是万能的，如果两个不同字符串的哈希值相同，程序自然会认为两个字符串相等，在很多情况下就会出现错误，我们称这样的问题为哈希冲突。上文中提到的哈希函数的冲突率极高，仅就长度为 $5$ 的小写字母字符串而言，可能的哈希值只有约 $126$ 种，而字符串总数约为 $26^5=1188$ 万种，冲突率显然十分高。

进制哈希

一种常见的避免哈希冲突的方式是使用 Base Hash，即进制哈希（又称滚动哈希）。其核心思想是：将字符串看作一个 $B$ 进制数，每一位字符的 ASCII 码作为该位上的数字，然后对这个 $B$ 进制数取模，得到最终的哈希值。 $B$ 的值通常为 $131,1331$ ^[1] 等。

相比于简单的 ASCII 码求和，进制哈希保留了字符的位置信息，哈希冲突概率大幅降低。

const int BASE=131;
const int MOD=1e9+7;
int hash_(string s) {
	int len=s.size(),res=0;
	for (int i=0;i<len;i++) res=(res*BASE+(int)s[i])%MOD;
	return res;
}
bool check(string s1,string s2) {
	return hash_(s1)==hash_(s2);
}

双模数优化

即使是用进制哈希，其哈希结果的数量也取决于 $MOD$ 的大小，如果题目当中给出的 $N$ 很大，就算使用进制哈希，冲突的概率也并不低。所以说，我们做两个进制哈希函数，其 $BASE$ 值和 $MOD$ 值都不同，程序在检查两个字符串是否相同时会同时调用这两个函数，如果两个哈希函数返回的值都相同，那么程序才认为两个字符串是相同的，冲突概率再次大大降低^[2]。

const int BASE=131;
const int MOD=1e9+7;
int hash_(string s) {
	int len=s.size(),res=0;
	for (int i=0;i<len;i++) res=(res*BASE+(int)s[i])%MOD;
	return res;
}
const int BASE2=1331;
const int MOD2=1e9+9;
int hash_2(string s) {
	int len=s.size(),res=0;
	for (int i=0;i<len;i++) res=(res*BASE2+(int)s[i])%MOD2;
	return res;
}
bool check(string s1,string s2) {
	return ((hash_(s1)==hash_(s2))&&(hash_2(s1)==hash_2(s2)));
}

前缀哈希

显然，这样的哈希函数时间复杂度为 $O(N)$ ，并不高效。然而在大多数题目中，我们需要频繁查询的是同一个字符串的不同子串。此时我们可以通过前缀哈希来预处理，实现 $O(1)$ 获取任意子串的哈希值。下文就是一个典型的 进制哈希+前缀哈希+双模数优化 的模板。

#define int long long
const int N=1e6+5;
const int BASE=131;
const int MOD=1e9+7;
const int MOD2=1e9+9;
string s;
int hs[N],hs2[N],pw[N],pw2[N];
int hash_(int a,int b) { 
	return (hs[b]-(hs[a-1]*pw[b-a+1])%MOD+MOD)%MOD;
}
int hash2_(int a,int b) { 
	return (hs2[b]-(hs2[a-1]*pw2[b-a+1])%MOD2+MOD2)%MOD2;
}
for (int i=1;i<s.size();i++) {
	hs[i]=hs[i-1]*BASE+s[i],hs2[i]=hs2[i-1]*BASE2+s[i];
	pw[i]=pw[i-1]*BASE,pw2[i]=pw2[i-1]*BASE2;
	hs[i]%=MOD,hs2[i]%=MOD2;
	pw[i]%=MOD,pw2[i]%=MOD2;
}