Java 集合框架深度解析：Collection 體系核心類別原理與實戰指南

Java 集合框架深度解析：Collection 體系核心類別原理與實戰指南

本文基於 JDK 8 源碼，系統梳理 Collection 介面下 Set、List、Queue 三大分支的核心實現類別，涵蓋資料結構、原理機制、效能特徵、執行緒安全性與選型建議，附帶類圖與源碼關鍵點註解。

一、核心抽象基類

AbstractCollection<E>

提供 Collection 介面骨幹實現，最小化實現成本：

• 不可修改集合：僅需實現 iterator() 和 size()
• 可修改集合：額外重寫 add() (否則拋 UnsupportedOperationException) 和迭代器的 remove()
• 建議提供無參構造器和 Collection 參數構造器

二、Set 介面族群

特徵：元素唯一 (e1.equals(e2) 為 false)，最多一個 null。

1. HashSet - 哈希表實現，效能王者

• 底層：HashMap<E, Object> (value 統一為 PRESENT 常量)
• 無序、非執行緒安全、允許一個 null
• 基本操作 O(1) (假設哈希分佈均勻)
• 迭代時間 ∝ size + capacity (桶數量)，不要將初始容量設太大
• 同步包裝：Collections.synchronizedSet(new HashSet<>())
• 快速失效迭代器：ConcurrentModificationException 僅作檢測 bug 用

2. LinkedHashSet - 保持插入順序

• 底層：LinkedHashMap (雙向鏈表維護順序)
• 迭代順序 = 插入順序，重新插入不影響順序
• 基本操作 O(1)，迭代時間 ∝ size (與 capacity 無關，優於 HashSet)
• 適用：需去重且保持輸入順序 (如 LRU 快取鍵集合)

3. TreeSet - 紅黑樹實現，自動排序

• 底層：TreeMap 實現 NavigableSet
• 自然序 (Comparable) 或自訂序 (Comparator)
• 基本操作保證 O(log n)
• 順序必須與 equals 一致，否則違反 Set 協定 (雖然行為定義良好)
• 同步包裝：Collections.synchronizedSortedSet(new TreeSet<>())
• 適用：排序去重、範圍查詢 (subSet, headSet, tailSet)

4. 並發/特殊 Set

三、Queue 介面族群

特徵：處理前保存元素，雙形式方法 (拋異常/返回特值)，通常 FIFO。

1. PriorityQueue - 優先級佇列

• 底層：最小堆 (陣列實現的完全二叉樹)
• 自然序或 Comparator 排序，頭部為最小元素
• 非執行緒安全、不允許 null、無界
• 入隊/出隊 O(log n)，peek O(1)
• 適用：任務調度、事件驅動、Top K 問題

2. ConcurrentLinkedQueue - 無界並發佇列

• 底層：CAS 無鎖鏈表 (Michael & Scott 算法)
• FIFO、非阻塞、高並發吞吐
• 不允許 null、弱一致性迭代器
• 適用：生產者-消費者、非阻塞任務佇列

3. ArrayDeque - 雙端佇列/棧 (推薦替代 Stack/LinkedList)

• 底層：循環陣列、雙指針 (head/tail)
• 非執行緒安全、不允許 null、容量自動擴容 (2倍)
• 頭尾增刪 O(1)、隨機存取 O(1)、比 LinkedList 效能高 (記憶體連續)
• 實現 Deque、Stack、Queue 三介面
• 官方推薦替代 Stack 和 LinkedList 作佇列/棧用途

四、List 介面族群

特徵：有序 (插入序)、可重複、索引存取、可視為動態陣列。

1. ArrayList - 動態陣列，通用首選

• 底層：Object[] elementData，transient 不序列化
• size, isEmpty, get, set, iterator 均 O(1)
• add 均攤 O(1) (擴容 1.5 倍：newCapacity = oldCapacity + (oldCapacity >> 1))
• 非執行緒安全、允許 null
• ensureCapacity 預分配減少擴容
• 串列化機制：writeObject 僅寫入 size 範圍元素

2. LinkedList - 雙向鏈表，特定場景優選

• 底層：Node<E> (item, next, prev)，首尾哨兵節點
• 實現 List、Deque、Queue
• 頭尾增刪 O(1)，索引操作 O(n) (從較近端遍歷)
• 非執行緒安全、允許 null
• 記憶體開銷大 (每節點 3 個引用)，CPU 快取不友好
• 僅在頻繁頭尾操作且無隨機存取時優於 ArrayList

3. Vector - 同步陣列，舊版遺留

• 所有方法 synchronized，效能差
• 擴容策略：capacityIncrement (默認 2倍)
• 不推薦新代碼使用，並發場景用 Collections.synchronizedList 或 CopyOnWriteArrayList

4. Stack - 後進先出棧，已棄用

• 繼承 Vector，五操作：push, pop, peek, empty, search
• 官方建議用 ArrayDeque 替代：Deque<Integer> stack = new ArrayDeque<>();

5. 並發/特殊 List

五、選型決策總表

六、原始碼閱讀建議路徑

1. AbstractCollection → 理解骨幹實現
2. ArrayList → 陣列擴容、序列化、subList 視圖
3. HashMap → 哈希表、紅黑樹轉換、擴容遷移 (HashSet 直接委託)
4. LinkedHashMap → 雙向鏈表維護順序 (LinkedHashSet 委託)
5. TreeMap → 紅黑樹旋轉、插入刪除修復 (TreeSet 委託)
6. PriorityQueue → 堆調整、siftUp/siftDown
7. ConcurrentHashMap → CAS、synchronized、擴容遷移 (JDK 8+)
8. CopyOnWriteArrayList → 寫時複製、快照迭代器

核心心法：集合選型無絕對優劣，只有場景匹配。理解底層資料結構 (陣列、鏈表、哈希表、紅黑樹、堆、跳表) 的時空間特性，結合業務訪問模式 (讀寫比、並發度、排序需求、順序敏感度) 做決策。原始碼是最好的文檔，建議配合 JMH 基準測試驗證假設。

深度掌握集合框架，不僅能寫出高效代碼，更能在排查線上效能問題、記憶體洩漏、並發異常時直指本質。