目錄

• 前言
• hash介紹
• 字符串hash初步
• 練習題

前言

散列(hash)是常用的算法之一。
為了了解hash我們先看一個簡單的題。
題目:

給出N個正整數，再給出M個正整數，問這M個數中的每個數分別是否在N個數中出現過， 其中N,M<=100000,且每個正整數均不超過100000。 例: M=3 (1,2,4) N=3 (1,2,7) 1,2出現過 7沒有出現過

最簡單的思路當輸入M中的數時就遍歷一次N。這樣算法的復雜度為O(MN)
當M和N很大的時候，算法顯然太慢了。
那么如何做呢? 不妨用空間換時間
設定一個bool型數組hashTable[100010] , 其中hashTable[x]=true表示正整數x在N中出現過,
而hashTable[x]=false表示正整數x在N中沒有出現過。
這樣就可以在一開始讀入N個正整數時就進行預處理，即當讀入的數為x時，就令hashTable[x]=true
(說明:hashTable數組需要初始化為false,表示初始化狀態下所有數均未出現過)。
于是,對M個欲查詢的數，就能直接通過hashTable數組判斷出每個數是否出現過。
這種算法的復雜度為O(N+M)。
代碼如下:

#include<cstdio> #include<algorithm> using namespace std; bool a[100010]={false}; int main(void) {int M,N;int N_number,M_number;int i,j;scanf("%d%d",&N,&M);for(i=0;i<N;i++){scanf("%d",&N_number);a[N_number]=true;}for(i=0;i<M;i++){scanf("%d",&M_number);if(a[M_number]==true)printf("Yes\n");elseprintf("No\n");}return 0; }

如果問的是求M中的數字，在N中的數字中出現的次數。
只需要把數組定義為int型，找到一次就hashTable[x]++就可以了
代碼如下:

#include<cstdio> #include<algorithm> using namespace std; int a[100010]={0}; int main(void) {int M,N;int N_number,M_number;int i,j;scanf("%d%d",&N,&M);for(i=0;i<N;i++){scanf("%d",&N_number);a[N_number]++;}for(i=0;i<M;i++){ scanf("%d",&M_number);printf("%d\n",a[M_number]);}return 0; }

上面的兩個問題都有一個特點，那就是直接把輸入的數作為數組的下標來對這個數的性質進行統計(這種做法非常實用，請務必牢記)。

hash介紹

接著上面的習題，你會發現一個問題就是輸入的數太大(10⁹)或者輸入的是一個一個字符串，就不能直接作為數組的下標了。
要是有一種方法可以把這些亂七八糟的元素轉換為一個在能接受范圍內的整數，那該多好啊。

于是散列(hash) 就誕生了。一般來說，散列可以濃縮成一句話"將元素通過一個函數轉換為整數，使得該整數可以盡量唯一地代表這個元素“。其中把這個轉換函數稱為散列函數H ,也就是說，如果元素在轉換前為key,那么轉換后就是一個整數H(key)。
那么對key是整數的情況來說，有哪些常用的散列函數呢？
一般來說，常用的有:直接定址法、平方取中法、除留余數法等，
其中直接定址法是指恒等變換(即H(key)=key,本節開始的問題就是直接把key作為數組下標,是最常見最實用的散列應用)或是線性變換(即，H(key)=a*key+b);而平方取中法是指key的平方的中間若干位作為hash值(很少用)。
除留余數法是比較實用的。
陳留余數法是指把key除以一個數mod得到的余數作為hash值的方法，即 H(key)=key%mod
通過這個散列函數，可以把很大的數轉換為不超過mod的整數，這樣就可以將它作為可行的數組下標(注意 : 表長TSize必須不小于mod,否則會產生越界)。顯然，當mod是一個素數時,H(key)能盡可能覆蓋 [0,mod) 范圍內的每一個數.因此一般為了方便起見，下文中取TSize是一個素數，而mod直接取成與TSize相等。

其實你會發現一個問題，通過除留余數法可能會有兩個不同的數key1和key2,它們的hash值H(key1)與H(key2)是相同的，這樣當key1已經把表中位置為H(key1)的單元占據時,key2便不能再使用這個位置了。我們把這種情況叫做 “沖突”。

既然沖突不可避免，那就要想辦法解決沖突。下面以三種方法來解決沖突為例，其中第一種和第二種都計算了新的hash值，又稱為開放定址法

線性探查法(Linear Probing)
當得到key的hash值H(key),但是表中下標為H(key)的位置已經被某個其他元素使用了，那么就檢查下一個位置H(key) +1是否被占，如果沒有，就使用這個位置；否則就繼續檢查下一個位置(也就是將hash值不斷加1),如果檢查過程中超過了表長，那么就回到表的首位繼續循環，直到找到一個可以使用的位置，或者是發現表中所有位置都已被使用。顯然，這個做法容易導致扎堆，即表中連續若干個位置都被使用，這在一定程度上會降低效率。

