hash，以及数据结构——map容器

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;
}