Hash Table：Intro(簡介)

先備知識與注意事項

在做資料處理時，常常需要「查詢資料」，譬如線上購物平台有會員登入時，首先確認輸入的帳號密碼是否在資料庫裡，如果是，便從資料庫裡找出此會員的資料，如購物記錄、暫存購物清單等等。

想到「查詢資料」，可能會想到能夠在時間複雜度為$O(\log{N})$完成查詢的平衡的Binary Search Tree(二元搜尋樹)，如圖一。

在圖一的BST中，要找到Key(17)的資料，需要比較$4=\lfloor{\log_{2}{15}\rfloor+1}$次，時間複雜度可以視為height(樹高)。

圖一：若為平衡的BST，查詢資料之時間複雜度為$O(\log{N})$。

但是若資料量非常龐大(例如社交平台的註冊會員資料庫)，即使是$O(\log{N})$也非常可觀。

如果能在時間複雜度為常數的$O(1)$完成查詢該有多好。

本篇文章便要介紹能夠在$O(1)$完成查詢的Hash Table(雜湊表)。

簡介：Dictionary(字典)

Dictionary是以「鍵值-資料對」(Key-Value pair)來描述資料的抽象資料形態(Abstract Data Type)。

舉例來說：

電話簿裡的Dictionary即是將「姓名」視為Key，「電話號碼」視為Value。
學校學籍系統的Dictionary將「學號」視為Key，「學生資料」(如姓名、修課記錄)視為Value。

所以，任何具有辨別功能、可以用在「查詢資料」的「符號」(像是姓名、學號、網址等等)都能夠視為Key。
而Value代表著較為廣義的「資料」，例如電話號碼、學籍資料、IP位置等等。

只要在系統輸入Key，便能找到相對應的Value，這就是Dictionary的基本概念。

圖二：。

一般Dictionary會支援三個操作：

新增資料(insert)
刪除資料(delete)
查詢資料(search)

以上三個操作：

若以平衡的BST(例如AVL樹、Red Black Tree)便能在$O(\log{N})$完成。
「理想情況」的Hash Table希望能夠以$O(1)$完成。

以Array實現的Direct Access Table

若要在$O(1)$對資料進行「新增」、「刪除」以及「查詢」，沒有比Array(矩陣)更適合的人選了：

若直接把Key當作Array的index，並將Value存放進Array，這樣的實作稱為Direct Access Table。

但是Direct Access Table有兩個重大缺陷：

Key一定要是「非負整數(non-negative integer)」，才能作為Array的index。
若Key的「範圍」非常大，可是Key的「數量」相對很少，那麼會非常浪費記憶體空間。
- 以圖三為例，因為Key的範圍從$2$到$47$，所以Array的大小(size)至少要「$48$」，因此$15$筆資料用了$48$單位的記憶體空間，也就浪費超過三分之二的記憶體空間。若Key的範圍更大，浪費的程度將非常可觀。

圖三：。

關於第一點「Key不是非負整數」的缺陷，可以先利用一個「一對一函數(one-to-one function)」將Key對應到非負整數，問題即可解決，稱為prehash。

例如，若Key是英文名字，那便利用「ASCII編碼」將字串轉換成非負整數。現要存放「T-MAC」與「KOBE」兩位球員的資料：

「T-MAC」$=84*10^4+45*10^3+77*10^2+65*10+67=893417$
「KOBE」$=75*10^3+79*10^2+66*10+69=83629$

以上的範例，至少需要一個大小為$893418$的Array，可是只有存放兩個英文名字，不划算。

Hash Table的核心概念就是要解決第二個缺陷：避免記憶體空間浪費。

Hash Table的概念

Hash Table希望能夠將存放資料的「Table」的大小(size)降到「真正會存放進Table的資料的數量」，也就是「有用到的Key的數量」：

若有用到的Key之數量為$n$，Table的大小為$m$，那麼目標就是$m=\Theta (n)$。

要達到這個目標，必須引入Hash Function，將Key對應到符合Table大小$m$的範圍內，$index=h(Key)$，即可成為Hash Table的index，如圖四。

圖四：Hash Table和Direct Access Table的差別在於Hash Function。

可惜事與願違，因為$|U|\gg m$，再加上Hash Function設計不易，所以很可能發生Collision。

很可能發生Collision

Collision就是兩筆資料存進同一個Table之slot的情形，這將會使得查詢資料失敗(例如：使用item1的Key，卻回傳item2的資料)。

若以Division Method實作Hash Function，定義$h(Key)=Key \bmod{m}$，Table大小為$m=6$，目前要處理的資料之Key有$67,26,50,33,16,71$，那麼各個Key將被對應到的index如下，同時參考圖五：

$h(67)=67 \bmod{6}=1$
$h(26)=26 \bmod{6}=2$
$h(50)=50 \bmod{6}=2$
$h(33)=33 \bmod{6}=3$
$h(16)=16 \bmod{6}=4$
$h(71)=71 \bmod{6}=5$

「item26」與「item50」經過Hash Function後，同時想要將資料存進Table[2]，這就是Collision。

圖五：。

Collision在「可能使用到的Key」之數量遠大於Table大小(亦即$|U|\gg m$)的情況下，無可避免。

解決的辦法有二：

Chaining：使用Linked list把「Hashing到同一個slot」的資料串起來。
Open Addressing：使用Probing Method來尋找Table中「空的slot」存放資料。

這兩個方法將分別在後續文章介紹。

Hash Function介紹

優秀的Hash Function($h()$)應具備以下特徵：

定義$h()$的定義域(domain)為整個Key的宇集合$U$，值域(range)應小於Table的大小$m$：

