# Hash Function

## 定義

雜湊技術是在記錄的儲存位置和其鍵值之間，建立一個確定的對應關係f，讓每個鍵值key對應一個儲存位置f(key)

fomula -> address = f(key)

### 雜湊搜尋步驟

1. 儲存時，透過雜湊函數來計算紀錄的雜湊位置，並按此雜湊位置儲存該紀錄。

2. 搜尋紀錄時，透過同樣的雜湊函數來計算紀錄的雜湊位置，然後按此雜湊位置訪問該紀錄。

### 雜湊適合的問題類型

* 搜尋與特定值相等的紀錄
* 不適合範圍搜尋
* 不適合多鍵值搜尋

### 碰撞

key~1~ != key~2~，f(key~1~) == f(key~2~)

發生這情況時key~1~ and key~2~ 稱為同義詞(Synonym)

### 雜湊函數構造方法

### 原則
* 計算簡單

:::info
雜湊函數的計算時間不應該超過其他搜尋技術與鍵值的比對時間。
:::
* 雜湊位置分布均勻

### 方法

* 直接定址法
> f(key) = a * key + b(a, b皆為常數)
> 適合搜尋資料表較小且連續的情況。
* 數字分析法
> 抽取數字組合某一部份進行反轉、左環位移、右環位移、或前兩數與後兩數疊加等方法。
> 適合處理鍵值位元數較大的情況。
* 平方取中法
> 將數值平方後取中間三位數當作鍵值
> 適合不知道鍵值的分佈，且位數又不大的情況。
* 摺疊法
> 9876543210 -> 987 + 654 + 321 + 0 = 1962 取最後三位 962 也可 987 and 321 反轉後相加 789 + 654 + 123 + 0 = 1566 取最後三位566來做鍵值。
> 適合不需事先知道鍵值分佈，鍵值位數較多的情況。
* 除法雜湊
> f(key) = key mod p (p <= m)(m 是 table length ， 最好是質數，或不包含小於20質因子的合數)
> p 選擇是關鍵為影響碰撞機率

* 隨機數法
> f(key)=random(key)，這裡的random是隨機函數。當鍵值長度不相等時，這個方法最合適

#### 選擇上述方法的思考方向

* 計算雜湊位置所需的時間
* 鍵值的長度
* 雜湊表的大小
* 鍵值的分佈情況
* 紀錄搜尋的頻率

### 處理碰撞的方法

* 開放位址法 （線性探測法）
1. 一次探測法
> f~i~(key) = ( f(key) + d~i~ ) MOD m (d~i~=1,2,3,4,5,...,m-1)
> 當發生碰撞，就去尋找下一個空的雜湊位置，只要雜湊表夠大，總能找到空的雜湊位置，並存入紀錄

2. 二次探測法
> f~i~(key) = ( f(key) + d~i~ ) MOD m (d~i~=1^2^,-1^2^,2^2^,-2^2^...,q^2^, -q^2^, q<=m/2)

3. 隨機探測法
> f~i~(key) = ( f(key) + d~i~ ) MOD m (d~i~是一個隨機數列)

* 重雜湊函數法
> f~i~(key) = RH~i~(key)(i=1,2,..,k)
> RH就是所有前面的方法都用上找出空的位置

* 鏈結法
> 在同一個位置透過Linked將其連接下去
> 搜尋時因走訪鏈結串列會帶來效能損耗

* 公共溢位區域法
> 將碰撞的鍵值建立一個公共的溢位區域來存放
> 搜尋時先從函數找基本表，如果在基本表沒找到就去溢位表循序搜尋

### 經典方法

* BKDR Hash

$forumla = (\displaystyle\sum_{n}a [n] s^n) \ mod \ 2^{31}$

version-1
unsigned int BKDRHash(char* str, unsigned int len)
{
   unsigned int seed = 131; /* 31 131 1313 13131 131313 etc.. */
   unsigned int hash = 0;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash = (hash * seed) + (*str);
   }

   return hash;
}

---------------------------------------

version-2
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131;
    unsigned int hash = 0;
    while (*str) {
        hash = hash * seed + (*str++);
    }
	
    return (hash & 0x7FFFFFFF);
}

---------------------------------------

version-3
unsigned int BKDRHash(char lastName[])
{
    unsigned int seed = 131;
    unsigned int hash = 0;
    int i = 0;
    while (i < strlen(lastName)) {
        hash = hash * seed + lastName[i];
        i++;
    }
    return (hash & 0x7FFFFFFF) % TABLE_SIZE;
}