台灣叫雜湊，中國那裡還直接翻成「哈希」。中文是毫無意義的翻譯，故下面我還是盡量用 Hash。Hash 的定義為：

每一次都可將輸入的數值 x 轉成一個 0..n 中的一個數字，而且(盡量)無碰撞

是有一點抽象，希望透過上篇文章雜湊表 Hash Table可以知道，原來 Hash 就是用來把 Dictionary 的 Key 轉成背後 Array 的 Index 的機制，所以我們不用一直被限制只能用 0 開始的整數，而可以隨心所欲加入 key-value 到 table 中。Hash 其實除了 Hash Table, 還有下面幾種應用：

• 檢查資料完整性
• 比較 2 個資料是否相同
• 驗證訊息來源(類似數位簽名)
• 區塊鏈
• 等等...

檢查資料完整性

因為相同的資料經過 Hash 後，會產生一樣的數值。在不考慮碰撞的情形下，若是不同的資料，產生出的 Hash 值一定不同。故我們可以利用此一特點，看檢查收到的檔案是否完整。可以計算金庸小說的 Hash 值後，然後下載小說後，比較下載的檔案的 Hash 值是否與網頁上顯示的一致。

比較 2 個資料是否相同

跟上方是一樣的概念，只是除了一個字元一個字元去比較 2 個檔案的內容，直接比較 Hash 值即可。

數位簽名

我舉個很簡易的例子：我在pdf 上簽了個名，傳給對方，對方哪知道那個簽名是不是有人截圖 copy 之後再貼上去的？附上一串 Hash 值，若駭客不知道我的 Hash 方程式，他們是無法產生出相同的 Hash 值的，對方即能驗證。(這個定義跟很嚴謹的 digital signature，不太一樣，但只是個例子)

區塊鏈

最近快退流行的區塊鏈也是利用了 Hash，每筆交易都會產出獨特的 Hash 值

怎麼做出 Hash 方程式？

大家可能好奇，到底哪裡有那麼神奇的數學方程式..其實，制作出 Hash Function 可以很簡單，我們舉一個極簡易的例子：

def a_simple_hash(input)
  case input[0]
  when 'a' then 0
  when 'b' then 1
  when 'c' then 2
  #...
  when 'z' then 25
  end
end

這樣不就作了一個可以依據輸入字串的首字元將輸入轉換成 0 到 25的 Hash Function 了？但為什麼通常不會使用這樣的 Hash Function 呢？假使我們真的有一個雜湊表 Hash Table使用了這個 Hash Function：

h = {
  Apple: '$10',
  Cat: '$20',
  Kate: '$30'
}

其背後的對應為：

這個 Hashing Function 發生碰撞的機率實在太高了！同樣字首的情形太多了。我們如果再加入

{
  Apron: '$40',
  Kitty: '$50'
}

馬上就有碰撞了

如何與其它人說明你的 Hashing Function 比較厲害？其中一個因素就是看它發生碰撞的機率是不是夠小。優良的 Hashing Function 發生碰撞的機率比你這個宅宅交到正妹女友的機率還低。

好，怎麼做出優秀的 Hash 方程式？

的確，要想出優秀的 Hash 方程式並不是一件容易的事。實務上我們一定是直接採用各數學家、電腦科學家所提出來的 Hash 方程式。我沒辦法詳細說明那些需要 PHD 才懂的數學，但是大致上是以下四種方式，再用不同的方式去做組合：

• 平方法 Middle of the square
• 餘數計算 Dividing
• 折壘 Folding
• 數字分析 Digits analysis

平方法 Middle of the square

將輸入的數值轉成 0 與 1 後，得出它的平方值，再取中間 X bits 當結果

餘數計算 Dividing

選擇一個數字 M 然後直接算輸入數值的餘數 (mod M)當結果，如果 M 夠大且又是質數的話可有效避免碰撞。

折壘 Folding

將輸入的數值轉成 0 與 1 後，區分多塊，再相加當結果

數字分析 Digits analysis

如果可以知道全部可能的輸入的數值的話，直接做出 1 對 1 的對應。

最後與大家分享一下，因為今年我也搬到加拿大生活，意外發現薯餅叫做 Hash Brown。滿有意思的，馬鈴薯 Hash 後變薯餅，請自由想像了。

References

雜湊表 Hash Table
https://zh.wikipedia.org/zh-tw/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8