哈希表是一種高效的數據結構，它能讓我們通過“鍵”快速找到對應的“值”。想象一下，哈希表就像一個巨大的抽屜集合，每個抽屜有唯一的編號（數組位置），我們通過一個“鑰匙規則”（哈希函數）把每個“物品”（鍵）放進對應的抽屜，這樣找東西時直接打開抽屜就能拿到，不需要翻遍所有抽屜。但這個“鑰匙規則”可能會出問題——不同的物品（鍵）可能被塞進同一個抽屜（數組位置），這就是“哈希衝突”。
一、哈希衝突是什麼？¶
當兩個不同的鍵（比如學號101和201）通過哈希函數計算後，映射到了哈希表的同一個數組位置（比如第5個抽屜），就發生了哈希衝突。就像兩個同學用不同的名字（鍵），但因爲某種規則（哈希函數）被分到了同一個教室座位（數組位置），這時就需要想辦法讓他們“各就各位”。
二、爲什麼會衝突？¶
哈希衝突的本質是 “鍵的數量遠大於數組容量”，或者 “哈希函數設計得不夠均勻”。
舉個簡單的例子：如果哈希表的數組長度是10（抽屜有10個），但我們有100個不同的鍵（比如1到100的學號），那麼根據“取模10”的哈希函數（即 鍵 % 10），鍵1、11、21…91都會被放進第1個抽屜，鍵2、12、22…92放進第2個抽屜，以此類推。但10個抽屜只能裝10個不同的餘數（0-9），當鍵的數量超過10時，必然有多個鍵會被塞進同一個抽屜，衝突就發生了。
三、如何解決哈希衝突？¶
解決衝突的核心思路是：當衝突發生時，想辦法讓衝突的鍵“各佔一個位置”。常見方法有以下幾種：
1. 鏈地址法（拉鍊法）——最常用的方法¶
原理：每個數組位置（抽屜）不再是單個“空抽屜”，而是一個“鏈表”（小鏈條）。當多個鍵衝突時，把它們按順序“掛”在對應的鏈表後面。
舉個例子：
- 數組有4個位置（抽屜0-3），哈希函數是 鍵 % 4。
- 插入鍵5（5%4=1）→ 抽屜1的鏈表：[5]
- 插入鍵1（1%4=1，衝突）→ 抽屜1的鏈表變成：5 → 1
- 插入鍵9（9%4=1，衝突）→ 抽屜1的鏈表變成：5 → 1 → 9
- 插入鍵3（3%4=3）→ 抽屜3的鏈表：[3]
- 插入鍵13（13%4=1，衝突）→ 抽屜1的鏈表變成：5 → 1 → 9 → 13
查找時：先根據鍵計算數組位置（抽屜1），再遍歷該位置的鏈表找到目標鍵（比如找13，就在鏈表中從5開始往後找）。
優點：實現簡單，空間利用率高，不會出現“空位浪費”，是大多數編程語言（如Java的HashMap）的底層實現方式。
2. 開放定址法——從衝突位置往後找空位置¶
原理：當發生衝突時，從衝突位置的下一個位置開始，依次尋找空位置。
線性探測（最簡單的開放定址法）：
- 衝突時，步長爲1，即 i+1, i+2, i+3...（i爲衝突位置）。
舉個例子：
- 數組位置1有鍵5，插入鍵1（衝突）→ 嘗試位置2（空），放入位置2。
- 插入鍵2（2%4=2，衝突）→ 嘗試位置3（空），放入位置3。
- 插入鍵6（6%4=2，衝突）→ 位置2已被佔，嘗試位置3（已被佔），嘗試位置4（空，假設數組長度爲5），放入位置4。
缺點：容易形成“聚集”（多個衝突鍵連續佔用多個位置），比如連續插入10個衝突鍵，會佔用10個位置，影響後續效率。
3. 二次探測——步長變大，減少聚集¶
原理：衝突時，步長不是1，而是平方數（1², 2², 3²…），比如 i+1², i+2², i+3²...。
舉個例子：
- 衝突位置i=1，步長1²=1 → 位置2；若衝突，步長2²=4 → 位置1+4=5；若還衝突，步長3²=9 → 位置1+9=10…
優點：相比線性探測，能減少聚集，但步長設計不當仍可能聚集，實現稍複雜。
4. 雙重哈希法——用多個哈希函數¶
原理：當第一個哈希函數衝突時，用第二個哈希函數計算新位置。
舉個例子：
- 第一個哈希函數：h1(k) = k % 4（衝突位置1）。
- 第二個哈希函數：h2(k) = (k // 10) % 5（另一種映射規則）。
- 衝突時，新位置 = h1(k) + h2(k)，直到找到空位置。
優點：通過多個哈希函數分散衝突，減少聚集，但需要維護多個哈希函數，實現較複雜。
5. 公共溢出區——主區+溢出區¶
原理：主數組存“不衝突的鍵”，衝突的鍵統一放進“溢出區”數組。
查找時：先在主數組找，沒找到再去溢出區找。
缺點：溢出區大小難確定，可能因空間不足導致插入失敗。
四、總結¶
哈希衝突是哈希表的“天生問題”，因爲鍵的數量永遠可能超過數組容量，而哈希函數無法做到絕對均勻。解決方法中，鏈地址法（拉鍊法） 最直觀、最常用，它通過“鏈表掛接”解決衝突，實現簡單且效率高；開放定址法（線性/二次/雙重）通過“往後找位置”解決衝突，但可能有聚集問題。實際使用中，需根據場景選擇合適的方法。
理解哈希衝突和解決方法，能幫助你更好地設計和優化哈希表，寫出高效的代碼~