U577837 字符串哈希详解
题目描述
哈希（Hash）函数是将输入（字符串）映射到输出（哈希值）的函数。
**注意：函数名称不要用 `hash`，C++11 标准库中提供了这个函数。**
想偷懒也可以用 `unordered_map`（底层为 Hash），不过容易被卡。
字符串哈希值分为三种情况：
1. 单射：每个字符串都拥有**唯一**的哈希值（不全部用完）。
2. 满射：每个字符串都有哈希值且哈希值全部用完。
3. 双射：每个字符串都拥有**唯一**的哈希值且哈希值全部用完。
双射是最理想的情况，但是几乎不可能出现。
日常生活中通常出现的是单射或满射。
一般的计算公式为：
$$
Hash(s)=\sum_{i=0}^{n-1} s_i\times p_{n-i-1} \bmod m
$$
p 通常为一个冷门的偏小的质数（如：$131,1151,13331$），$m$ 一般为一个大质数（不要用 $998244353,10^9+7$ 之类的常见的模数，容易被卡）。
## 哈希冲突
若两个字符串不同但是哈希函数值相同，则称之为哈希冲突。
最直观的体现就是代码 Wrong Answer。
如何解决？
### 1：自然溢出
我们都知道，`unsigned` 类型（无符号整型）仅能存储无符号整型。
我们可以理解为，若数字超出了 $2^{64}-1$ 的最大限制，**将自动对 $2^{64}$ 取模**。
注意加粗的那一部分，虽然 $2^{64}$（为 $18446744073709551616$）不是质数，但是因为过于巨大，所以哈希冲突的概率较小。
### 2：多重哈希
一般上双哈希就够了，不过也有三个甚至以上的，就统称为多重哈希好了。
单哈希即使用自然溢出，也可能会哈希冲突，所以多重哈希相当于又上了一道保险。
一个哈希函数中，两个字符串函数值相同并不代表这两个字符串一定相同，只有用多个哈希函数进行验证，才能降低哈希冲突的概率。
所以多重哈希的判断条件是：无论使用哪个哈希函数判断，得到的哈希值都是相等的。
---
### 双哈希例题：[P3370 【模板】字符串哈希](https://www.luogu.com.cn/problem/P3370?contestId=255781)
单哈希过不了。
因此使用自然溢出+多重哈希。
对于两个哈希函数值，如果两个哈希函数值均不相同，则这时候可以判断这两个字符串不相同。
#### 实现
```cpp
#include
using namespace std;
#define int long long
int n,ans=1;
paira[10005];
string s[10005];
unsigned long long Hash1(string s){
unsigned long long base=1129,sum=0;
for(auto z:s){
sum=sum*base+z;
}
return sum;
}
unsigned long long Hash2(string s){
unsigned long long base=2287,sum=0;
for(auto z:s){
sum=sum*base+z;
}
return sum;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i>s[i];
a[i]={Hash1(s[i]),Hash2(s[i])};
}
sort(a+1,a+n+1);
for(int i=2;im;m;m--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
cout
输入格式
无
输出格式
无