圖解:什么是哈希?

為什么要有哈希？

假設(shè)我們要設(shè)計一個系統(tǒng)來存儲將員工手機號作為主鍵的員工記錄，并希望高效地執(zhí)行以下操作：

1. 插入電話號碼和相應(yīng)的信息。（插入）
2. 搜索電話號碼并獲取信息。（查找）
3. 刪除電話號碼及相關(guān)信息。（刪除）

我們可以考慮使用以下數(shù)據(jù)結(jié)構(gòu)來維護不同電話所對應(yīng)的信息：

1. 數(shù)組
2. 鏈表
3. 平衡二叉樹（紅黑樹等等）
4. 直接訪問表

對于數(shù)組和鏈表而言，我們需要以線性的方式進行查找，這在實際應(yīng)用中代價太大；如果我們使用數(shù)組且保證數(shù)組中電話號碼有序排列，那么使用二分查找可將查找電話號碼的時間復(fù)雜度降到 ，但同時由于要維持?jǐn)?shù)組的有序性，插入和刪除操作的代價將變大 。

對于平衡二叉查找樹而言，插入、查找和刪除操作的時間復(fù)雜度均為 ，這似乎已經(jīng)看著很不錯了，那么是否有更好的數(shù)據(jù)結(jié)構(gòu)呢？

再來看直接訪問表的方式，首先創(chuàng)建一個大數(shù)組（至少能夠用電話號碼作為數(shù)組下標(biāo)），如果電話號碼沒有出現(xiàn)在數(shù)組當(dāng)中，就在相應(yīng)下標(biāo)填充 NULL ；如果電話號碼出現(xiàn)了，則下標(biāo)中數(shù)據(jù)填充該電話號碼關(guān)聯(lián)的記錄的地址。

這樣一來，插入、查找和刪除的時間復(fù)雜度將降為 ，比如插入一條記錄（15002629900，0xFF0A “可愛的讀者”），只需要將手機號碼 15002629900 當(dāng)做下標(biāo)，然后在該下標(biāo)的位置填充記錄的地址，即 arr[15002629900] = 0xFF0A;

但是直接訪問表有實踐上的限制。首先需要申請額外的存儲空間，并且存在大量的空間浪費。比如對于一個含有 n 位的電話號碼，我們需要 的空間復(fù)雜度，其中 m 表示數(shù)據(jù)本身所占用的空間。另外一個問題是，編程語言本身提供的整型無法表示電話號碼。

由于上述限制，使用直接訪問表并不是最明智的方法。而哈希則是解決以上問題的最好數(shù)據(jù)結(jié)構(gòu)，并且與上面所提到的數(shù)據(jù)結(jié)構(gòu)（數(shù)組，鏈表，AVL樹）在實踐中相比，性能非常好。通過哈希，可以在 的時間復(fù)雜度內(nèi)實現(xiàn)插入、查找和刪除操作（在合理的假設(shè)下），最壞情況下為 的時間復(fù)雜度。

哈希是對直接訪問表的改進。使用哈希函數(shù)將給定的電話號碼或任何其他鍵轉(zhuǎn)換為較小的數(shù)字，將該較小的數(shù)字稱為哈希表的索引（哈希值）

什么是哈希表？

哈希表和直接訪問表很類似，同樣是一個用于存儲指向給定電話號碼對應(yīng)記錄的指針的數(shù)組，只不過，此時的數(shù)組下標(biāo)不再是電話號碼，而是經(jīng)過哈希函數(shù)映射后的輸出值。

什么是哈希函數(shù)？

哈希函數(shù)用于將一個大數(shù)（手機號碼）或字符串映射為一個可以作為哈希表索引的較小整數(shù)的函數(shù)。比如活動開發(fā)中經(jīng)常使用的 MD5 和 SHA 都是歷史悠久的Hash算法。

[lovefxs@localhost?~]$?echo?-n??"I?love?J"??|?openssl?md5?
(stdin)=?ef821d9b424fd5f0aac7faf029152e04

一個好的哈希函數(shù)應(yīng)該滿足四個條件：

1. 執(zhí)行效率要高（效率高）

對于一段很長的字符串或者二進制文本也能快速計算出哈希值。

1. 散列結(jié)果應(yīng)當(dāng)具有同一性（輸出值盡量均勻，越均勻沖突就越少）。（同一性）

