# 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 系列實驗](http://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed)

## 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](https://know99.com/technology/best-collection-of-string-hash-function-comparison/) 提供很多種 string keys 的 hash function 的比較
* [BKDR hash 詳盡解說](http://blog.csdn.net/wanglx_/article/details/40400693)

## 參考及引用資料
* [維基百科](https://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8#.E6.95.A3.E5.88.97.E8.A1.A8)
* [StackOverflow -- What does “distribution of the hash function” mean?](http://stackoverflow.com/questions/10039788/what-does-distribution-of-the-hash-function-mean)
* [hashing](http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/hashing.pdf)
* [密碼雜湊函式](https://zh.wikipedia.org/wiki/%E5%AF%86%E7%A2%BC%E9%9B%9C%E6%B9%8A%E5%87%BD%E6%95%B8)