JDK 7 vs JDK 8

HashMap 是 Java 中最常用的數據結構之一，其實現並非一成不變。JDK 8 對 HashMap 進行了一次重大重構，帶來了顯著的性能提升和功能優化。理解這些變化，是深入理解 Java 集合框架的關鍵。

一、核心結論：從“數組+鏈表”到“數組+鏈表+紅黑樹”

最根本的區別在於其底層數據結構的演進：

JDK 7：完全基於 數組 + 鏈表 的實現。當發生哈希衝突時，總是將新元素插入到鏈表的頭部（頭插法）。
JDK 8：主要基於 數組 + 鏈表，但當鏈表長度超過一定閾值（TREEIFY_THRESHOLD = 8）時，會將鏈表轉換為紅黑樹（Treeify）。同時，插入新元素時採用尾插法。

這一核心變化解決了 JDK 7 HashMap 在極端情況下的性能缺陷，並引入了更現代的工程實現。

二、詳細對比與解析

以下表格和詳解列出了兩者在各個方面的主要區別：

1. 數據結構的優化：引入紅黑樹

JDK 7 的問題：在極端情況下，如果多個 key 的 hashCode() 值相同，會導致大量的哈希衝突，使得鏈表變得非常長。此時，HashMap 的查詢性能會從 O(1)  退化到 O(n) ，就像遍歷一個鏈表一樣，效率極低。

JDK 8 的解決方案：引入了紅黑樹（一種自平衡的二叉查找樹）。當鏈表的長度超過 8 且 數組（桶）的總容量大於 64 時，鏈表會轉化為紅黑樹。這樣，即使在最壞情況下，查詢性能也能保持在 O(log n) ，極大地提升了抗風險能力。
為什麼要設定閾值 8？
這是一個基於概率統計（泊松分佈）的權衡。開發者認為，哈希碼分佈良好的情況下，鏈表長度達到 8 的概率極低（小於千萬分之一）。因此，在絕大多數情況下，HashMap 都能享受鏈表的簡單性，只在極少數極端情況下啓用更復雜的紅黑樹，這是一種空間和時間的折衷方案。

2. 插入方式的改變：從頭插法到尾插法

JDK 7：頭插法

void transfer(Entry[] newTable) {
    for (Entry<K,V> e : table) { // 遍歷舊數組
        while(null != e) {
            Entry<K,V> next = e.next; // 記錄下一個節點
            int i = indexFor(e.hash, newTable.length); // 計算新位置
            e.next = newTable[i]; // **關鍵：將當前節點的next指向新桶的頭節點**
            newTable[i] = e;      // **將當前節點設為新桶的頭節點**
            e = next;             // 處理下一個節點
        }
    }
}

缺點：在多線程擴容時，頭插法會改變鏈表中元素的順序，容易導致環形鏈表的形成，進而引起 Infinite Loop 和 CPU 100% 的問題。雖然這是非線程安全導致的bug，但頭插法是其誘因。
JDK 8：尾插法
在擴容時，會保持鏈表中原有元素的順序。這樣即使在多線程環境下錯誤地進行了擴容，也不會形成環形鏈表（但依然可能產生數據覆蓋等線程安全問題，只是避免了死循環）。這修復了一個著名的併發bug，但並不意味着HashMap變成了線程安全的。

3. 擴容機制的優化：更高效的重哈希

在擴容時（resize），需要將舊數組中的元素重新計算位置後放到新數組中（rehash）。

JDK 7：對每個元素都使用新的數組長度重新計算其索引位置 indexFor()。
JDK 8：進行了巧妙的優化。由於擴容後數組大小是原來的2倍（2^n），元素的新位置要麼是原位置（oldIndex） ，要麼是原位置 + 舊容量（oldIndex + oldCapacity） 。
它通過 (e.hash & oldCap) == 0 來判斷元素的新位置。這只是一個位操作，效率遠高於重新計算哈希，極大地提升了擴容時的性能。

4. 其他優化

哈希計算簡化：JDK 8 簡化了 hash() 函數的計算過程，減少了擾動次數，在哈希分佈均勻的前提下提升了一點計算性能。
方法整合：JDK 8 將一些特定情況（如 null key）的處理邏輯整合到了主方法中，使得代碼結構更清晰，但可讀性可能有所降低。

三、總結與影響

最後！
JDK 8 對 HashMap 的優化是一次非常成功的現代化改造。它通過引入紅黑樹解決了性能瓶頸，通過尾插法修復了知名的併發隱患，並通過優化的重哈希算法提升了擴容效率。這些改變使得 HashMap 在面對各種場景時都更加健壯和高效。

儘管發生了這些內部變化，但 HashMap 的 API 完全保持不變，這是優秀軟件設計的一個典範——在提升性能和質量的同時，保證了向後兼容性。

對於任何新的項目，都應優先使用 JDK 8 及以上版本，以享受這些自動的性能改進。