浅谈字符串映射算法----字符串哈希
___new2zy___
·
·
个人记录
浅谈字符串映射算法----字符串哈希
----谨以此篇纪念我可怜的字符串算法水平
最近看完了字符串匹配的三大算法：KMP、Trie、AC自动机，感觉神清气爽
回过头来发现好像我的hash还很菜。。。初赛出的那道字符串hash题都没做出来
所以来复习一下哈希
行，废话不多说，直接讲好了
哈希hash的定义
以下摘自度娘：
这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值
简单的说，哈希就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数
显然，哈希对应的数据结构是**哈希表**，也叫**散列表**
$hash$ $table$（散列表，又称哈希表），是根据关键码值$key$ $value$直接进行访问的数据结构
也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。其中这个映射函数叫做散列函数（即$hash$函数），存放记录的数组叫做散列表
给定表$M$，若存在函数$f(key)$，对任意给定的关键字值$key$，将$key$代入函数后若能得到包含该关键字的记录在表中的地址，则称表$M$为哈希$(hash)$表，函数$f(key)$为哈希$(hash)$函数
~~MMP度娘说的好复杂根本看不懂~~
哈希其实也是有分类的
今天我们要~~江~~讲的其实是**字符串哈希**
~~其实也没什么好讲的~~
## 问题引入
现在给你$n$个字符串，现在要求将他们区别开来
有人说：直接看一下字符串等不等不就行了？但我们怎么知道哪个字符串是哪个呢？
于是乎，我们就引入了哈希$hash$的概念
## $hash$基本思想
映射，将一个长度为$len$的字符串映射成一个非负整数，方法是将字符串看成$base$进制数，每次都利用一定的$hash$函数来达到映射效果，最终$hash$函数的返回值即为该字符串的哈希值
常见的哈希函数有：$base=33$哈希、大质数取模哈希等
## 哈希冲突
你理解了哈希的基本思想，那么你也能想到：既然一个字符串能被映射成一个非负整数，那么可能存在其他的不同字符串使得最终二者的哈希值相等，如果用数学公式来表达就是$f(key1)==f(key2)$，其中$key1!=key2$，这种情况被称为**哈希冲突**
通常，哈希冲突是一个非常不好的情形，它可能使得我们映射成的非负整数出现$1$对多的情况，那么这样我们就分不清哪个字符串是哪个了
为了解决这个问题，人们想出了解决冲突的方法，比如**开发定址法、再哈希法和链地址法**
由于正式的$OI$赛事中，真正存在哈希冲突的地方很少，所以大多数$OIer$都会使用
再哈希法。所以就大概讲一下**再哈希法**
**再哈希法**，又叫**二哈希法**，是一种能有效解决哈希冲突的方法。顾名思义，对于一个字符串，我们对它进行两次哈希，**如果当需要判断某两个字符串是否相等时，只有当两次哈希值完全相等我们才认为它们完全相等**
其实再哈希法也可以不只哈希两次，甚至可以哈希多次，但需要注意的是每次的哈希函数都应该有所不同，比如在所取的模数上就要有区分
最后。。。~~就没什么讲的了~~
提供一下我的板子代码：(luogu 模板题)
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int inf=1e9+7;
const int p1=19260817;
const int p2=19660813;
//以上是两次hash的模数
const int base=233;
//两次hash的基础数字("进制数")
inline int read()
{
int p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;}
struct str
{
int hs_1,hs_2;
}H[10009];
//每一个字符串都有两次hash值(以免出现hash冲突)
int n,Ans;//总个数和最后结果
int Hash_str_1(char s[])//进行hash1操作
{
int len=strlen(s),ans=0;
for(int i=0;i<len;i++)
ans=(ans*base+(int)s[i])%p1;
//Hash(S+ch)=={Hash(s)*base+value[ch]}%mod计算hash值
return ans;
}
int Hash_str_2(char s[])//同上,进行hash2操作
{
int len=strlen(s),ans=0;
for(int i=0;i<len;i++)
ans=(ans*base+(int)s[i])%p2;
return ans;
}
bool cmp(str x,str y)
{return x.hs_1<y.hs_1;}
int main()
{
n=read();
for(int i=1;i<=n;i++)//读入每个字符串并进行两次hash
{
char s[1509];
scanf("%s",s);
H[i].hs_1=Hash_str_1(s);
H[i].hs_2=Hash_str_2(s);
}
sort(H+1,H+1+n,cmp);//(以hash1结果)排一遍序
for(int i=1;i<=n;i++)
if(H[i].hs_1!=H[i+1].hs_1||H[i].hs_2!=H[i+1].hs_2)
Ans++;//如果两次hash值不同就说明两字符串不同
printf("%d",Ans);
return 0;
}
```
恩，就这样吧