文章出處：極客時間《數據結構和算法之美》-作者：王爭。該系列文章是本人的學習筆記。

哈希算法的定義

文章來自極客時間。
參考網頁
定義：將任意長度的二進制值串映射為固定長度的二進制值串。映射之后的二進制值串稱為哈希值。
符合幾點要求：
　1 從哈希值不能推導出原文。
　2 原文有一個bit的值發生變化，哈希值不相同。
　3 散列沖突的概率要小，對于不同的原文產生相同哈希值的概率要小。
　4 高效，對長文本生成哈希值也要非常快。

哈希算法的常見應用

1 安全加密

最常用于加密的算法有MD5,SHA、DES、AES。
　鴿巢原理。哈希算法只能盡量減少碰撞沖突不能完全避免沖突的理論基礎就是鴿巢原理。10個鴿巢，11只鴿子，肯定有2只鴿子在同一個鴿巢內。哈希值的長度是固定的，例如MD5算法哈希值是128位。128位能表示$2^{128}$個數據。超出范圍就會產生沖突。一般情況下，哈希值越長，產生沖突的概率就越低。
　加密算法選擇多長的哈希值主要由破解難度和計算時間兩方面決定。

2 唯一標識

圖片查詢
　唯一標識是指用哈希值表示一個長文件。例如圖片、文件。如果我們想查找一個圖片在我們的圖片庫中是否存在，我們希望通過比對文件查找。因為圖片標題可能和圖片內容不匹配。一個圖片文件一般10幾K，甚至幾M，要想直接比較非常耗時。我們可以讀取圖片文件的開頭100個字節，中間100個字節，末尾100個字節，放到一起計算哈希值。查詢圖片的時候，對于輸入的圖片也按照同樣的方式計算哈希值，然后比較是否有相同哈希值的圖片。

3 數據校驗

BT下載
　BT下載是基于P2P協議從多臺機器上同時下載一個2G的電影。這個文件可能被分割為很多塊。等所有塊下載完成再組裝成一個文件。但是網絡傳輸是不安全的。我們需要在電影文件分割的時候，記錄每個文件對應的哈希值，寫在種子文件中。當下載完成后，計算下載文件的哈希值和種子文件中的哈希值比對。如果不一致，需要重新下載。

4 散列函數

要求散列函數計算的哈希值能夠均勻分布在各個槽。
要求散列函數簡單高效。

5 負載均衡

會話粘滯的負載均衡算法
　我們可以維護一個映射表，將會話ID與對應的服務器IP做映射。這樣簡單，但是映射表會很大。客戶端上下線、服務端上下線，都要維護，維護成本高。
　我們借助哈希算法，對每個會話ID計算哈希值。將取得的哈希值與服務器列表大小取余，得到最終服務器編號。

6 數據分片

統計日志文件中搜索詞次數
　如果日志文件很多很大，單臺計算內存可能不夠，而且計算也很慢。可以考慮分布式計算。我們對搜索詞取哈希值，然后跟服務器個數取余，最終得到的值就是服務器編號。這樣同樣的關鍵詞就被分配到同一臺服務器，進而計算出現次數。

7 分布式存儲

一致性哈希
　我們可以通過哈希算法把數據分別存儲到某臺服務器上。如果需要增加一臺服務器，則所有緩存的數據都失效，需要再次計算哈希值取余，放到新的服務器上。但是此時對數據庫壓力很大，容易形成雪崩。
　解決的方法是采用一致性哈希。我們把哈希值想象為一個閉環。
　
　整個空間按順時針方向存儲。當插入數據A、B、C、D的時候，如下圖所示。A存儲咋server1，B、C存儲在server2，D存儲在server3。假設server3發生意外宕機，只需要把數據D遷移到seerver2。
　
　
　假設我們有k個服務器，哈希值的取值范圍是[0,MAX]。我們將哈希值分為m個區間（m遠大于k），每個機器負責m/k個小區間。當有新機器加入的時候，我們就將某幾個小區間的數據，從原來的機器上搬移到新的機器中。這樣既不會重新哈希全部的數據，也保持了各個機器上的數據量的均衡。

總結

以上是生活随笔為你收集整理的算法四——哈希的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。