什么是哈希算法

通過之前的學(xué)習(xí)椿访，我們已經(jīng)了解了哈希函數(shù)在散列表中的應(yīng)用掏膏，哈希函數(shù)就是哈希算法的一個應(yīng)用。那么在這里給出哈希的定義：將任意長度的二進(jìn)制值串映射為固定長度的二進(jìn)制值串抽减，這個映射規(guī)則就是哈希算法祥得，得到的二進(jìn)制值串就是哈希值兔沃。
要設(shè)計一個好的哈希算法并不容易，它應(yīng)該滿足以下幾點要求：

• 從哈希值不能反向推導(dǎo)出原始數(shù)據(jù)（所以哈希算法是單向的）啃沪。
• 對輸入數(shù)據(jù)敏感粘拾，兩個數(shù)據(jù)中有任何一點不同，最后得到的哈希值也不同创千。
• 散列沖突的概率要小缰雇，不同數(shù)據(jù)計算得到的哈希值相同的概率非常小入偷。
• 哈希算法執(zhí)行高效，對大文本也能快速計算出哈希值械哟。

哈希算法的應(yīng)用

哈希算法的應(yīng)用非常廣泛疏之，在這里就介紹七點應(yīng)用：

應(yīng)用一：安全加密

有很多著名的哈希加密算法：MD5、SHA暇咆、DES...它們都是通過哈希進(jìn)行加密的算法锋爪。
對于加密的哈希算法來說，有兩點十分重要：一是很難根據(jù)哈希值反推導(dǎo)出原始數(shù)據(jù)爸业；二是散列沖突的概率要很小其骄。
當(dāng)然，哈希算法不可能排除散列沖突的可能扯旷，這用數(shù)學(xué)中的鴿巢原理就可以很好解釋拯爽。以MD5算法來說，得到的哈希值為一個 128 位的二進(jìn)制數(shù)钧忽，它的數(shù)據(jù)容量最多為 2¹²⁸ bit毯炮，如果超過這個數(shù)據(jù)量，必然會出現(xiàn)散列沖突耸黑。
在加密解密領(lǐng)域沒有絕對安全的算法桃煎，一般來說，只要解密的計算量極其龐大大刊，我們就可以認(rèn)為這種加密方法是較為安全的为迈。

應(yīng)用二：唯一標(biāo)識

假設(shè)我們有100萬個圖片，如果我們在圖片中尋找某一個圖片是非常耗時的奈揍，這是我們就可以使用哈希算法的原理為圖片設(shè)置唯一標(biāo)識曲尸。比如赋续，我們可以從圖片的二進(jìn)制碼串開頭取100個字節(jié)男翰，從中間取100個字節(jié)，從結(jié)尾取100個字節(jié)纽乱，然后將它們合并蛾绎，并使用哈希算法計算得到一個哈希值，將其作為圖片的唯一標(biāo)識鸦列。
使用這個唯一標(biāo)識判斷圖片是否在圖庫中租冠，這可以減少甚多工作量。

應(yīng)用三：數(shù)據(jù)校驗

在傳輸消息的過程中薯嗤，我們擔(dān)心通信數(shù)據(jù)被人篡改顽爹，這時就可以使用哈希函數(shù)進(jìn)行數(shù)據(jù)校驗。比如BT協(xié)議中就使用哈希栓發(fā)進(jìn)行數(shù)據(jù)校驗骆姐。

應(yīng)用四：散列函數(shù)

在散列表那一篇中我們就講過散列函數(shù)的應(yīng)用镜粤，相比于其它應(yīng)用捏题，散列函數(shù)對于散列算法沖突的要求低很多（我們可以通過開放尋址法或鏈表法解決沖突），同時散列函數(shù)對于散列算法是否能逆向解密也并不關(guān)心肉渴。
散列函數(shù)比較在意函數(shù)的執(zhí)行效率公荧，至于其它要求，在之前的我們已經(jīng)講過同规，就不再贅述了循狰。

接下來的三個應(yīng)用主要是在分布式系統(tǒng)中的應(yīng)用

應(yīng)用五：負(fù)載均衡

復(fù)雜均衡的算法很多，如何實現(xiàn)一個會話粘滯的負(fù)載均衡算法呢券勺？也就是說绪钥，我們需要在同一個客戶端上，在一次會話中的所有請求都路由到同一個服務(wù)器上关炼。

最簡單的辦法是我們根據(jù)客戶端的 IP 地址或會話 ID 創(chuàng)建一個映射關(guān)系昧识。但是這樣很浪費內(nèi)存，客戶端上線下線盗扒，服務(wù)器擴(kuò)容等都會導(dǎo)致映射失效跪楞，維護(hù)成本很大。

