聽說過時間表，但是你是否知道「哈希表」

探索 哈希表 hash table 的世界並理解其底層的機制是非常有趣的，並且將會受益匪淺。所以，讓我們了解它，並從頭開始探索吧。

哈希表是許多現代軟體應用程序中一種常見的數據結構。它提供了類似字典的功能，使你能夠在其中執行插入、刪除和刪除等操作。這麼說吧，比如我想找出「蘋果」的定義是什麼，並且我知道該定義被存儲在了我定義的哈希表中。我將查詢我的哈希表來得到定義。它在哈希表內的記錄看起來可能像："蘋果" => "一種擁有水果之王之稱的綠色水果"。這裡，「蘋果」是我的關鍵字，而「一種擁有水果之王之稱的水果」是與之關聯的值。

還有一個例子可以讓我們更清楚，哈希表的內容如下：

"麵包" => "固體"
"水" => "液體"
"湯" => "液體"
"玉米片" => "固體"

我想知道麵包是固體還是液體，所以我將查詢哈希表來獲取與之相關的值，該哈希表將返回「固體」給我。現在，我們大致了解了哈希表是如何工作的。使用哈希表需要注意的另一個重要概念是每一個關鍵字都是唯一的。如果到了明天，我擁有一個麵包奶昔（它是液體），那麼我們需要更新哈希表，把「固體」改為「液體」來反映哈希表的改變。所以，我們需要添加一條記錄到字典中：關鍵字為「麵包」，對應的值為「液體」。你能發現下面的表發生了什麼變化嗎？（LCTT 譯註：不知道這個「麵包奶昔」是一種什麼食物，大約是一種麵包做的奶昔，總之你就理解成作者把液體的「麵包奶昔」當成一種麵包吧。）

"麵包" => "液體"
"水" => "液體"
"湯" => "液體"
"玉米片" => "固體"

沒錯，「麵包」對應的值被更新為了「液體」。

關鍵字是唯一的，我的麵包不能既是液體又是固體。但是，是什麼使得該數據結構與其他數據結構相比如此特殊呢？為什麼不使用一個數組來代替呢？它取決於問題的本質。對於某一個特定的問題，使用數組來描述可能會更好，因此，我們需要注意的關鍵點就是，我們應該選擇最適合問題的數據結構。例如，如果你需要做的只是存儲一個簡單的雜貨列表，那麼使用數組會很適合。考慮下面的兩個問題，兩個問題的本質完全不同。

1. 我需要一個水果的列表
2. 我需要一個水果的列表以及各種水果的價格（每千克）

正如你在下面所看到的，用數組來存儲水果的列表可能是更好的選擇。但是，用哈希表來存儲每一種水果的價格看起來是更好的選擇。

//示例數組
["蘋果", "桔子", "梨子", "葡萄"]   
//示例哈希表  
{ "蘋果" : 3.05,
  "桔子" : 5.5,
  "梨子" : 8.4,
  "葡萄" : 12.4  
}

實際上，有許多的機會需要使用哈希表。

時間以及它對你的意義

這裡有篇對時間複雜度和空間複雜度的一個複習。

平均情況下，在哈希表中進行搜索、插入和刪除記錄的時間複雜度均為 O(1) 。實際上，O(1) 讀作「大 O 1」，表示常數時間。這意味著執行每一種操作的運行時間不依賴於數據集中數據的數量。我可以保證，查找、插入和刪除項目均只花費常數時間，「當且僅當」哈希表的實現方式正確時。如果實現不正確，可能需要花費很慢的 O(n) 時間，尤其是當所有的數據都映射到了哈希表中的同一位置/點。

構建一個好的哈希表

到目前為止，我們已經知道如何使用哈希表了，但是如果我們想構建一個哈希表呢？本質上我們需要做的就是把一個字元串（比如 「狗」）映射到一個哈希代碼（一個生成的數），即映射到一個數組的索引。你可能會問，為什麼不直接使用索引呢？為什麼要這麼麻煩呢？因為通過這種方式我們可以直接查詢 「狗」 並立即得到 「狗」 所在的位置，String name = Array["狗"] // 名字叫拉斯。而使用索引查詢名稱時，可能出現的情況是我們不知道名稱所在的索引。比如，String name = Array[10] // 該名字現在叫鮑勃 - 那不是我的狗的名字。這就是把一個字元串映射到一個哈希代碼的益處（對應於一個數組的索引而言）。我們可以通過使用模運算符和哈希表的大小來計算出數組的索引：index = hash_code % table_size。

我們需要避免的另一種情況是兩個關鍵字映射到同一個索引，這叫做哈希碰撞，如果哈希函數實現的不好，這很容易發生。實際上，每一個輸入比輸出多的哈希函數都有可能發生碰撞。通過下面的同一個函數的兩個輸出來展示一個簡單的碰撞：

