Java 集合框架全景深度解析：結構、源碼、遍歷、比較器與工具類一網打盡

學習策略：抓數據結構 → 推導特性 → 記核心 API → 看源碼關鍵點。

二、Collection 體系

1. List 接口及實現

ArrayList 擴容機制（JDK 8）

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
    elementData = Arrays.copyOf(elementData, newCapacity);
}

默認初始容量 10，首次 add 若為空數組則擴至 10。

LinkedList 節點結構

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

雙向鏈表，頭尾指針 first/last，索引查找採用「二分方向」優化：index < size/2 從頭找，否則從尾找。

2. Set 接口及實現

本質：HashSet 內部持有 HashMap<E, Object>，Value 統一用 PRESENT 佔位對象。

三、Map 體系

1. HashMap (JDK 8 重點)

• 結構：數組 + 鏈表 + 紅黑樹（鏈表長度 ≥ 8 且數組長度 ≥ 64 時樹化）。
• 核心字段：Node<K,V>[] table、size、threshold = capacity * loadFactor（默認 0.75）、modCount。
• put 流程：計算 hash → 索引 → 為空直接放入 / 不空掛鏈表或樹化 → 檢測 key 重複覆蓋 value → size++ → 達閾值 resize()（擴容 2 倍）。
• get 流程：hash → 索引 → 遍歷鏈表/樹比較 key.equals() → 命中返回 value。
• 線程不安全：多線程 put 導致鏈表成環、數據丟失。並發場景用 ConcurrentHashMap。

2. TreeMap

• 紅黑樹：自平衡二叉搜索樹，保證 O(log n) 增刪查。
• 排序依據：Key 實現 Comparable 或構造傳入 Comparator。
• 導航方法：firstKey()、lastKey()、lowerKey()、higherKey()、subMap() 等極其實用。

3. 遍歷方式性能對比

// HashMap 推薦：entrySet 避免二次 get
for (Map.Entry<K,V> e : map.entrySet()) { ... }

// ArrayList 推薦：for 索引 / for-each > Iterator
// LinkedList 推薦：for-each / Iterator（避免 get(index) O(n)）

四、比較器：Comparable vs Comparator

最佳實踐：元素類實現 Comparable 定義自然序；需多維排序時編寫獨立 Comparator 實現類或 Lambda。

五、工具類

Collections

• sort(List) / sort(List, Comparator)
• shuffle(List) 洗牌
• reverse(List) 反轉
• binarySearch(List, key) 前提已排序
• max/min(Collection, Comparator)
• synchronizedXxx() 線程安全包裝
• unmodifiableXxx() 唯讀視圖

Arrays

• sort(T[]) / sort(T[], Comparator)
• asList(T...) 數組 → List（定長，不可增刪）
• toString(array)、deepToString()
• stream(array) 並行流入口

六、避坑指南精選

七、總結

掌握集合框架的關鍵在於數據結構決定性能特徵。面試與實戰中，重點關注：

1. ArrayList vs LinkedList 選型依據
2. HashMap JDK 8 樹化機制與擴容
3. HashSet/TreeSet 去重原理（equals/hashCode vs Comparable/Comparator）
4. 遍歷方式對性能的影響
5. Comparable（內部自然序）與 Comparator（外部策略）的配合使用
6. 工具類 Collections/Arrays 的高頻方法

內化這些核心知識，集合相關問題將不再是難點。