借助哈希算法侣灶，我們可以很輕松的解決這些問題：對客戶端的 IP 地址或會話 ID 計算哈希值甸祭，將取得的哈希值域服務(wù)器的列表的大小進(jìn)行取模運算，最后得到的值就是被路由到的服務(wù)器的編號褥影。

應(yīng)用六：數(shù)據(jù)分片

假設(shè)有一個非常大的日志文件池户，里面記錄了用戶的搜索關(guān)鍵詞，我們想要快速統(tǒng)計出每個關(guān)鍵詞被搜索的次數(shù)凡怎，該怎么做呢校焦？

分析一下，這個問題有兩個難點：一是搜索日志很大统倒，沒辦法放到一臺機(jī)器的內(nèi)存中寨典；二是如果用一臺機(jī)器處理這么大的數(shù)據(jù)，處理時間會很長房匆。

針對這兩個難點耸成，我們可以先對數(shù)據(jù)進(jìn)行分片，然后使用多臺機(jī)器處理浴鸿，提高處理速度井氢。具體思路：使用 n 臺機(jī)器并行處理，從日志文件中讀出每個搜索關(guān)鍵詞岳链，通過哈希函數(shù)計算哈希值花竞，然后用 n 取模，最終得到的值就是被分配的機(jī)器編號掸哑。
這樣约急，相同的關(guān)鍵詞被分配到了相同的機(jī)器上寇仓，不同機(jī)器只要記錄屬于自己那部分的關(guān)鍵詞的出現(xiàn)次數(shù)，最終合并不同機(jī)器上的結(jié)果即可烤宙。

針對這種海量數(shù)據(jù)的處理問題遍烦，我們都可以采用多機(jī)分布式處理。借助這種分片思路躺枕，可以突破單機(jī)內(nèi)存服猪、CPU等資源的限制。

應(yīng)用七：分布式存儲

處理思路和上面出現(xiàn)的思路類似：對數(shù)據(jù)進(jìn)行哈希運算拐云，對機(jī)器數(shù)取模罢猪，最終將存儲數(shù)據(jù)（可能是硬盤存儲，或者是緩存分配）分配到不同的機(jī)器上叉瘩。

哈希算法-分布式存儲的擴(kuò)容問題.jpg

你可以看一下上圖汤徽，你會發(fā)現(xiàn)之前存儲的數(shù)據(jù)在新的存儲規(guī)則下全部失效，這種情況是災(zāi)難性的灸撰。面對這種情況谒府，我們就需要使用一致性哈希算法。

假設(shè)我們有 k 個機(jī)器浮毯，數(shù)據(jù)的哈希值的范圍是[0, MAX]完疫。我們將整個范圍劃分成 m 個小區(qū)間（m 遠(yuǎn)大于 k），每個機(jī)器負(fù)責(zé) m/k 個小區(qū)間债蓝。當(dāng)有新機(jī)器加入的時候壳鹤，我們就將某幾個小區(qū)間的數(shù)據(jù)，從原來的機(jī)器中搬移到新的機(jī)器中惦蚊。這樣器虾，既不用全部重新哈希、搬移數(shù)據(jù)蹦锋，也保持了各個機(jī)器上數(shù)據(jù)數(shù)量的均衡。
一致性哈希算法的基本思想就是這么簡單欧芽。除此之外莉掂，它還會借助一個虛擬的環(huán)和虛擬結(jié)點，更加優(yōu)美地實現(xiàn)出來千扔。這里我就不展開講了憎妙，如果感興趣库正，你可以看下這里。

小結(jié)

哈希算法是應(yīng)用非常廣泛的算法厘唾，你可以回顧上面的七個應(yīng)用感受一下褥符。

其實在這里我想說的是一個思想：用優(yōu)勢彌補不足。
例如抚垃，在計算機(jī)中喷楣，數(shù)據(jù)的計算主要依賴 CPU ，數(shù)據(jù)的存儲交換主要依賴內(nèi)存鹤树。兩者一起配合才能實現(xiàn)各種功能铣焊，而兩者在性能上依然無法匹配，這種差距主要是：CPU運算性能對內(nèi)存的要求遠(yuǎn)高于現(xiàn)在的內(nèi)存能提供的性能罕伯。
也就是說曲伊，CPU運算很快，內(nèi)存相對較慢追他，為了抹平這種差距坟募，工程師們想了很多方法。在我看來邑狸，散列表的使用就是利用電腦的高計算性能（優(yōu)勢）去彌補內(nèi)存速度（不足）的不足婿屹，你仔細(xì)思考散列表的執(zhí)行過程，就會明白我的意思推溃。

以上就是哈希的全部內(nèi)容

注：本文章的主要內(nèi)容來自我對極客時間app的《數(shù)據(jù)結(jié)構(gòu)與算法之美》專欄的總結(jié)昂利，我大量引用了其中的代碼和截圖，如果想要了解具體內(nèi)容铁坎，可以前往極客時間