圖解哈希表及其原理
要點回顧
此部分方便知識點快速回顧，首次閱讀請從引言部分開始。
-
哈希表（Hash Table）其實也叫散列表，是一個數據結構。
-
哈希表本質上就是一個數組，只不過數組存放的是單一的數據，而哈希表中存放的是鍵值對（key – value pair）。
-
key 通過哈希函數（hash function）得到數組的索引，進而存取索引位置的值。
-
不同的 key 通過哈希函數可能得到相同的索引值，此時，產生了哈希碰撞。
-
通過在數組中插入鏈表或者二叉樹，可以解決哈希碰撞問題。
引言
哈希這個詞想必大家經常聽到，這也說明了它使用的頻繁程度，HashMap 和 HashTable 都與哈希這個詞有關係。那哈希是什麼，要搞清楚它，我們得先來說下哈希表。
什麼是哈希表？
哈希表（Hash Table） 是一種用於存儲 鍵值對 的基本數據結構。在 C++ 中，哈希表使用 哈希函數 來計算數組的索引，進而存取數組中對應索引位置的值。
百科定義：
散列表（Hash table，也叫哈希表），是根據鍵（Key）而直接訪問在內存存儲位置的數據結構。也就是說，它通過計算一個關於鍵值的函數，將所需查詢的數據映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數稱做散列函數，存放記錄的數組稱做散列表。
計算索引的過程被稱為 哈希（hash）。
哈希表實現原理
用一個簡單的例子來說明哈希表的原理：
假設：有一本中文詞典，裏面包含了所有的漢字，但是這些漢字是按任意順序隨意排版的，那麼想要在其中找到某一個漢字，你就需要從頭至尾一個一個核查，如果運氣差，這個漢字正好在詞典的末尾，那你需要遍歷整本詞典才能找到你要查的漢字。
優化：因為漢字和拼音之間存在着一種確定的關係，為了提高查找速度，現在將所有漢字按照拼音（key）進行排序（拼音可以根據首字母，第二個字母依次進一步排序），並且每個拼音都有一個對應頁碼（index），從該頁開始，存放拼音對應的漢字（value）。所以找到拼音，也就能在對應的頁碼找到對應的漢字。其中，拼音和頁碼之間，有着某種固定的映射關係，可以通過某種方式計算出來（hash function）。
由此可見，哈希表可以根據一個 key 值來直接訪問數據，因此查找速度快。
但是，上面的例子，還存在一個問題，放在同一頁碼（具有相同拼音）的漢字可能不止一個（同音字），這時候通過拼音（key）獲取到的漢字（value）應該是哪個呢？這就出現了碰撞（hash collision）。
為了解決碰撞，實現哈希表可以有以下兩種方式：
- 數組 + 鏈表
- 數組 + 二叉樹
所以，哈希表本質上就是一個數組。只不過數組存放的是單一的數據，而哈希表中存放的是鍵值對。
鏈表或二叉樹是用來解決碰撞的。
下面用圖例說明哈希表以及解決哈希碰撞的鏈表實現：
因為哈希表中 key 必須是唯一的，所以圖示給拼音加了後綴 _1 和 _2。key han_1 和 han_2 通過哈希函數 F(x) 計算出來的頁碼都是 244。這時就產生了哈希碰撞。為了解決碰撞問題，新建了一個鏈表，鏈表的每個結點都包含了一個鍵值對，當輸入 key han_2 時，哈希表在 244 位置找到了鍵值對 [han_1 – 漢]，但是通過比對發現找到的鍵值對的 key 是 han_1，不等於 han_2，所以繼續遍歷到鏈表的下一個結點，下一個結點存放了鍵值對 [han_2 – 汗]，通過比較發現 key 確實是 han_2，因此返回了漢字（value）汗。
引用
//www.educba.com/c-plus-plus-hash-table/
//mp.weixin.qq.com/s/AkPIN6Ugno9vkQ2AAmCEAA