例如對于電話號碼而言，一個好的哈希函數(shù)應(yīng)該考慮電話號碼的后四位，而一個糟糕的哈希算法可能考慮電話號碼的前四位，因為后四位更有區(qū)分性，相當(dāng)于輸入更加分散，那么輸出也可能更加均勻，當(dāng)然這兩種選擇方式都不是什么好辦法，只是希望大家理解同一性原理。

1. 雪崩效應(yīng)（微小的輸入值變化使得輸出值發(fā)生巨大的變化）。

[lovefxs@localhost?~]$?echo?-n??"I?love?J"??|?openssl?md5?
(stdin)=?ef821d9b424fd5f0aac7faf029152e04
[lovefxs@localhost?~]$?echo?-n??"I?love?Y"??|?openssl?md5?
(stdin)=?fb49af24bebae07658650ae8eb1c0f5b

其中輸入 I love J 和 I love Y 只改變了一個字母，輸出值卻千差萬別。

1. 從哈希函數(shù)的輸出值不可反向推導(dǎo)出原始的數(shù)據(jù)。（不可反向推導(dǎo)）

比如上面的原始數(shù)據(jù) I love J ?與經(jīng)過 MD5 算法映射后的輸出值之間沒有對應(yīng)關(guān)系。

什么是 Hash 碰撞?

由于哈希函數(shù)的原理是將輸入空間的一個較大的值映射成 hash 空間內(nèi)一個較小的值，那么就會出現(xiàn)兩個不同的輸入值被映射到了同一個較小的輸出值。當(dāng)一個新插入的值被哈希函數(shù)映射到了哈希表中一個已經(jīng)被占用的槽，就認為產(chǎn)生了 Hash 碰撞（沖突）。

那么這種沖突是否可以避免呢？

答案是只能緩解，不可避免。

由于哈希函數(shù)的原理是將輸入空間一個較大的值映射到一個較小的 Hash 空間內(nèi)，而 Hash空間一般遠小于輸入的空間。根據(jù)抽屜原理，一定會存在不同的輸入被映射成同一輸出的情況。

何為抽屜原理？

桌上有十個蘋果，要把這十個蘋果放到九個抽屜里，無論怎樣放，我們會發(fā)現(xiàn)至少會有一個抽屜里面放不少于兩個蘋果。這一現(xiàn)象就是“抽屜原理”。抽屜原理的一般含義為：“如果每個抽屜代表一個集合，每一個蘋果就可以代表一個元素，假如有n+1個元素放到n個集合中去，其中必定有一個集合里至少有兩個元素。” 抽屜原理有時也被稱為鴿巢原理。它是組合數(shù)學(xué)中一個重要的原理

知道了為什么哈希碰撞不可避免，那哈希碰撞該如何緩解呢？

Hash 碰撞的解決方案?

1. 鏈地址法
2. 開放地址法
3. 再哈希

鏈地址法

鏈地址法的思想就是將所有發(fā)生碰撞的元素用一個單鏈表串起來。

我們以一個簡單的哈希函數(shù) H(key) = key MOD 7 （除數(shù)取余法）對一組元素 [50, 700, 76, 85, 92, 73, 101] 進行映射，來理解鏈地址法處理 Hash 碰撞。

除數(shù)為 7 ，初始化一個大小為 7 的空 Hash 表：

然后插入元素 50 ，首先對 50 % 7 = 1 ，得到其哈希值 1 ，在下標(biāo)為 1 的位置插入 50 ：

然后計算 700 % 7 = 0 ，76 % 7 = 6 ，得到的哈希值均未發(fā)生碰撞，填入相應(yīng)位置：

然后計算 85 % 7 = 1 ， 但是下標(biāo)為 1 的位置已經(jīng)有元素 50 ，發(fā)生了碰撞，所以使用單鏈表將 85 和 50 鏈接起來：

以同樣的方式插入所有元素得到如下的哈希表。鏈地址法解決沖突的方式與圖的鄰接表存儲方式在樣式上很相似，思想還是蠻簡單，發(fā)生沖突，就用單鏈表組織起來。

鏈地址法實現(xiàn)

首先創(chuàng)建一個空的哈希表，哈希表的表長為 。

哈希函數(shù)：Hash(key) = key % N

插入：計算要插入關(guān)鍵字 key 的哈希值 Hash(key) ，然后在哈希表中找到對應(yīng)哈希值的位置，再將 key 插入鏈表的末尾；

