資料結構- 雜湊表(HashTable)

雜湊表

雜湊表(HashTable)，根據鍵值(key)直接查詢在記憶體儲存的位置。也就是透過雜湊函數(hash function)，計算鍵(Key)所對應的位置，進而找到對應值(value)

碰撞

當兩筆以上不同的資料進行雜湊函數運算時有著相同的結果，此時就會發生碰撞(Collision)，碰撞問題太多，就會導致雜湊表效能變差，所以雜湊函數會盡量避免碰撞。

解決碰撞的方法有

1. 開放定址(Opening Address)：當發生碰撞時，會找出第二個替代位址儲存，若還是發生碰撞，會一直找到空的位址並且儲存值(value)

1. 分離鏈結法(Separate Chaining)：在每一個Hash value裡頭置放鏈結串列(Linked List)，當資料有碰撞的情況時，就將值放入鏈結串列(Linked List)之中，但需要額外儲存鏈結串列(Linked List)

特性

• 雜湊表(HashTable)利用雜湊函數hash function進行搜尋，搜尋時間複雜度為O(1)

• 新增、移除時間複雜度為O(1)

• 當發生碰撞時，通常會使用開放定址(Opening Address)、額外鏈結法(Separate Chaining)這兩種方法解決

參考資料：

• 雜湊表

• 用 JavaScript 學習資料結構和演算法：字典（Dictionary）和雜湊表（Hash Table）篇

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

• 《演算法圖鑑》第一章：資料結構