作者：Vamei 出處：http://www.cnblogs.com/vamei 歡迎轉載，也請保留這段聲明。謝謝！

?

HASH

哈希表(hash table)是從一個集合A到另一個集合B的映射(mapping)。映射是一種對應關系，而且集合A的某個元素只能對應集合B中的一個元素。但反過來，集合B中的一個元素可能對應多個集合A中的元素。如果B中的元素只能對應A中的一個元素，這樣的映射被稱為一一映射。這樣的對應關系在現實生活中很常見，比如：

A? -> B

人 -> 身份證號

日期 -> 星座

?

上面兩個映射中，人 -> 身份證號是一一映射的關系。在哈希表中，上述對應過程稱為hashing。A中元素a對應B中元素b，a被稱為鍵值(key)，b被稱為a的hash值(hash value)。

?韋小寶的hash值

?

映射在數學上相當于一個函數f(x):A->B。比如 f(x) = 3x + 2。哈希表的核心是一個哈希函數(hash function)，這個函數規定了集合A中的元素如何對應到集合B中的元素。比如：

A: 三位整數??? hash(x) = x % 10? ? B: 一位整數

104???????????? ? ? ? ? ?? ?? ??? 4

876???????????? ? ? ? ? ? ? ? ? ? 6

192??????????????? ? ? ? ? ? ? ?? 2

上述對應中，哈希函數表示為hash(x) = x % 10。也就是說，給一個三位數，我們取它的最后一位作為該三位數的hash值。

?

哈希表在計算機科學中應用廣泛。比如：

Ethernet中的FCS：參看小喇叭開始廣播 (以太網與WiFi協議)

IP協議中的checksum：參看我盡力 (IP協議詳解)

git中的hash值：參看版本管理三國志

上述應用中，我們用一個hash值來代表鍵值。比如在git中，文件內容為鍵值，并用SHA算法作為hash function，將文件內容對應為固定長度的字符串(hash值)。如果文件內容發生變化，那么所對應的字符串就會發生變化。git通過比較較短的hash值，就可以知道文件內容是否發生變動。

?

再比如計算機的登陸密碼，一般是一串字符。然而，為了安全起見，計算機不會直接保存該字符串，而是保存該字符串的hash值(使用MD5、SHA或者其他算法作為hash函數)。當用戶下次登陸的時候，輸入密碼字符串。如果該密碼字符串的hash值與保存的hash值一致，那么就認為用戶輸入了正確的密碼。這樣，就算黑客闖入了數據庫中的密碼記錄，他能看到的也只是密碼的hash值。上面所使用的hash函數有很好的單向性：很難從hash值去推測鍵值。因此，黑客無法獲知用戶的密碼。

(之前有報道多家網站用戶密碼泄露的時間，就是因為這些網站存儲明文密碼，而不是hash值，見多家網站卷入CSDN泄密事件 明文密碼成爭議焦點)

?

注意，hash只要求從A到B的對應為一個映射，它并沒有限定該對應關系為一一映射。因此會有這樣的可能：兩個不同的鍵值對應同一個hash值。這種情況叫做hash碰撞(hash collision)。比如網絡協議中的checksum就可能出現這種狀況，即所要校驗的內容與原文并不同，但與原文生成的checksum(hash值)相同。再比如，MD5算法常用來計算密碼的hash值。已經有實驗表明，MD5算法有可能發生碰撞，也就是不同的明文密碼生成相同的hash值，這將給系統帶來很大的安全漏洞。(參考hash collision）

?

HASH與搜索

hash表被廣泛的用于搜索。設定集合A為搜索對象，集合B為存儲位置，利用hash函數將搜索對象與存儲位置對應起來。這樣，我們就可以通過一次hash，將對象所在位置找到。一種常見的情形是，將集合B設定在數組下標。由于數組可以根據數組下標進行隨機存取(random access，算法復雜度為1)，所以搜索操作將取決于hash函數的復雜程度。

?

比如我們以人名(字符串)為鍵值，以數組下標為hash值。每個數組元素中存儲有一個指針，指向記錄 (有人名和電話號碼)。

?

下面是一個簡單的hash函數:

#define HASHSIZE 1007
/* By Vamei
* hash function
*/ int hash(char *p) {int value=0;while((*p) != '\0') {value = value + (int) (*p); // convert char to int, and sump++;}return (value % HASHSIZE); // won's exceed HASHSIZE }

hash value of "Vamei": 498

hash value of "Obama": 480

?

我們可以建立一個HASHSIZE大小的數組records，用于儲存記錄。HASHSIZE被選擇為質數，以便hash值能更加均勻的分布。在搜索"Vamei"的記錄時，可以經過hash，得到hash值498，再直接讀取records[498]，就可以讀取記錄了。

(666666是Obama的電話號碼，111111是Vamei的電話號碼。純屬杜撰，請勿當真)

hash搜索

如果不采用hash，而只是在一個數組中搜索的話，我們需要依次訪問每個記錄，直到找到目標記錄，算法復雜度為n。我們可以考慮一下為什么會有這樣的差別。數組雖然可以隨機讀取，但數組下標是隨機的，它與元素值沒有任何關系，所以我們要逐次訪問各個元素。通過hash函數，我們限定了每個下標位置可能存儲的元素。這樣，我們利用鍵值和hash函數，就可以具備相當的先驗知識，來選擇適當的下標進行搜索。在沒有hash碰撞的前提下，我們只需要選擇一次，就可以保證該下標指向的元素是我們想要的元素。

?

沖突

hash函數需要解決hash沖突的問題。比如，上面的hash函數中，"Obama"和"Oaamb"有相同的hash值，發生沖突。我們如何解決呢？

?

一個方案是將發生沖突的記錄用鏈表儲存起來，讓hash值指向該鏈表，這叫做open hashing:

open hashing

我們在搜索的時候，先根據hash值找到鏈表，再根據key值遍歷搜索鏈表，直到找到記錄。我們可以用其他數據結構代替鏈表。

?

open hashing需要使用指針。我們有時候想要避免使用指針，以保持隨機存儲的優勢，所以采用closed hashing的方式來解決沖突。

closed hashing

這種情況下，我們將記錄放入數組。當有沖突出現的時候，我們將沖突記錄放在數組中依然閑置的位置，比如圖中Obama被插入后，隨后的Oaamb也被hash到480位置。但由于480被占據，Oaamb探測到下一個閑置位置(通過將hash值加1)，并記錄。

closed hashing的關鍵在如何探測下一個位置。上面是將hash值加1。但也可以有其它的方式。概括的說，在第i次的時候，我們應該探測POSITION(i)=(h(x) + f(i)) % HASHSIZE的位置。上面將hash值加1的方式，就相當于設定f(i) = 1。當我們在搜索的時候，就可以利用POSITION(i)，依次探測記錄可能出現的位置，直到找到記錄。

(f(i)的選擇會帶來不同的結果，這里不再深入)

如果數組比較滿，那么closed hashing需要進行許多次探測才能找到空位。這樣將大大減小插入和搜索的效率。這種情況下，需要增大HASHSIZE，并將原來的記錄放入到新的比較大的數組中。這樣的操作稱為rehashing。

?

總結

hash表，搜索

hash沖突, open hashing, closed hashing

?

歡迎繼續閱讀“紙上談兵: 算法與數據結構”系列。

?

轉載于:https://www.cnblogs.com/vamei/archive/2013/03/24/2970339.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的纸上谈兵: 哈希表 (hash table)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。