[演算法] 雜湊表(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),代表不論雜湊表多麼大,耗費的時間皆維持不變的意思。

 

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

您可在此處留言

avatar

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

  Subscribe  
Notify of