哈希（Hash）的本质就是将一个东西通过自己定义的奇奇怪怪的运算法则，确定一个对应的特殊的数字（哈希值），便于之后进行字符串的比较（处理好的一大堆哈希值称为哈希表）。如果两个不一样的东西很倒霉的哈希值一样，我们称之为“撞哈希”，可以通过双哈希（两个哈希表相互应证）来解决，也可以在处理哈希表时，遇到地址相同的情况就从1开始搜索，找一个最小的空位填进去。通过各种操作使撞哈希的可能极其小约等于0。
一、举个例子？
比如我们要对一个数组（45,67,23,36,47,58,76,23）进行操作。
我们定义这个奇怪的运算法则为“地址1=x%10(地址2=x%3）”
首先我们用双哈希试一下：
??????? ? ? 45 67 23 36 47 58 76 23
地址1：5?? 7?? 3?? 6?? 7?? 8?? 6?? 3
地址2：0?? 1?? 2?? 0?? 2?? 0??? 1? 2
我们就可以发现，只有a[3]和a[8]两个地址都相同，所以a[3]和a[8]数字相等，字符串也是和数字一个道理。
然后我们再用这个后推地址的哈希试一下，如果发现正在处理的这个数与之前的数“撞哈希”，就给这个正在处理的数的哈希值加上一个大质数直到不重复。
来看这个很奇怪的例子
??????????? 26 36
如果我们用一个哈希就会撞，所以：
??????????? 26??????? 36
???????????? 6??? 6+1e9+7
这下就ok了
二.看个例题？
题目描述
如题，给定 N 个字符串（第 i个字符串长度为 Mi，字符串内包含数字、大小写字母，大小写敏感），请求出 N个字符串中共有多少个不同的字符串。
输入格式
第一行包含一个整数 N，为字符串的个数。
接下来 N 行每行包含一个字符串，为所提供的字符串。
输出格式
输出包含一行，包含一个整数，为不同的字符串个数。
二、处理哈希表？
1.双哈希
#include<bits/stdc++.h>
using namespace std;
int base1=131,base2=4777;
char s[10010];
int n;
int prime=233317;
int mod=212370440130137957ll;
struct emm{
int haxi1,haxi2;
}a[10010];
int haxi11(char s[]){
int len=strlen(s);
int ans=0;
for(int i=0;i<len;i++){
ans=(ans*base1+(int)s[i])%mod+prime;
}
return ans;
}
int haxi22(char s[]){
int len2=strlen(s);
int ans=0;
for(int i=0;i<len2;i++){
ans=(ans*base2+(int)s[i])%mod+prime;
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
a[i].haxi1=haxi11(s);
a[i].haxi2=haxi22(s);
}
int ans=n;
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if(a[i].haxi1==a[j].haxi1&&a[i].haxi2==a[j].haxi2){
a[j].haxi1+=prime;//防止如果1 2一样，1 3一样时，2 3又记录了一次
ans--;
prime++;
}
}
}
printf("%d",ans);
return 0;
}
2.后推哈希
#include<bits/stdc++.h>
using namespace std;
int base=131,a[10010],b[10010];
char s[10010];
int n,ans=1;
int prime=233317;
int mod=212370440130137957ll;
bool check(int x){
for(int j=1;j<=n;j++){
if(x==a[j])return false;
}
return true;
}
int haxi(char s[]){
int len=strlen(s);
int ans=0;
for(int i=0;i<len;i++){
ans=(ans*base+(int)s[i])%mod+prime;
}
return ans;
}
int main(){
scanf("%d",&n);
for(int j=1;j<=n;j++){
scanf("%s",s);
a[j]=haxi(s);
}
for(int i=1;i<=n;i++){
while(check(a[i])==false){
a[i]+=19260817;
break;
}
}
sort(a+1,a+n+1);
for(int i=1;i<n;i++){
if(a[i]!=a[i+1]||b[i]!=b[i+1])ans++;
}
printf("%d",ans);
return 0;
}
|