資料結構筆記-雜湊表 (Hash Table)

雜湊表介紹

雜湊表 (Hash Table) 是用來儲存 key-value pairs 的一種資料結構，有點類似陣列 (Array) ，但它的 key 並沒有順序可言，此外，雜湊表在 Search 、 Insert、Remove 方面的處理速度都比陣列 (Array) 快上許多; 幾乎所有的程式語言都具有類似Hash Table的資料結構(例如 Python 的Dictionary ，J avaScript 的 Object 以及 Map ， Java 的 Maps ， Ruby 的Hashes )。好的 Hash Table 必須具備:

• 確定性 (Deterministic) :
  倘若兩個雜湊值不同，則這兩個雜湊值的原始輸入也不會一樣。

• 均勻分布 (uniform distribution) :
  假設一個 Hash Table 的大小 (Size) 為 N ，並加入K組 ( K 小於 N ) 資料之後，每組資料都只能對應 Table 內所屬的 Slot (雜湊值都不一樣)，倘若不同 key 的資料對應相同的 Slot 時，這種情況稱為雜湊碰撞 (hash collision)。

雜湊碰撞 (hash collision) 以及如何盡量避免

如下方程式碼中的 hash functions ，不同的 key ( name 以及 weight )回傳了一樣的 index ，即是雜湊碰撞。倘若在函式內加入質數的話，可以讓碰撞的機率降低。

碰撞 (Collision) 發生時要如何處理?

可以透過 1. Separate Chaining 或是 2. Linear Probing 來處理。

• Separate Chaining :
  是將衝突的資料放在 Table 內的同一個 Slot ，

• Linear Probing :
  則是將衝突的資料放入相鄰且空的 Slot 。

JavaScript 實現雜湊表 Set Method

在下方程式碼中，為了處理雜湊碰撞 (Hash Collision) 的情況，使用 Separate Chaining 的處理方式。

Get Method

存取 Table 內的 key 所對應的 value 。

Keys and Values Method

用來回傳 Table 內所有的 key 以及 value (不重複)。

測試結果

雜湊表 (Hash table) 的時間複雜度

• Insert: O(1)
• Deletion: O(1)
• Access: O(1)

參考資料

• JavaScript Algorithms and Data Structures Masterclass