雜湊表與衝突處理

引言：$O(1)$ 的承諾

雜湊表 (Hash Table / Map) 堪稱編程中最重要資料結構。它承諾了常數時間 $O(1)$ 的插入、刪除和查找性能。

然而，由於可能的 Key 是無限的，而陣列空間是有限的，兩個不同的 Key 最終會映射到同一個索引上。這就是 衝突 (Collision)。一個系統如何處理衝突，決定了它的性能上限和記憶體佔用。

演算法要解決什麼問題？

• 輸入： 鍵值對 (Key-Value)。
• 輸出： 透過 Key 瞬間存取 Value。
• 承諾： 性能不隨數據集的增大而變慢。

核心思想 (直覺版)

想像一面巨大的 編號郵箱牆。

1. 你拿一個名字 (“Luke”)。
2. 雜湊函數 將 “Luke” 轉換為一個數字（例如 42）。
3. 你直接走向 42 號郵箱。
4. 如果 “Sarah” 的雜湊值也是 42，麻煩就來了。

衝突處理策略

1. 拉鏈法 (Separate Chaining) - Java HashMap 採用

每個「桶」實際上是一個 鏈表。

• 如果多個 Key 都映射到索引 42，她們就排隊存在 42 號位的鏈表裡。
• 優點： 實現簡單，永遠不會被「填滿」。
• 缺點： 衝突多時，$O(1)$ 會退化成 $O(N)$（遍歷鏈表）。

2. 開放定址法 (Open Addressing) - Python dict 採用

如果 42 號位被佔了，就去找 下一個可用 的位置。

• 線性探測： 看 43, 44, 45…
• 優點： 快取局部性好（所有數據都在一個連續陣列裡）。
• 缺點： 容易產生「聚集效應」（一大片連續空間被佔用，導致搜尋變慢）。

工程中的核心考量

• 裝載因子 (Load Factor)： 當表被填滿 75% 時，性能會急劇下降。此時大多數雜湊表會進行 擴容 (Resize)（通常容量翻倍）。
• 雜湊洪水攻擊 (Hash Flooding)： 如果攻擊者知道你的雜湊演算法，她們可以發送數千個故意碰撞到同一個索引的 Key，讓你的 $O(1)$ 伺服器變成 $O(N^2)$ 的蝸牛。現代語言透過 雜湊加鹽/隨機化 來防禦。

性能與複雜度總結

• 時間 (平均)： $O(1)$。
• 時間 (最壞)： $O(N)$ (發生大量衝突時)。
• 空間： $O(N)$。

小結：一句話記住它

「雜湊表透過將 Key 轉換為索引來實現瞬間存取。拉鏈法和開放定址法是處理『兩個 Key 爭搶同一個位置』時的兩種交通規則。」