引言?
? ? ? ?將任意長度的二進(jìn)制字符串映射為定長二進(jìn)制字符串的映射規(guī)則我們稱為散列（hash）算法挎狸，又叫哈希（hash）算法懦窘，而通過原始數(shù)據(jù)映射之后得到的二進(jìn)制值稱為哈希值圆凰。哈希表（hash表）結(jié)構(gòu)是哈希算法的一種應(yīng)用带污，也叫散列表。用的是數(shù)組支持按照下標(biāo)隨機(jī)訪問數(shù)據(jù)的特性擴(kuò)展竞思、演化而來表谊。可以說沒有數(shù)組就沒有散列表盖喷。
哈希算法主要特點
????????從哈希值不能反向推導(dǎo)原始數(shù)據(jù)爆办，也叫單向哈希。
????????對輸入數(shù)據(jù)敏感课梳，哪怕只改了一個Bit距辆，最后得到的哈希值也大不相同。
????????散列沖突的概率要小暮刃。
????????哈希算法執(zhí)行效率要高跨算，散列結(jié)果要盡量均衡。
哈希算法的核心應(yīng)用
? ??? ??安全加密：對于敏感數(shù)據(jù)比如密碼字段進(jìn)行MD5或SHA加密傳輸椭懊。
? ??????唯一標(biāo)識：比如圖片識別诸蚕，可針對圖像二進(jìn)制流進(jìn)行摘要后MD5，得到的哈希值作為圖片唯一標(biāo)識氧猬。
????????散列函數(shù):是構(gòu)造散列表的關(guān)鍵背犯。它直接決定了散列沖突的概率和散列表的性質(zhì)。不過相對哈希算法的其他方面應(yīng)用盅抚，散列函數(shù)對散列沖突要求較低漠魏，出現(xiàn)沖突時可以通過開放尋址法或鏈表法解決沖突。對散列值是否能夠反向解密要求也不高妄均。反而更加關(guān)注的是散列的均勻性柱锹，即是否散列值均勻落入槽中以及散列函數(shù)執(zhí)行的快慢也會影響散列表性能哪自。所以散列函數(shù)一般比較簡單，追求均勻和高效禁熏。
? ??? ? *負(fù)載均衡：常用的負(fù)載均衡算法有很多壤巷，比如輪詢、隨機(jī)匹层、加權(quán)輪詢隙笆。如何實現(xiàn)一個會話粘滯的負(fù)載均衡算法呢？可以通過哈希算法升筏，對客戶端IP地址或會話SessionID計算哈希值撑柔，將取得的哈希值與服務(wù)器列表大小進(jìn)行取模運(yùn)算，最終得到應(yīng)該被路由到的服務(wù)器編號您访。這樣就可以把同一IP的客戶端請求發(fā)到同一個后端服務(wù)器上铅忿。
? ? ? ? *數(shù)據(jù)分片：比如統(tǒng)計1T的日志文件中“搜索關(guān)鍵詞”出現(xiàn)次數(shù)該如何解決？我們可以先對日志進(jìn)行分片灵汪，然后采用多機(jī)處理檀训，來提高處理速度。從搜索的日志中依次讀取搜索關(guān)鍵詞享言，并通過哈希函數(shù)計算哈希值峻凫，然后再跟n(機(jī)器數(shù))取模，最終得到的值就是應(yīng)該被分到的機(jī)器編號览露。這樣相同哈希值的關(guān)鍵詞就被分到同一臺機(jī)器進(jìn)行處理荧琼。每臺機(jī)器分別計算關(guān)鍵詞出現(xiàn)的次數(shù)，再進(jìn)行合并就是最終結(jié)果差牛。這也是MapReduce的基本思想命锄。再比如圖片識別應(yīng)用中給每個圖片的摘要信息取唯一標(biāo)識然后構(gòu)建散列表，如果圖庫中有大量圖片偏化，單機(jī)的hash表會過大脐恩，超過單機(jī)內(nèi)存容量。這時也可以使用分片思想侦讨，準(zhǔn)備n臺機(jī)器驶冒，每臺機(jī)器負(fù)責(zé)散列表的一部分?jǐn)?shù)據(jù)。每次從圖庫取一個圖片韵卤，計算唯一標(biāo)識骗污，然后與機(jī)器個數(shù)n求余取模，得到的值就是被分配到的機(jī)器編號怜俐，然后將這個唯一標(biāo)識和圖片路徑發(fā)往對應(yīng)機(jī)器構(gòu)建散列表身堡。當(dāng)進(jìn)行圖片查找時邓尤，使用相同的哈希函數(shù)對圖片摘要信息取唯一標(biāo)識并對n求余取模操作后拍鲤，得到的值k贴谎，就是當(dāng)前圖片所存儲的機(jī)器編號，在該機(jī)器的散列表中查找該圖片即可季稳。實際上海量數(shù)據(jù)的處理問題擅这，都可以借助這種數(shù)據(jù)分片思想，突破單機(jī)內(nèi)存景鼠、CPU等資源限制仲翎。
? ? ? ? *分布式存儲：一致性哈希算法解決緩存等分布式系統(tǒng)的擴(kuò)容、縮容導(dǎo)致大量數(shù)據(jù)搬移難題铛漓。
????????JDK集合工具實現(xiàn)：HashMap溯香、?LinkedHashMap、ConcurrentHashMap浓恶、TreeMap等玫坛。Map實現(xiàn)類源碼分析，詳見?http://www.reibang.com/p/602324fa59ac
總結(jié)
????????本文從哈希算法的原理及特點包晰，總結(jié)了哈希算法的常見應(yīng)用場景湿镀。
????????其中基于余數(shù)思想和同余定理實現(xiàn)的哈希算法（除留取余法），廣泛應(yīng)用在分布式場景中（散列函數(shù)伐憾、數(shù)據(jù)分片勉痴、負(fù)載均衡）。由于組合數(shù)學(xué)中的“鴿巢”原理树肃，理論上不存在完全沒有沖突的哈希算法蒸矛。（PS:“鴿巢”原理是指有限的槽位，放多于槽位數(shù)的鴿子時扫外，勢必有不同的鴿子落在同一槽內(nèi)莉钙，即沖突發(fā)生。同余定理：如果a和b對x取余數(shù)操作時a%x = b%x筛谚，則a和b同余）
? ? ? ? 構(gòu)造哈希函數(shù)的常規(guī)方法有：數(shù)據(jù)分析法磁玉、直接尋址法、除留取余法驾讲、折疊法蚊伞、隨機(jī)法、平方取中法等 ?吮铭。
????????常規(guī)的解決哈希沖突方法有開放尋址法（線性探測时迫、再哈希）和鏈表法。JDK中的HashMap和LinkedHashMap均是采用鏈表法解決哈希沖突的谓晌。鏈表法適合大數(shù)據(jù)量的哈希沖突解決掠拳，可以使用動態(tài)數(shù)據(jù)結(jié)構(gòu)（比如：跳表、紅黑樹等）代替鏈表纸肉，防止鏈表時間復(fù)雜度過度退化導(dǎo)致性能下降溺欧；反之開放尋址法適合少量數(shù)據(jù)的哈希沖突解決喊熟。
