Java HashMap get() 與 put() 方法的時間複雜度深度解析

引言

在 Java 開發中，HashMap 是最常用的集合類之一。了解其核心操作 get() 和 put() 的時間複雜度，對於編寫高效能程式碼至關重要。本文將從最佳、平均、最壞三種情況，深入剖析 Java 7 與 Java 8 中 HashMap 的效能表現。

核心結構演進

Java 7 的 HashMap 採用「數組 + 鏈表」結構；Java 8 引入紅黑樹，當鏈表長度超過閾值（預設 8）且數組長度大於 64 時，鏈表會轉換為紅黑樹，大幅優化最壞情況下的查詢效能。

時間複雜度詳細分析

最佳情況：O(1)

當鍵值對的哈希值分佈均勻，無碰撞發生時，無論是 get() 還是 put()，都能直接通過索引定位到目標位置，完成操作。

平均情況：近似 O(1)

得益於優秀的哈希函數與擴容機制，實際應用中碰撞極少。Java 8 的樹化機制進一步保證了平均查找長度極短，效能極其接近常數時間。

最壞情況：O(N) / O(log N)

• Java 7： 所有鍵的哈希值完全相同，退化為單鏈表，查找與插入需遍歷整個鏈表，時間複雜度為 O(N)。
• Java 8： 同樣的極端碰撞下，鏈表轉為紅黑樹後，查找與插入複雜度降為 O(log N)，顯著提升了抗攻擊能力。

總結建議

合理設計 hashCode() 方法，避免大量鍵哈希碰撞；對於高併發場景，建議使用 ConcurrentHashMap。理解底層原理，才能在性能調優時做出正確選擇。