【51CTO.com快譯】

為什么如此重視？

首先
• 在表格中哈希映射、關(guān)聯(lián)數(shù)組或字典數(shù)據(jù)結(jié)構(gòu)如何工作？
• 什么時候適合使用哈希表存儲項(xiàng)目？
• 如何處理哈希表中的“沖突”？

方便查找：

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

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

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

正是因?yàn)?strong>哈希表以鍵值對的方式存儲，使查找數(shù)據(jù)的速度比在數(shù)組中循環(huán)快得多。

創(chuàng)建哈希表

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

假設(shè)每個用戶都有一個唯一的名稱，并將其用作主鍵。在實(shí)際應(yīng)用中，例如使用ID作為主鍵。

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

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

存儲表

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

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

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

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

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

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

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

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

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

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

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

當(dāng)我們以這種方式計(jì)算存儲桶時，哈希表如下所示：

沖突

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

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

接著存儲“Tim：

現(xiàn)在，我們有兩個用戶需要存儲在存儲桶3中：

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

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

當(dāng)以后需要檢索該數(shù)組時，我們?nèi)匀豢梢灾苯犹D(zhuǎn)到正確的存儲桶。不過，這次存儲桶可能包含多個數(shù)組。在這種情況下，我們將依次檢查存儲桶中的每個數(shù)組，尋找我們想要的數(shù)組。
這稱為 公共溢出區(qū)，通常用于哈希表實(shí)現(xiàn)。

這就是為什么好的哈希函數(shù)對性能至關(guān)重要的原因之一 。

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

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

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