哈希算法

---前言

?????????"加密是信息時代的鎖,密碼是鑰匙。" - 斯科特·萊普斯基(Scott Adams)

? ? ? ? 當(dāng)今，為了信息的存儲安全，密碼學(xué)興起，哈希（hash)算法也由此應(yīng)運而生，哈希算法是一種加密算法，是將一個數(shù)據(jù)轉(zhuǎn)換為一個標(biāo)志，這個標(biāo)志和源數(shù)據(jù)有十分緊密的關(guān)系。哈希 算法還有一個特點，就是很難找到逆向的規(guī)律。所以在日常的使用中，哈希算法常被用來對字符串進行壓縮編碼，將一段字符串轉(zhuǎn)化成對應(yīng)的數(shù)字或其他標(biāo)志，以方便存儲和比較。

---正文

? ? ? ? ·整數(shù)哈希（哈希介紹）

? ? ? ? 做為競賽算法來說，整數(shù)哈希算法經(jīng)常用來存儲極大的數(shù)據(jù)以起到縮小數(shù)據(jù)規(guī)模的效果，而經(jīng)過哈希算法處理后的數(shù)據(jù)會被存到一個數(shù)據(jù)結(jié)構(gòu)-散列表（hash表）中，其采用映射的思想，可以通過關(guān)鍵字在表中快速查找數(shù)據(jù)，而Hash函數(shù)的設(shè)計也層出不窮，在算法競賽中，最常用的就是取模法，下文也以取模法為例來介紹+實現(xiàn)。

舉個例子，對于數(shù)據(jù)5，9，18，28，16來說，如果使用hash表存儲，模數(shù)為7，那么就應(yīng)該為

5：5 mod 7=5，存儲在下標(biāo)為5處。

9：9 mod 7=2，存儲在下標(biāo)為2處。

18：18 mod 7=4,存儲在下標(biāo)為4處。

28：28 mod 7=0，存儲在下標(biāo)為0處。

16: 16 mod 7=2,應(yīng)當(dāng)存儲在下標(biāo)為2處。

????????這時我們發(fā)現(xiàn)16和9的模數(shù)相同，也就是說，發(fā)生了哈希沖突，對于整數(shù)哈希沖突，也有許多不同的解決方案，此處，提供兩種解決方案，開放地址法和鏈地址法。

開放地址法：將當(dāng)前的數(shù)向后（或向其他方向，不定）挪移，直到可以存儲。

鏈地址法：將當(dāng)前的數(shù)在該下標(biāo)下再拉一條鏈，形成一個鏈表，并將該數(shù)存儲到鏈表下。

? ? ? ? 但是顯而易見，這兩種辦法對于解決哈希沖突并不十分有效，所以我們要盡量減少哈希沖突的情況，一般而言，將模數(shù)設(shè)為足夠大的質(zhì)數(shù)可以有效減少哈希沖突出現(xiàn)的情況。

? ? ? ? 不過，對于整數(shù)哈希，我們一般不需要手寫哈希，可以使用C++的STL庫中的自帶的無序map:unordered_map和無序集合：unordered_set來代替手寫整數(shù)哈希，故此處不附代碼，若想手寫直接按照上述過程模擬即可。

? ? ? ? ·字符串哈希（哈希拓展）

? ? ? ? 經(jīng)過上述介紹，我們知道利用哈希函數(shù)可以很快的查詢和比較，而對于字符串來說，若要比較字符串是否相等，需要逐位比較，效率顯然很低，時間復(fù)雜度為O(n)，所以我們考慮使用哈希優(yōu)化，而如何將字符串轉(zhuǎn)成可以正常按位置比較大小的數(shù)字呢？，類比進制轉(zhuǎn)換，我們把字符串看成一個128進制（ASCII碼）的數(shù)字，每個字符相對應(yīng)的就是其ASCII碼值，再按權(quán)展開就能得到其哈希值，如abcd這個字符串，它的哈希值就是97*128^3+98*128^2+99*128^1+100*128^0,由此我們可以得到一個公式（其中hash[i]表示第1位到第i位的哈希值，base表示底數(shù)，mod表示模數(shù),s是原字符串）：

hash[i]=(hash[i-1]*base%mod+s[i]%mod)%mod

哈希值是可以進行正常比較的，我們類比十進制來理解，一個數(shù)按權(quán)展開后就是得到的原數(shù)，其值完全可以正常比較，所以哈希值也是可以進行字符串之間的正常比較的，而且它不需要逐位比較，效率比逐位比較更高，基本為O(1)，這樣就能極大程度的優(yōu)化時間，使得程序不會超時。

