哈希表（hash table）又叫散列表，是一種很實用的數(shù)據(jù)結(jié)構(gòu)。首先來看一下百度給出的定義：散列表，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
通俗一點來說，就是我們有一堆值，他們的范圍很大，但是又很分散，直接存儲本身的話會非常占地方，所以我們就把它映射到一個較小的范圍內(nèi)，這樣不但節(jié)省了空間，而且還方便查找。
舉個例子就是，假設(shè)我們要存儲 1000000000 、2000000 、17 這幾個數(shù)，直接存的話就是開一個1000000000的數(shù)組，但是我們只用到了三個位置，有很多位置都浪費了，而且很占地方，運行著運行著就爆內(nèi)存了。所以我們想一個解決辦法，既然只有三個數(shù)，那我們不妨就開一個10的數(shù)組，把它們映射到10以內(nèi)，比如2000000映射為2，所以就把2000000存儲到位置2上；17映射為5，所以就把17存儲到位置5上（不一定按大小順序），然后我們想看看有沒有這幾個數(shù)的時候，只要映射一下，看看映射的位置有沒有就好了。這樣不但節(jié)省了很大的空間，而且還很方便能找到數(shù)據(jù)，因為只有十個位置。雖然多了一個麻煩的映射操作，但是比起哈希表的優(yōu)點，這點小問題微不足道。
但是，這有一個顯而易見的問題。如果不可避免地把倆數(shù)映射到了一個位置上面，那就需要特殊處理一下了。這種現(xiàn)象叫做哈希沖突，下面會詳細(xì)解釋怎么盡可能地避免哈希沖突，以及遇到后該如何解決這個問題。
一、對整數(shù)的哈希
先給出一道簡單的模板題：acwing.模擬散列表
維護(hù)一個集合，支持如下幾種操作：
I x，插入一個數(shù) x；
Q x，詢問數(shù) x 是否在集合中出現(xiàn)過；
現(xiàn)在要進(jìn)行 N 次操作，對于每個詢問操作輸出對應(yīng)的結(jié)果。
輸入格式
第一行包含整數(shù) N，表示操作數(shù)量。
接下來 N 行，每行包含一個操作指令，操作指令為 I x，Q x 中的一種。
輸出格式
對于每個詢問指令 Q x，輸出一個詢問結(jié)果，如果 x 在集合中出現(xiàn)過，則輸出 Yes，否則輸出 No。
每個結(jié)果占一行。
數(shù)據(jù)范圍
1≤N≤105
?109≤x≤109
輸入樣例：5
I 1
I 2
I 3
Q 2
Q 5輸出樣例：
Yes
No
1.1、哈希函數(shù)
對整數(shù)數(shù)據(jù)的映射，叫整數(shù)哈希。
首先我們要設(shè)計一個哈希函數(shù)，也就是映射函數(shù)。當(dāng)然這不用我們自己來設(shè)計，已經(jīng)有被設(shè)計好的哈希方法并且是經(jīng)過前人千錘百煉的，已經(jīng)基本上沒有什么錯誤的方法了。這里只介紹一種方法：除留余數(shù)法。說白了就是讓數(shù)模上另一個數(shù)，以達(dá)到得到其映射位置的一個方法。那么我們要解決的就是模上誰這個問題了。
首先要模上的這個數(shù)是比較有講究的，第一，模的這個數(shù)要是一個質(zhì)數(shù)，這樣可以極大地減少哈希沖突；第二，這個數(shù)要盡量離2的次冪遠(yuǎn)一點，這樣進(jìn)一步減少了哈希沖突的可能。
舉個例子，我們假設(shè)數(shù)據(jù)的范圍是 10-9~109（也即在32位和64位的編譯器上int的“上下限”。在32位和64位編譯器中，int占四個字節(jié)，即 -2147483648到2147483647，是1010級的），數(shù)據(jù)的個數(shù)至多是105。正常情況下，我們會選擇開一個 105+10 的數(shù)組來存儲數(shù)據(jù)，多一點空間為了防止越界，但是這里開數(shù)組就比較有講究：首先要模上的數(shù)就是數(shù)組的長度，所以說，按理來說，應(yīng)該取比數(shù)據(jù)數(shù)量大的第一個質(zhì)數(shù)，這個要根據(jù)實際情況計算一下，這里算出來是100003，它離2的次方也很遠(yuǎn)。
同時要注意的是，因為數(shù)據(jù)中還存在負(fù)數(shù)，但是數(shù)組沒有負(fù)的下標(biāo)，所以我們要特殊處理一下。在C++中，對負(fù)數(shù)的取模就是對這個負(fù)數(shù)的絕對值取模再加個負(fù)號，所以操作很容易。但是其他語言要記得根據(jù)實際情況特殊處理一下。這樣就得到了這個例子中的哈希函數(shù)：
const int N = 100003;
int hash(int x)
{
//正常情況下應(yīng)該是x % N，這是對包含負(fù)數(shù)情況的特殊操作
return (x % N + N) % N;
}
通過這個函數(shù)，我們可以給定一個x，然后得到它對應(yīng)的映射位置。
1.2、哈希沖突
解決了哈希函數(shù)，下一步就要詳細(xì)解釋怎么解決哈希沖突了。
解決哈希沖突的方式有很多種，這里只介紹兩種主流的方式：拉鏈法和開放尋址法。
1.2.1、拉鏈法解決哈希沖突
正如其名，當(dāng)遇到哈希沖突的時候，拉鏈法會在沖突的位置拉一條鏈來依次存放沖突的數(shù)據(jù)。舉個例子，假設(shè)100被哈希到了4，那么這時候：
然后，24也被哈希到了4，所以我們就在100的基礎(chǔ)上延長一下：
這樣就解決了兩個數(shù)的位置沖突的問題。不難想到，其實這就是鏈表嘛，只不過是好多條好多條鏈表。對數(shù)組模擬鏈表有疑問，可以參考我的這篇文章C++：【數(shù)據(jù)結(jié)構(gòu)】用數(shù)組實現(xiàn)的單鏈表和雙向鏈表。有了這個思路，實現(xiàn)起來就很容易了。這里給出例題的題解1（拉鏈法）：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 100003;
//h代表哈希數(shù)組，還有就是鏈表三件套
int h[N], e[N], ne[N], idx;
//處理插入
void insert(int x)
{
int k = (x % N + N) % N;
//相當(dāng)于頭插法
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
//處理詢問
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x) return true;
return false;
}
int main()
{
int n;
cin >> n;
//初始化哈希數(shù)組，將每一個元素都設(shè)置位-1
//相當(dāng)于每個位置都是一個鏈表的頭節(jié)點
//對于memset的講解放在本節(jié)末尾
memset(h, -1, sizeof h);
while (n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') insert(x);
else
{
if (find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
1.2.2、開放尋址法解決哈希沖突
遇到哈希沖突時，開放選址法會從發(fā)生沖突的位置開始，依次向后尋找，直到找到一個空閑的位置，再將它放進(jìn)去。這也暗示了從發(fā)生沖突的位置，到存入數(shù)據(jù)的位置都是被占滿的。當(dāng)找位置找到數(shù)組末尾時，再返回數(shù)組開頭繼續(xù)尋找。
使用開放尋址法時，數(shù)組的大小也是有講究的。數(shù)組一般要開數(shù)據(jù)數(shù)量的兩到三倍，并且取質(zhì)數(shù)。例如例題中給定數(shù)據(jù)數(shù)量不會超過105個，那我們就開一個2×105的數(shù)組，并且通過計算得到大于200000的最小質(zhì)數(shù)為200003，所以我們數(shù)組大小就開200003。一般開到這個長度，發(fā)生沖突的概率就會大大降低，并且一般來說，尋址次數(shù)不會超過5次，所以查找速度也是很快的。
解決了方法問題，下一步就要考慮怎么來表示空位了。因為數(shù)組的每一個元素存儲的都是10-9~109 的數(shù)，所以我們自然不能用在這個范圍里的數(shù)來表示空位。那么我們就用一個比數(shù)據(jù)范圍大的數(shù)來表示空位。這個數(shù)即是 0x3f3f3f3f 。
一般以0x3f3f3f3f作為int的無窮大的原因：
首先int的范圍是 -2147483648到2147483647，最大值也就是2147483647（也即0x7fffffff，也即INT_MAX），但是用它作為無窮大的時候，再加一個數(shù)就會溢出，變成一個很小的數(shù)。在一些其他算法中，這會導(dǎo)致出現(xiàn)問題，所以一般不用它作為無窮大。
用0x3f3f3f3f的好處是，首先它的十進(jìn)制是1061109567，是1010級別的，一般數(shù)據(jù)都小于這個數(shù)。其次，0x3f3f3f3f × 2等于2122219134，并未溢出int的最大值，所以仍是無窮大。
總結(jié)以上所述，就可以實現(xiàn)拉鏈尋址法了：
#include <iostream>
#include <cstdio>
using namespace std;
//設(shè)置null為無窮大
const int N = 200003, null = 0x3f3f3f3f;
int h[N];
//此函數(shù)返回的是將x映射后，合適的位置
//如果用于插入，那么它可以得到該插入的位置
//如果用于查找，那么它不是返回x的存在的位置，就是返回null
int find(int x)
{
int t = (x % N + N) % N;
///依次向后尋址
while (h[t] != null && h[t] != x)
{
t ++ ;
//到達(dá)數(shù)組末尾時，返回開頭元素
if (t == N) t = 0;
}
return t;
}
int main()
{
int n;
cin >> n;
memset(h, 0x3f, sizeof h);
while (n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') h[find(x)] = x;
else
{
if (h[find(x)] == null) puts("No");
else puts("Yes");
}
}
return 0;
}
對于拉鏈尋址法，有一個恰當(dāng)?shù)侵乜谖兜谋扔鳎汉帽认胍卓?，去找坑位，看到一個坑里有人就往前找沒人的坑。（bushi
附注：對memset的解釋
首先來看看memset函數(shù)的原型：
void memset(void *str, int ch, size_t n);
它的作用是：從當(dāng)前位置（即str指向的位置）開始，向后n個字節(jié)全部用ch來代替。
一定要注意，它操作的是字節(jié)。
這里給出一些常用用法：
- 令ch為127，127的二進(jìn)制是01111111，在int型數(shù)組里，四個字節(jié)表示一個數(shù)，那么每個數(shù)都會被初始化為四個01111111，也就是2139062143，常用于把int數(shù)組中的元素全部初始化為很大的數(shù)；
- 令ch為128，128的二進(jìn)制是10000000，四個10000000合起來就是-2139062144（因為最后一位是符號位），常用于初始化為很小的數(shù)；
- 令ch為-1，-1的二進(jìn)制是11111111，四個合起來是32個1，也表示-1，所以可以用于將數(shù)組中的元素全部初始化位-1；
- 令ch為0， 用于將數(shù)組全部元素初始化為0；
- 令ch為0x3f，則對于int數(shù)組來說，每個元素都是0x3f3f3f3f。
二、字符串哈希
和上面提到的整數(shù)哈希類似，字符串哈希就是將某個字符串看作一個數(shù)，并將其映射到哈希數(shù)組中，以達(dá)到快速查找的目的。
那么首先面臨的問題是，如何把字符串看作一個數(shù)。這里采用的是p進(jìn)制法，即把字符串看作是一個p進(jìn)制的數(shù)。舉個例子，ABCD就是 A×p3+B×p2+C×p1+D×p0。這里ABCD具體的值就是它們的ASCII碼。根據(jù)經(jīng)驗，p一般取131或13331，取這兩個數(shù)可以極大地避免沖突。
將字符串看作一個數(shù)后，就要考慮哈希函數(shù)的設(shè)計了。一般用字符串模上的數(shù)是264，這樣可以極大地避免哈希沖突，甚至可以理解為幾乎沒有沖突。這里講到的哈希方法是前綴哈希，舉個例子就是，給一個字符串ABCDEF，我們依次求得A、AB、ABC、ABCD、…、ABCDEF的哈希值，并把它們存放到哈希數(shù)組中位置1、2、3、4、…、6上。用這種方法，可以很快的求得給定字符串的任意子串的哈希值。
下面來看一下實現(xiàn)的方法。這里的用來存儲字符串的數(shù)組是從下標(biāo)1開始的，為了方便計算。首先給一個字符串：
然后要計算它所有前綴字符串的哈希值，也就是A、AB、ABC、…、ABCDEFGH的哈希值。這里的p進(jìn)制采用131進(jìn)制，將每一個前綴字符串看作一個數(shù)，和數(shù)一樣，最右邊是最低位，最左邊是最高位。這樣就得到了字符串所有前綴字符串的哈希數(shù)組，順便預(yù)處理一下p的冪，留著右面有用：
h[0] = 0, p[0] = 1;
for (int i = 1; i < n; i ++ )
{
h[i] = h[i - 1] * p + str[i];
p[i] = p[i - 1] * p;
}
處理完后的p數(shù)組是：
可以看到，下標(biāo)對應(yīng)的即是131的次冪。
這時候可能會有人發(fā)現(xiàn)，你這哈希數(shù)組也沒哈希啊。是這樣的，這是因為我們耍了一些卑劣的小詭計。把h數(shù)組和p數(shù)組開成unsigned long long類型（取值范圍0~18 446 744 073 709 551 615（264-1）），這種類型在溢出后是自動取模的，而unsigned long long的范圍是264-1，所以在溢出后會自動對264取模，這也就省去了進(jìn)行取模操作的步驟。
通過以上操作，我們得到了前綴字符串的哈希數(shù)組，其中每個元素代存儲每個前綴字符串的值。也就是下標(biāo)1存儲長度為1的前綴，下標(biāo)2存儲長度為2的前綴。
接下來，就要實現(xiàn)它的作用了，也就是快速查找它的任意一個子串。因為在這套算法里面，每個不同的字符串都對應(yīng)一個值（幾乎不考慮沖突），所以每個子串也都對應(yīng)一個值。比如ABCDEFGH中，它的子串CDE、DEFG等都對應(yīng)了一個特定的映射值。那么我們該如何求得這個映射值呢？下面來看過程：
假如已經(jīng)求得ABCDEFGH的前綴哈希數(shù)組，這時候要求子串CDE的哈希值。很自然地想到，用ABCDE減去AB就得到了CDE，方法是正確的，但是有一點需要特殊處理一下：在ABCDE中，B是第3位，在AB中，B是第0位。但是按照我們的目的即得到DE，那按照減法規(guī)則要讓對應(yīng)的位對齊。舉個例子，給一個數(shù)123456，我們想得到56，肯定不是讓123456減去1234吧，而是讓123456減去123400，這就是一個對齊的過程。
如圖所示，我們要讓AB對齊后，再用ABCDE減去AB，才能得到正確的DE。對齊過程也就是對AB進(jìn)行移位的過程，那么要移多少位呢？子串CDE的右邊界是下標(biāo)5，左邊界是下標(biāo)3，移動的位數(shù)也就是 right-left+1 ，所以我們就==把待減去的子串乘以 131的right-left+1次方 ==就完事了。
這就是字符串哈希的一種例子，下面給出一道模板題并給出題解。acwing.字符串哈希
給定一個長度為 n 的字符串，再給定 m 個詢問，每個詢問包含四個整數(shù) l1,r1,l2,r2，請你判斷[l1,r1] 和 [l2,r2] 這兩個區(qū)間所包含的字符串子串是否完全相同。
字符串中只包含大小寫英文字母和數(shù)字。輸入格式
第一行包含整數(shù) n 和 m，表示字符串長度和詢問次數(shù)。
第二行包含一個長度為 n 的字符串，字符串中只包含大小寫英文字母和數(shù)字。
接下來 m 行，每行包含四個整數(shù) l1,r1,l2,r2，表示一次詢問所涉及的兩個區(qū)間。
注意，字符串的位置從 1 開始編號。輸出格式
對于每個詢問輸出一個結(jié)果，如果兩個字符串子串完全相同則輸出 Yes，否則輸出 No。
每個結(jié)果占一行。數(shù)據(jù)范圍
1≤n,m≤105
輸入樣例：8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2輸出樣例：
Yes
No
Yes文章來源：http://www.zghlxwxcb.cn/news/detail-770358.html
#include <iostream>
#include <cstdio>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
char str[N];
ULL p[N], h[N];
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
int n, m;
cin >> n >> m;
scanf("%s", str + 1);
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
while (m -- )
{
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}
這里有一個問題沒提到，就是p數(shù)組（即存放p的冪的數(shù)組）是指數(shù)級增長的，很快就會突破上限。我們假如在范圍上10次方的時候突破上限了，我們只有在想要查找的子串長度大于10的時候才會用到p的10次方，此時較長的前綴（即被減的前綴）一定也大于p的十次方了，已經(jīng)進(jìn)行取模操作了，就這樣，在一種神奇的機(jī)緣巧合之下，你取模，我也取模，就得到了正確答案。感興趣的朋友可以自己深入研究一下，在這里本人就不深入探討了。文章來源地址http://www.zghlxwxcb.cn/news/detail-770358.html
到了這里，關(guān)于C++：【數(shù)據(jù)結(jié)構(gòu)】哈希表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
