還記得 2011 年 CSDN 的“脫庫”事件嗎？當時，CSDN 網站被黑客攻擊，超過 600 萬用戶的註冊郵箱和密碼明文被洩露，很多網友對 CSDN 明文保存用戶密碼行為產生了不滿。如果你是 CSDN 的一名工程師，你會如何存儲用戶密碼這麼重要的數據嗎？僅僅 MD5 加密一下存儲就夠了嗎？ 要想搞清楚這個問題，就要先弄明白哈希算法。
哈希算法歷史悠久，業界著名的哈希算法也有很多，比如 MD5、SHA 等。在我們平時的開發中，基本上都是拿現成的直接用。所以，我今天不會重點剖析哈希算法的原理，也不會教你如何設計一個哈希算法，而是從實戰的角度告訴你，在實際的開發中，我們該如何用哈希算法解決問題。
什麼是哈希算法？
我們前面幾節講到“散列表”“散列函數”，這裡又講到“哈希算法”，你是不是有點一頭霧水？實際上，不管是“散列”還是“哈希”，這都是中文翻譯的差別，英文其實就是“Hash”。所以，我們常聽到有人把“散列表”叫作“哈希表”“Hash 表”，把“哈希算法”叫作“Hash 算法”或者“散列算法”。那到底什麼是哈希算法呢？
哈希算法的定義和原理非常簡單，基本上一句話就可以概括了。將任意長度的二進制值串映射為固定長度的二進制值串，這個映射的規則就是哈希算法，而通過原始數據映射之後得到的二進制值串就是哈希值。但是，要想設計一個優秀的哈希算法並不容易，根據我的經驗，我總結了需要滿足的幾點要求：
- 從哈希值不能反向推導出原始數據（所以哈希算法也叫單向哈希算法）；
- 對輸入數據非常敏感，哪怕原始數據只修改了一個 Bit，最後得到的哈希值也大不相同；
- 散列衝突的概率要很小，對於不同的原始數據，哈希值相同的概率非常小；
- 哈希算法的執行效率要儘量高效，針對較長的文本，也能快速地計算出哈希值。
這些定義和要求都比較理論，可能還是不好理解，我拿 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），跟用戶的密碼組合在一起，增加密碼的複雜度。我們拿組合之後的字符串來做哈希算法加密，將它存儲到數據庫中，進一步增加破解的難度。不過我這裡想多說一句，我認為安全和攻擊是一種博弈關係，不存在絕對的安全。所有的安全措施，只是增加攻擊的成本而已。
內容小結
今天的內容比較偏實戰，我講到了哈希算法的四個應用場景。我帶你來回顧一下。
第一個應用是唯一標識，哈希算法可以對大數據做信息摘要，通過一個較短的二進制編碼來表示很大的數據。
第二個應用是用於校驗數據的完整性和正確性。
第三個應用是安全加密，我們講到任何哈希算法都會出現散列衝突，但是這個衝突概率非常小。越是複雜哈希算法越難破解，但同樣計算時間也就越長。所以，選擇哈希算法的時候，要權衡安全性和計算時間來決定用哪種哈希算法。
第四個應用是散列函數，這個我們前面講散列表的時候已經詳細地講過，它對哈希算法的要求非常特別，更加看重的是散列的平均性和哈希算法的執行效率。
閱讀更多 xiuxiuing 的文章