int cat_idx = hashCode("貓") % table_size; //cat_idx 現在等於 1
int dog_idx = hashCode("狗") % table_size; //dog_idx 也等於 1

我們可以看到，現在兩個數組的索引均是 1 。這樣將會出現兩個值相互覆蓋，因為它們被寫到了相同的索引中。如果我們查找 「貓」 的值，將會返回 「拉斯」 ，但是這並不是我們想要的。有許多可以解決哈希碰撞的方法，但是更受歡迎的一種方法叫做鏈接。鏈接的想法就是對於數組的每一個索引位置都有一個鏈表，如果碰撞發生，值就被存到鏈表中。因此，在前面的例子中，我們將會得到我們需要的值，但是我們需要搜索數組中索引為 1 的位置上的鏈表。伴有鏈接的哈希實現需要 MARKDOWN_HASH8c59565b6a2b04d9bd4230517279ce7dMARKDOWNHASH 時間，其中 α 是裝載因子，它可以表示為 n/k，其中 n 是哈希表中的記錄數目，k 是哈希表中可用位置的數目。但是請記住，只有當你給出的關鍵字非常隨機時，這一結論才正確（依賴於 [SUHA](https://en.wikipedia.org/wiki/SUHA(computer_science)）。

這是做了一個很大的假設，因為總是有可能任何不相等的關鍵字都散列到同一點。這一問題的一個解決方法是去除哈希表中關鍵字對隨機性的依賴，轉而把隨機性集中於關鍵字是如何被散列的，從而減少矛盾發生的可能性。這被稱為……

通用散列

這個觀念很簡單，從 通用散列 universal hash 家族集合隨機選擇一個哈希函數 h 來計算哈希代碼。換句話來說，就是選擇任何一個隨機的哈希函數來散列關鍵字。通過這種方法，兩個不同的關鍵字的散列結果相同的可能性將非常低（LCTT 譯註：原文是「not be the same」，應是筆誤）。我只是簡單的提一下，如果不相信我那麼請相信數學。實現這一方法時需要注意的另一件事是如果選擇了一個不好的通用散列家族，它會把時間和空間複雜度拖到 O(U)，其中 U 是散列家族的大小。而其中的挑戰就是找到一個不需要太多時間來計算，也不需要太多空間來存儲的哈希家族。

上帝哈希函數

追求完美是人的天性。我們是否能夠構建一個完美的哈希函數，從而能夠把關鍵字映射到整數集中，並且幾乎沒有碰撞。好消息是我們能夠在一定程度上做到，但是我們的數據必須是靜態的（這意味著在一定時間內沒有插入/刪除/更新）。一個實現完美哈希函數的方法就是使用 2 級哈希 2-Level Hashing ，它基本上是我們前面討論過的兩種方法的組合。它使用通用散列來選擇使用哪個哈希函數，然後通過鏈接組合起來，但是這次不是使用鏈表數據結構，而是使用另一個哈希表。讓我們看一看下面它是怎麼實現的：


但是這是如何工作的以及我們如何能夠確保無需關心碰撞？

它的工作方式與生日悖論相反。它指出，在隨機選擇的一堆人中，會有一些人生日相同。但是如果一年中的天數遠遠大於人數（平方以上），那麼有極大的可能性所有人的生日都不相同。所以這二者是如何相關的？對於每一個鏈接哈希表，其大小均為第一級哈希表大小的平方。那就是說，如果有兩個元素被散列到同一個點，那麼鏈接哈希表的大小將為 4 。大多數時候，鏈接哈希表將會非常稀疏/空。

重複下面兩步來確保無需擔心碰撞：

• 從通用散列家族中選擇一個哈希函數來計算
• 如果發生碰撞，那麼繼續從通用散列家族中選擇另一個哈希函數來計算

字面上看就是這樣（這是一個 O(n^2) 空間的解）。如果需要考慮空間問題，那麼顯然需要另一個不同的方法。但是值得慶幸的是，該過程平均只需要進行兩次。

總結

只有具有一個好的哈希函數才能算得上是一個好的哈希表。在同時保證功能實現、時間和空間的提前下構建一個完美的哈希函數是一件很困難的事。我推薦你在解決問題的時候首先考慮哈希表，因為它能夠為你提供巨大的性能優勢，而且它能夠對應用程序的可用性產生顯著差異。哈希表和完美哈希函數常被用於實時編程應用中，並且在各種演算法中都得到了廣泛應用。你見或者不見，哈希表就在這兒。

via: http://www.zeroequalsfalse.press/2017/02/20/hashtables/

作者：Marty Jacobs 譯者：ucasFL 校對：wxy

本文由 LCTT 原創編譯，Linux中國 榮譽推出

本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive