哈希表衝突怎麼辦？簡單看懂數據結構的哈希解決方法
哈希表通過哈希函數映射鍵到數組槽位，不同鍵映射同一槽位即哈希衝突。解決核心是爲衝突元素找新位置，主要方法如下： 1. **鏈地址法（拉鍊法）**：每個槽位存鏈表，衝突元素掛在鏈表上。例如鍵1、6、11哈希到同一槽位，其鏈表爲[1,6,11]。優點：實現簡單，適合動態數據；缺點：需額外空間存鏈表，查找最壞O(n)。 2. **開放尋址法**：衝突時找空槽位，分線性探測（i+1循環）和二次探測（i+1²等）。如鍵6哈希到槽位1衝突，線性探測到2；鍵11到3。優點：空間利用率高；缺點：線性探測易聚集，二次探測需更大數組。 其他方法：再哈希法（多哈希函數）、公共溢出區（基本表+溢出表），適合衝突少場景。選擇依場景：鏈地址法（如Java HashMap）適合動態大量數據；開放尋址法適合固定數組、衝突少場景。
閱讀全文哈希表怎麼存數據？哈希函數讓查找變簡單
文章用找書類比引出問題：順序查找數據（如數組）效率低，哈希表是高效存儲工具。哈希表核心是哈希函數，將數據映射到“桶”（數組位置），實現快速存取。哈希函數把數據轉爲哈希值（桶編號），如學號取後兩位得哈希值。存儲時，先算哈希值定位桶，若多數據哈希值相同（衝突），用鏈表法（桶內掛鏈表）或開放尋址法（找下一個空桶）解決。查找時，直接算哈希值定位桶，再在桶內查找，無需遍歷全部數據，速度極快。哈希表應用廣泛（如通訊錄、緩存），核心是用哈希函數將查找從“翻遍”轉爲“直達”。
閱讀全文