圖解雜湊表及其原理

要點回顧

此部分方便知識點快速回顧，首次閱讀請從引言部分開始。

• 雜湊表（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）汗。

參照

https://www.educba.com/c-plus-plus-hash-table/

https://mp.weixin.qq.com/s/AkPIN6Ugno9vkQ2AAmCEAA