哈希表衝突怎麼辦？簡單看懂數據結構的哈希解決方法

哈希表通過哈希函數映射鍵到數組槽位，不同鍵映射同一槽位即哈希衝突。解決核心是爲衝突元素找新位置，主要方法如下： 1. **鏈地址法（拉鍊法）**：每個槽位存鏈表，衝突元素掛在鏈表上。例如鍵1、6、11哈希到同一槽位，其鏈表爲[1,6,11]。優點：實現簡單，適合動態數據；缺點：需額外空間存鏈表，查找最壞O(n)。 2. **開放尋址法**：衝突時找空槽位，分線性探測（i+1循環）和二次探測（i+1²等）。如鍵6哈希到槽位1衝突，線性探測到2；鍵11到3。優點：空間利用率高；缺點：線性探測易聚集，二次探測需更大數組。 其他方法：再哈希法（多哈希函數）、公共溢出區（基本表+溢出表），適合衝突少場景。選擇依場景：鏈地址法（如Java HashMap）適合動態大量數據；開放尋址法適合固定數組、衝突少場景。