Skip to main content

雜湊表(HashMap)

雜湊表（Hash Table）是一種用於快速查找和存儲數據的數據結構。它的工作方式類似於一個巨大的數據字典，其中每條記錄都與一個唯一的關鍵字（Key）相關聯。而這個關鍵字將用來快速訪問或搜索對應的值（Value）。

hash table

特色​

  1. 無論原本的內容長短，經過雜湊演算法處理過的值都會是固定長度
  2. 經由雜湊處理過的資料無法反推出原本的輸入為何
  3. 兩個輸入的內容即使只差一個字， 算出來的結果會會相差非常多
  4. 常用的雜湊演算法有 MD5 和 SHA ，後者的安全性更高

雜湊函式（hash function）​

雜湊函數是一個特別的數學函數，它將給定的 input（key）轉換為一個 index 或位置。這個位置通常對應到雜湊表的儲存位置，這樣可以快速找到相關資料。好的雜湊函數應該將不同的 key 映射到不同的位置，並且應該是高效的。

雜湊衝突​

即便經過複雜的乘法運算，仍然有可能兩個不同的 key 經過雜湊函數後映射到相同的位置，這稱作「雜湊衝突」，常見的處理衝突方法為：鏈式解決法、開放定址法。

  1. 鏈式解決法 - 將新的 key-value 值插入到已經被佔用的位置

    • 在每個儲存位置創建一個儲存空間，可以是一個鏈結串列或陣列。
    • 當發生衝突時，新的鍵-值對被插入這個儲存空間。
    • 如果多個鍵映射到相同的位置，它們會形成一個鏈結串列。
    • 查找時，計算雜湊，然後遍歷儲存位置的儲存空間，直到找到匹配的鍵。

  2. 開放定址法 (open addressing) - 繼續找，直接找到空的位置

  • 當發生衝突時，我們試圖找到下一個可用的儲存位置，通常使用一種序列的方式。
  • 在插入或查找時，計算雜湊並檢查該位置是否被佔用。如果是，我們尋找下一個位置，直到找到可用位置。

性能評估 - 時間複雜度​

不論是搜尋、插入和刪除操作，一般來說時間複雜度為 O(1)，最壞情況下可能會到 O(n)