Tommy Chen home

哈希

6 Oct 2025

1. 简介

哈希的本质是从相对较大范围到相对较小范围的映射，便于比较。
哈希最直接的应用是判断两个字符串是否相同，比较时间可做到 O(1)。
两个性质：① 哈希值不同时，两个字符串一定不同；② 哈希值相同时，两个字符串大概率相同。
哈希值相同、但原字符串不同的情况称为哈希碰撞。

2. 原理

对于一个字符串，将其转化为一个数字。若两个数字不同，则它们对应的原字符串不相同；若两个数字相同，则它们对应的原字符串大概率是相同的。

通常将字符串转化为以 131 或 13331 为基的数字，再对模数 M 取模（M 通常选择较大的质数，如 1e9+537），便得到对应的哈希值。基数和 M 均选用质数时，哈希碰撞概率会大幅降低。

3. 实现

通过递推的方式，将字符串转化为 131 进制数。

long long Hash(const string& s) {
	const long long base = 131;
	const long long M = 1000000537LL;
	long long res = 0;
	for(char c : s) {
		res = (res * base) + c;
		res %= M;
	}
	return res;
}

但多次判断完整字符串是否相同时，时间复杂度较高；求子串哈希值也不方便。因此可维护前缀数组 h：h[i] 表示字符串前 i 个字符（即 s[1…i]）的哈希值；同时维护幂数组 g，其中 g[i] 存储 base 的 i 次方模 M 的值，用于计算子串哈希值。

预处理如下，时间复杂度为O(n)。

for(int i = 1; i <= n; i++) {
		h[i] = (1LL * h[i-1] * base + s[i]) % M;
		g[i] = 1LL * g[i-1] * base % M;
}

提取下标从l到r的子串的哈希值，计算可以做到O(1)。

auto get = [&](int l, int r) -> int {
		return (h[r] - 1LL * h[l-1] * g[r - l + 1] % M + M) % M;
};

此外，字符串下标从0开始，与数组从1开始不同，不方便处理，因此这样操作：

s = " " + s;

4. 例题

示例 1：洛谷 P10468

题意：给定一个字符串和 q 次询问。每次询问给出原字符串中两个子串的范围，判断这两个子串是否相同。

模板题，直接使用上述函数即可。

哈希

Related Posts