【51CTO.com快譯】

為什么如此重視？

首先
• 在表格中哈希映射、關聯數組或字典數據結構如何工作？
• 什么時候適合使用哈希表存儲項目？
• 如何處理哈希表中的“沖突”？

方便查找：

假設，我們想存儲一個用戶列表，以便以后可以根據他們的名字查找。

我們可以簡單地將用戶存儲在一個數組中，當以后需要找人時，可通過遍歷所有數據的方式查找目標用戶。

當我們只有3個用戶時，通過簡單的方式便可以輕松的查找到。但是，如果我們有成千上萬的用戶，過程將會十分的慢。因此，通過使用哈希表，可以更好地完成查詢。

正是因為哈希表以鍵值對的方式存儲，使查找數據的速度比在數組中循環快得多。

創建哈希表

使用哈希表，首先需要為每個用戶提供一個唯一的值-即 key（索引），將使用此索引存儲該項，便于以后檢索中使用。

假設每個用戶都有一個唯一的名稱，并將其用作主鍵。在實際應用中，例如使用ID作為主鍵。

哈希表的工作原理是將鍵值對存儲在桶（Bucket）中，Hashtable由多個Bucket組成，每個Bucket中存放著所有HashKey相同的(Key, Value)，如圖所示：

為了簡單的示例，我們將使用4個存儲桶（Bucket）。
當將一個用戶添加到哈希表時，我們使用其索引來確定將其存儲在哪個存儲桶（Bucket）中。
當需要再次檢索用戶時，即可以直接跳到正確的桶（Bucket）以找到目標，這樣比依次查找要更快。

存儲表

在表中存儲第一個用戶“ Ada”。

首先，確定將其存儲在哪個存儲桶中。這意味著我們需要從一個字符串（'Ada'）存放在關鍵字的位置，代入函數后若能得到包含該關鍵字的記錄在表中的地址。這樣做的過程是我們的哈希表，函數為哈希函數。

在此示例中，我們將創建一個簡單的哈希函數。以用戶名中的每個字母為它分配一個數字； A=0， B=1， C=2等等。最后，把所有的值加在一起，結果就是散列值，也就是哈希值，所在的位置就是散列地址。

對于“ Ada”，該數字為3—因此我們可以將Ada存儲在存儲區3中：

當以后需要檢索“ Ada”時，可以對她的名字執行相同的哈希函數。這將告訴我們在3號存儲桶中尋找她，而無需遍歷數組。

接著存儲下一個用戶“ Grace”：

“Grace”的哈希值為29，但我們沒有29個存儲桶！

只使用其散列值存儲數組將意味著我們將需要大量的Bucket。相反，我們需要一種方法將哈希值（29）轉換為Bucket號（從0到3）。

一種常見的實現方法是將哈希值除以存儲桶數，然后將其余部分用作Bucket號。

將兩個數相除后得到的余數稱為模。“Grace”的哈希值為29，我們有4個存儲桶。將29除以4后的余數為1，因此“Grace”存儲在編號為1的存儲桶中。

此操作可以編寫為29 % 4 = 1，或者是29 mod 4 = 1。

當我們以這種方式計算存儲桶時，哈希表如下所示：

沖突

一個好的Hash函數不僅性能優越，而且還會讓存儲于底層數組中的值分配的更加均勻，減少沖突發生。

實際上是將輸入鍵（定義域）映射到一個非常小的空間中，所以沖突是無法避免的，能做的只是減少Hash碰撞發生的概率。

接著存儲“Tim：

現在，我們有兩個用戶需要存儲在存儲桶3中：

有兩種方法可以解決這個問題：
我們可以使用一種算法來不斷選擇新的存儲桶，直到找到一個空的存儲桶，然后將散列地址存儲在那里。每個存儲桶中只有一個底層數組的方法稱為 開放式尋址。

或者，存儲一組散列地址，而不是在每個bucket中只存儲一個散列地址。當我們使用這種方法發現碰撞時，我們只需將沖突的鍵值對放在同一個存儲桶中即可。

當以后需要檢索該數組時，我們仍然可以直接跳轉到正確的存儲桶。不過，這次存儲桶可能包含多個數組。在這種情況下，我們將依次檢查存儲桶中的每個數組，尋找我們想要的數組。
這稱為 公共溢出區，通常用于哈希表實現。

這就是為什么好的哈希函數對性能至關重要的原因之一 。

不好的哈希函數無法平均分配項目，因此它們最終只能集中在少數可用的存儲桶中。

在最壞的情況下，如果一切都在同一個桶里，則可能會遍歷每個項目來查找所需的內容。這就是我們通過使用哈希表來避免麻煩的原因！

【51CTO譯稿，合作站點轉載請注明原文譯者和出處為51CTO.com】