1.hash是什么?
定义:hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出, 该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间。
这么一说肯定会觉得很难,这百度百科果然不适合小白,可恶
用大白话来说,举个例子,我们有一个字符串ABC,我们会通过一系列运算将其转换为哈希值,使其与别的字符串不相同
哈希算法不过是一个更为复杂的运算,它的输入可以是字符串,可以是数据,可以是任何文件,经过哈希运算后,变成一个固定长度的输出, 该输出就是哈希值。但是哈希算法有一个很大的特点,就是你不能从结果推算出输入,所以又称为不可逆的算法
2.map容器(map<T1, T2>SUM)
注:T1和T2都是数据类型
map是STL的一个关联容器,它提供一对一的hash。
T1可以称为关键字(key),每个关键字只能在map中出现一次;
T2可以称为该关键字的值(value);
因此我们就可以借助map函数来轻易实现hash的用法,那么我们来看几个简单的例题
3.例题
(1)第一题: 字符串哈希模版
题解:刚做这道题的时候我并没有了解到map函数,导致我的代码显得很冗长,是自己去实现map函数的功能的,我首先想到的就是可不可以将abc这种字符串换成一个整数,然后我就想着直接累加,后续我又想到了可能会存在冲突,比如说abc的值等于cba的值,因此我给字符串加上了进制,每一位都多乘一个10,然后,我才过的,如果当前那个数组存在当前值,就减一,最后输出总值,请看AC代码
#include<bits/stdc++.h>
using namespace std;
int n,sum;
char a[10005][2000];
unsigned long long b[10005];
int len[10005];
unsigned long long tt=47;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int cnt=0;
int ans=0;
scanf("%s",a[i]);
len[i]=strlen(a[i]);
while(cnt<=len[i])
{
ans=ans*tt+(unsigned long long)a[i][cnt];
cnt++;
}
b[i]=ans;
}
sort(b+1,b+n+1);
for(int i=1;i<=n-1;i++)
{
if(b[i]!=b[i+1])
sum++;
}
printf("%d",sum+1);
return 0;
}
(2) 第二题:错误点名的开始
、题解:这时候我就已经学会用map函数了,因此,直接用map函数可以迅速秒杀这道题
#include <bits/stdc++.h>
using namespace std;
int n,m;
string s;
map<string,int>sum;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>s;
sum[s]=1;
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
cin>>s;
if(sum[s]==1)
{
printf("OK\n");
sum[s]++;
continue;
}
if(sum[s]<1)
printf("WRONG\n");
if(sum[s]>1)
printf("REPEAT\n");
}
return 0;
}
第三题:密文搜索
题解:我们只需要将后面的密码转变为哈希数,然后从上述字符串中取出连续的八个字符,如果其哈希值和下面的密码一样的话,就说明,配对成功,次数要加1,最后统计总数即可
#include<bits/stdc++.h>
using namespace std;
map<string,int>sum;
string s,t;
int n;
int ans;
int main()
{
cin>>s;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
cin>>t;
sort(t.begin(),t.end());
sum[t]++;
}
for(int i=0;i<s.size()-7;i++)
{
t=s.substr(i,8);
sort(t.begin(),t.end());
ans+=sum[t];
}
printf("%d",ans);
return 0;
}