HashMap 工作原理深度解析：哈希、碰撞、擴容、線程不安全與面試高頻考點

HashMap 工作原理深度解析：哈希、碰撞、擴容、線程不安全與面試高頻考點

核心原理

HashMap 基於哈希表（數組 + 鏈表/紅黑樹）。
put(key, value) → key.hashCode() → 擾動函數 → 索引 → 存入 Node<K,V>（含 key、value、hash、next）。
get(key) → 同樣計算索引 → 遍歷鏈表/樹 → key.equals() 匹配 → 返回 value。

關鍵點 1：碰撞解決

• 不同 key hashCode() 相同或索引相同 → 碰撞
• JDK 7：頭插法鏈表
• JDK 8：尾插法鏈表，長度 > 8 且數組 > 64 → 樹化（紅黑樹），O(log n) 查找

關鍵點 2：equals() 與 hashCode() 契約

• equals() 判斷 key 相等（鏈表遍歷時用）
• 不可變對象（String、Integer）作 key 最佳：hashCode() 可緩存，無副作用

關鍵點 3：擴容

• 默認負載因子 0.75，閾值 = capacity * 0.75
• 擴容為 2 倍，rehash 重新計算索引遷移節點
• JDK 7 遷移會反轉鏈表順序，多線程下易形成環形鏈表死循環
• JDK 8 尾插法保持順序，但仍非線程安全

關鍵點 4：線程不安全場景

1. put 競爭：覆蓋數據、數據丟失
2. 擴容死循環 (JDK 7)：CPU 100%
3. size 統計不準

解決方案

• Collections.synchronizedMap(new HashMap())：鎖整個 Map，性能差
• ConcurrentHashMap：JDK 7 分段鎖，JDK 8 CAS + synchronized + 紅黑樹，**生產首選**
• Hashtable：全表鎖，過時

面試高頻追問清單

1. HashMap 底層結構？JDK 7 vs 8 差異？
2. put/get 流程？擾動函數作用？
3. 碰撞如何解決？何時樹化/退化？
4. 為什麼負載因子 0.75？
5. 擴容過程？JDK 7 死循環原因？JDK 8 如何改進？
6. 為什麼 String、Integer 適合作 key？
7. 如何實現線程安全 Map？ConcurrentHashMap 原理？

實戰建議

• 預估數據量用 new HashMap<>(capacity) 避免頻繁擴容
• 高併發讀寫用 ConcurrentHashMap
• 只讀場景用 Collections.unmodifiableMap 或 Guava ImmutableMap