【51CTO.com快譯】

為什么如此重視？

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

方便查找：

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

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

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

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

創(chuàng)建哈希表

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

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

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

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

存儲(chǔ)表

在表中存儲(chǔ)第一個(gè)用戶“ Ada”。

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

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

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

當(dāng)以后需要檢索“ Ada”時(shí)，可以對(duì)她的名字執(zhí)行相同的哈希函數(shù)。這將告訴我們?cè)?號(hào)存儲(chǔ)桶中尋找她，而無(wú)需遍歷數(shù)組。

接著存儲(chǔ)下一個(gè)用戶“ Grace”：

“Grace”的哈希值為29，但我們沒(méi)有29個(gè)存儲(chǔ)桶！

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

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

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

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

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

沖突

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

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

接著存儲(chǔ)“Tim：

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

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

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

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

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

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

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

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