刪除：計算要刪除關(guān)鍵字 key 的哈希值 Hash(key) ，然后在哈希表中找到對應(yīng)哈希值的位置，再將 key 充鏈表中刪除。

查找：計算要查找關(guān)鍵字 key 的哈希值 Hash(key) ，然后在哈希表中找到對應(yīng)哈希值的位置，從該位置開始進行單鏈表的線性查找。

using?namespace?std;?
??
class?Hash?
{?
????int?N;????//?哈希表的表長??
????//?指向?qū)?yīng)存儲下標(biāo)的指針。
????list<int>?*table;?
public:?
????Hash(int?V);?
????void?insertKey(int?x);?
????void?deleteKey(int?key);?????
????int?hashFunction(int?x)?{?
????????return?(x?%?N);?
????}?
??
????void?displayHash();?
};?
??
Hash::Hash(int?b)?
{?
????this->N?=?b;?
????table?=?new?list<int>[N];?
}?
??
void?Hash::insertKey(int?key)?
{?
????int?index?=?hashFunction(key);?
????table[index].push_back(key);??
}?
??
void?Hash::deleteKey(int?key)?
{?
?//計算key的哈希值?Hash(key)
?int?index?=?hashFunction(key);?
??
????//找到?index
????list?<int>?::?iterator?i;?
????for?(i?=?table[index].begin();?
??????i?!=?table[index].end();?i++)?{?
?????if?(*i?==?key){
???break;?
????????}
??}?
??//如果找到了對應(yīng)的key，刪除之
??if?(i?!=?table[index].end())?
????table[index].erase(i);?
}?
??
//?輸出哈希表
void?Hash::displayHash()?{?
????for?(int?i?=?0;?i?????????cout?<?????for?(auto?x?:?table[i]){
?????????cout?<"?-->?"?<????????}?
?????cout?<endl;?
????}?
}?
?
int?main()?
{?
????int?a[]?=?{50,?700,?76,?85,?92,?73,?101};?
????int?n?=?sizeof(a)/sizeof(a[0]);?
??
????Hash?h(7);
????for?(int?i?=?0;?i?????????h.insertKey(a[i]);??
????}??
????h.deleteKey(92);?
????h.displayHash();?
??
????return?0;?
}?

鏈地址法的優(yōu)缺點：

優(yōu)點：

1. 實現(xiàn)起來簡單；
2. 哈希表永遠不會溢出，我們可以向單鏈表中添加更多的元素；
3. 對于哈希函數(shù)和裝填因子（后面會說）的選擇沒啥要求；
4. 在不知道要插入和刪除關(guān)鍵字多少和頻率的情況下，鏈地址法有絕對優(yōu)勢。

缺點：

1. 由于使用鏈表來存儲關(guān)鍵字，鏈地址法的緩存性能不佳。開放尋址法使用連續(xù)的地址空間進行存儲，所以緩存性能更好。
2. 浪費空間（因為哈希表的有些位置從未被使用）。
3. 如果鏈表太長，在最壞的情況下查找的時間復(fù)雜度將變?yōu)? 。
4. 需要額外的空間存儲鏈表指針。

鏈地址法的性能

假設(shè)任何一個關(guān)鍵字都以相等的相等的概率被映射到哈希表的任意一個槽位。

其中 ?表示哈希表的槽位數(shù)， 表示插入到哈希表中的關(guān)鍵字的數(shù)目。

裝填因子（load factor） （將 n 個球隨機均勻地扔進 m 個箱子里的概率）。

期望的查找，插入和刪除的時間均等于

當(dāng) 為 量級時，鏈地址法的插入、查找和刪除操作的時間復(fù)雜度就是 量級。

極端情況下我們將 n 個數(shù)都扔進了同一個槽，也就是 n 個數(shù)形成了一個單鏈表，那么時間復(fù)雜度將降為 ，但這個概率微乎其微。

開放地址法

與鏈地址法一樣，開放地址法也是一個經(jīng)典的處理沖突的方式。只不過，對于開放地址法，所有的元素都是存儲在哈希表當(dāng)中的，所以無論任何時候都要保證哈希表的槽位數(shù) ?大于或等于關(guān)鍵字的數(shù)目 （必要的時候，我們還會復(fù)制舊數(shù)據(jù)，然后對哈希表進行動態(tài)擴容）。

