# Hash Tables 雜湊表

### Dictionary

> 一種ADT，每一個元素都有Key，可以依照Key找到對應資料。

* Operations：
* `INSERT(T,x)` 插入元素
* `DELETE(T,x)` 刪除元素
* `SEARCH(T,x)` 搜尋元素
* Example：
* 編譯器中的symbol table

#
### Hash Tables
> Hash Tables是實作Dictionary的資料結構

* Serach Time
* `worst case` Θ(n)
* `expected time` O(1)

>使用一個Array來實作，Array index由Key計算而來

#
### Direct-Address Tables

> Key來自於U = {0,1,2,...,m-1}
>m不會太大，不會有兩個相同key的元素
>表示成Array T[0,1,...,m-1]
>solt k直接對應key = k

* 沒有hash function
* 沒有collision
* 所有操作都是O(1)
* Operations：
* `Direct-Address-Search(T,k)`
return T[K]

* `Direct-Address-Insert(T,k)`
T[ key[x] ] <- x

* `Direct-Address-Delete(T,k)`
T[ key[x] ] <- NIL


#### 問題
* key universe太大 -> 記憶體不實際
* 浪費空間，實際使用的Key可能很少

#### Hash Table解決方法
* 空間需求降為Θ(|K|)
* 平均搜尋時間 O(1)

#
### Hash Tables


* `Hash function` *h*(k)
> 把key映射成Array index
* `Load factor(負載因子)` *a = n/m*
> 平均每個slot裡有多少個元素
* `Collision(碰撞)`
> 無法避免，兩種處理方式是重點：
* Chaining (鏈表法)
* Open Addressing (開放地址法)

#
### Chaining 鏈表法

* 同一個slot的元素使用`linked list`存
* slot存的是list的`head pointer`
* load factor 可以 >= 1
* 如果slot沒有元素則放`NULL`
* Operations：
* `Chaining-Hash-Insert(T,x)`
插入在鏈表的頭部 T[ *h*(key[x]) ]

* `Chaining-Hash-Search(T,x)`
在list中線性查找x

* `Chaining-Hash-Delete(T,x)`
從list中移除x


#
### Open Addressing 開放地址法

* 所有的元素都放在table中
* 每個slot只有一個key或NULL
* load factor <= 1
* 插入時：
* 不斷probe(探測)直到找到空的slot
* 刪除困難：
* 不能接設為`NIL`
* 使用特殊標記`Deleted`
#### Example：
*h*(3) = 3 -> T[3] = 3 `放入`
*h*(13) = 3 -> T[3] 已經有了東西了，probe -> T[4] (空的) = 13 `放入`

要搜尋 **13** `bool Open-Addressing-Hash-Search(k,13)` -> T[3]=3
不是**13** 就probe(探測) -> T[4] = 13 `找到` return `True`

如果刪除**3**直接設為`NIL`，要搜尋**13**就會有問題
`bool Open-Addressing-Hash-Search(k,13)` -> T[3] = `NIL`
看到NIL代表不用繼續probe -> return `False`
所以刪除不能直接把值改成`NIL`，要放入特殊標記`Delete`讓尋找時能繼續probe

插入同理`Open-Addressing-Hash-Insert(k,23)` -> T[3] = `Delete`
看到是`Delete`就可以直接放入。

### Linear Probing 線性探測

> 給一個雜湊函數 *h'* 探測序列從 *h*(k) 開使 也就是Array T[ *h*(k) ]的位置
> 接著依序往後一格一格檢查整個表，當走到slot m-1之後，繞回slot 0的位置繼續
> 缺點是只要一段連續被填滿新元素容易碰撞，效能會急遽下降。

### Quadratic Probing 二次探測

> 跟Linear Probing一樣，給定一個雜湊函數後從*h*(k)開始，
> 但是不是一格格往後探測，是依照二次函數跳躍，避免群聚

#### Example：

