Java 集合框架核心實現原理與選型指南

Java 集合框架是日常開發與面試的高頻考點。本文從源碼層面剖析主流集合類的底層資料結構、核心方法實現、效能特徵，並提供實戰選型決策指南。

集合體系繼承結構

Collection
├── List (有序、可重複)
│   ├── ArrayList (動態陣列)
│   ├── LinkedList (雙向鏈表)
│   └── Vector (同步動態陣列)
└── Set (無序、不可重複)
    ├── HashSet (HashMap 鍵值)
    ├── LinkedHashSet (有序 HashSet)
    └── TreeSet (紅黑樹，有序)
Map (鍵值對)
├── HashMap (陣列+鏈表/紅黑樹)
├── LinkedHashMap (維護插入/存取順序)
├── TreeMap (紅黑樹，鍵有序)
├── Hashtable (同步 HashMap)
└── WeakHashMap (弱引用鍵)

List 族群深度解析

ArrayList：動態陣列

• 底層 Object[] elementData，預設容量 10，擴容 1.5 倍
• 隨機存取 O(1)，尾部新增攤還 O(1)，中間插入/刪除 O(n) 需陣列拷貝
• 非同步，單執行緒效能優於 Vector

LinkedList：雙向鏈表

• 節點結構：prev | item | next，不佔用連續記憶體
• 頭尾操作 O(1)，指定位置存取 O(n) 需遍歷
• 頻繁增刪場景優勢明顯，但記憶體開銷大（節點物件）、CPU 快取不友善
• 實現 Deque，可作棧、佇列使用

Vector：同步動態陣列

• 方法級 synchronized，多執行緒安全但效能低
• 擴容 2 倍，可指定增量
• 現代開發建議用 Collections.synchronizedList 或並發包替代

Set 族群實現機制

HashSet：基於 HashMap

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

鍵為元素，值為靜態常量 PRESENT。HashMap 鍵唯一性保證 Set 去重。非同步、允許 null。

LinkedHashSet：維護插入順序

繼承 HashSet，內部使用 LinkedHashMap，雙向鏈表串聯節點，迭代順序等於插入順序。

TreeSet：紅黑樹有序集合

• 基於 TreeMap，元素需實現 Comparable 或提供 Comparator
• 插入、刪除、查詢 O(log n)，支援範圍查詢
• 非同步

Map 族群核心差異

實戰選型決策樹

1. 需鍵值對 → Map；需單值集合 → List/Set
2. List：頻繁隨機存取 → ArrayList；頻繁頭尾增刪 → LinkedList；多執行緒 → CopyOnWriteArrayList
3. Set：去重無序 → HashSet；去重有序(插入序) → LinkedHashSet；去重排序 → TreeSet
4. Map：高併發 → ConcurrentHashMap；需順序 → LinkedHashMap；需排序 → TreeMap；單執行緒高效查詢 → HashMap

常見陷阱與最佳實踐

• 初始化容量：預估資料量設定 initialCapacity，減少擴容開銷
• 避免遍歷中修改：使用 Iterator.remove() 或並發集合
• 自定義類作鍵：必須正確重寫 hashCode() 與 equals()
• 基本型別集合：考慮 Eclipse Collections、FastUtil 避免裝箱拆箱開銷

總結

理解集合底層資料結構與演算法複雜度，是寫出高效、穩健 Java 程式的前提。實際專案中應根據業務訪問模式、併發需求、資料規模綜合選型，而非單純追求「通用」。建議閱讀 JDK 源碼（ArrayList、HashMap、ConcurrentHashMap 為優先），深入掌握擴容、樹化、並發控制等核心邏輯。