<What's Hash>
Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的。

我們通常說的Hash，其實指的是Hash算法（即散列算法）：把任意長度的輸入，通過Hash算法，變換成固定長度的輸出（即Hash值、散列值）。

Hash算法有多種實現形式，比如MD5、SHA1，這里就不對算法本身進行討論了。重點談談Hash算法的特性和作用吧：
??? 1）Hash是一種壓縮映射：散列值的長度通常遠小于輸入的長度（比如emule，任意大小是視頻文件，都可以映射成一個固定長度的字符串，它就相當于這個文件的信息摘要）
??? 2）不同的輸入可能會Hash成相同的輸出：這是一個小概率事件，且采用安全性高的Hash算法時，兩個不同的輸入幾乎不可能得到相同的Hash結果。
??? 3）與加密算法不同，Hash算法是一個不可逆的單向函數，不可能從散列值來唯一的確定輸入值。



<What's Hash Table>
0. 在下面的討論中，我們將用到三國這個例子：假設我們要做個存儲結構，需要存儲下來三國中的英雄，以及他們的詳細信息。我們用他們的名字來作為存儲的關鍵值，例如：劉備，關羽，張飛，曹操，孫權...n。

1. 一般的表
??? name?? ?age?? ?身高?? ?體重
??? 劉備?? ?30?? ?175?? ?60
??? 關羽?? ?28?? ?190?? ?80
??? 張飛?? ?27?? ?185?? ?80
??? ...n
這時，如果我們想要查找某個英雄，就需要一邊遍歷表，一邊對名字進行比較。它的時間復雜度為O（n）--線性階。

總結：記錄在結構中的相對位置和記錄的關鍵字之間不存在確定的關系，在結構中查找記錄時需進行一系列和關鍵字的比較，查找的效率與比較次數密切相關。

2. 數組
??? 1）通過地址的訪問方式（數組）：Array[2]，這里2就是它的“物理”地址，找到2所對應的內容是通過“直接定位”，而不是“遍歷比較”。所以，在所有的線性數據結構中，數組的定位速度最快。它的時間復雜度為O（1）--常熟階。

??? 這時，我們會想，那我們把劉-關-張-...n，按照1-2-3-...n的順序放在一個數組里（數組的內容就是這個英雄的對象）不就可以直接定位了？
??? arrayid?? ?（name?? ?age?? ?身高?? ?體重）
??? 1?? ???? ??? （劉備?? ?30?? ?175?? ?60）
??? 2?? ???? ??? （關羽?? ?28?? ?190?? ?80）
??? 3?? ???? ??? （張飛?? ?27?? ?185?? ?80）
??? ...n

??? 2）但是：
??? ??? a）可你憑什么說劉=1，關=2呢？（顯然不是叫你用拼音或者筆畫排序）
??? ??? b）我們查找的時候，不可能用arrayid作為查找條件（那還查個P呀），怎樣通過name=關羽，“計算”得到arrayid=2呢？


3. 散列表：其主要目的是用于解決數據的快速定位問題，也即，怎樣通過關鍵字，計算（而不是遍歷比較）得到物理地址。

1）存放時
??? Hash（劉備）=13
??? Hash（關羽）=7
??? Hash（張飛）=26
??? ...n

??? arrayid?? ?（name?? ?age?? ?身高?? ?體重）
??? ...
??? 7?? ???? ??? （關羽?? ?28?? ?190?? ?80）
??? ...
??? 13?? ??? ?? （劉備?? ?30?? ?175?? ?60）
??? ...
??? 26?? ?????? （張飛?? ?27?? ?185?? ?80）
??? ...n

??? 我們也可以看出：
??? a）散列，數據并非緊湊的、按順序存入的：我們可以先在13的位置存上劉備，再在7的位置存上關羽；有些位置還可能一直是空的。
??? b）空間換時間：因為散列，顯然數組的大小要大于實際實際數據的數量。比如，即使我們只存劉關張3個人，我們也需要一個至少26的數組。

2）查找時，就很簡單了
??? Aarry[Hash（關羽）]=Array[7]

3）當然實際的hash算法，要比上述復雜，比如
??? “把Key通過Hash算法轉換成一個整型數字，然后就將該數字對數組長度進行取余，取余結果就當作數組的下標，將value存儲在以該數字為下標的數組空間里；
??? 而當使用哈希表進行查詢的時候，就是再次使用哈希函數將key轉換為對應的數組下標，并定位到該空間獲取value，如此一來，就可以充分利用到數組的定位性能進行數據定位。”

4）Hash沖突：前面說了，不同的輸入是有可能hash成相同的輸出的
??? 如果Hash（關羽）=Hash（張飛）=250，我們豈不是在存儲過程中會遇到麻煩，怎么安排他們二位的地方呢?（總不能讓二位打一架，誰贏了誰呆在那吧），這就需要一個解決沖突的方法。
??? 先存儲好了關羽，當張飛進入系統時會發現關羽已經是250了，那咱就加一位，251得了。我們查找張飛的時候也是，一看250不是張飛，那就加個1，就找到了。
??? 更極端地，如果這時Hash（趙云）=251，張飛已經早早占了他的地方，那就再加1存到252唄。呵呵，這時我們會發現，當哈希函數沖突發生的機率很高時，可能會有一群英雄在250這個值后面扎堆排隊。要命的是查找的時候，時間算法復雜度早已不是O（1）了。所以我們說理想情況下哈希表的時間算法復雜度為O（1）。
??? 這就是說哈希函數的編寫是哈希表的一個關鍵問題，會涉及到一個存儲值在哈希表中的統計分布。如果哈希函數已經定義好了，沖突的解決就成為了改變系統性能的關鍵因素。其實還有很多種方法來解決沖突情況下的存儲和查找問題，不一定非要線性向后排隊，如果有好的哈希表沖突的解決方法也能很大程度上提高系統的效率。


FYI，比較書面化的定義：
??? 理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲位置和它的關鍵字之間建立一確定的對應關系f，使每個關鍵字和結構中一個唯一的存儲位置相對應。因而查找時，只需根據這個對應關系f找到給定值K的像f（K）。若結構中存在關鍵字和K相等的記錄，則必定在f（K）的存儲位置上，由此不需要進行比較便可直接取得所查記錄。在此，稱這個對應關系f為哈希函數，按這個思想建立的表為哈希表（又稱為雜湊法或散列法）。


參考：
http://calmness.javaeye.com/blog/184465
http://blog.163.com/xx_snoopy/blog/static/12577162008426731299/