什么是Hash算法：#####
簡(jiǎn)單的說(shuō)疾瓮，hash算法就是將字符串轉(zhuǎn)化為數(shù)字的算法俺祠。
用一個(gè)例子說(shuō)Hash的優(yōu)勢(shì)#####
試想如果我們對(duì)一個(gè)數(shù)組進(jìn)行Query瓦堵，這個(gè)數(shù)組里困鸥，每一個(gè)元素都是一個(gè)字符串嗅蔬。我們知道數(shù)組最快的檢索辦法是通過(guò)數(shù)組的下標(biāo)進(jìn)行檢索，但是對(duì)于這種場(chǎng)景疾就，我們無(wú)能為力澜术，只能從頭查到尾，從而查詢(xún)出目標(biāo)元素猬腰。
假設(shè)鸟废，我要找gaofei，那就需要遍歷整個(gè)數(shù)組姑荷，十分的低效盒延。這樣最壞情況下時(shí)間復(fù)雜度是O（n）的缩擂，但是數(shù)組的查詢(xún)時(shí)間復(fù)雜度是O（1）的（下標(biāo)查詢(xún)），那有沒(méi)有一種方法能達(dá)到O（1）的時(shí)間復(fù)雜度呢添寺？有胯盯！那就是用 Hash。
我們需要達(dá)到O（1）的時(shí)間復(fù)雜度计露，那無(wú)疑使用數(shù)組的下標(biāo)查找博脑。那么我們就需要將存儲(chǔ)的元素轉(zhuǎn)化為數(shù)組的下標(biāo)。
那怎么設(shè)計(jì)hash函數(shù)呢票罐？我們用一種最笨的方法叉趣，將所有字符串中的字符轉(zhuǎn)化為數(shù)字后相加。那ok该押，我們簡(jiǎn)單的實(shí)現(xiàn)下君账。
zhangsan=>hash()=>858
lisi=>hash()=>433
wanger=>hash()=>644
wangwu=>hash()=>665
zhangsi=>hash()=>756
gaofei=>hash()=>619
這樣，我們就計(jì)算出來(lái)了每一個(gè)字符串對(duì)應(yīng)的數(shù)字映射了沈善，我們叫這個(gè)數(shù)字為hash值乡数，接下來(lái)我們?cè)俜诺綌?shù)組里：
上圖中數(shù)組的下標(biāo)就是字符串對(duì)應(yīng)的數(shù)字值。這下我們查找gaofei就很容易了闻牡，首先我們根據(jù)hash函數(shù)計(jì)算出gaofei的位置為619净赴，然后去數(shù)組的619中找到gaofei，這樣時(shí)間復(fù)雜度就是O（1）啦罩润。
hash沖突（拉鏈法）：#####
但是上面的實(shí)現(xiàn)是存在一個(gè)問(wèn)題的玖翅，如果還有一個(gè)元素叫feigao會(huì)怎么樣？
我們首先計(jì)算下feigao的hash值割以，計(jì)算結(jié)果竟然和gaofei一樣金度，也是619。這下產(chǎn)生了Hash沖突了严沥，怎么辦猜极？619已經(jīng)有g(shù)aofei了，feigao放在哪消玄？所以接下來(lái)我們只能改變數(shù)組的結(jié)構(gòu)了跟伏，怎么改變？我們將數(shù)組內(nèi)的元素改變?yōu)橐粋€(gè)鏈表翩瓜，這樣就能裝下足夠多的元素了受扳。這樣就能解決hash沖突的問(wèn)題了：
如上圖，我們將沖突的元素變?yōu)榱随湵斫Y(jié)構(gòu)兔跌，這樣我們就能把feigao也放在了這個(gè)table結(jié)構(gòu)里面勘高，其實(shí)這個(gè)數(shù)據(jù)結(jié)構(gòu)就叫做Hash表（HashTable）。
我們?cè)跈z索的時(shí)候可以這樣檢索
找到gaofei后，我們便可以遍歷鏈表华望，找到feigao了层亿。是不是很開(kāi)森？
怎樣壓縮hash表#####
但是立美，問(wèn)題又來(lái)了匿又，上面的數(shù)組好像不是很連續(xù)啊，從433直接跳到了619.中間的數(shù)組都浪費(fèi)了啊!!!建蹄。其實(shí)也不能說(shuō)是浪費(fèi)碌更，只不過(guò)暫時(shí)沒(méi)有用啊，如果沒(méi)有對(duì)應(yīng)的元素出現(xiàn)洞慎，就這樣一直浪費(fèi)著痛单？顯然是不可取的。那我們想辦法壓縮下這個(gè)數(shù)組劲腿。
其實(shí)很簡(jiǎn)答旭绒，只要減小hash值就行了嘛，那么我們對(duì)hash值取模焦人，這樣就能保證所有的hash值落在模值之內(nèi)了挥吵。
但是對(duì)于取模的運(yùn)算計(jì)算機(jī)通常用位運(yùn)算是更快的，例如java的HashMap的默認(rèn)容量是16花椭，每次擴(kuò)容之后也都維持2^n,為什么呢忽匈？
對(duì)于取模運(yùn)算hashMap是這樣實(shí)現(xiàn)的hashcode& (length-1)。如果length為16矿辽，那么正好是hashcode&15丹允，例如feigao這個(gè)計(jì)算吧：
hash值：619 => ...0001001101011
length-1:15 => ...0000000001111
二者做與運(yùn)算結(jié)果為：...000000001011 => 11(十進(jìn)制)
其實(shí)可以口算一下結(jié)果為38余11（注意這里是除16而不是15）。同理對(duì)于32也是一樣的袋倔。但是這里有一個(gè)很著名的問(wèn)題雕蔽，就是因?yàn)閿?shù)字的不均勻會(huì)導(dǎo)致hash值的二進(jìn)制數(shù)末尾都是1的這種場(chǎng)景。這種場(chǎng)景會(huì)導(dǎo)致很多的值集中在最后一個(gè)數(shù)組元素宾娜，從而分布不均勻批狐。解決方案是對(duì)hash值進(jìn)行重新計(jì)算hash。這種機(jī)制比較復(fù)雜碳默。至今沒(méi)搞懂贾陷。
這里主要是考慮這樣設(shè)計(jì)主要考慮計(jì)算速度會(huì)十分的快，根據(jù)不同實(shí)現(xiàn)這個(gè)容量也是不固定的嘱根，這里只是以java的HashMap為例。
用幾個(gè)例子說(shuō)一下HashTable的用處：#####
Case1:兩文件找出重復(fù)的元素#####
問(wèn)題是這樣的巷懈，有兩個(gè)文件该抒，文件中有一些短字符串，字符串個(gè)數(shù)分別為n顶燕。它們是有重復(fù)的字符串凑保，現(xiàn)在需要找出所有重復(fù)的字符串冈爹。
首先我們考慮最笨的方法，遍歷文件1中的每個(gè)元素欧引，取出每一個(gè)元素分別去文件2中進(jìn)行查找频伤，這樣的時(shí)間復(fù)雜度為O（n^2）
接下來(lái)我們使用HashTable，我們遍歷文件1中的元素和文件2中的元素芝此，放入HashTable中憋肖，對(duì)于重復(fù)的字符串我們做計(jì)數(shù)處理：
接下來(lái)遍歷整個(gè)列表，找出所有個(gè)數(shù)大于1的即為重復(fù)的元素婚苹。
Case2:兩文件找出出現(xiàn)次數(shù)最多的元素#####
和上面是同理的岸更，但是在遍歷的時(shí)候需要找計(jì)數(shù)最大的元素，即為出現(xiàn)次數(shù)最多的元素膊升。
Case3：路由算法#####
在一個(gè)多線(xiàn)程處理數(shù)據(jù)的場(chǎng)景下怎炊，我們需要將一個(gè)數(shù)據(jù)集分給不同的處理線(xiàn)程，同時(shí)要保證廓译，相同的元素需要分到相同的處理線(xiàn)程上去评肆，那么我們?cè)趺刺幚砟兀?br> 其實(shí)這個(gè)就是一個(gè)很典型的Hash值應(yīng)用場(chǎng)景，對(duì)于很多的計(jì)算引擎默認(rèn)都是用hash算法去解決這個(gè)問(wèn)題非区。因?yàn)橄嗤氐腍ash值相同糟港，那么我們可以取hash之后進(jìn)行模運(yùn)算，運(yùn)算結(jié)果分配到不同的線(xiàn)程：
Hash算法的要點(diǎn)#####
在設(shè)計(jì)Hash算法的時(shí)候院仿。一定要保證相同字符串產(chǎn)生的Hash值相同秸抚，同時(shí)要盡量的減小Hash沖突的發(fā)生（雖然避免不了）。這樣才是一個(gè)好的hash算法歹垫。目前剥汤，MurmurHash是一種沖突率最低的Hash算法。如果有需要排惨，可以?xún)?yōu)先考慮此算法吭敢。