平方探查法(Quadratic probing)
在平方探查法中，為了盡可能避免扎堆現象，當表中下標為H(key)的位置被占時，將按下面的順序檢查表中的位置: H(key)+ 1²、H(key)-1²、H(key)+2²、H(key)-2²、H(key) + 3²、…如果檢查過程中H(key)+k²超過了表長TSize,那么就把H(key)+ k²對表長TSize取模；如果檢查過程中出現H(key)- k²<0的情況(假設表的首位為0)，那么將(H(key) -k²%TSize +TSize)% TSize作為結果(等價于將H(key)- k²不斷加上TSize直到出現第一個非負數)。如果想避免負數的麻煩，可以只進行正向的平方探查。可以證明，如果k在[0, TSize)范圍內都無法找到位置，那么當k≥TSize時，也一定無法找到位置。

鏈地址法(拉鏈法)
和上面兩種方法不同，鏈地址法不計算新的hash值，而是把所有H(key)相同的key連接成一條單鏈表。這樣可以設定一個數組 Link,范圍是Link[0] ~ Link[mod- 1]， 其中Link[h]存放H(key)= h的一條單鏈表，于是當多個關鍵字key 的hash值都是h時，就可以直接把這些沖突的key直接用單鏈表連接起來，此時就可以遍歷這條單鏈表來尋找所有H(key)=h的key。
當然，一般來說，可以使用標準庫模板庫中的map 來直接使用hash的功能(C++11以后可以用unordered_map, 速度更快),因此除非必須模擬這些方法或是對算法的效粹要求比較高，一般不需要自己實現上面解決沖突的方法。

字符串hash初步

如果key不是整數，那么又應當如何設計散列函數呢?

一個例子是: 如何將一個二維整點P的坐標映射為一個整數，使得整點P可以由該整數唯一地代表。假設一個整點P的坐標是(x,y),其中0≤x, y≤Range,那么可以令hash函數為H§=X* Range+ y,這樣對數據范圍內的任意兩個整點P與P2, H(P1)都不會 等于H(P2),就可以用H( P )來唯一地代表該整點 P,接著便可以通過整數hash的方法來進一步映射到較小的范圍。

字符串hash是指將一個字符串 S映射為一個整數，使得該整數可以盡可能唯一地代表字符串 S。
為了討論問題方便，先假設字符串均由大寫字母A-Z構成。在這個基礎上，不妨把A~ Z 視為0~25，這樣就把26個大寫字母對應到了二十六進制中。接著，按照將二十六進制轉換為十進制的思路，由進制轉換的結論可知，在進制轉換過程中，得到的十進制肯定是唯一的，由此便可實現將字符串映射為整數的需求(注意:轉換成的整數最大為是26^len-1, 其中len 為字符串長度)。
代碼如下:

int hushFunc(char s[],int len)//將字符串轉換成整數 {int id=0;for(int i;i<len;i++){id=id*26+s[i]-'A';//將26進制轉換為10進制}return id; }

顯然，如果字符串S的長度較長，那么轉換成的整數也會很大,因此需要注意使用時len不能太長。如果字符串中出現了小寫字母，那么可以把 A~Z作為0-25，而把a-z作為26-51,這樣就變成了52進制轉換為10進制的問題，做法也是相同的;

int hushFunc(char s[]),int len) {int id=0;for(int i;i<len;i++){if(s[i]>='a'&&s[i]<='z')id=id*52+s[i]-'A'+26;else if(s[i]>='A'&&s[i]<='Z')id=id*52+s[i]-'A';}return id; }

而如果出現了數字，一般有兩種處理方法：

按照小寫字母的處理方法，增大進制數至62。

如果保證在字符串的末尾是確定個數的數字，那么就可以把前面英文字母的部分按上面的思路轉換成整數，再將末尾的數字直接拼接上去。例如對由三個字符加一位數字組成的字符串“BCD4"來說，就可以先將前面的“BCD"轉換為整數(12626+2*26+3)731,然后直接拼接上末位的4變為7314即可

下面的代碼體現了這個例子：

int hushFunc(char s[]),int len) {int id=0;for(int i;i<len-1;i++)//末位為數字，所以排除末位{if(s[i]>='a'&&s[i]<='z')id=id*52+s[i]-'A'+26;else if(s[i]>='A'&&s[i]<='Z')id=id*52+s[i]-'A';}id=id*10+s[len-1]-'0';return id; }

練習題

給出N個字符串(由恰好三位大寫字母組成)，再給出M個查詢字符串，問每個查詢字符串在N個字符串中出現的次數。

#include<cstdio> int hushF(char a[],int len) {int id=0;for(int i=0;i<len;i++){id=id*26+a[i]-'A';}return id; } int hush[26*26*26+10]; char s[100][5],temp[5]; int main(void) {int M,N;int i;scanf("%d%d",&N,&M);for(i=0;i<N;i++){scanf("%s",s[i]);hush[hushF(s[i],3)]++;}for(i=0;i<M;i++){scanf("%s",temp);printf("%d\n",hush[hushF(temp,3)]);} }

總結

以上是生活随笔為你收集整理的散列(哈希 hash)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。