還記得 2011 年 CSDN 的“脫庫”事件嗎？當時，CSDN 網站被黑客攻擊，超過 600 萬使用者的注冊郵箱和密碼明文被洩露，很多網友對 CSDN 明文儲存使用者密碼行為産生了不滿。如果你是 CSDN 的一名工程師，你會如何存儲使用者密碼這麼重要的資料嗎？僅僅 MD5 加密一下存儲就夠了嗎？ 要想搞清楚這個問題，就要先弄明白雜湊演算法。
雜湊演算法曆史悠久，業界著名的雜湊演算法也有很多，比如 MD5、SHA 等。在我們平時的開發中，基本上都是拿現成的直接用。是以，我今天不會重點剖析雜湊演算法的原理，也不會教你如何設計一個雜湊演算法，而是從實戰的角度告訴你，在實際的開發中，我們該如何用雜湊演算法解決問題。
什麼是雜湊演算法？
“散清單”、“散列函數”、“雜湊演算法”實際上，不管是“散列”還是“哈希”，這都是中文翻譯的差别，英文其實就是“Hash”。是以，我們常聽到有人把“散清單”叫作“哈希表”“Hash 表”，把“雜湊演算法”叫作“Hash 算法”或者“雜湊演算法”。那到底什麼是雜湊演算法呢？
雜湊演算法的定義和原理非常簡單，基本上一句話就可以概括了。将任意長度的二進制值串映射為固定長度的二進制值串，這個映射的規則就是雜湊演算法，而通過原始資料映射之後得到的二進制值串就是哈希值。但是，要想設計一個優秀的雜湊演算法并不容易，根據經驗，總結了需要滿足的幾點要求：
（1）從哈希值不能反向推導出原始資料（是以雜湊演算法也叫單向雜湊演算法）；
（2）對輸入資料非常敏感，哪怕原始資料隻修改了一個 Bit，最後得到的哈希值也大不相同；
（3）散列沖突的機率要很小，對于不同的原始資料，哈希值相同的機率非常小；
（4）雜湊演算法的執行效率要盡量高效，針對較長的文本，也能快速地計算出哈希值。
這些定義和要求都比較理論，可能還是不好了解，我拿 MD5 這種雜湊演算法來具體說明一下。
我們分别對“今天我來講雜湊演算法”和“jiajia”這兩個文本，計算 MD5 哈希值，得到兩串看起來毫無規律的字元串（MD5 的哈希值是 128 位的 Bit 長度，為了友善表示，我把它們轉化成了 16 進制編碼）。可以看出來，無論要哈希的文本有多長、多短，通過 MD5 哈希之後，得到的哈希值的長度都是相同的，而且得到的哈希值看起來像一堆随機數，完全沒有規律。
（1）MD5(" 今天我來講雜湊演算法 ") = bb4767201ad42c74e650c1b6c03d78fa
（2）MD5("jiajia") = cd611a31ea969b908932d44d126d195b
我們再來看兩個非常相似的文本，“我今天講雜湊演算法！”和“我今天講雜湊演算法”。這兩個文本隻有一個感歎号的差別。如果用 MD5 雜湊演算法分别計算它們的哈希值，你會發現，盡管隻有一字之差，得到的哈希值也是完全不同的。
（1）MD5(" 我今天講雜湊演算法！") = 425f0d5a917188d2c3c3dc85b5e4f2cb
（2）MD5(" 我今天講雜湊演算法 ") = a1fb91ac128e6aa37fe42c663971ac3d
我在前面也說了，通過雜湊演算法得到的哈希值，很難反向推導出原始資料。比如上面的例子中，我們就很難通過哈希值“a1fb91ac128e6aa37fe42c663971ac3d”反推出對應的文本“我今天講雜湊演算法”。
雜湊演算法要處理的文本可能是各種各樣的。比如，對于非常長的文本，如果雜湊演算法的計算時間很長，那就隻能停留在理論研究的層面，很難應用到實際的軟體開發中。比如，我們把今天這篇包含 4000 多個漢字的文章，用 MD5 計算哈希值，用不了 1ms 的時間。
雜湊演算法的應用非常非常多，我選了最常見的七個，分别是安全加密、唯一辨別、資料校驗、散列函數、負載均衡、資料分片、分布式存儲。
這節我們先來看前四個應用。
應用一：安全加密
說到雜湊演算法的應用，最先想到的應該就是安全加密。最常用于加密的雜湊演算法是MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和SHA（Secure Hash Algorithm，安全雜湊演算法）。
除了這兩個之外，當然還有很多其他加密算法，比如DES（Data Encryption Standard，資料加密标準）、AES（Advanced Encryption Standard，進階加密标準）。
前面我講到的雜湊演算法四點要求，對用于加密的雜湊演算法來說，有兩點格外重要。第一點是很難根據哈希值反向推導出原始資料，第二點是散列沖突的機率要很小。
第一點很好了解，加密的目的就是防止原始資料洩露，是以很難通過哈希值反向推導原始資料，這是一個最基本的要求。是以我着重講一下第二點。實際上，不管是什麼雜湊演算法，我們隻能盡量減少碰撞沖突的機率，理論上是沒辦法做到完全不沖突的。為什麼這麼說呢？
這裡就基于組合數學中一個非常基礎的理論，鴿巢原理（也叫抽屜原理）。這個原理本身很簡單，它是說，如果有 10 個鴿巢，有 11 隻鴿子，那肯定有 1 個鴿巢中的鴿子數量多于 1 個，換句話說就是，肯定有 2 隻鴿子在 1 個鴿巢内。
有了鴿巢原理的鋪墊之後，我們再來看，為什麼雜湊演算法無法做到零沖突？
我們知道，雜湊演算法産生的哈希值的長度是固定且有限的。比如前面舉的 MD5 的例子，哈希值是固定的 128 位二進制串，能表示的資料是有限的，最多能表示 2^128 個資料，而我們要哈希的資料是無窮的。基于鴿巢原理，如果我們對 2^128+1 個資料求哈希值，就必然會存在哈希值相同的情況。這裡你應該能想到，一般情況下，哈希值越長的雜湊演算法，散列沖突的機率越低。
（1）2^128=340282366920938463463374607431768211456
為了讓你能有個更加直覺的感受，我找了兩段字元串放在這裡。這兩段字元串經過 MD5 雜湊演算法加密之後，産生的哈希值是相同的。
不過，即便雜湊演算法存在散列沖突的情況，但是因為哈希值的範圍很大，沖突的機率極低，是以相對來說還是很難破解的。像 MD5，有 2^128 個不同的哈希值，這個資料已經是一個天文數字了，是以散列沖突的機率要小于 1/2^128。
如果我們拿到一個 MD5 哈希值，希望通過毫無規律的窮舉的方法，找到跟這個 MD5 值相同的另一個資料，那耗費的時間應該是個天文數字。是以，即便雜湊演算法存在沖突，但是在有限的時間和資源下，雜湊演算法還是被很難破解的。
除此之外，沒有絕對安全的加密。越複雜、越難破解的加密算法，需要的計算時間也越長。比如 SHA-256 比 SHA-1 要更複雜、更安全，相應的計算時間就會比較長。密碼學界也一直緻力于找到一種快速并且很難被破解的雜湊演算法。我們在實際的開發過程中，也需要權衡破解難度和計算時間，來決定究竟使用哪種加密算法。
應用二：唯一辨別
我先來舉一個例子。如果要在海量的圖庫中，搜尋一張圖是否存在，我們不能單純地用圖檔的元資訊（比如圖檔名稱）來比對，因為有可能存在名稱相同但圖檔内容不同，或者名稱不同圖檔内容相同的情況。那我們該如何搜尋呢？
我們知道，任何檔案在計算中都可以表示成二進制碼串，是以，比較笨的辦法就是，拿要查找的圖檔的二進制碼串與圖庫中所有圖檔的二進制碼串一一比對。如果相同，則說明圖檔在圖庫中存在。但是，每個圖檔小則幾十 KB、大則幾 MB，轉化成二進制是一個非常長的串，比對起來非常耗時。有沒有比較快的方法呢？
我們可以給每一個圖檔取一個唯一辨別，或者說資訊摘要。比如，我們可以從圖檔的二進制碼串開頭取 100 個位元組，從中間取 100 個位元組，從最後再取 100 個位元組，然後将這 300 個位元組放到一塊，通過雜湊演算法（比如 MD5），得到一個哈希字元串，用它作為圖檔的唯一辨別。通過這個唯一辨別來判定圖檔是否在圖庫中，這樣就可以減少很多工作量。
如果還想繼續提高效率，我們可以把每個圖檔的唯一辨別，和相應的圖檔檔案在圖庫中的路徑資訊，都存儲在散清單中。當要檢視某個圖檔是不是在圖庫中的時候，我們先通過雜湊演算法對這個圖檔取唯一辨別，然後在散清單中查找是否存在這個唯一辨別。
如果不存在，那就說明這個圖檔不在圖庫中；如果存在，我們再通過散清單中存儲的檔案路徑，擷取到這個已經存在的圖檔，跟現在要插入的圖檔做全量的比對，看是否完全一樣。如果一樣，就說明已經存在；如果不一樣，說明兩張圖檔盡管唯一辨別相同，但是并不是相同的圖檔。
應用三：資料校驗
電驢這樣的 BT 下載下傳軟體你肯定用過吧？我們知道，BT 下載下傳的原理是基于 P2P 協定的。我們從多個機器上并行下載下傳一個 2GB 的電影，這個電影檔案可能會被分割成很多檔案塊（比如可以分成 100 塊，每塊大約 20MB）。等所有的檔案塊都下載下傳完成之後，再組裝成一個完整的電影檔案就行了。
我們知道，網絡傳輸是不安全的，下載下傳的檔案塊有可能是被主控端器惡意修改過的，又或者下載下傳過程中出現了錯誤，是以下載下傳的檔案塊可能不是完整的。如果我們沒有能力檢測這種惡意修改或者檔案下載下傳出錯，就會導緻最終合并後的電影無法觀看，甚至導緻電腦中毒。現在的問題是，如何來校驗檔案塊的安全、正确、完整呢？
具體的 BT 協定很複雜，校驗方法也有很多，我來說其中的一種思路。
我們通過雜湊演算法，對 100 個檔案塊分别取哈希值，并且儲存在種子檔案中。我們在前面講過，雜湊演算法有一個特點，對資料很敏感。隻要檔案塊的内容有一丁點兒的改變，最後計算出的哈希值就會完全不同。是以，當檔案塊下載下傳完成之後，我們可以通過相同的雜湊演算法，對下載下傳好的檔案塊逐一求哈希值，然後跟種子檔案中儲存的哈希值比對。如果不同，說明這個檔案塊不完整或者被篡改了，需要再重新從其他主控端器上下載下傳這個檔案塊。
應用四：散列函數
前面講了很多雜湊演算法的應用，實際上，散列函數也是雜湊演算法的一種應用。
散列函數是設計一個散清單的關鍵。它直接決定了散列沖突的機率和散清單的性能。不過，相對雜湊演算法的其他應用，散列函數對于雜湊演算法沖突的要求要低很多。即便出現個别散列沖突，隻要不是過于嚴重，我們都可以通過開放尋址法或者連結清單法解決。
不僅如此，散列函數對于雜湊演算法計算得到的值，是否能反向解密也并不關心。散列函數中用到的雜湊演算法，更加關注散列後的值是否能平均分布，也就是，一組資料是否能均勻地散列在各個槽中。除此之外，散列函數執行的快慢，也會影響散清單的性能，是以，散列函數用的雜湊演算法一般都比較簡單，比較追求效率。
解答開篇：
好了，有了前面的基礎，現在你有沒有發現開篇的問題其實很好解決？
我們可以通過雜湊演算法，對使用者密碼進行加密之後再存儲，不過最好選擇相對安全的加密算法，比如 SHA 等（因為 MD5 已經号稱被破解了）。不過僅僅這樣加密之後存儲就萬事大吉了嗎？
字典攻擊你聽說過嗎？如果使用者資訊被“脫庫”，黑客雖然拿到是加密之後的密文，但可以通過“猜”的方式來破解密碼，這是因為，有些使用者的密碼太簡單。比如很多人習慣用 00000、123456 這樣的簡單數字組合做密碼，很容易就被猜中。
那我們就需要維護一個常用密碼的字典表，把字典中的每個密碼用雜湊演算法計算哈希值，然後拿哈希值跟脫庫後的密文比對。如果相同，基本上就可以認為，這個加密之後的密碼對應的明文就是字典中的這個密碼。（注意，這裡說是的是“基本上可以認為”，因為根據我們前面的學習，雜湊演算法存在散列沖突，也有可能出現，盡管密文一樣，但是明文并不一樣的情況。）
針對字典攻擊，我們可以引入一個鹽（salt），跟使用者的密碼組合在一起，增加密碼的複雜度。我們拿組合之後的字元串來做雜湊演算法加密，将它存儲到資料庫中，進一步增加破解的難度。不過我這裡想多說一句，我認為安全和攻擊是一種博弈關系，不存在絕對的安全。所有的安全措施，隻是增加攻擊的成本而已。
内容小結：
今天的内容比較偏實戰，我講到了雜湊演算法的四個應用場景。我帶你來回顧一下。
第一個應用是唯一辨別，雜湊演算法可以對大資料做資訊摘要，通過一個較短的二進制編碼來表示很大的資料。
第二個應用是用于校驗資料的完整性和正确性。
第三個應用是安全加密，我們講到任何雜湊演算法都會出現散列沖突，但是這個沖突機率非常小。越是複雜雜湊演算法越難破解，但同樣計算時間也就越長。是以，選擇雜湊演算法的時候，要權衡安全性和計算時間來決定用哪種雜湊演算法。
第四個應用是散列函數，這個我們前面講散清單的時候已經詳細地講過，它對雜湊演算法的要求非常特别，更加看重的是散列的平均性和雜湊演算法的執行效率。