$$ h:U\rightarrow \{\,0,1,...,m-1\,\},\:where \:|U|\gg m $$
盡可能讓Key在經過Hash Function後，在值域(也就是Table的index)能夠平均分佈(uniform distributed)，如此才不會有「兩筆資料存進同一個Table空格(稱為slot)」的情況。

若把Table想像成「書桌」，slot想像成書桌的「抽屜」，那麼為了要能更快速找到物品，當然是希望「每一個抽屜只放一個物品」，如此一來，只要拿著Key，透過Hash Function找到對應的抽屜(Hash Function的功能是指出「第幾個」抽屜，也就是抽屜的index)，就能保證是該Key所要找的物品。
反之，如果同一個抽屜裡有兩個以上的物品時，便有可能找錯物品。

以下介紹兩種Hash Function的基本款：

Division Method：$m$有限制，但是比較快。
Multiplication Method：$m$沒有限制，但是比較慢。

Division Method

要把大範圍的$|U|$對應到較小範圍的$\{0,1,...,m-1\}$，最直覺的做法就是利用Modulus(mod)取餘數。
假設Table大小為$m$，定義Hash Function為：

$$ h(Key)=Key \bmod{m} $$

例如，選定Table大小為$m=8$，那麼以下的Key與Table之index將有對應關係如下：

$h(14)=14 \bmod{8}=6$
- 代表「編號$14$」的物品要放進「第$6$格」抽屜。
$h(23)=23 \bmod{8}=7$
- 代表「編號$23$」的物品要放進「第$7$格」抽屜。
$h(46)=46 \bmod{8}=6$
- 代表「編號$46$」的物品要放進「第$6$格」抽屜。
$h(50)=50 \bmod{8}=2$
- 代表「編號$50$」的物品要放進「第$2$格」抽屜。

優點

以Division Method實現Hash Function的優點就是非常快，只要做一次餘數(一次除法)運算即可。

缺點

較為理想的Table大小$m$是「距離$2^{p}$夠遠」的質數，像是$701$。

換句話說，Table大小$m$必須慎選。

例如，要儘量避開「2的指數($2^{p}$)」，否則就只有「最低位的p-bit」會影響Hash Function的結果。
轉換成二進位會更容易看出，以$m=8=2^{3}$為例，$h(Key)=Key \bmod{2^{3}}$的意思就是，只取「以二進位表示的Key的最低位的$3$個bit」來決定Key對應到的Table之index，見圖六。

圖六：。

這種情況下，若有大量變數以相同的命名規則，例如「a_count、b_count、c_count」，很有可能在prehash(在Direct Access Table提過的「T-MAC」與「KOBE」)將字串轉換成Key時，得到「低位bit」完全相同的key，因為以上三個變數的結尾都是_count，那麼Division Method就會把這三個變數都放進同一個slot，造成Collision。

Multiplication Method

由於在實際面對資料時，時常無法預先得知「Key的範圍」以及「在該範圍內Key的分佈情形」，在這個前提下，不需要避開特定$m$的Multiplication Method可能會比較優秀。

步驟如下：

圖七(a)：。

而且這個將「Key乘上$A$、取小數點部分、再乘上$m$、再取整數部分」的Hash Function能夠儘量把更多的Key的bit納入考慮，來得到$h(Key)$。

轉換成二進位會更容易看出來。
先把圖七(a)中的「$constant\:A=\frac{13}{32}$」轉換成二進位：

再把「$K$乘上$A$」以二進位表示，見圖七(b)：

圖七(b)：。

得到的$r_{0}=\frac{17}{32}$其實就是$KA$的小數部分(fractional part)，亦即$r_{0}=KA-\lfloor KA \rfloor$，也就等於圖七(a)中的「f」。

那麼，接下來對「$KA$的小數部分乘上$m=2^{3}$」，以二進位表示法解讀，就會是把「小數點往右移$3$位」：

最後一步：$h(K)=\lfloor m(KA-\lfloor KA \rfloor) \rfloor$，其實就是取$m\times r_{0}$的整數部分，結果與圖七(a)吻合。

到這裡，再看一次圖七(b)，可以發現，決定出$h(21)=4$的過程當中，以二進位表示的Key$=21$的「每一個部分的bit」都用上了，二進位的$4$是由二進位的$Key=21$之：

頭：$101$
中：$101$
尾：$01$

三者相加得到的，因為參與的「部位」變多了，那麼隨機性也就增加了，如此$h(Key)$便能得到較為隨機的結果。

圖七(b)：。

以上範例是將Key以$5$-bit表示，試想，若以$32$-bit表示，並且增加Key的範圍，那麼可以預期「參與並相加出最後$h(Key)$」的部分會更加「隨機」，也就能夠將不同Key「更隨機地」對應到不同的值(也就是不同的slot)，有效降低Collision的發生。

還有一個小議題是，如何找到「$constant\:A$」？
根據Knuth的說法，選擇黃金比例還不錯：

$$ A=\frac{\sqrt{5}-1}{2}\approx 0.6180339887... $$

至於程式的實作上，利用bit-shifting會更有效率，請參考：Geoff Kuenning：Hash Functions

最後，在Hashing的議題裡，還有兩位大魔王叫做Universal Hashing以及Perfect Hashing(有鑒於筆者可能一輩子都看不懂，所以這裡就放個連結)，據說可以產生最低限度的Collision，請參考：

以上是Hash Table之基本概念介紹。

接下來兩篇將介紹Chaining與Open Addressing解決Collision。

參考資料：

Hash Table系列文章

Hash Table：Intro(簡介)
Hash Table：Chaining
Hash Table：Open Addressing

回到目錄：

目錄：演算法與資料結構