Table of Contents
前言
昨天介紹Distribution Sort的時候提到了Map/Dictionary，相信應該很多人對這個物件已經不陌生了，而今天主要是圍繞在Hash Table上面，說明當進行Hashing的時候如果遇到衝突，該怎麼解決？那就讓我們看下去吧～
Hash Table
Hash Table說穿了就是Key-Value Paired Array，，進行Insertion的時候，會依據Key來決定Value要儲存在哪一個位置(index)裡面，而因為Hash Table是Key-Value Paired，在進行Search的時候，永遠都是𝜪(1)的時間複雜度。
假設現在有一組資料，長度為n，要使用Hash Table紀錄這組資料，首先是要找出這組資料的規律，藉此取得屬於每一個值特有的Key，然後再放入Hash Table中，如下範例，當每個值除以10之後，其餘數分別是0, 1, 2,…,8，而利用這個餘數作為key值，如此一來每個值都有一個唯一的Key，並藉此放進Hash Table中。
- Dataset: { 10, 21, 32, 43, 54, 65, 76, 87, 98}
- Key = k(x) = x mod 10
- Keyset : { 0, 1, 2, 3, 4, 5, 6, 7, 8}
但上面這個情況是Hash Table的長度與資料長度相等，倘若現在Hash Table的長度比資料長度小，那絕對就會發生 『衝突』，因此問題來了：如果發生衝突了，該怎麼處理勒？
Separate Chaining Hashing
Separate Chaining Hashing就是針對Hash Table發生衝突時的解決方案之一，其特點為：
- 允許一個Key值的位置可以存放多個值。
- 每一個位置都指向(point)一個Linked List，藉此在當中存放多個值。
- 若某一個位置並無存放任何值，則此時pointer會被設定為
null。
範例如下：
從上範例可以看到，16和4兩個值除以12後餘數均為4，1和25除以12餘1，9和33除以12餘9，因此這些值爾後放進Hash Table時被分別放到4, 1, 9的位置下面。
Open Address Hashing
另一種處理衝突的方式是使用Open Address Hashing，這個方法一樣是規定每一個Element只能記錄一個值，但是當遇到衝突的時候，有兩種方式可以用來應對：
1. Linear Probing：
Linear Probing面對衝突的解決方式是針對當前位置去尋找下一個沒放值的Element，並將值存入，先看下面GIF試著了解這句話吧～
可以看到，當要新增10的時候，因為1的位置中已經有值了，因此去找下一個空的位置，才把10放進去；而新增25的時候，從index 7開始，一路找到index 5，才找到空的位置可以存25，這個就是Linear Probing的機制。
2. Double Hashing：
在使用Double Hashing前，基本上會準備兩個hashing function(F1, F2)用來計算，第一次使用F1來計算，當遇到衝突時，則合併兩個hashing function計算，取得新的Primer，依據這個Primer看看是否有衝突，沒有衝突，就把值存入；有衝突，再一次地計算，直到沒衝突為止：
- 第一次計算：
Primer = F1(x) - 如果第一點的Primer衝突，則：
Primer = F1(x) + F2(x) - 若第二點的Primer還是衝突，則：
Primer = F1(x) + 2·F2(x) - 若第三點的Primer再一次衝突，則：
Primer = F1(x) + 3·F2(x) - 依此類推，直到不再衝突。
小結
- Hash Table在Insertion的過程中，若遇到衝突，可以透過Separate Chaining Hashing和Open Address Hashing解決。
- Separate Chaining Hashing是在每一個Element透過Linked List紀錄多個值。
- Open Address Hashing又可以分為Linear Probing和Double Hashing兩種方式。
- Linear Probing是當遇到衝突時，去尋找下一個空的位置存入值。
- Double Hashing是透過兩個Hashing function來反覆計算Primer，直到沒有衝突為止。
預告
明天開始的一年三天，我們將會介紹Dynamic Programming這個類別的演算法。