一、什么是哈希算法

哈希和散列都來源于單詞hash，前者是音譯，后者是意譯。是一種可以將任意長度的二進(jìn)制值映射為固定長度二進(jìn)制值的算法，映射后固定長度的二進(jìn)制值被稱為哈希值。一個優(yōu)秀的哈希算法需要滿足以下幾點要求：

不能從哈希值反向推導(dǎo)出原始數(shù)據(jù)；

對輸入數(shù)據(jù)非常敏感，一個bit不同就會導(dǎo)致哈希值非常不一樣；

散列沖突的概率要很小；

哈希算法的計算過程要足夠簡單高效，即使原始數(shù)據(jù)很長，也能很快得到哈希值；

二、哈希算法的使用場景

2.1 安全加密

比較常見的哈希加密算法有MD5(MD5 Message-Digest Algorithm, MD5消息摘要算法)和SHA(Secure Hash Algorithm, 安全散列算法)。

不能從哈希值密文反推出明文密碼，且散列沖突概率比較小，這兩點確保了哈希算法作為安全加密手段的可靠性。

為什么哈希算法不能完全避免散列沖突，只能盡量減少？

鴿巢原理告訴我們，11個鴿子飛進(jìn)10個鴿子籠，那么必定有一個鴿子籠里面有2只及以上的鴿子。那么散列值是固定長度的，也就決定了散列值可以被窮舉，但是理論上原始數(shù)據(jù)是無窮無盡的，因此必定有可能會導(dǎo)致散列沖突。

這種應(yīng)用場景用到了哈希算法的特點1和3，其中3保證了密碼被正向破解的難度很大（以MD5為例，散列值長度為128位，有2^128個不同的哈希值，很難被破解）。

安全領(lǐng)域沒有絕對的安全，雖然MD5很難被破解，但是還是有辦法被破解的，比如使用彩虹表匹配可以很輕松地破解常見密碼。

所以一般我們會使用加鹽的哈希算法來進(jìn)行安全加密，加鹽的方法需要嚴(yán)格保密，如此讓破解的難度和成本都大大增加。

2.2 唯一標(biāo)志

我們在校驗兩個文件是否一樣的時候，是不能簡單地通過文件名來進(jìn)行判斷的。因為同名文件的存在太常見了。

我們可以從大文件中按照特定的規(guī)則取一些二進(jìn)制數(shù)據(jù)，利用哈希算法得出哈希值作為該文件的唯一標(biāo)志。如此相同的文件必定具有相同的哈希值，也就是相同的唯一標(biāo)志；不同的文件在很大概率上是具有不同的哈希值唯一標(biāo)志的；

即使真的遇到了散列沖突，我們可以再詳細(xì)比對兩個文件的全部二進(jìn)制數(shù)據(jù)，進(jìn)一步判斷它們是否是同一個文件，這個事件發(fā)生的概率太小了。但是這種方案既保證了高效，又保證了可靠。

這種應(yīng)用場景用到了哈希算法的特點2和3。

2.3 數(shù)據(jù)校驗

在P2P下載協(xié)議中，我們會從不同的機(jī)器上下載同一部電影的不同部分，然后在自己的機(jī)器上將電影組裝起來。如果這其中某個部分的電影下載過程中出了錯誤或者內(nèi)容被篡改了，就可能導(dǎo)致下載出錯或者中病毒。

因此，我們先對所有部分進(jìn)行hash計算，并保存在種子文件中。等到所有部分下載完成，我們對所有部分進(jìn)行哈希計算得到哈希值，再和種子文件中的進(jìn)行比較，以此來校驗文件是否完整。

這種應(yīng)用場景用到了哈希算法的特點2和4。

2.4 散列函數(shù)

這種場景在前面講過散列表的時候就已經(jīng)介紹了。這種場景下，對特點1要求不是很高，特點2的要求是散列值要盡量均勻分布，特點3也在一定程度上可以接受沖突，使用開放尋址法和拉鏈法就可以解決，就是特點4要求高一點，需要追求性能。

2.5 負(fù)載均衡

負(fù)載均衡的算法有很多，比如輪詢、隨機(jī)、加權(quán)輪詢等，但是目標(biāo)是要實現(xiàn)一個會話粘滯的負(fù)載均衡算法，即同一個客戶端在一個會話期間所有的請求都是路由到同一臺服務(wù)器的。

我們可以將客戶端的IP或者會話ID進(jìn)行哈希計算，得到的哈希值與服務(wù)器個數(shù)進(jìn)行取模運算，最終得到的值就是需要路由的服務(wù)器，這樣就能實現(xiàn)會話粘滯的目的。

2.6 數(shù)據(jù)分片

當(dāng)我們需要處理海量數(shù)據(jù)的時候，單臺服務(wù)器無法加載和計算如此海量的數(shù)據(jù)，那么我們就需要將海量數(shù)據(jù)均勻地分給N臺服務(wù)器進(jìn)行并行計算，如何將數(shù)據(jù)均勻地分給N臺服務(wù)器呢？

我們對數(shù)據(jù)進(jìn)行哈希計算，用得到的哈希值對服務(wù)器個數(shù)N取模，相同結(jié)果的數(shù)據(jù)會被分到相同的服務(wù)器上，交給這臺服務(wù)器處理。N臺服務(wù)器并行處理海量數(shù)據(jù)，最終再將結(jié)果合并起來即可。

2.7 分布式存儲

將海量數(shù)據(jù)存儲到分布式緩存或者分布式數(shù)據(jù)庫中，借用的思想和上面的數(shù)據(jù)分片是類似的。只不過，當(dāng)原先設(shè)定好的服務(wù)器數(shù)量不夠的時候該如何處理呢？

并不是簡單地加幾臺機(jī)器就能解決的，這會破壞哈希值的取模運算，導(dǎo)致緩存穿透，引起雪崩效應(yīng)。同理，當(dāng)某個機(jī)器故障被移除時也會導(dǎo)致相同的問題。這個時候需要借助一致性哈希算法來解決這個問題。

一致性哈希算法簡單地說就是構(gòu)造一個hash環(huán)，環(huán)上有2^32個節(jié)點，將服務(wù)器IP和文件都hash計算映射到對應(yīng)的節(jié)點上。所有文件順時針遇到的第一個服務(wù)器就作為自己存放的服務(wù)器。如此，當(dāng)增加或者刪除某個服務(wù)器的時候，影響的文件個數(shù)就可控，不會造成全局雪崩。

hash環(huán)

但是，在一定概率上，服務(wù)器IP在映射到hash環(huán)上時，會出現(xiàn)hash環(huán)偏斜的問題，此時會導(dǎo)致服務(wù)器上文件分布極其不均勻，退化為一開始在增刪服務(wù)器時容易造成雪崩效應(yīng)的場景。

hash環(huán)的偏斜

我們可以人為地為這些服務(wù)器增加若干虛擬節(jié)點，使得所有服務(wù)器節(jié)點在hash環(huán)上分布均勻。

帶虛擬節(jié)點的hash環(huán)

三、總結(jié)

Hash算法的使用場景遠(yuǎn)遠(yuǎn)不止上述這些，還有比如CRC校驗。