hash function 觀念和實務

tags: sysprog2017

hash function 是什麼？

一種從任何一種資料中建立小的數字「指紋」的方法。雜湊函式 把訊息或資料 (key) 壓縮成摘要，使得資料量變小，將資料的格式固定下來。該函式將資料打亂混合，重新建立一個叫做 雜湊值（hash values，hash codes，hash sums，或hashes） 的指紋。這個雜湊值就當作是陣列的索引，資料就儲存在這個索引的位置中。雜湊值通常用一個短的隨機字母和數字組成的字串來代表。

hash function 性質

1. 運算速度快
2. 不可逆性： 無法從雜湊值推回原本的資料是什麼
3. 如果兩個雜湊值是 不相同 的（根據同一函式），那麼這兩個雜湊值的原始輸入也是 不相同 的
4. 如果兩個雜湊值是 相同 的（根據同一函式），那麼這兩個雜湊值的原始輸入 不一定 是相同的 (雜湊碰撞)

• 衝突 (collision)
  也就是 第 2 種情況 發生時就稱為「雜湊衝突」。好的雜湊函式在輸入域中很少出現雜湊衝突。在雜湊表和資料處理中，不抑制衝突來區別資料，會使得資料庫記錄更難找到。

• hash distribution
  好的 hash function 所產生的 hash 值應盡可能均勻分佈
  hash distribution 系列實驗
  

hash function 應用

由於雜湊函式的應用的多樣性，它們經常是專為某一應用而設計的。

加密

密碼雜湊函式（Cryptographic hash function），又譯為加密雜湊函式、密碼雜湊函式、加密雜湊函式，是雜湊函式的一種。它被認為是一種單向函式，也就是說極其難以由雜湊函式輸出的結果，回推輸入的資料是什麼。這種雜湊函式的輸入資料，通常被稱為訊息（message），而它的輸出結果，經常被稱為訊息摘要（message digest）或摘要（digest）。
許多重要的應用，都使用了密碼雜湊函式來實作，例如數位簽章，訊息鑑別碼。

Hash Table

雜湊表是雜湊函式的一個主要應用，使用雜湊表 能夠快速的按照關鍵字 (雜湊值)。

雜湊表雜湊函式的幾乎不可能/不切實際的理想是把每個關鍵字對映到唯一的索引上（也就是完全零碰撞），因為這樣能夠保證直接存取表中的每一個資料。

一個好的雜湊函式（包括大多數加密雜湊函式）具有 均勻 的真正隨機輸出。同樣重要的是，隨機雜湊函式不太會出現非常高的衝突率。但是，少量的可以估計的衝突在實際狀況下是不可避免的（參考生日悖論或鴿籠原理）。

可以用 陣列 、 tree 或者是 linked list 建表。使用 linked list 遇到碰撞時就接在同一個索引後面即可，如下圖。

效能不佳的雜湊函式表意味著尋找操作會退化為費時的線性搜尋。

• hash distribution
  The hash values should be "spread randomly across their domain without an apparent pattern"

  • 影響 hash distribution 的因子
    • 選用的 hash function
    • table size
      • 如採取 mod 運算，則 table size 選擇質數分佈較均勻

• Best Collection of String Hash Function Comparison 提供很多種 string keys 的 hash function 的比較

  • BKDR hash 詳盡解說

參考及引用資料

• 維基百科
• StackOverflow – What does “distribution of the hash function” mean?
• hashing
• 密碼雜湊函式