哈希表是數據結構裏的“查找小能手”，它通過哈希函數把鍵快速映射到數組的某個位置，實現O(1)的平均查找效率。但如果兩個不同的鍵通過哈希函數映射到同一個位置，就會發生哈希衝突。這時候，我們該怎麼解決衝突呢？今天用最簡單的方式聊聊幾種常見的哈希衝突解決方法，讓你輕鬆理解數據結構裏的哈希邏輯。

一、哈希衝突是什麼？¶

先回憶一下哈希表的基本原理：哈希表本質是一個數組，數組的每個位置叫做“槽位”（slot）。我們把鍵（比如學生的名字、商品的ID）通過哈希函數（比如key % 數組長度）計算出一個索引，這個索引就是鍵在數組裏的“家”。

但問題來了：如果兩個不同的鍵算出來的索引相同（比如鍵1和鍵6，數組長度是5，哈希函數都是key % 5，那麼1%5=1，6%5=1，衝突！），這時候就會搶同一個“家”，這就是哈希衝突。

二、解決衝突的核心思路¶

衝突發生後，我們需要給衝突的元素找“新的家”。常見的思路有兩種：
1. 把衝突的元素“掛”在同一個槽位（比如多個元素共用一個鏈表）；
2. 往其他空槽位“擠一擠”（比如順着數組往後找空位置）。

三、最常用的兩種解決方法¶

1. 鏈地址法（拉鍊法）：給衝突元素“建鏈表”¶

原理：每個槽位不是隻存一個元素，而是存一個鏈表（或數組），所有衝突的元素都“掛”在這個鏈表上。
類比：就像快遞櫃，每個櫃子（槽位）一開始是空的。如果兩個快遞的哈希值相同（比如都對應“櫃子0”），就把它們放進這個櫃子旁邊的“臨時貨架”（鏈表）裏，取件時先找櫃子，再在貨架上找。

舉個例子：
假設哈希表數組長度是5（槽位0-4），哈希函數是key % 5。現在插入鍵1、6、11：
- 鍵1：1%5=1 → 槽位1是空的，直接放進去，鏈表[1] = [1]；
- 鍵6：6%5=1 → 槽位1已有元素，把6掛到鏈表末尾，鏈表[1] = [1,6]；
- 鍵11：11%5=1 → 同樣掛到鏈表，鏈表[1] = [1,6,11]。

查找時：比如找鍵6，先算6%5=1，定位到槽位1，然後遍歷鏈表[1,6,11]，找到6。

優點：實現簡單，適合動態數據（隨時增刪），不會浪費空間（沒衝突就不用建鏈表）。
缺點：需要額外空間存鏈表，查找時需要遍歷鏈表（最壞O(n)時間，但平均還是O(1)）。

2. 開放尋址法：“擠一擠”找空槽位¶

原理：如果槽位i被佔用，就從i開始往後找空槽位（或往前），直到找到空位。根據“找空槽位”的規則不同，分爲：
- 線性探測：衝突時，依次探測i+1, i+2, ..., m-1, 0, 1,...（循環）；
- 二次探測：衝突時，探測i+1², i+2², i+3²,...（避免連續聚集）。

類比：排隊買奶茶，第一個人（鍵）站在1號窗口（槽位1），第二個人（鍵）也站1號窗口衝突了，就站2號窗口（線性探測）；如果2號也衝突，就站4號（二次探測，1+1²=2，2+1²=3，3+1²=4）。

舉個例子：
數組長度5，哈希函數key%5，插入鍵1（槽位1）、鍵6（槽位1衝突）：
- 鍵1：1%5=1 → 空槽位，放1；
- 鍵6：6%5=1 → 衝突，線性探測到1+1=2（空），放6。

再插入鍵11：11%5=1 → 衝突，線性探測到2（被6佔），3（空），放11。

查找時：找鍵6，算6%5=1→槽位1，發現不是，線性探測到2（6），找到。

優點：空間利用率高（數組不用浪費額外空間），實現簡單（不需要鏈表）。
缺點：線性探測會導致“聚集”（多個衝突元素擠在一起），可能填滿數組；二次探測可以緩解聚集，但需要更大的數組空間（避免找不到空位）。

四、其他方法（簡單瞭解）¶

• 再哈希法：衝突時用另一個哈希函數重新計算位置，直到找到空位。比如f(key, i) = (f1(key) + i*f2(key)) % m，i=0,1,2…。適合衝突較少的場景，但需要多個哈希函數。
• 公共溢出區：把哈希表分爲“基本表”和“溢出表”。基本表存無衝突的元素，衝突的元素全放溢出表。查找時先查基本表，沒找到再查溢出表。適合衝突少的靜態數據，但溢出表管理複雜。

五、總結：選哪種方法？¶

• 鏈地址法：Java的HashMap、Python的字典都用這種方法，實現簡單，適合動態數據量大、衝突多的場景（比如數據量不固定時）。
• 開放尋址法：適合數組大小固定、衝突少的場景（比如已知數據範圍時），線性探測簡單但聚集多，二次探測更靈活。
• 其他方法：再哈希法適合衝突少且需嚴格避免聚集的場景，公共溢出區適合衝突極少的靜態數據。

哈希衝突的解決方法本質是“如何給衝突元素找新位置”，理解這兩種核心方法（鏈地址法和開放尋址法）就能應對大部分場景啦。下次寫代碼實現哈希表時，就知道該怎麼處理衝突了～