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

?