一文搞懂Hash算法以及應用場景
一、什么是哈希算法
哈希和散列都來源于單詞hash，前者是音譯，后者是意譯。是一種可以將任意長度的二進制值映射為固定長度二進制值的算法，映射后固定長度的二進制值被稱為哈希值。一個優秀的哈希算法需要滿足以下幾點要求：
不能從哈希值反向推導出原始數據；
對輸入數據非常敏感，一個bit不同就會導致哈希值非常不一樣；
散列沖突的概率要很小；
哈希算法的計算過程要足夠簡單高效，即使原始數據很長，也能很快得到哈希值；
二、哈希算法的使用場景
2.1 安全加密
比較常見的哈希加密算法有MD5(MD5 Message-Digest Algorithm, MD5消息摘要算法)和SHA(Secure Hash Algorithm, 安全散列算法)。
不能從哈希值密文反推出明文密碼，且散列沖突概率比較小，這兩點確保了哈希算法作為安全加密手段的可靠性。
為什么哈希算法不能完全避免散列沖突，只能盡量減少？
鴿巢原理告訴我們，11個鴿子飛進10個鴿子籠，那么必定有一個鴿子籠里面有2只及以上的鴿子。那么散列值是固定長度的，也就決定了散列值可以被窮舉，但是理論上原始數據是無窮無盡的，因此必定有可能會導致散列沖突。
這種應用場景用到了哈希算法的特點1和3，其中3保證了密碼被正向破解的難度很大（以MD5為例，散列值長度為128位，有2^128個不同的哈希值，很難被破解）。
安全領域沒有絕對的安全，雖然MD5很難被破解，但是還是有辦法被破解的，比如使用彩虹表匹配可以很輕松地破解常見密碼。
所以一般我們會使用加鹽的哈希算法來進行安全加密，加鹽的方法需要嚴格保密，如此讓破解的難度和成本都大大增加。
2.2 唯一標志
我們在校驗兩個文件是否一樣的時候，是不能簡單地通過文件名來進行判斷的。因為同名文件的存在太常見了。
我們可以從大文件中按照特定的規則取一些二進制數據，利用哈希算法得出哈希值作為該文件的唯一標志。如此相同的文件必定具有相同的哈希值，也就是相同的唯一標志；不同的文件在很大概率上是具有不同的哈希值唯一標志的；
即使真的遇到了散列沖突，我們可以再詳細比對兩個文件的全部二進制數據，進一步判斷它們是否是同一個文件，這個事件發生的概率太小了。但是這種方案既保證了高效，又保證了可靠。
這種應用場景用到了哈希算法的特點2和3。
2.3 數據校驗
在P2P下載協議中，我們會從不同的機器上下載同一部電影的不同部分，然后在自己的機器上將電影組裝起來。如果這其中某個部分的電影下載過程中出了錯誤或者內容被篡改了，就可能導致下載出錯或者中病毒。
因此，我們先對所有部分進行hash計算，并保存在種子文件中。等到所有部分下載完成，我們對所有部分進行哈希計算得到哈希值，再和種子文件中的進行比較，以此來校驗文件是否完整。
這種應用場景用到了哈希算法的特點2和4。
2.4 散列函數
這種場景在前面講過散列表的時候就已經介紹了。這種場景下，對特點1要求不是很高，特點2的要求是散列值要盡量均勻分布，特點3也在一定程度上可以接受沖突，使用開放尋址法和拉鏈法就可以解決，就是特點4要求高一點，需要追求性能。
2.5 負載均衡
負載均衡的算法有很多，比如輪詢、隨機、加權輪詢等，但是目標是要實現一個會話粘滯的負載均衡算法，即同一個客戶端在一個會話期間所有的請求都是路由到同一臺服務器的。
我們可以將客戶端的IP或者會話ID進行哈希計算，得到的哈希值與服務器個數進行取模運算，最終得到的值就是需要路由的服務器，這樣就能實現會話粘滯的目的。
2.6 數據分片
當我們需要處理海量數據的時候，單臺服務器無法加載和計算如此海量的數據，那么我們就需要將海量數據均勻地分給N臺服務器進行并行計算，如何將數據均勻地分給N臺服務器呢？
我們對數據進行哈希計算，用得到的哈希值對服務器個數N取模，相同結果的數據會被分到相同的服務器上，交給這臺服務器處理。N臺服務器并行處理海量數據，最終再將結果合并起來即可。
2.7 分布式存儲
將海量數據存儲到分布式緩存或者分布式數據庫中，借用的思想和上面的數據分片是類似的。只不過，當原先設定好的服務器數量不夠的時候該如何處理呢？
并不是簡單地加幾臺機器就能解決的，這會破壞哈希值的取模運算，導致緩存穿透，引起雪崩效應。同理，當某個機器故障被移除時也會導致相同的問題。這個時候需要借助一致性哈希算法來解決這個問題。
一致性哈希算法簡單地說就是構造一個hash環，環上有2^32個節點，將服務器IP和文件都hash計算映射到對應的節點上。所有文件順時針遇到的第一個服務器就作為自己存放的服務器。如此，當增加或者刪除某個服務器的時候，影響的文件個數就可控，不會造成全局雪崩。
hash環
但是，在一定概率上，服務器IP在映射到hash環上時，會出現hash環偏斜的問題，此時會導致服務器上文件分布極其不均勻，退化為一開始在增刪服務器時容易造成雪崩效應的場景。
hash環的偏斜
我們可以人為地為這些服務器增加若干虛擬節點，使得所有服務器節點在hash環上分布均勻。
帶虛擬節點的hash環
三、總結
Hash算法的使用場景遠遠不止上述這些，還有比如CRC校驗。
