LeetCode | 你不得不了解的雜湊演算法 ！

⒈哈希是什麼 ？

問大家一個問題 。如果手機上存儲了 1000 個聯系人 ，現在要你給小詹打個電話 ，跟他說 ，他老婆喊他回家吃飯 。你會怎麼做 ？

當然是按姓名搜尋呀 ！（假裝你有小詹電話号碼~）言歸正傳 ，那你能想到這和哈希表有異曲同工之妙嘛 ？

哈希表簡單說可以了解成一個映射關系 ，類似 python 文法中字典的鍵值對 。根據鍵（Key）而直接通路在記憶體存儲位置的資料結構。

将任意長度的二進制值串映射為固定長度的二進制值串 ，這個映射的規則就是雜湊演算法 。原始資料映射得到的二進制值串就是哈希值 。

回到通訊錄的例子 ，是不是可以類比 ? 電話号碼是原始資料 ，根據雜湊演算法（這就是你自定義的規則）存儲為通訊錄備注 。嚴格來講二者是有差別的 ，隻是為了便于了解 ，若舉例不當 ，杠精讀者輕噴 。

一個優秀的雜湊演算法主要有以下幾點特征 ：

 ●  單方向推導 ，不能從哈希值反向推導出原始資料 ，或者說很困難 。

 ●  對輸入敏感 ，原始資料的微小變化會導緻哈希值的大差異 。

 ●  散列沖突小 ，不同原始資料得到相同哈希值的機率小 。其實最好是避免 ，但是諸如 MD5 這種也難以徹底避免 ，是以隻說盡可能小 。

 ●  執行效率高 ，即使是較長的文本 ，也能快速計算出哈希值 。

⒉雜湊演算法有何用 ？

一般而言 ，算法或産品的使用往往取決于特征 。是以根據上文的特征不難想到一些應用如下 。

 ●  安全加密

因為優秀的雜湊演算法具有單方向推導和散列沖突小兩個特征 ，這就決定了用來進行安全加密具有很好的應用 。

相信你一定聽過 MD5（MD5 Message-Digest Algorithm ) 和 SHA（Secure Hash Algorithm）吧 ，這就是兩個常用于安全加密的雜湊演算法 。

 ●  資料結構

其實還有很多應用與安全加密類似 ，比如資料校驗之類的 ，都是利用單向性和沖突小特性 ，就不贅述了 。

其實雜湊演算法在資料結構中用于查找是一個非常不錯的方法 ，可以快速定位查找到想要查找的資料資訊 。這一用法在刷 LeetCode 題的時候遇到的非常多 ！

⒊雜湊演算法刷題

 ●  K數之和

Leetcode第一題就是兩數之和 ，後邊又有三數之和 、四數之和 ，其實 K 數之和原理類似 。

以兩數之和為例 ，除了簡單暴力的周遊方法 ，雜湊演算法能夠極大的提高解題效率 ！具體參照第一題推文的第二種解法 ：

LeetCode | No.001 兩數之和 LeetCode | No.015 三數之和

 ●  模式比對

模式比對問題比較經典 。最簡單的舉例 ：數字串「 1 2 1 2 」應該對應英文「 one two one two 」。

現在如果給定一個模式（數字串）和一個輸入（英文），要你寫代碼實作判斷是否模式比對 ，你該怎麼做呢 ？這一題來個有獎互動 ！

其實這就可以考慮使用雜湊演算法實作了 ，python 中的字典有個鍵值對 ，其實有些類似 ，這裡小詹給出思路 ，不分享代碼 。按照思路用 python 寫出可行代碼的同學歡迎在留言區回複 ，将在前 3 個親測有效的代碼中選取一個最優的送上實體書一本（下次送書活動預留一個名額）歡迎動腦 ，中獎機率三分之一

思路如下 ：

 ●  首先對輸入的英文串分割 ，可以用 input.split(' ') 方法 。

 ●  建立哈希表存儲資料 ，這裡友情提醒下可以建立多個喲 。

 ●  從給定模式逐一循環判斷 。單次判斷邏輯如下列出 。

 ●  首先判斷目前位置的模式（pattern）是否初次出現 ，如果不是第一次出現 ，則說明有一個哈希值與之相對應 ，判斷 input 對應位置是否與該哈希值一緻 ，如果不一緻則直接傳回 false ，肯定不比對 。

 ●  如果目前模式是第一次出現 ，先不急着直接加入哈希表 ，還需要判斷對應位置的 input 英文單詞是否是其他模式的哈希值 ，如果是說明之前已經和别的模式比對了 ，不能反複比對 ，傳回 false 。

 ●  如果目前位置的模式是第一次出現且對應的 input 也沒有和别的模式比對過 ，則二者作為一個鍵值對存入哈希表 。

 ●  如果直到循環結束沒有傳回 false 說明完全比對 ，傳回 true 。

原文釋出時間為：2018-11-29

本文來自雲栖社群合作夥伴“

小詹學Python

”，了解相關資訊可以關注“

”。