字符串哈希
字符串哈希
字符串哈希就是将一个字符串映射为P进制的整数.
- 将一个字符串映射成一个P进制整数
对于一个长度为n的字符串s,这样定义一个Hash函数:\(h(s)=\sum_{i=1}^{n}s[i] \times p^{n-i}(mod M)\)
例如,字符串,abc,其哈希值为\(ap^2 + bp^1 + c\) - 如果两个字符串不一样,哈希值却一样,这种现象称为哈希碰撞
- 解决哈希碰撞的方法:
巧妙地设置P和M的值,保证P与M互质.
P通常取质数131或者13331
M通常取大整数\(2^{64}\),把哈希函数值的数据类型定义为UUL(unsigned long long
),超过则自动移除,等价于取模
练习
Luogu P3370 【模板】字符串哈希
解法一:😤
AC代码,展开查看
#include<bits/stdc++.h>
using namespace std;
int main(){
unordered_map<string, int> m;
int n;
cin >> n;
while(n -- ){
string s;
cin >> s;
m[s] ++ ;
}
cout << m.size();
return 0;
}
解法二:
AC代码,展开查看