今天來點輕鬆的~我們來介紹hash table

雜湊表是一種關聯性陣列(associative array)允許使用者用key來索引資料儲存位子hash value，或者說它是一個abstract data type可以map key to value。這個mapping的關係是，key 透過一個雜湊式(hash function)得到一個hash value。如果雜湊式夠好，hash values可以均勻的分散在雜湊表，沒有collision (一個key對一個hash value)，搜尋一個資料的時間複雜度為O(1)。相反的，如果雜湊式不好，有collision的狀況(多個key對上一個hash value)，最差的情況下搜尋一個資料的時間複雜度則變為O(n)。最有名的例子其實就是python的dictionary，其有內建的hash function讓我們可以透過key來尋找value，當然裡面也有內建解決collision的方法。

如果說是想自己製作hash function，當遇到collision時，可以用以下方法解決:
1. Direct Chaining: 用linked list的方式將colliding elements儲存。由於其用linked list儲存，用direct chaining的hash table不會有滿了(full)的狀況。但越多collision，搜尋時間複雜度就變為O(n) (因為是linked list，可以參閱前幾章)。
2. Open Addressing: 將colliding elements 儲存在其他空的位子。用probing的方式決定他們要存在哪個空的位子。而probing又分為: linear probing、quadratic probing、double hashing。linear probing: 將新的key產生的hash value(跟其他key重複了)重新assign到最近的下一個空位裡。quadratic probing:將index二次方後，若位子是空的assign直進去，若不是空的，再二次方，直到找到空的位子。Double hashing: probes間的距離由另一個hash function決定。
e.g. ABCD, EFGH, IJKLM 這三組key在經由hash function 後hash value 皆為2 (假使其餘位子 皆為空的)
Linear probing:
ABCD -> 2, EFGH -> 3, IJKLM -> 4
Quadratic probing:
ABCD-> 2, EFGH -> 4, IJKLM -> 8
Double Hashing:
Hash reassign = index+4(frequency-1)
ABCD -> 2, EFHG -> 2+4(1)=6, IJKLM -> 2+4(2)=8
當使用open addressing建的雜湊表滿了的時候，會再建一個比現在雜湊表大兩倍的雜湊表，並把所有現在的key再hashing一遍，時間複雜度為O(n)。總之，有好的hash function真的非常非常重要。
下表為各資料結構，搜尋、插入、刪除資料的時間複雜度比較。

參考資料:
The Complete Data Structures and Algorithms Course in Python (udemy) 有興趣的人可以自己上去看唷~