简介
哈希是一种能把字符串(实际上数组也行,不过本文都会以字符串为例)映射成一个数的算法,哈希就是把一个字符串转成一个 \(K\) 进制数,但由于得到的数可能会非常大,所以其中会用到取模,因此哈希也有些玄学(建议 CF 有赛后 hack 的比赛不要使用哈希,或提高哈希的安全度)。
普通哈希
可以将 a b c ... z
分别映射为 \(1,2,3,\dots,26\) (本文默认只包含小写英文字母,如果有其它字符再进行映射即可)。
注意不能将 a
映射为 \(0\),因为这样哈希就会认为 ab
\(=\) b
。
单次时间复杂度 \(O(|S|)\)。
代码
const int base = 27, MOD = int(1e9) + 7;
int Hash(const string &s) {
int res = 0;
for(int i = 0; i < int(s.size()); ++i) {
res = (1ll * res * base % MOD + s[i] - 'a' + 1) % MOD;
}
return res;
}
Hash(s);
前缀哈希
令 \(sum_i\) 表示前 \(i\) 个字符的哈希值,那么可以得到 \(sum_i=(sum_{i-1}\cdot base+mp_{s_i})\bmod m\),其中 \(base\) 指进制,\(mp_c\) 指字符 \(c\) 映射出的值,\(m\) 指模数。
我们还可以得到 \([l,r]\) 的哈希值是 \((sum_r - sum_{l-1}\cdot base^{r-l+1})\bmod m\)。
预处理时间复杂度 \(O(|S|)\),单次时间复杂度 \(O(1)\)(因为可以预处理出 \(base^k\) 的值)。
代码
const int base = 27, MOD = int(1e9) + 7;
int Calc(int l, int r) {
return ((sum[r] - 1ll * sum[l - 1] * Pow[r - l + 1] % MOD) % MOD + MOD) % MOD;
}
s = ' ' + s, Pow[0] = 1;
for(int i = 1; i <= n; ++i) {
sum[i] = (1ll * sum[i - 1] * base % MOD + s[i] - 'a' + 1) % MOD;
Pow[i] = 1ll * Pow[i - 1] * base % MOD;
}
Calc(l, r)
哈希的安全性
因为哈希使用了取模,所以就有可能不同的字符串会被当做是相同的。这种情况被称为哈希冲突。
生日悖论
生日悖论是说:你有 \(30\) 个朋友,一年有 \(365\) 天(不考虑闰年),那么有朋友的生日在同一天的概率是多少?
可以先算出每个朋友都不相同的概率,然后用 \(1\) 减,可以得到:
\(1-\frac{365}{365}\cdot \frac{364}{365}\cdot\frac{363}{365}\cdot\dots\cdot\frac{336}{365}=1-\frac{365!}{335!\cdot365^{30}}\approx 70\%\)。
这个故事告诉我们,哈希冲突的概率比你想得可能要大的多。
大质数
一种最简单的方法就是:让你的模数更大!(并且使用质数)
比如说你可以把模数设为:\(10^{18}+3,10^{18}+9,10^{18}+31\)(注意!\(10^{18}+7\) 不是质数!)。
或者把你的进制也改为质数,比如:\(131,133,13331,1145141\)。
代码
using ll = long long;
const ll base = 1145141, MOD = (ll)(1e18) + 3;
多重哈希
还有一种方法,就是多用几个模数(进制也可以用多个),只有在所有结果下都相同我们才认为两个字符串相同,这样也可以大大提升哈希的安全性。
建议在使用双重哈希时可以使用孪生素数(差为 \(2\) 的一对质数,如:\(10^9 + 7,10^9+9\))。
代码
using ll = long long;
const ll base[2] = {131, 1145141}, MOD[2] = {(ll)(1e18) + 3, (ll)(1e18) + 9};
int Hash(const string &s, int op) {
int res = 0;
for(int i = 0; i < int(s.size()); ++i) {
res = ((__int128)res * base[op] % MOD[op] + s[i] - 'a' + 1) % MOD[op];
}
return res;
}
Hash(s, 0), Hash(s, 1);
标签:int,res,ll,base,哈希,MOD
From: https://www.cnblogs.com/yaosicheng124/p/18138749