? ? ? ? 但是，一般來說，底數(shù)（即權(quán)值）最好要定義成一個質(zhì)數(shù)（避免哈希沖突），所以一般會選擇第一個比128大的質(zhì)數(shù)131來做底數(shù)，不過，事實上，只要大小合理，且為質(zhì)數(shù)，任何大于128的數(shù)都是一個不錯的底數(shù)，但是最常用的底數(shù)仍然是131。

模板（求哈希值）

題面概括：

? ? ? ? 給定一個字符串，求其對應(yīng)的哈希值，對998244353取模。

思路：

? ? ? ??純模板題，直接按上述過程模擬即可。

代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-835351.html

#include<bits/stdc++.h>
using namespace std;
long long has[100005];
const int mod=998244353;
int main(){
    string s;
    getline(cin,s);
    has[0]=s[0]%mod;
    for(int i=1;i<s.size();i++){
    	has[i]=(has[i-1]*128+(long long)s[i]%mod)%mod;
	}
	cout<<has[s.size()-1];
    return 0;
}

T2.查字典

題面概括：

? ? ? ? 給定n組單詞和其翻譯后的單詞，然后輸入q個單詞，將單詞翻譯后輸出，如果沒有對應(yīng)的單詞則輸出“eh"。

思路：

? ? ? ??這道題也是模板題，先把原單詞轉(zhuǎn)為哈希值后存儲，每輸入一個需要翻譯的單詞，就將其的哈希值求出，并與之前求出的所有原單詞的哈希值做比較，如果相等，輸出記錄的對應(yīng)的翻譯后的單詞即可，如果沒有相等的單詞則輸出”eh"。

代碼：

#include<iostream>
using namespace std;
long long has[1005];
const int mod=998244353;
string k[1005];
int main(){
    int n,q;
    string s;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>k[i]>>s;
        int len=s.size();
        for(int j=0;j<len;j++){
            if(j==len-1){
                has[i]=(has[i]+(long long)s[j])%mod;
            }
            has[i]=((has[i]+(long long)s[j])*128)%mod;
        }
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>s;
        int sum=0;
        int len=s.size();
        for(int j=0;j<len;j++){
            if(j==len-1){
                sum=(sum+(long long)s[j])%mod;
            }
            sum=((sum+(long long)s[j])*128)%mod;
        }
        bool flag=0;
        for(int j=1;j<=n;j++){
            if(sum==has[j]){
                flag=1;
                cout<<k[j]<<endl;
            }
        }
        if(flag==0){
            cout<<"eh"<<endl;
        }
    }
    return 0;
}

T3.消失的密文

———————————————————————————————————————————

前置知識：

