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

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

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



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

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

總結(jié)：記錄在結(jié)構(gòu)中的相對位置和記錄的關(guān)鍵字之間不存在確定的關(guān)系，在結(jié)構(gòu)中查找記錄時需進行一系列和關(guān)鍵字的比較，查找的效率與比較次數(shù)密切相關(guān)。

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

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

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


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

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

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

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

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

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

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


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


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