什么是Hash算法：#####
簡單的說，hash算法就是將字符串轉(zhuǎn)化為數(shù)字的算法。
用一個例子說Hash的優(yōu)勢#####
試想如果我們對一個數(shù)組進(jìn)行Query，這個數(shù)組里，每一個元素都是一個字符串。我們知道數(shù)組最快的檢索辦法是通過數(shù)組的下標(biāo)進(jìn)行檢索，但是對于這種場景，我們無能為力，只能從頭查到尾，從而查詢出目標(biāo)元素。
假設(shè)，我要找gaofei，那就需要遍歷整個數(shù)組，十分的低效。這樣最壞情況下時間復(fù)雜度是O（n）的，但是數(shù)組的查詢時間復(fù)雜度是O（1）的（下標(biāo)查詢），那有沒有一種方法能達(dá)到O（1）的時間復(fù)雜度呢？有！那就是用 Hash。
我們需要達(dá)到O（1）的時間復(fù)雜度，那無疑使用數(shù)組的下標(biāo)查找。那么我們就需要將存儲的元素轉(zhuǎn)化為數(shù)組的下標(biāo)。
那怎么設(shè)計(jì)hash函數(shù)呢？我們用一種最笨的方法，將所有字符串中的字符轉(zhuǎn)化為數(shù)字后相加。那ok，我們簡單的實(shí)現(xiàn)下。
zhangsan=>hash()=>858
lisi=>hash()=>433
wanger=>hash()=>644
wangwu=>hash()=>665
zhangsi=>hash()=>756
gaofei=>hash()=>619
這樣，我們就計(jì)算出來了每一個字符串對應(yīng)的數(shù)字映射了，我們叫這個數(shù)字為hash值，接下來我們再放到數(shù)組里：
上圖中數(shù)組的下標(biāo)就是字符串對應(yīng)的數(shù)字值。這下我們查找gaofei就很容易了，首先我們根據(jù)hash函數(shù)計(jì)算出gaofei的位置為619，然后去數(shù)組的619中找到gaofei，這樣時間復(fù)雜度就是O（1）啦。
hash沖突（拉鏈法）：#####
但是上面的實(shí)現(xiàn)是存在一個問題的，如果還有一個元素叫feigao會怎么樣？
我們首先計(jì)算下feigao的hash值，計(jì)算結(jié)果竟然和gaofei一樣，也是619。這下產(chǎn)生了Hash沖突了，怎么辦？619已經(jīng)有g(shù)aofei了，feigao放在哪？所以接下來我們只能改變數(shù)組的結(jié)構(gòu)了，怎么改變？我們將數(shù)組內(nèi)的元素改變?yōu)橐粋€鏈表，這樣就能裝下足夠多的元素了。這樣就能解決hash沖突的問題了：
如上圖，我們將沖突的元素變?yōu)榱随湵斫Y(jié)構(gòu)，這樣我們就能把feigao也放在了這個table結(jié)構(gòu)里面，其實(shí)這個數(shù)據(jù)結(jié)構(gòu)就叫做Hash表（HashTable）。
我們在檢索的時候可以這樣檢索
找到gaofei后，我們便可以遍歷鏈表，找到feigao了。是不是很開森？
怎樣壓縮hash表#####
但是，問題又來了，上面的數(shù)組好像不是很連續(xù)啊，從433直接跳到了619.中間的數(shù)組都浪費(fèi)了啊!!!。其實(shí)也不能說是浪費(fèi)，只不過暫時沒有用啊，如果沒有對應(yīng)的元素出現(xiàn)，就這樣一直浪費(fèi)著？顯然是不可取的。那我們想辦法壓縮下這個數(shù)組。
其實(shí)很簡答，只要減小hash值就行了嘛，那么我們對hash值取模，這樣就能保證所有的hash值落在模值之內(nèi)了。
但是對于取模的運(yùn)算計(jì)算機(jī)通常用位運(yùn)算是更快的，例如java的HashMap的默認(rèn)容量是16，每次擴(kuò)容之后也都維持2^n,為什么呢？
對于取模運(yùn)算hashMap是這樣實(shí)現(xiàn)的hashcode& (length-1)。如果length為16，那么正好是hashcode&15，例如feigao這個計(jì)算吧：
hash值：619 => ...0001001101011
length-1:15 => ...0000000001111
二者做與運(yùn)算結(jié)果為：...000000001011 => 11(十進(jìn)制)
其實(shí)可以口算一下結(jié)果為38余11（注意這里是除16而不是15）。同理對于32也是一樣的。但是這里有一個很著名的問題，就是因?yàn)閿?shù)字的不均勻會導(dǎo)致hash值的二進(jìn)制數(shù)末尾都是1的這種場景。這種場景會導(dǎo)致很多的值集中在最后一個數(shù)組元素，從而分布不均勻。解決方案是對hash值進(jìn)行重新計(jì)算hash。這種機(jī)制比較復(fù)雜。至今沒搞懂。
這里主要是考慮這樣設(shè)計(jì)主要考慮計(jì)算速度會十分的快，根據(jù)不同實(shí)現(xiàn)這個容量也是不固定的，這里只是以java的HashMap為例。
用幾個例子說一下HashTable的用處：#####
Case1:兩文件找出重復(fù)的元素#####
問題是這樣的，有兩個文件，文件中有一些短字符串，字符串個數(shù)分別為n。它們是有重復(fù)的字符串，現(xiàn)在需要找出所有重復(fù)的字符串。
首先我們考慮最笨的方法，遍歷文件1中的每個元素，取出每一個元素分別去文件2中進(jìn)行查找，這樣的時間復(fù)雜度為O（n^2）
接下來我們使用HashTable，我們遍歷文件1中的元素和文件2中的元素，放入HashTable中，對于重復(fù)的字符串我們做計(jì)數(shù)處理：
接下來遍歷整個列表，找出所有個數(shù)大于1的即為重復(fù)的元素。
Case2:兩文件找出出現(xiàn)次數(shù)最多的元素#####
和上面是同理的，但是在遍歷的時候需要找計(jì)數(shù)最大的元素，即為出現(xiàn)次數(shù)最多的元素。
Case3：路由算法#####
在一個多線程處理數(shù)據(jù)的場景下，我們需要將一個數(shù)據(jù)集分給不同的處理線程，同時要保證，相同的元素需要分到相同的處理線程上去，那么我們怎么處理呢？
其實(shí)這個就是一個很典型的Hash值應(yīng)用場景，對于很多的計(jì)算引擎默認(rèn)都是用hash算法去解決這個問題。因?yàn)橄嗤氐腍ash值相同，那么我們可以取hash之后進(jìn)行模運(yùn)算，運(yùn)算結(jié)果分配到不同的線程：
Hash算法的要點(diǎn)#####
在設(shè)計(jì)Hash算法的時候。一定要保證相同字符串產(chǎn)生的Hash值相同，同時要盡量的減小Hash沖突的發(fā)生（雖然避免不了）。這樣才是一個好的hash算法。目前，MurmurHash是一種沖突率最低的Hash算法。如果有需要，可以優(yōu)先考慮此算法。
