紙上談兵: 哈希表 (hash table)

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值，