Sitan Chen home

哈希(Hash)

6 Oct 2025

1.简介

哈希的本质是从一个相对较大范围到相对较小范围的映射，这样方便进行比较。
哈希最直接的应用是判断两个字符串是否相同，比较时间为O(1)。
两个性质：1. hash值不一样时，两个字符串不一样 2. hash值一样时，两个字符串大概率一样。
将hash值相同但原字符串不同的情况称为哈希碰撞。

2.原理

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

通常选择将字符串转化为基（即进制）为131或13331的数字，并且对一个数M取模（M通常选择大质数，如1e9+537）就得到了对应的hash值。基和M若选择质数，那么哈希碰撞的概率会大大降低。

3.实现

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

int Hash(string s) {
	const int base = 131;
	const int M = 1e9 + 537;
	int res = 0;
	for(auto &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] = ((h[i-1] * base) + s[i]) % M;
		g[i] = (g[i-1] * base) % M;
}

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

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

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

s = " " + s;

4.例题

Example 1 洛谷P10468

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

模版题，直接套入函数即可。

哈希(Hash)

Related Posts