[演算法] 雜湊表(Hash Table)

雜湊表是非常實用的資料結構之一，有三個主要的面向需要學習，分別是：實作(Implementation)、碰撞(Collision)、雜湊函數。

雜湊函數 

是一種輸入字串，然後輸出數字的函數。也就是「將字串對應至數字」。

例：

“Apple” → 雜湊函數 → 3

作用原理：

1、雜湊函數始終將一個特定的名稱對應於相同的數字，每次輸入 “Apple”，都會得到相同的數字(例如 3)。

2、雜湊函數將不同的字串對應至不同的索引值。例： “Apple” 對應至 3；”Milk” 對應至 4。

3、雜湊函數知道陣列的大小，而且只傳回有效的索引值。

透過雜湊函數與陣列的結合，可得到一個 雜湊表(Hash Table) 資料結構。雜湊表又稱為雜湊地圖(Hash Map)、字典(Dictionary)、關聯式陣列(Associative Array)。例：

book['apple'] = 0.65
book['milk'] = 1.43

使用案例：手機內建電話簿、網址對應至 IP、用在網頁快取(Cache)的應用(URL對應至網頁內容)。

碰撞

使用者必須瞭解雜湊表的效能，也就是碰撞。如果碰撞的問題過多，那將會導致雜湊表的效能變慢，所以應該儘可能避免，好的雜湊函數，會儘量避免碰撞的問題發生。

什麼是碰撞？先前提到，雜湊函數必定將不同的鍵對應至不同的陣列儲存槽。但事實上，還是有可能發生同一個鍵對應到相同的陣列儲存槽情況，例如：一個雜湊函數的定義，將字母為 A 開頭的，對應至第1個儲存槽，則 Apple 的價格會被放到第1個儲存槽，然後 Almond 的價格也會被放到第1個儲存槽，因為都是以 A 開頭，那 Apple 的價格就被 Almond 覆寫了，這就是碰撞。解決辦法是在此儲存槽啟用連結串列。如果項目不多，啟用連結串列是還ok，但如果項目很多，效能就會因此而降低了。

所以一般來說：

1、理想的雜湊函數是將在雜湊表上均勻的完成鍵的對應。

2、連結串列過長會導致雜湊表變慢，所以好的雜湊函數，將不致於發生連結串列過長的問題。

雜湊表的效能

平均情況：搜尋、插入、刪除，皆為 O(1)

最壞情況：搜尋、插入、刪除，皆為 O(n)

O(1) 稱為常數時間(Constant Time)，代表不論雜湊表多麼大，耗費的時間皆維持不變的意思。

 

註：雜湊表一般來說，不需要自己實作，因為通常程式都會內建了，例如：關聯式陣列、字典。