開放地址法分三種方式。

線性探測法（Linear Probing）

設(shè) Hash(key) 表示關(guān)鍵字 key 的哈希值， 表示哈希表的槽位數(shù)（哈希表的大?。?。

線性探測法則可以表示為：

如果 Hash(x) % M 已經(jīng)有數(shù)據(jù)，則嘗試 (Hash(x) + 1) % M ;

如果 (Hash(x) + 1) % M 也有數(shù)據(jù)了，則嘗試 (Hash(x) + 2) % M ;

如果 (Hash(x) + 2) % M 也有數(shù)據(jù)了，則嘗試 (Hash(x) + 3) % M ;

......

我們同樣以哈希函數(shù) H(key) = key MOD 7 （除數(shù)取余法）對 [50, 700, 76, 85, 92, 73, 101] 進行映射，來理解線性探測法處理 Hash 碰撞。

依次計算 50 % 7 = 1 、700 % 7 = 0 及 76 % 7 = 6 ，均沒有發(fā)生沖突（碰撞），則直接放入相應(yīng)的位置：

計算 85 % 7 = 1 ，但是下標(biāo) 1 的位置已經(jīng)有元素 50 ，發(fā)生碰撞，則尋找下一個可以存放元素 85 的空位 (85 % 7 + 1) % 7 = 2 ，下標(biāo)二沒有元素，所以將 85 放進去：

