当前位置：首页 > news >正文

20251115 - Hash

news 2026/5/12 17:23:03

前言

为什么此次题单不叫字符串 hash 呢？

~~应该搞点 [哈希表](P11615 【模板】哈希表 - 洛谷) 的！~~

概念

哈希，就像是把一个很大的东西，映射到一个小盒子里，这个盒子就是哈希表。

字符串哈希，顾名思义，就是把很 long 的字符串，映射到很 short 的范围里。:

当然，不保证正确性。

性质

在 hash 函数值不一样的时候，两个字符串一定不一样；
在 hash 函数值一样的时候，两个字符串不一定一样。

如果出现字符串不相同但 hash 值一样，就称为哈希冲突。

防止 \(hash\) 冲突的方法

其实 \(hash\) 冲突无法防止，但可以降低冲突的概率。

取一个较大的质数，比如 \(1e9 + 7\) ，\(114514\) ， \(2^{62}-1\) 等……
\(base\) 尽量随机，防止出题人卡你 \(hash\)

用法

如何求出 hash 值呢？~~还是用 unordered_map吧~~

自然溢出

利用 \(unsigned \ long \ long\) 的特性，可以不用模数了！

\(base\) 一般取值 \(2^{61} - 1\)

const ull base = (1ULL << 61) - 1;
ull get_hash(char s[]){int len = strlen(s + 1);vector<int>ve(len + 1);for(int i = 1;i <= len;i++){ve[i] = ve[i - 1] * base + s[i];}return ve[len];
}

模数哈希

自然溢出实际上是对 \(2^{62} - 1\) 取模，而模数哈希就是换了个模式而已！

const int base = 131; // 一定要大于字符集
const int P = 998244353;
int get_hash(char s[]){int len = strlen(s + 1);vector<int>ve(len + 1);for(int i = 1;i <= len;i++){ve[i] = (1LL * ve[i - 1] * base) % P + s[i] % P;ve[i] %= P;}return ve[len] % P;
}

C++ 的标准模版库（STL）有一个好用的哈希表，他叫 unordered_map，目前仅仅基本数据结构！

unordered_map<int,int>mp;
void solve(){for(int i = 1;i <= n;i++){int x,y;read(x,y);mp[x] = y;}
} // 和map几乎一致

区间截取字符串

众所不周知，字符串匹配可以用 KMP 算法，但哈希也不是不行。

想想前缀和是什么样子的 s[r] - s[l - 1]，那么 hash 也可以做减法！

int h[N],power[N];
void init(){power[0] = 1;for(int i = 1;i <= n;i++)h[i] = (1LL * h[i - 1] * base) % P + s[i] % P;for(int i = 1;i <= n;i++)power[i] = power[i - 1] * base;
}
int get_hash(char s[],int l,int r){int x = 1LL * h[l - 1] * power[r - l + 1] % P;return (h[r] - x + P) % P;
}

这样，我们就可以开心的字符串匹配了！

例题

P3370 【模板】字符串哈希

~~友情提醒：如果真的想好好练习哈希的话，请自觉。~~

此题即为字符串哈希的模版题！

计算字符串的 \(hash\) 值时，我们一般把原串的 \(B\) 进制数作为它的 \(hash\) 值，这样比较方便计算，并且预处理之后，也可以 \(O(1)\) 求出任意一个子串的 \(hash\) 值。

建议别用自然溢出，不然被出题人卡了就老实了！

字符串的长度一般会很长， \(int128\) 都存不下，怎么办？

~~高精度~~ 取模！

建议自己手写 \(add\) 与 \(mul\) 函数，不然被出题人卡了就老实了

注意！！注意！！别 #define int __uint128_t ！！！！！

代码：

#include <bits/stdc++.h>using namespace std;
#define ll long long
const int N = 1e5 + 7;
const int P = 998244353;
const int inf = (1 << 30);
const int base = 173397;
template<class T> void read(T &x){x = 0;int f = 1;char ch = getchar();while(!(ch >= '0' && ch <= '9')){if(ch == '-') f = -f;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}x *= f;
}int n;
int get_hash(const string &x){int len = x.size(),res = 0;for(int i = 0;i < len;i++){res = ((ll)res * base) + x[i] % P;res %= P;}return res;
}
int a[N];
string s;
int main(){read(n);for(int i = 1;i <= n;i++){cin >> s;a[i] = get_hash(s);}int cnt = 0;for(int i = 1;i <= n;i++){bool ok = false;for(int j = i + 1;j <= n;j++){if(a[i] == a[j]) ok = 1;}if(!ok) cnt++;}printf("%d\n",cnt);return 0;
}
// 由于是vscode写的，所以排版有亿点不好