哈希 Hash
MiPloRAs_3316
·
·
个人记录
前置芝士
散列表：
一种以 「key-value」形式 存储数据的数据结构。即任意的键值 key 都唯一对应到内存中的某个位置。可以根据 key 而直接进行访问。
也就是说，它通过把关键码值映射到表中一个位置以加快查找的速度。
理想情况下，对散列表进行查找的时间复杂度为 O(1)
散列函数：
一个把查找表中的关键字映射成散列表中一个位置的函数，记为 Hash(Key)=Addr。
冲突：
不太成功的散列函数把多个不同的 key 映射到了同一 addr 上。
散列函数的构造
直接取模
适用情况： key 是 10^9 范围内的整数。
\operatorname{Hash(key)}=key \bmod M
### base 进制
**适用情况：** key 是个字符串。
**思想：** 一般采用进制的思想，将字符串想象成一个 $base$ 进制的数。那么，对于每一个长度为 $n$ 的字符串 $s$，就有：
$$\operatorname{Hash(s)}=s_0\cdot base^n+s_1\cdot base^{n-1}+s_2\cdot base^{n-2}+\dots + s_n \cdot base^0$$
我们可以将得到的 $\operatorname{Hash(s)}$ 对 $2^64$（即 `unsigned long long` 的最大值）取模。这样 `unsigned long long` 的自然溢出就等价于取模操作了。可以使操作更加方便。
## 例子
[P2957 [USACO09OCT] Barn Echoes G](https://www.luogu.com.cn/problem/P2957)
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull maxn=10010,base=131;
char s[maxn],t[maxn];
ull pre[maxn],bse[maxn],Pre[maxn],ans=0;
void init()
{
bse[0]=1;
for(int i=1; i<=10001; i++)
bse[i]=bse[i-1]*base;
}
int main()
{
init();
cin>>s+1>>t+1;
int ls=strlen(s+1),lt=strlen(t+1);
for(int i=1; i<=ls; i++)
pre[i]=pre[i-1]*base+(ull)s[i];
for(int i=1; i<=lt; i++)
Pre[i]=Pre[i-1]*base+(ull)t[i];
for(int i=1; i<=min(ls,lt); i++)
{
if(pre[ls]-pre[ls-i]*bse[i]==Pre[i]) ans=i;
if(Pre[lt]-Pre[lt-i]*bse[i]==pre[i]) ans=i;
}
cout<<ans;
return 0;
}
```