圖解:什麼是哈希?

為什麼要有哈希？

假設我們要設計一個系統來存儲將員工手機號作為主鍵的員工記錄，並希望高效地執行以下操作：

我們可以考慮使用以下數據結構來維護不同電話所對應的信息：

對於數組和鍊表而言，我們需要以線性的方式進行查找，這在實際應用中代價太大；如果我們使用數組且保證數組中電話號碼有序排列，那麼使用二分查找可將查找電話號碼的時間複雜度降到

對於平衡二叉查找樹而言，插入、查找和刪除操作的時間複雜度均為

再來看直接訪問表的方式，首先創建一個大數組（至少能夠用電話號碼作為數組下標），如果電話號碼沒有出現在數組當中，就在相應下標填充 NULL ；如果電話號碼出現了，則下標中數據填充該電話號碼關聯的記錄的地址。

這樣一來，插入、查找和刪除的時間複雜度將降為

但是直接訪問表有實踐上的限制。首先需要申請額外的存儲空間，並且存在大量的空間浪費。比如對於一個含有 n 位的電話號碼，我們需要

由於上述限制，使用直接訪問表並不是最明智的方法。而哈希則是解決以上問題的最好數據結構，並且與上面所提到的數據結構（數組，鍊表，AVL樹）在實踐中相比，性能非常好。通過哈希，可以在

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

什麼是哈希表？

哈希表和直接訪問表很類似，同樣是一個用於存儲指向給定電話號碼對應記錄的指針的數組，只不過，此時的數組下標不再是電話號碼，而是經過哈希函數映射後的輸出值。

什麼是哈希函數？

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

[lovefxs@localhost ~]$ echo -n  "I love J"  | openssl md5 
(stdin)= ef821d9b424fd5f0aac7faf029152e04
一個好的哈希函數應該滿足四個條件：
對於一段很長的字符串或者二進位文本也能快速計算出哈希值。
散列結果應當具有同一性（輸出值儘量均勻，越均勻衝突就越少）。（同一性）
例如對於電話號碼而言，一個好的哈希函數應該考慮電話號碼的後四位，而一個糟糕的哈希算法可能考慮電話號碼的前四位，因為後四位更有區分性，相當於輸入更加分散，那麼輸出也可能更加均勻，當然這兩種選擇方式都不是什麼好辦法，只是希望大家理解同一性原理。
雪崩效應（微小的輸入值變化使得輸出值發生巨大的變化）。
[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 只改變了一個字母，輸出值卻千差萬別。
從哈希函數的輸出值不可反向推導出原始的數據。（不可反向推導）
比如上面的原始數據 I love J  與經過 MD5 算法映射後的輸出值之間沒有對應關係。
什麼是 Hash 碰撞?
由於哈希函數的原理是將輸入空間的一個較大的值映射成 hash 空間內一個較小的值，那麼就會出現兩個不同的輸入值被映射到了同一個較小的輸出值。當一個新插入的值被哈希函數映射到了哈希表中一個已經被佔用的槽，就認為產生了 Hash 碰撞（衝突）。
那麼這種衝突是否可以避免呢？
答案是只能緩解，不可避免。
由於哈希函數的原理是將輸入空間一個較大的值映射到一個較小的 Hash 空間內，而 Hash空間一般遠小於輸入的空間。根據抽屜原理，一定會存在不同的輸入被映射成同一輸出的情況。
何為抽屜原理？
桌上有十個蘋果，要把這十個蘋果放到九個抽屜裡，無論怎樣放，我們會發現至少會有一個抽屜裡面放不少於兩個蘋果。這一現象就是「抽屜原理」。抽屜原理的一般含義為：「如果每個抽屜代表一個集合，每一個蘋果就可以代表一個元素，假如有n+1個元素放到n個集合中去，其中必定有一個集合裡至少有兩個元素。」 抽屜原理有時也被稱為鴿巢原理。它是組合數學中一個重要的原理
知道了為什麼哈希碰撞不可避免，那哈希碰撞該如何緩解呢？
Hash 碰撞的解決方案?鏈地址法 
鏈地址法的思想就是將所有發生碰撞的元素用一個單鍊表串起來。
我們以一個簡單的哈希函數 H(key) = key MOD 7 （除數取餘法）對一組元素 [50, 700, 76, 85, 92, 73, 101] 進行映射，來理解鏈地址法處理 Hash 碰撞。
除數為 7 ，初始化一個大小為 7 的空 Hash 表：
然後插入元素 50 ，首先對 50 % 7 = 1 ，得到其哈希值 1 ，在下標為 1 的位置插入 50 ：
然後計算 700 % 7 = 0 ，76 % 7 = 6 ，得到的哈希值均未發生碰撞，填入相應位置：
然後計算 85 % 7 = 1 ， 但是下標為 1 的位置已經有元素 50 ，發生了碰撞，所以使用單鍊表將 85 和 50 連結起來：
以同樣的方式插入所有元素得到如下的哈希表。鏈地址法解決衝突的方式與圖的鄰接表存儲方式在樣式上很相似，思想還是蠻簡單，發生衝突，就用單鍊表組織起來。
鏈地址法實現
首先創建一個空的哈希表，哈希表的表長為 
哈希函數：Hash(key) = key % N
插入：計算要插入關鍵字 key 的哈希值 Hash(key) ，然後在哈希表中找到對應哈希值的位置，再將 key 插入鍊表的末尾；
刪除：計算要刪除關鍵字 key 的哈希值 Hash(key) ，然後在哈希表中找到對應哈希值的位置，再將 key 充鍊表中刪除。
查找：計算要查找關鍵字 key 的哈希值 Hash(key) ，然後在哈希表中找到對應哈希值的位置，從該位置開始進行單鍊表的線性查找。
using namespace std; 
  
class Hash 
{ 
    int N;    // 哈希表的表長  
    // 指向對應存儲下標的指針。
    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; 
        }
  } 
  //如果找到了對應的key，刪除之
  if (i != table[index].end()) 
    table[index].erase(i); 
} 
  
