摘要:
哈希算法是將不同長度二進制串轉(zhuǎn)換為固定長度二進制串的算法，在加密，唯一性校驗，數(shù)據(jù)分片等方面都有應(yīng)用
該叫散列函數(shù)還是哈希函數(shù)
看到哈希函數(shù)時心中總是會泛起疑問，哈希算法需要單獨列出，那散列函數(shù)又是什么？之前我們討論過散列表以及散列函數(shù)，散列其實就是哈希，只是翻譯的不同而已，不過散列表中的散列函數(shù)只是哈希算法的一種應(yīng)用而已。
哈希算法的定義比較簡單，就是將不同長度二進制串轉(zhuǎn)換為固定長度（128 bit）二進制串的算法，哈希算法通過原始數(shù)據(jù)計算得到的值就是「哈希值」，雖然哈希算法的定義簡單，但哈希算法在實現(xiàn)上有幾個需要注意的原則：
- 哈希值不能逆推原始數(shù)據(jù)
- 哈希算法的沖突要小
- 哈希算法執(zhí)行要高效
- 差異較小的原始數(shù)據(jù)生成的哈希值應(yīng)完全不同
哈希算法具有不能逆轉(zhuǎn)的特性，但哈希算法并不能完全避免哈希值沖突，因為哈希值的長度固定，128 bit 長度的數(shù)據(jù)只能保證 個數(shù)據(jù)不會有重復(fù)哈希值出現(xiàn)，如果使用
個數(shù)據(jù)進行哈希計算肯定會得到相同的哈希值。不過你就會想，那增加哈希值長度不就可以降低沖突的可能？這種方式確實可以降低哈希沖突的概率，但生成更長的哈希值也會使哈希算法的效率降低。在面對差異較小的數(shù)據(jù)時，哈希算法也應(yīng)該生成不同的哈希值。
實際應(yīng)用
由于哈希算法的特性，在實際中可以用于加密數(shù)據(jù)、驗證唯一性、負載均衡、數(shù)據(jù)分片等方面，接下來詳細討論一下哈希算法的實際運用。
數(shù)據(jù)加密
在實際生產(chǎn)中像密碼等敏感數(shù)據(jù)都不應(yīng)該明文存儲，明文保存的密碼在數(shù)據(jù)泄漏后會使用戶的登錄安全蕩然無存，因為哈希值的不可逆推特性可以保證原始數(shù)據(jù)的安全，所以哈希算法也被應(yīng)用在數(shù)據(jù)加密方面。不過如果是過于簡單的密碼「000000」、「123456」等，都可以通過常用密碼字典生成哈希值進行對應(yīng)，以推出原始數(shù)據(jù)，所以對數(shù)據(jù)加密時可以將密碼與「鹽（salt）」組合后通過哈希算法計算，這樣就可以使哈希值較難破解。當然，也可以選擇更加復(fù)雜，更加安全的加密算法，不過算法執(zhí)行效率也會相應(yīng)降低。
唯一性驗證
哈希算法不可逆且唯一，使其成為驗證唯一性的不二選擇。比如使用 BT 工具下載文件時，種子文件中記載著正確文件的哈希值，下載完成的文件會將文件內(nèi)容生成哈希值與種子文件中的比對，如果比對失敗那就說明文件被篡改或者被損壞，需要重新到相應(yīng)服務(wù)器進行下載。有些從官網(wǎng)下載的文件也是會生成 MD5 碼，可以與官網(wǎng)上記錄的 MD5 碼進行比較，驗證文件的正確性。
圖片查找
驗證兩個圖片是否相同的辦法就是比較兩個圖片轉(zhuǎn)化的二進制數(shù)據(jù)是否完全一致，但使用這種方式在大量圖片中查找相同圖片效率就太過低下。其實可以截取圖片數(shù)據(jù)片段生成哈希值，將哈希值與圖片路徑對應(yīng)存儲在庫表中，當要查找某張圖片時將傳入圖片進行相同的數(shù)據(jù)截取，并且生成哈希值，利用哈希值查找相應(yīng)圖片路徑，再將路徑下的圖片與傳入圖片轉(zhuǎn)換為二進制比對，這樣可以極大提高圖片查找的執(zhí)行效率。
散列函數(shù)
正如開篇提到的，散列函數(shù)也是哈希算法的一種應(yīng)用，不過它對安全性和唯一性并沒有較高的要求，散列函數(shù)需要哈希值能夠均勻分布，并且能夠執(zhí)行高效，即使有一定的沖突也可以利用開放尋址或者鏈表法解決，所以散列函數(shù)的計算都較為簡單。
除了以上的幾個方面外，在分布式場景下哈希算法也有所應(yīng)用。
負載均衡
在負載均衡中有一種情況是需要同一會話路由到同一服務(wù)器，這種稱為「會話粘滯（sticky session）」，簡單的做法就是將會話 ID 與服務(wù)器對應(yīng)存儲在庫表中，通過請求的會話 ID 查找應(yīng)該路由到的服務(wù)器。但這種方法有些問題，當請求量增加時庫表存儲的數(shù)據(jù)量會不斷增大，而且這種對應(yīng)關(guān)系在服務(wù)器數(shù)量進行擴容或者縮容時也可能被破壞，增加了數(shù)據(jù)維護的壓力。其實可以通過將會話 ID 進行哈希計算，將得到的哈希值與服務(wù)器數(shù)量取模，取模結(jié)果是多少就表示此會話路由到第幾個服務(wù)器上。
數(shù)據(jù)分片
接著前面講到的圖片查找問題討論。當圖片數(shù)量過多，如果還存儲在一臺服務(wù)器上的話，維護圖片哈希值與路徑對應(yīng)關(guān)系的庫表就會非常大，導(dǎo)致不宜查找，我們可以將圖片存放在不同的服務(wù)器上，此服務(wù)器只維護本機上圖片哈希值與圖片路徑的對應(yīng)關(guān)系，圖片的哈希值可以與服務(wù)器數(shù)量取模確定該圖片需要存儲于哪臺服務(wù)器，這樣不僅將存儲壓力分散在不同服務(wù)器上，同時也將計算的壓力進行了分攤。
分布式存儲
如今因為數(shù)據(jù)量激增，很多數(shù)據(jù)都是分布式存儲的，如果使用數(shù)據(jù)分片的方式利用哈希值取模確定數(shù)據(jù)存儲于哪臺服務(wù)器，那當對服務(wù)器進行擴容或者縮容的時候所有數(shù)據(jù)都需要重新計算搬移一遍，這樣對于數(shù)據(jù)維護的壓力過大。這里可以使用「一致性哈希算法」，我們將哈希值限定在 0 至 M 之間，假設(shè)有 n 個服務(wù)器，將哈希值區(qū)間劃分為 m 個小區(qū)間，每個服務(wù)器負責 m/n 個區(qū)間的哈希值，如果增加一臺服務(wù)器，就將每個服務(wù)器負責的區(qū)間數(shù)據(jù)分一部分搬移到新服務(wù)器上，這樣即可以保證服務(wù)器的擴容縮容不用維護過多數(shù)據(jù)，也可以保證數(shù)據(jù)分布均勻。
總結(jié)
哈希算法擁有安全性、唯一性并且高效的特點，這些特點使其被應(yīng)用在數(shù)據(jù)加密、唯一性驗證、負載均衡、分布式存儲等方面，其實除了上面介紹的應(yīng)用場景之外哈希算法還有很多的應(yīng)用場景。
文章中如有問題歡迎留言指正
數(shù)據(jù)結(jié)構(gòu)與算法之美筆記系列將會做為我對王爭老師此專欄的學習筆記，如想了解更多王爭老師專欄的詳情請到極客時間自行搜索。