計算 92 % 7 = 1 ，50 已經(jīng)在 1 的位置，發(fā)生碰撞；線性探測下一個位置 (92 % 7 + 1） % 7 = 2 ，85 已經(jīng)在 2 的位置，發(fā)生碰撞；線性探測下一個位置 ?(92 % 7 + 2） % 7 = 3 ，此時為空位，填入 92 :

計算 73 % 7 = 3 ，92 已經(jīng)占用了 3 號位置，發(fā)生碰撞；線性探測下一個位置 (73 % 7 + 1） % 7 = 4 ，此時為空位，填入 73 :

計算 101 % 7 = 3 , 3 號位置已經(jīng)有元素，發(fā)生碰撞；線性探測下一個位置 (101 % 7 + 1） % 7 = 4 ，4 號位置已有元素，發(fā)生碰撞；線性探測下一個位置 (101 % 7 + 2） % 7 = 5 ， 此時為空，填入 101 :

到這里你不難看出線性探測的缺陷，容易產(chǎn)生聚集（發(fā)生碰撞的元素形成組，比如 [50,85,92,73,101] 之間均是由于碰撞而緊挨著），而且發(fā)生碰撞的情況大大增加，需要花費更多的時間來尋找空閑的槽位和查找元素。

至于（lazy delete）懶刪除就是并不將存儲空間釋放，只是將里面的數(shù)據(jù)清除。

比如刪除元素 92 ，先計算 92 % 7 = 1 ，但是發(fā)現(xiàn)下標(biāo) 1 是 50，線性向下探測 (92 % 7 + 1） % 7 = 2 ，下標(biāo) 2 為 85，繼續(xù)線性向下探測 (92 % 7 + 2） % 7 = 3 ，發(fā)現(xiàn)下標(biāo) 3 剛好為 92，將該存儲單元的數(shù)據(jù)清空。

平方探測法（Quadratic Probing)

所謂 Quadratic Probing，就是每次向下探測的寬度變成了 ，其中的 表示迭代次數(shù)。

設(shè) Hash(key) 表示關(guān)鍵字 key 的哈希值， 表示哈希表的槽位數(shù)（哈希表的大?。?。

平方探測法則可以表示為：

如果 Hash(x) % M 已經(jīng)有數(shù)據(jù)，則嘗試 (Hash(x) + 1 * 1) % M ;

如果 (Hash(x) + 1 * 1) % M 也有數(shù)據(jù)了，則嘗試 (Hash(x) + 2 * 2) % M ;

如果 (Hash(x) + 2 * 2) % M 也有數(shù)據(jù)了，則嘗試 (Hash(x) + 3 * 3) % M ;

............

雙重哈希（Double Hashing）

對于雙重哈希，我們需要一個新的哈希函數(shù) Hash2(key) ，而且對于第 i 次迭代探測，我們查找的位置為 i * Hash2(key) .

設(shè) Hash(key) 表示關(guān)鍵字 key 的一個哈希值， Hash2(key) 表示關(guān)鍵字 key 的另一個哈希值， 表示哈希表的槽位數(shù)（哈希表的大?。?。

雙重哈希探測法則可以表示為：

如果 Hash(x) % M 已經(jīng)有數(shù)據(jù)，則嘗試 (Hash(x) + 1 * Hash2(x)) % M ;

如果 (Hash(x) + 1 * Hash2(x)) % M 也有數(shù)據(jù)了，則嘗試 (Hash(x) + 2 * Hash2(x)) % M ;

如果 (Hash(x) + 2 * Hash2(x)) % M 也有數(shù)據(jù)了，則嘗試 (Hash(x) + 3 * Hash2(x)) % M ;

............

開放地址法的實現(xiàn)

using?namespace?std;?
??
//?哈希表的大小?
#define?TABLE_SIZE?13?
??
//?用于定義?Hash2(key)
#define?PRIME?7?

class?DoubleHash?{?
????//?定義一個哈希表?
????int*?hashTable;?//int[]?hashTable;
????int?curr_size;?
??
public:?
????//?判斷哈希表是否滿了
????bool?isFull()?
????{?
????????//當(dāng)前的大小大于哈希表的大小
????????return?(curr_size?==?TABLE_SIZE);?
????}?
??
????//?哈希函數(shù)1
????int?hash1(int?key)?
????{?
????????return?(key?%?TABLE_SIZE);?
????}?
??
????//?哈希函數(shù)2
????int?hash2(int?key)?
????{?
????????return?(PRIME?-?(key?%?PRIME));?
????}?
???
????DoubleHash()?
????{?
????????hashTable?=?new?int[TABLE_SIZE];?
????????curr_size?=?0;?
????????for?(int?i?=?0;?i?????????????hashTable[i]?=?-1;???
????????}
????}?
??
????//?插入操作
????void?insertHash(int?key)?
????{?
????????//?判斷哈希表是否已滿
????????if?(isFull())?
????????????return;?
??
????????//?獲取哈希函數(shù)1計算的結(jié)果
????????int?index?=?hash1(key);?
??
????????//?如果發(fā)生碰撞?
????????if?(hashTable[index]?!=?-1)?{?
????????????//由哈希函數(shù)2獲取另一個哈希值
????????????int?index2?=?hash2(key);?
????????????int?i?=?1;?
????????????while?(1)?{?
????????????????//得到雙重哈希的索引，對于線性探測，平方探測改這里就可以
????????????????int?newIndex?=?(index?+?i?*?index2)?%?TABLE_SIZE;?
??
????????????????//如果新的哈希值newIndex為空，退出循環(huán)。
????????????????if?(hashTable[newIndex]?==?-1)?{?
????????????????????hashTable[newIndex]?=?key;?
????????????????????break;?
????????????????}?
????????????????i++;?
????????????}?
????????}?
????????else{
????????????hashTable[index]?=?key;?
????????}
????????curr_size++;?
????}?
??
????//?哈希表查找操作
????void?search(int?key)?
????{?
????????int?index1?=?hash1(key);?
????????int?index2?=?hash2(key);?
????????int?i?=?0;?
????????while?(hashTable[(index1?+?i?*?index2)?%?TABLE_SIZE]?!=?key)?{?
????????????if?(hashTable[(index1?+?i?*?index2)?%?TABLE_SIZE]?==?-1)?{?
????????????????cout?<":\t哈希表中不存在"?<endl;?
????????????????//java?這里自己改成響應(yīng)輸出
????????????????return;?
????????????}?
????????????i++;?
????????}?
????????cout?<"找到啦！"?<endl;?
????}?
??
????//?打印輸出
????void?displayHash()?
????{?
????????for?(int?i?=?0;?i?????????????if?(hashTable[i]?!=?-1)?
????????????????cout?<"?-->?"
?????????????????????<endl;?
????????????else
????????????????cout?<endl;?
????????}?
????}?
};?

int?main()?
{?
????int?a[]?=?{50,?700,?76,?85,?92,?73,?101};?
????int?n?=?sizeof(a)?/?sizeof(a[0]);?
??
????//創(chuàng)建哈希表，插入a[]中的元素
????DoubleHash?h;?
????for?(int?i?=?0;?i?????????h.insertHash(a[i]);?
????}?
????//查找
????h.search(36);?//不存在
????h.search(101);?//存在
????//打印輸出
????h.displayHash();?
????return?0;?
}?

至于線性探測和平方探測的實現(xiàn)比較簡單，只需要修改一下代碼中 newIndex 的計算方式即可。

線性探測：

int?newIndex?=?(index?+?i)?%?TABLE_SIZE;?

平方探測：

int?newIndex?=?(index?+?i*i)?%?TABLE_SIZE;?

以上三種探測方法的比較：

線性探測具有最佳的緩存性能，但會受到原始聚集（primary cluster）的影響。線性探測易于計算。

何為原始聚集（原始聚集是相對于線性探測而言的）？

如圖所示，如果對于任意一個關(guān)鍵字 key ，其哈希值 Hash(key) 指向圖中從左向右的紅色箭頭的任意位置，聚集（圖中的淺藍色區(qū)域）都將得到擴充，而隨著聚集的不斷擴充，這個聚集會越來越大。

還不理解聚集的概念的話，我們一起看個例子：

上圖中的 700，50，76 在插入的時候均未產(chǎn)生碰撞，所以以元素本身單位構(gòu)成聚集（聚集的大小為 1，此時可以認為不是聚集）。

但是之后插入的元素就不一樣了，85 與 50 發(fā)生碰撞，插入到了 50 的后面，導(dǎo)致聚集變大。

插入 92 與 50 發(fā)生碰撞，線性探測插入到了 85 之后，聚集進一步擴大。

插入 73 與 92 產(chǎn)生碰撞，線性探測插入到 92 之后，聚集進一步擴大。

插入 101 與 92 產(chǎn)生碰撞，線性探測插入到 73 之后，聚集進一步擴大。

這就是原始聚集的概念，顯然聚集越大，產(chǎn)生碰撞的可能越來越大，哈希算法的性能也會受到影響。

平方探測在緩存性能和受聚集影響方面介于兩者中間，平方探測隨解決了線性探測的原始聚集問題，但是同時也會產(chǎn)生更細的二次聚集問題。

二重探測的緩存性能較差，但不用擔(dān)心聚集的情況，但同時由于要計算兩個散列函數(shù)，時間性能方面受限。

開放地址法的性能分析

與鏈地址法類似，假設(shè)任何一個關(guān)鍵字都以相等的相等的概率被映射到哈希表的任意一個槽位。

其中 ?表示哈希表的槽位數(shù)， 表示插入到哈希表中的關(guān)鍵字的數(shù)目。

裝填因子（load factor） （對于開放地址法而言， m > n）。

期望的插入、查找和刪除的時間 .

所以對于開放地址法而言，插入、查找和刪除的時間復(fù)雜度為 .

這里你一定會有困惑，舉個栗子， ，那么 則表示最多探測10次就可以查找、插入或刪除一個元素。

至于為什么是 ？

對這個感興趣的小伙伴，推薦看看嚴(yán)蔚敏老師的書籍《數(shù)據(jù)結(jié)構(gòu)（C語言版）》262 頁的證明。

開放地址法與鏈地址法的比較

所謂比較，算是對前面的一個總結(jié)：

再哈希（Rehashing）

對于開放地址法而言，插入、查找和刪除的時間復(fù)雜度為 ，意味著哈希算法的時間復(fù)雜度取決于裝填因子 ， ?越大，開放地址法的時間復(fù)雜度也就越高。

裝填因子 表中填入的記錄數(shù)哈希表的長度 .

一般將裝填因子的值設(shè)置為 0.75，隨著填入哈希表中記錄數(shù)的增加，裝填因子就會增大甚至超過設(shè)置的默認值 0.75，意味著哈希算法的時間復(fù)雜度的增加。為了解決裝填因子超過默認設(shè)置的值 0.75，可以對數(shù)組（哈希表）進行擴容（二倍擴容），并將原哈希表中的值進行 再哈希，存儲到二倍大小的新數(shù)組（哈希表）中，從而保證裝填因子維持在一個較低的值（不超過 0.75），哈希算法的時間復(fù)雜度保證在 量級。

這就是為什么需要在哈希的原因所在，下面我們一起看一下再哈希的實現(xiàn)。

再哈希可以大致分為四個步驟：

1. 對于每一次向哈希表中添加新的鍵值對，檢查裝填因子 的大?。?/li>
2. 如果 ，則進行 再哈希 。
3. 對于再哈希而言，創(chuàng)建一個新的數(shù)組（原數(shù)組的兩倍大?。┳鳛楣１?。
4. 遍歷原數(shù)組中的每一個元素，并將其插入到新的數(shù)組當(dāng)中。

我們依舊以 [50, 700, 76, 85, 92, 73, 101] 為例進行說明，其中可能會省略部分計算步驟。

開辟一個大小為 7 的空數(shù)組：

接下來就是插入并檢查裝填因子 ，我們將裝填因子自己寫到了圖中：

此時要注意啦，此時裝填因子 ，創(chuàng)建一個長度為 14 的新數(shù)組（原始數(shù)組的兩倍）：

此時的數(shù)組長度為 14 ，我們的哈希函數(shù)也變了，由原來的 Hash(key) = key % 7 變成了 Hash(key) = key % 14 。然后遍歷原始數(shù)組，并將原始數(shù)組中的元素映射到新的數(shù)組當(dāng)中：

然后計算 101 % 14 = 3 ，插入到 73 的后面：

這就是再哈希，我相信你也理解啦！但是我們的實現(xiàn)可能不是這樣的，我們將插入的是一個鍵值對，比如 [<50, "I">, <700, "Love">, <76, "Data">, <85, "Structure">, <92, "and">, <73, "Jing">, <101, "Yu">] 。此外代碼是以鏈地址法來實現(xiàn)再哈希的奧！可不是畫圖講的開放地址法線性探測，如果不會寫開放地址法再哈?？梢栽u論區(qū)留言，我寫了發(fā)你學(xué)習(xí)！

再哈希實現(xiàn)

import?java.util.ArrayList;?
??
class?Map<K,?V>?{?
??
????class?MapNode<K,?V>?{?
??
????????K?key;?
????????V?value;?
????????MapNode?next;?//鏈地址法
??
????????public?MapNode(K?key,?V?value)?
????????{?
????????????this.key?=?key;?
????????????this.value?=?value;?
????????????next?=?null;?
????????}?
????}?
??
????//?鍵值對就存儲在
????ArrayList?>?hashTable;?
??
????//?裝填因子?alpha?的分子?--?表中填入的記錄數(shù)
????int?size;?
??
????//?裝填因子 alpha 的分母?--?哈希表的長度。
????int?numHashTable;?
??
????//?默認的裝填因子?0.75?
????final?double?DEFAULT_LOAD_FACTOR?=?0.75;?
??
????public?Map()?
????{?
????????numHashTable?=?5;?
??
????????hashTable?=?new?ArrayList<>(numHashTable);?
??
????????for?(int?i?=?0;?i?????????????//?初始化哈希表?
????????????hashTable.add(null);?
????????}?
????}?
??
????private?int?getBucketInd(K?key)?
????{?
??
????????//?Using?the?inbuilt?function?from?the?object?class?
????????int?hashCode?=?key.hashCode();?
??
????????//?array?index?=?hashCode%numHashTable?
????????return?(hashCode?%?numHashTable);?
????}?
??
????public?void?insert(K?key,?V?value)?
????{?
????????//?獲取插入的關(guān)鍵字?key?的哈希值
????????int?bucketInd?=?getBucketInd(key);?
??
????????MapNode?head?=?hashTable.get(bucketInd);?
??
????????//插入?K-V
????????while?(head?!=?null)?{?
????????????if?(head.key.equals(key))?{?
????????????????head.value?=?value;?
????????????????return;?
????????????}?
????????????head?=?head.next;?
????????}?
???
????????MapNode?newElementNode?=?new?MapNode(key,?value);?
?
????????head?=?hashTable.get(bucketInd);?

????????newElementNode.next?=?head;?
??
????????hashTable.set(bucketInd,?newElementNode);?
?
????????size++;?
??
????????//?計算當(dāng)前的裝填因子?
????????double?loadFactor?=?(1.0?*?size)?/?numHashTable;?
??
????????//?裝填因子?>?0.75，執(zhí)行再哈希
????????if?(loadFactor?>?DEFAULT_LOAD_FACTOR)?{??
????????????rehash();?
????????}?
????}?
??
????private?void?rehash()?
????{?
??
????????System.out.println("\n***Rehashing?Started***\n");?
??
????????//?保存原始哈希表
????????ArrayList?>?temp?=?hashTable;?
??
????????//創(chuàng)建新的數(shù)組（原始數(shù)組的兩倍）
????????hashTable?=?new?ArrayList?>(2?*?numHashTable);?
??
????????for?(int?i?=?0;?i?2?*?numHashTable;?i++)?{??
????????????buckets.add(null);?
????????}?
????????//?將舊數(shù)組中數(shù)據(jù)拷貝到新數(shù)組中
????????size?=?0;?
????????numHashTable?*=?2;?
??
????????for?(int?i?=?0;?i?????????????MapNode?head?=?temp.get(i);?
??
????????????while?(head?!=?null)?{?
????????????????K?key?=?head.key;?
????????????????V?val?=?head.value;?
?
????????????????insert(key,?val);?
????????????????head?=?head.next;?
????????????}?
????????}??
????}?
??
????public?void?printMap()?
????{?
????????ArrayList?>?temp?=?hashTable;?
??
????????System.out.println("當(dāng)前的哈希表:");?
????????for?(int?i?=?0;?i?????????????//?獲取哈希表當(dāng)前?i?的頭結(jié)點
????????????MapNode?head?=?temp.get(i);?
??
????????????while?(head?!=?null)?{?
????????????????System.out.println("key?=?"?+?head.key?+?",?
???????????????????????????????????val?=?"?+?head.value);?
??
????????????????head?=?head.next;?
????????????}?
????????}?
????????System.out.println();?
????}?
}?
??
public?class?Rehashing?{?
??
????public?static?void?main(String[]?args)?
????{?
??
????????//?創(chuàng)建一個哈希表?
????????Map?map?=?new?Map();?
??
????????//?插入元素[<50,?"I">,?<700,?"Love">,?<76,?"Data">,?
????????//<85,?"Structure">,?<92,?"and">,?<73,?"Jing">,?<101,?"Yu">]
????????map.insert(50,?"I");?
????????map.printMap();?
??
????????map.insert(700,?"Love");?
????????map.printMap();?
??
????????map.insert(76,?"Data");?
????????map.printMap();?
??
????????map.insert(85,?"Structure");?
????????map.printMap();?
??
????????map.insert(92,?"and");?
????????map.printMap();?

????????map.insert(73,?"Jing");?
????????map.printMap();?

????????map.insert(101,?"Yu");?
????????map.printMap();?
????}?
}?

哈希算法的應(yīng)用

哈希算法在日常生活中的應(yīng)用非常普遍，包括信息摘要（Message Digest），密碼校驗（Password Verification），數(shù)據(jù)結(jié)構(gòu)（編程語言），編譯操作（Compiler Operation），Rabin-Karp 算法（模式匹配算法），負載均衡等等。

當(dāng)你注冊一個網(wǎng)站在客戶端輸入郵箱和密碼時，客戶端會對用戶輸入的密碼進行 hash 運算，然后在服務(wù)端的數(shù)據(jù)庫中保存用戶密碼的 Hash 值，從而保護用戶的數(shù)據(jù)。

C++ 當(dāng)中的 unordered_set & unordered_map ，以及 Java 中 HashSet & HashMap 和 Python 中的 dict 等各種編程語言均實現(xiàn)了哈希表數(shù)據(jù)結(jié)構(gòu)。

Rabin-Karp 算法利用哈希來查找字符串的任意一組模式，并且可以用來檢查抄襲。

可以利用一致性哈希解決負載均衡問題。

同樣可以用于版本校驗、防篡改、密碼校驗，此外還廣泛應(yīng)用于各類數(shù)據(jù)庫當(dāng)中（包括MySQL、Redis等等）。

關(guān)于哈希算法應(yīng)用的詳細內(nèi)容大家可以看看參考資料[1]。

參考資料

[1] https://www.zhihu.com/question/26762707/answer/890181997

[2] https://hit-alibaba.github.io/interview/basic/algo/Hash-Table.html

[3] 嚴(yán)蔚敏老師的《數(shù)據(jù)結(jié)構(gòu)（C語言）》版。

[4] https://www.cs.princeton.edu/~rs/AlgsDS07/10Hashing.pdf

[5] http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture05.pdf

[6] http://courses.csail.mit.edu/6.006/fall11/lectures/lecture10.pdf

[7] https://www.cse.cuhk.edu.hk/irwin.king/_media/teaching/csc2100b/tu6.pdf

來個直擊靈魂的三連吧！