// 輸出哈希表
void Hash::displayHash() { 
    for (int i = 0; i < N; i++) { 
        cout << i; 
     for (auto x : table[i]){
         cout << " --> " << x;             
        } 
     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 < n; i++){
        h.insertKey(a[i]);  
    }  
    h.deleteKey(92); 
    h.displayHash(); 
  
    return 0; 
} 
鏈地址法的優缺點：
優點：哈希表永遠不會溢出，我們可以向單鍊表中添加更多的元素；對於哈希函數和裝填因子（後面會說）的選擇沒啥要求；在不知道要插入和刪除關鍵字多少和頻率的情況下，鏈地址法有絕對優勢。缺點：由於使用鍊表來存儲關鍵字，鏈地址法的緩存性能不佳。開放尋址法使用連續的地址空間進行存儲，所以緩存性能更好。如果鍊表太長，在最壞的情況下查找的時間複雜度將變為 
假設任何一個關鍵字都以相等的相等的概率被映射到哈希表的任意一個槽位。
其中 
裝填因子（load factor） 
期望的查找，插入和刪除的時間均等於
當 
極端情況下我們將 n 個數都扔進了同一個槽，也就是 n 個數形成了一個單鍊表，那麼時間複雜度將降為 
開放地址法 
與鏈地址法一樣，開放地址法也是一個經典的處理衝突的方式。只不過，對於開放地址法，所有的元素都是存儲在哈希表當中的，所以無論任何時候都要保證哈希表的槽位數 
開放地址法分三種方式。
線性探測法（Linear Probing）
設 Hash(key) 表示關鍵字 key 的哈希值，
線性探測法則可以表示為：
如果 Hash(x) % M 已經有數據，則嘗試 (Hash(x) + 1) % M ;
如果 (Hash(x) + 1) % M 也有數據了，則嘗試 (Hash(x) + 2) % M ;
如果 (Hash(x) + 2) % M 也有數據了，則嘗試 (Hash(x) + 3) % M ;
.
我們同樣以哈希函數 H(key) = key MOD 7 （除數取餘法）對 [50, 700, 76, 85, 92, 73, 101] 進行映射，來理解線性探測法處理 Hash 碰撞。
依次計算 50 % 7 = 1 、700 % 7 = 0 及 76 % 7 = 6 ，均沒有發生衝突（碰撞），則直接放入相應的位置：
計算 85 % 7 = 1 ，但是下標 1 的位置已經有元素 50 ，發生碰撞，則尋找下一個可以存放元素 85 的空位 (85 % 7 + 1) % 7 = 2 ，下標二沒有元素，所以將 85 放進去：
計算 92 % 7 = 1 ，50 已經在 1 的位置，發生碰撞；線性探測下一個位置 (92 % 7 + 1） % 7 = 2 ，85 已經在 2 的位置，發生碰撞；線性探測下一個位置  (92 % 7 + 2） % 7 = 3 ，此時為空位，填入 92 :
計算 73 % 7 = 3 ，92 已經佔用了 3 號位置，發生碰撞；線性探測下一個位置 (73 % 7 + 1） % 7 = 4 ，此時為空位，填入 73 :
計算 101 % 7 = 3 , 3 號位置已經有元素，發生碰撞；線性探測下一個位置 (101 % 7 + 1） % 7 = 4 ，4 號位置已有元素，發生碰撞；線性探測下一個位置 (101 % 7 + 2） % 7 = 5 ， 此時為空，填入 101 :
到這裡你不難看出線性探測的缺陷，容易產生聚集（發生碰撞的元素形成組，比如 [50,85,92,73,101] 之間均是由於碰撞而緊挨著），而且發生碰撞的情況大大增加，需要花費更多的時間來尋找空閒的槽位和查找元素。
至於（lazy delete）懶刪除就是並不將存儲空間釋放，只是將裡面的數據清除。
比如刪除元素 92 ，先計算 92 % 7 = 1 ，但是發現下標 1 是 50，線性向下探測 (92 % 7 + 1） % 7 = 2 ，下標 2 為 85，繼續線性向下探測 (92 % 7 + 2） % 7 = 3 ，發現下標 3 剛好為 92，將該存儲單元的數據清空。
平方探測法（Quadratic Probing)
所謂 Quadratic Probing，就是每次向下探測的寬度變成了 
設 Hash(key) 表示關鍵字 key 的哈希值，
平方探測法則可以表示為：
如果 Hash(x) % M 已經有數據，則嘗試 (Hash(x) + 1 * 1) % M ;
如果 (Hash(x) + 1 * 1) % M 也有數據了，則嘗試 (Hash(x) + 2 * 2) % M ;
如果 (Hash(x) + 2 * 2) % M 也有數據了，則嘗試 (Hash(x) + 3 * 3) % M ;
..
雙重哈希（Double Hashing）
對於雙重哈希，我們需要一個新的哈希函數 Hash2(key) ，而且對於第 i 次迭代探測，我們查找的位置為 i * Hash2(key) .
設 Hash(key) 表示關鍵字 key 的一個哈希值， Hash2(key) 表示關鍵字 key 的另一個哈希值，
雙重哈希探測法則可以表示為：
如果 Hash(x) % M 已經有數據，則嘗試 (Hash(x) + 1 * Hash2(x)) % M ;
如果 (Hash(x) + 1 * Hash2(x)) % M 也有數據了，則嘗試 (Hash(x) + 2 * Hash2(x)) % M ;
如果 (Hash(x) + 2 * Hash2(x)) % M 也有數據了，則嘗試 (Hash(x) + 3 * Hash2(x)) % M ;
..
開放地址法的實現
using namespace std; 
  
// 哈希表的大小 
#define TABLE_SIZE 13 
  
// 用於定義 Hash2(key)
#define PRIME 7 

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

int main() 
{ 
    int a[] = {50, 700, 76, 85, 92, 73, 101}; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    //創建哈希表，插入a[]中的元素
    DoubleHash h; 
    for (int i = 0; i < n; i++) { 
        h.insertHash(a[i]); 
    } 
    //查找
    h.search(36); //不存在
    h.search(101); //存在
    //列印輸出
    h.displayHash(); 
    return 0; 
} 
至於線性探測和平方探測的實現比較簡單，只需要修改一下代碼中 newIndex 的計算方式即可。
線性探測：
int newIndex = (index + i) % TABLE_SIZE; 
平方探測：
int newIndex = (index + i*i) % TABLE_SIZE; 
以上三種探測方法的比較：
線性探測具有最佳的緩存性能，但會受到原始聚集（primary cluster）的影響。線性探測易於計算。
何為原始聚集（原始聚集是相對於線性探測而言的）？
如圖所示，如果對於任意一個關鍵字 key ，其哈希值 Hash(key) 指向圖中從左向右的紅色箭頭的任意位置，聚集（圖中的淺藍色區域）都將得到擴充，而隨著聚集的不斷擴充，這個聚集會越來越大。
還不理解聚集的概念的話，我們一起看個例子：
上圖中的 700，50，76 在插入的時候均未產生碰撞，所以以元素本身單位構成聚集（聚集的大小為 1，此時可以認為不是聚集）。
但是之後插入的元素就不一樣了，85 與 50 發生碰撞，插入到了 50 的後面，導致聚集變大。
插入 92 與 50 發生碰撞，線性探測插入到了 85 之後，聚集進一步擴大。
插入 73 與 92 產生碰撞，線性探測插入到 92 之後，聚集進一步擴大。
插入 101 與 92 產生碰撞，線性探測插入到 73 之後，聚集進一步擴大。
這就是原始聚集的概念，顯然聚集越大，產生碰撞的可能越來越大，哈希算法的性能也會受到影響。
平方探測在緩存性能和受聚集影響方面介於兩者中間，平方探測隨解決了線性探測的原始聚集問題，但是同時也會產生更細的二次聚集問題。
二重探測的緩存性能較差，但不用擔心聚集的情況，但同時由於要計算兩個散列函數，時間性能方面受限。
開放地址法的性能分析
與鏈地址法類似，假設任何一個關鍵字都以相等的相等的概率被映射到哈希表的任意一個槽位。
其中 
裝填因子（load factor） 
期望的插入、查找和刪除的時間 
所以對於開放地址法而言，插入、查找和刪除的時間複雜度為 
這裡你一定會有困惑，舉個慄子， 
至於為什麼是 
對這個感興趣的小夥伴，推薦看看嚴蔚敏老師的書籍《數據結構（C語言版）》262 頁的證明。
開放地址法與鏈地址法的比較 
所謂比較，算是對前面的一個總結：
No鏈地址法開放地址法1易於實現需要更多的計算2使用鏈地址法，哈希表永遠不會填充滿，不用擔心溢出。哈希表可能被填滿，需要通過拷貝來動態擴容。3對於哈希函數和裝載因子不敏感需要額外關注如何規避聚集以及裝載因子的選擇。4適合不知道插入和刪除的關鍵字的數量和頻率的情況適合插入和刪除的關鍵字已知的情況。5由於使用鍊表來存儲關鍵字，緩存性能差。所有關鍵字均存儲在同一個哈希表中，所以可以提供更好的緩存性能。6空間浪費（哈希表中的有些鏈一直未被使用）哈希表中的所有槽位都會被充分利用。7指向下一個結點的指針要消耗額外的空間。不存儲指針。再哈希（Rehashing） 
對於開放地址法而言，插入、查找和刪除的時間複雜度為 
裝填因子 
一般將裝填因子的值設置為 0.75，隨著填入哈希表中記錄數的增加，裝填因子就會增大甚至超過設置的默認值 0.75，意味著哈希算法的時間複雜度的增加。為了解決裝填因子超過默認設置的值 0.75，可以對數組（哈希表）進行擴容（二倍擴容），並將原哈希表中的值進行 再哈希，存儲到二倍大小的新數組（哈希表）中，從而保證裝填因子維持在一個較低的值（不超過 0.75），哈希算法的時間複雜度保證在 
這就是為什麼需要在哈希的原因所在，下面我們一起看一下再哈希的實現。
再哈希可以大致分為四個步驟：
對於每一次向哈希表中添加新的鍵值對，檢查裝填因子 
我們依舊以 [50, 700, 76, 85, 92, 73, 101] 為例進行說明，其中可能會省略部分計算步驟。
開闢一個大小為 7 的空數組：
接下來就是插入並檢查裝填因子 
此時要注意啦，此時裝填因子 
此時的數組長度為 14 ，我們的哈希函數也變了，由原來的 Hash(key) = key % 7 變成了 Hash(key) = key % 14 。然後遍歷原始數組，並將原始數組中的元素映射到新的數組當中：
然後計算 101 % 14 = 3 ，插入到 73 的後面：
這就是再哈希，我相信你也理解啦！但是我們的實現可能不是這樣的，我們將插入的是一個鍵值對，比如 [<50, "I">, <700, "Love">, <76, "Data">, <85, "Structure">, <92, "and">, <73, "Jing">, <101, "Yu">] 。此外代碼是以鏈地址法來實現再哈希的奧！可不是畫圖講的開放地址法線性探測，如果不會寫開放地址法再哈希可以評論區留言，我寫了發你學習！
再哈希實現
import java.util.ArrayList; 
  
class Map<K, V> { 
  
    class MapNode<K, V> { 
  
        K key; 
        V value; 
        MapNode<K, V> next; //鏈地址法
  
        public MapNode(K key, V value) 
        { 
            this.key = key; 
            this.value = value; 
            next = null; 
        } 
    } 
  
    // 鍵值對就存儲在
    ArrayList<MapNode<K, V> > hashTable; 
  
    // 裝填因子 alpha 的分子 -- 表中填入的記錄數
    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 < numHashTable; 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) 
    { 
        // 獲取插入的關鍵字 key 的哈希值
        int bucketInd = getBucketInd(key); 
  
        MapNode<K, V> head = hashTable.get(bucketInd); 
  
        //插入 K-V
        while (head != null) { 
            if (head.key.equals(key)) { 
                head.value = value; 
                return; 
            } 
            head = head.next; 
        } 
   
        MapNode<K, V> newElementNode = new MapNode<K, V>(key, value); 
 
        head = hashTable.get(bucketInd); 

        newElementNode.next = head; 
  
        hashTable.set(bucketInd, newElementNode); 
 
        size++; 
  
        // 計算當前的裝填因子 
        double loadFactor = (1.0 * size) / numHashTable; 
  
        // 裝填因子 > 0.75，執行再哈希
        if (loadFactor > DEFAULT_LOAD_FACTOR) {  
            rehash(); 
        } 
    } 
  
    private void rehash() 
    { 
  
        System.out.println("\n***Rehashing Started***\n"); 
  
        // 保存原始哈希表
        ArrayList<MapNode<K, V> > temp = hashTable; 
  
        //創建新的數組（原始數組的兩倍）
        hashTable = new ArrayList<MapNode<K, V> >(2 * numHashTable); 
  
        for (int i = 0; i < 2 * numHashTable; i++) {  
            buckets.add(null); 
        } 
        // 將舊數組中數據拷貝到新數組中
        size = 0; 
        numHashTable *= 2; 
  
        for (int i = 0; i < temp.size(); i++) { 
            MapNode<K, V> 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<MapNode<K, V> > temp = hashTable; 
  
        System.out.println("當前的哈希表:"); 
        for (int i = 0; i < temp.size(); i++) { 
            // 獲取哈希表當前 i 的頭結點
            MapNode<K, V> 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) 
    { 
  
        // 創建一個哈希表 
        Map<Integer, String> map = new Map<Integer, String>(); 
  
        // 插入元素[<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(); 
    } 
} 
哈希算法的應用 
哈希算法在日常生活中的應用非常普遍，包括信息摘要（Message Digest），密碼校驗（Password Verification），數據結構（程式語言），編譯操作（Compiler Operation），Rabin-Karp 算法（模式匹配算法），負載均衡等等。
當你註冊一個網站在客戶端輸入郵箱和密碼時，客戶端會對用戶輸入的密碼進行 hash 運算，然後在服務端的資料庫中保存用戶密碼的 Hash 值，從而保護用戶的數據。
C++ 當中的 unordered_set & unordered_map ，以及 Java 中 HashSet & HashMap 和 Python 中的 dict 等各種程式語言均實現了哈希表數據結構。
Rabin-Karp 算法利用哈希來查找字符串的任意一組模式，並且可以用來檢查抄襲。
可以利用一致性哈希解決負載均衡問題。
同樣可以用於版本校驗、防篡改、密碼校驗，此外還廣泛應用於各類資料庫當中（包括MySQL、Redis等等）。
關於哈希算法應用的詳細內容大家可以看看參考資料[1]。
參考資料
[1] https://www.zhihu.com/question/26762707/answer/890181997
[2] https://hit-alibaba.github.io/interview/basic/algo/Hash-Table.html
[3] 嚴蔚敏老師的《數據結構（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
推薦閱讀：
終於，一鍵打通了微信和QQ
雙系統的日子結束了：Windows和Linux將合二為一
學算法的那些年，吳師兄接觸的網站、軟體、視頻、書籍大揭秘