輔助的hash function：*h'*(k) = k%11
二次探測的 function：*h*(k,i) = (*h'*(k)+i^2)%11
依序插入11, 33, 44的流程如下：
* *h'*(11) = 11%11 = 0 -> i=0 `(0+0^2)%11` = 0 -> T[0]是空的 -> `放入`
* *h'*(33) = 33%11 = 0 -> i=0 `(0+0^2)%11` = 0 -> T[0] = 11 -> `Quadratic Probing`
i=1 `(0+1^2)%11` = 1 -> T[1]是空的 -> `放入`
* *h'*(44) = 44%11 = 0 -> i=0 `(0+0^2)%11` = 0 -> T[0] = 11 -> `Quadratic Probing`
i=1 `(0+1^2)%11` = 1 -> T[1] = 33 -> `Quadratic Probing`
i=2 `(0+2^2)%11` = 4 -> T[4]是空的 -> `放入`

### Double Hashing 雙重雜湊

> 使用兩個輔助雜湊函數來決定探測的路線
> 每個不同的Key幾乎不會走相同的路線
> 公式：`h(k,i) = [h1(k)+i．h2(k)]%m`
> **i** = 0, 1, 2, ..., m-1 ; **m** = table size ; *h2*(k) 與 **m** 互質

#### Eaxmple：

> 以圖片中舉例，將 `79` `69` `72` `50` 依序插入後，我們要將 `98` 插入時該怎麼做？
> *h1*(98) = `98 % 13` = `7` , *h2*(98) = `1+(98 % 11)` = `11`
> *h*(98,i) = `(7+i．11) % 13`
> **i** = `0` , *h*(98,0) = `7` -> T[7] = `72` -> `Collision`
> **i** = `1` , *h*(98,1) = `5` -> T[5] = `NIL` -> `存入`

> `14` 插入的過程：
> *h*(14,0) = `1` -> T[1] = `79` -> `Collision`
> *h*(14,1) = `5` -> T[5] = `98` -> `Collision`
> *h*(14,2) = `9` -> T[9] = `NIL` -> `存入`
#
### Good Hash Functions

> 一個好的雜湊函數應該要讓每一個Key有相同的機率被雜湊到任意一個 slot
> 並且不受到其他key雜湊到哪裡的影響，彼此獨立達到均勻隨機分佈
> 理想上如此但實際上不可能完全做到，我們通常不知道Key是依照什麼機率分布產生的
> Key之間可能不是彼此獨立的

#
### Keys as Natural Numbers

> 將Key視為自然數，當Key不是數字的時候，必須要將它轉換成自然數
#### Example：
假設Key是字串，就要把字串解釋成某種底數表示法的整數
以字串 `pt` 為例子，ASCII `p` , `t` 分別是 `112` , `116`
那就將 `pt` 視為 (112,116) 將它轉換成128進位(ASCII有128個basic values)
轉換後 `pt` -> `112 * 128^1 + 116` = `14452`
就可以將 `14452` 視為代表 `pt` 自然數的Key
#
### Hash Functions 雜湊函數

* Division method **除法法**
$$ h(k) = k\ \% \ m $$
* 一個不太接近2的整數次方的質數，是m的良好選擇
像是 m = `23` , k = `91` -> *h*(k) = `22`

* Multiplication method **乘法法**
$$h(k) = \lfloor \ m (\ kA \ \%\ 1) \rfloor$$
* m的選擇不是那麼關鍵，比 `除法法` **慢**
* 容易實作
#### Example：

* 不碰位元
`A` 是一個介於 0~1之間的小數，`kA % 1` 就是求 `key．A` 後的小數部分
`m` 再乘上求出的小數部分後取 `地板函數`
以 `m = 16` , `A = 0.618` , `k = 123` 為例
`kA = 123．0.168 = 76.014` , `kA % 1 = 0.014` , `m．kA取地板函數 = 0`
$h(123) = \lfloor 16 \times (76.014\ \%\ 1) \rfloor = \lfloor 0.224 \rfloor = 0$
Array index = `0`

* 位元處理