什么是哈希算法

通過之前的學(xué)習(xí)，我們已經(jīng)了解了哈希函數(shù)在散列表中的應(yīng)用，哈希函數(shù)就是哈希算法的一個應(yīng)用。那么在這里給出哈希的定義：將任意長度的二進制值串映射為固定長度的二進制值串，這個映射規(guī)則就是哈希算法，得到的二進制值串就是哈希值。
要設(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ù)哈希值反推導(dǎo)出原始數(shù)據(jù)；二是散列沖突的概率要很小。
當(dāng)然，哈希算法不可能排除散列沖突的可能，這用數(shù)學(xué)中的鴿巢原理就可以很好解釋。以MD5算法來說，得到的哈希值為一個 128 位的二進制數(shù)，它的數(shù)據(jù)容量最多為 2¹²⁸ bit，如果超過這個數(shù)據(jù)量，必然會出現(xiàn)散列沖突。
在加密解密領(lǐng)域沒有絕對安全的算法，一般來說，只要解密的計算量極其龐大，我們就可以認(rèn)為這種加密方法是較為安全的。

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

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

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

在傳輸消息的過程中，我們擔(dān)心通信數(shù)據(jù)被人篡改，這時就可以使用哈希函數(shù)進行數(shù)據(jù)校驗。比如BT協(xié)議中就使用哈希栓發(fā)進行數(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ù)器擴容等都會導(dǎo)致映射失效，維護成本很大。

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

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

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

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

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

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

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

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

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

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

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

小結(jié)

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

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

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

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