學習筆記
學習書目：《算法圖解》- Aditya Bhargava

---

安全散列算法(SHA)

在學SHA算法之前，我們先回顧一下前幾個Blog所學的散列函數。

散列函數是這樣的一個函數，即無論我們給它什么樣的數據，它都還我們一個數字。如果用專業術語來表達的話，我們可以說，散列函數“將輸入映射到數字”。

有一種散列函數是安全散列算法(secure hash algorithm，SHA)函數。當我們給定一個字符串時，SHA會返回其散列值:

對于每個不同的字符串，SHA生成的散列值都不同：

比較文件是否相同

我們可使用SHA來判斷兩個文件是否相同，這在比較超大型文件時很有用。假設我有一個4 GB的文件，并要檢查朋友是否也有這個大型文件。為此，我不用通過電子郵件將這個大型文件發送給朋友，而可計算它們的SHA散列值，再對結果進行比較。

檢查密碼

SHA還能讓我們在不知道原始字符串的情況下對其進行比較。假設Gmail遭到攻擊，攻擊者竊取了所有的密碼，我們的密碼沒有因此暴露，因為Google存儲的并非密碼，而是密碼的SHA散列值。當我們輸入密碼時，Google計算其散列值，并將結果同其數據庫中的散列值進行比較。SHA被廣泛用于計算密碼的散列值。這種散列算法是單向的。我們可根據字符串計算出散列值。 但無法根據散列值推斷出原始字符串。 這意味著計算攻擊者竊取了Gmail的SHA散列值，也無法據此推斷出原始密碼。

局部敏感的散列算法(Simhash)

SHA還有一個重要特征，那就是局部不敏感的。

假設我們有一個字符串，并計算了其散列值：

如果我們修改其中一個字符，再計算其散列值，結果將截然不同：

在針對密碼保護時，這種特性看起來很不錯，因為這會讓攻擊者無法通過比較散列值來破解密碼。但有的時候，我們希望結果相反，即希望散列函數是局部敏感的。在這種情況下，可使用局部敏感的散列算法(Simhash)。如果我們對字符串做細微的修改，Simhash生成的散列值也只存在細微的差別，這讓我們能夠通過比較散列值來判斷兩個字符串的相似程度。

比如：

• Google通過Simhash來判斷網頁是否已經收集。

• 老師使用Simhash判斷學生論文是否抄襲。

所以說，需要檢查兩項內容的相似程度時，Simhash很有用。

---

后記：這個系列應該完結了。其實還有動態規劃和KNN，但是動態規劃里面圖太多，感覺不太好用Blog表述，KNN我想以后放在其他系列里詳細闡述，所以就到此為止啦！

總結

以上是生活随笔為你收集整理的小白的算法初识课堂(part9)--SHA及Simhash算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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