? ? ? ??對于一個已經(jīng)求得下標(biāo)從1開始所有長度哈希值的字符串來說，如何求它的子串呢？，我們考慮將哈希值當(dāng)成前綴和的形式來求得，那么如果要求l~r這段子串的哈希值，是用hash[r]-hash[l-1]嗎？答案是否定的，因為，hash[l-1]比hash[r]少乘了r-l+1個base(底數(shù)），導(dǎo)致指數(shù)無法對齊，所以我們就可以得到正確的公式（hash(l，r)表示l~r這段子串的哈希值,p[i]表示底數(shù)的i次方）:

hash(l,r)=(hash[r]-(hash[l-1]*p[r-l+1])%mod+mod)%mod

———————————————————————————————————————————

題面概括：

? ? ? ? 給定一個密碼表S，S[i]表示第i個小寫字母解密后對應(yīng)的字母（下標(biāo)由1開始），然后給出一條密文K，密文的末尾缺失了一部分單詞，而完整密文的前半段是密文，后半段是解密后的”明文“，要求求出最短的完整的密文。

思路：

? ? ? ??這道題的難點，也是中心，就在于如何確定給出的密文中哪部分是密文，那部分是“明文”，也就是完整密文的中點位置，對于這道題來說，密文不是很長，所以可以使用枚舉的方法來枚舉中點，先用hash數(shù)組記錄哈希值,再枚舉中點k,取最前面n-k個字符的哈希值和k后面n-k個字符的哈希值（先將面n-k個字符轉(zhuǎn)為明文后）作比較，如果兩者相等就說明k是最小的中點，直接跳出循環(huán)并輸出前k個密文和后k個明文即可。

代碼：

#include<bits/stdc++.h>
using namespace std;
long long has[100005],p[100005],mhas[100005];
const int mod=998244353;
long long mid;
map<char,char> ma,pma;
int main(){
    int n;
    string s,b;
    cin>>n;
    for(int i=1;i<=n;i++){
    	ma.clear();
    	pma.clear();
        memset(has,0,sizeof has);
        memset(mhas,0,sizeof mhas);
        cin>>s>>b;
        b=' '+b;
        s=' '+s;
        for(int i=1;i<=s.size();i++){
        	ma['a'-1+i]=s[i];
        	pma[s[i]]='a'-1+i;
		}
        int len=b.size();
        len-=1;
        p[1]=1;
        for(int j=2;j<=len;j++){
            p[j]=p[j-1]*128;
        }
        for(int j=1;j<=len;j++){
            if(j==len){
                has[j]=has[j-1]+(long long)b[j];
                mhas[j]=mhas[j-1]+(long long)ma[b[j]];
            }
            has[j]=(has[j-1]+(long long)b[j])*128;
            mhas[j]=(mhas[j-1]+(long long)ma[b[j]])*128;
        }
        for(int j=(len+1)/2;j<=len;j++){
            long long hh=mhas[len]-mhas[j-1]*p[len-(j-1)+1];
            if(has[len-j+1]==hh){
                mid=j;
                break;
            }
        }
		for(int j=1;j<mid;j++){
			cout<<b[j];
		}
		for(int j=1;j<mid;j++){
			cout<<pma[b[j]];
		}
		cout<<"\n";
    }
    return 0;
}

T4.不同子串（雙哈希）

———————————————————————————————————————————

前置知識：

? ? ? ? 整數(shù)哈希中最重要的問題便是哈希沖突，而在字符串哈希中同樣如此，由于字符串哈希的局特殊性，我們無法使用一些在整數(shù)哈希中使用的方法來解決哈希沖突，所以我們主要來通過方法使得哈希沖突的概率降到一個極其微小的地步，這里介紹一個方法：雙哈希，顧名思義，就是對同一個字符串，使用兩個底數(shù)不同且模數(shù)不同的哈希函數(shù)分別求值，在判斷時要求兩個哈希函數(shù)的值必須都一一對應(yīng)才能判斷兩個字符串相等，這樣能令哈希沖突基本不可能出現(xiàn)。

———————————————————————————————————————————

?題面概括：

? ? ? ??給出一個字符串S，求這個字符串中有多少長度不同的子串。

思路：

? ? ? ? 這道題是一道經(jīng)典的哈希例題，但是如果直接使用單哈希會被卡數(shù)據(jù)，所以考慮使用雙哈希，與上一題相同，這道題也是枚舉所有字串開頭的字符下標(biāo)位置（也可以是結(jié)尾字符下標(biāo)位置），然后對沒有出現(xiàn)的哈希值進行記錄，并累加，最后累加的值即為答案，輸出即可，注意，在記錄和判斷時要使用pair，否則會出現(xiàn)數(shù)據(jù)不對應(yīng)導(dǎo)致答案錯誤。

代碼：

//雙哈希 
#include<bits/stdc++.h>
using namespace std;
long long hasa[1000005],hasb[1000005],p[1000005],p1[1000005];
const int mod=1e9+7,modb=998244353;
const int base=131,base1=128;
map<pair<long long,long long>,int> ma;
int main(){
    string s;
	int n,l;
	cin>>n>>l;
	cin>>s;
	s=' '+s;
	int len=s.size();
	len-=1;
	p[0]=p1[0]=1;
	for(int i=1;i<=len;i++){
	    p[i]=p[i-1]*base%mod;
	    p1[i]=p1[i-1]*base1%modb;
	}
	for(int i=1;i<=len;i++){
	    hasa[i]=((hasa[i-1]*base)%mod+(long long)s[i]%mod)%mod;
	    hasb[i]=((hasb[i-1]*base1)%modb+(long long)s[i]%modb)%modb;
	}
	long long cnt=0;
	for(int i=l;i<=len;i++){
	    long long xx=hasa[i]-hasa[i-l]*p[l]%mod;
	    long long yy=hasb[i]-hasb[i-l]*p1[l]%modb;
	    //cout<<i<<":"<<xx<<" "<<yy<<endl; 
	    if(ma[make_pair(xx,yy)]==0){
	    	cnt++;
		}
		ma[make_pair(xx,yy)]=1;
	}
	cout<<cnt;
	return 0;
}

到了這里，關(guān)于算法---哈希及其在字符串中的應(yīng)用（字符串hash）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！