Hash算法详解
MoonCake2011 · · 个人记录
Hash算法是一个著名而简单的算法，它可以用一点空间
Hash函数
Hash函数是将一个大数字或字符串转化成小数字塞进Hash表的,对字符串能做到基本不重复。
Hash表(散列表)
Hash表，又称散列表，能用桶的思想将一些数
我们来想想，桶是不是占用空间很大，但时间复杂度很低。
我们来尝试对其进行改进。
我们可以选择一个模数m，在将要存进去的数
于是我们设
这样就可以解决空间问题，那么这样后，准确度这样就不是100%了。
于是对于每个桶，我们建一个邻接表，出现一个数把它插入那个邻接表，这样，遍历每个邻接表就能去重，访问。
.
至于m建议去一个较大的质数，如:999983.
代码:
#include<bits/stdc++.h>
using namespace std;
#define m 999983
struct hash{
int head[m+2],val[m+2],nxt[m+2],tot;
hash(){
memset(head,0,sizeof head);
memset(val,0,sizeof val);
memset(nxt,0,sizeof nxt);
tot=0;
}
void add(int x){
int mod=x%m;
val[++tot]=x;
nxt[tot]=head[mod];
head[mod]=tot;
}
void insert(int x){
int mod=x%m;
for(int i=head[mod];i;i=nxt[i])
if(val[i]==x) return;
add(x);
}
bool count(int x){
int mod=x%m;
for(int i=head[mod];i;i=nxt[i])
if(val[i]==x) return 1;
return 0;
}
int main() {
return 0;
}练习:[JLOI2011] 不重复数字.
字符串Hash
基本用途
Hash的精髓来了，字符串Hash.
我们可以将一个字符串映射成一个整数存进Hash，已来去重.
那怎么转换呢，我们以进制转换思想，把字符串看成131进制，边取模边转换，这样，就可以了。
例题:【模板】字符串哈希.
简单的Hash去重.
代码:
#include<bits/stdc++.h>
using namespace std;
#define mod 999983
int ans;
vector<string>h[mod+2];
void insert(string x){
int m=0;
for(int i=0;i<x.size();i++) m=(m*131+x[i])%mod;
for(int i=0;i<h[m].size();i++)
if(h[m][i]==x) return;
h[m].push_back(x);
ans++;
}
int main() {
int n;
cin>>n;
for(int i=1;i<=n;i++){
string s;
cin>>s;
insert(s);
}
cout<<ans;
return 0;
}练习:[USACO16DEC] Cities and States S.
接着，头脑风暴即将到来。
真正的 字符串Hash->随机算法 即将到来。
我们可以用某数值代表一个字符串，这样字符串冲突的概率极低，于是，用自然溢出的方法，用unsigned int或unsigned long long存下一个字符串的值，不用取模（更快）。
但，不保证有两个不同字符串取模后的Hash值相同，所以它是随机算法。
我们可以求出那个字符串的前缀Hash值以用前缀和思想求出任意子串的Hash值。
一个子串[l,r]的Hash值为hash[r]-hash[l-1]*pow(r-l+1)。
还可以求出那个字符串的后缀Hash值以用前缀和思想求出任意子串翻转后的的Hash值。
例题:【模板】manacher 算法.
最长回文子串，这在
于是，我们可以处理出前缀与后缀Hash值，在字符串每个字母的空隙插入其他字符（处理对称点在缝隙里的情况），对某个点进行左右扩散，如果它在扩散范围内的左串的Hash值与在扩散范围内的右串翻转后的Hash值一样(回文了)，就记录ans，并继续扩散。
并且没越界。
因为以前搜出的范围长度小的子串就不用搜了（不会更新ans）。
所以当扩散时可以直接从长度为ans的长度枚举.
总时间为
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn=2.2e7+10;
unsigned int s1[maxn],s2[maxn],power[maxn];
int ans,tot,len;
char s[maxn],t[maxn];
unsigned int gethash1(int l,int r){
return s1[r]-s1[l-1]*power[r-l+1];
}
unsigned int gethash2(int l,int r){
return s2[l]-s2[r+1]*power[r-l+1];
}
int main() {
scanf("%s",t);
len=strlen(t);
power[0]=1;
s[++tot]='~';
for(int i=0;i<len;i++)
s[++tot]=t[i],s[++tot]='~';
len=tot;
for(int i=1;i<=len;i++){
power[i]=power[i-1]*131;
s1[i]=s1[i-1]*131+s[i]-'a'+1;
}
for(int i=len;i>=1;i--)
s2[i]=s2[i+1]*131+s[i]-'a'+1;
for(int i=1;i<=len;i++)
while(i-ans>=1 && i+ans<=len && gethash1(i-ans,i+ans)==gethash2(i-ans,i+ans))
ans++;
cout<<ans-1;
return 0;
}提高精确度
我们可以对它计算以多个数为进制数进行双重保险，如果两个Hash值都相等那就相等，否则不相等（即便有一个Hash值相等）。
字符串Hash可以处理 KMP字符串匹配 类似的问题，以
总结
Hash表是个很好的东西，可以以一点空间以
连字符串都能去重。
字符串Hash是一个随机算法，它可以快速判断一些关于子串与字符串相等的问题。
当然,Hash还有很多用途可以发掘，如：快速访问