Java 集合框架深度解析（上）：Collection、List、Set、Queue 核心原理與選型指南

集合框架整體架構

• 綠色：介面（Collection、List、Set、Queue、Map 等）。
• 紅色：常用實作類（ArrayList、LinkedList、HashSet、TreeSet、PriorityQueue、HashMap 等）。

一、核心概念區分

二、List 實作深度對比

ArrayList：動態陣列，隨機訪問王者

• 底層：transient Object[] elementData，預設容量 10，擴容 1.5 倍。
• 隨機訪問：get(i) O(1)，CPU 緩存友好。
• 中間插入/刪除：System.arraycopy 移動元素，O(N)。
• 擴容觸發：ensureCapacityInternal(size+1) → grow() → Arrays.copyOf。

LinkedList：雙向鏈表，插刪高手

• 底層：Node { E item; Node next; Node prev; }，頭尾哨兵節點。
• 中間插入/刪除：修改指標 O(1)（找到位置後），但定位位置需 O(N)。
• 隨機訪問：get(i) 從頭/尾較近端遍歷，O(N)。
• 額外功能：實作 Deque、Queue，天然支援棧、隊列操作。

選型決策樹

需要頻繁隨機訪問、尾部增刪、記憶體敏感 → ArrayList
需要頻繁頭部/中間增刪、實作 Queue/Deque → LinkedList
不確定 → 先用 ArrayList，效能瓶頸再換

三、Set 實作深度對比

HashSet：基於 HashMap，查詢最快

• 底層 HashMap，Value 共用 PRESENT 常量。
• 無序、允許一個 null、非執行緒安全。
• add/remove/contains 平均 O(1)。

TreeSet：基於 TreeMap（紅黑樹），有序

• 元素需實作 Comparable 或提供 Comparator。
• 自然序或自訂序有序輸出，範圍查詢（subSet、headSet、tailSet）極強。
• 操作 O(log N)。

LinkedHashSet：插入序有序

• 雙向鏈表維護插入順序，iterator() 依插入序遍歷。
• 適合「去重且保持輸入順序」場景（如 LRU 快取鍵集合）。

四、Queue 實作與優先級隊列

基本 Queue（LinkedList 實作）

PriorityQueue：優先級隊列（堆實作）

• 預設自然序（最小堆），可傳 Comparator 反序或自訂序。
• offer/poll/peek 保證每次取出優先級最高元素。
• 允許重複元素，非執行緒安全（併發用 PriorityBlockingQueue）。

五、Iterator 與 foreach 陷阱

foreach 本質

for (E e : collection) { ... }
// 編譯器轉換為：
for (Iterator it = collection.iterator(); it.hasNext(); ) {
    E e = it.next();
    ...
}

邊遍歷邊刪除錯誤示範

// 錯誤 1：for 迴圈刪除 → 索引錯位漏刪
for (int i = 0; i < list.size(); i++) {
    if (list.get(i).equals(target)) list.remove(i);
}

// 錯誤 2：foreach 刪除 → ConcurrentModificationException
for (String s : list) {
    if (s.equals(target)) list.remove(s);
}

正確姿勢：使用 Iterator.remove()

Iterator it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals(target)) {
        it.remove(); // 唯一安全刪除方式
    }
}

原理：ArrayList.Itr 維護 expectedModCount，remove() 同步更新 modCount，直接呼叫 list.remove() 導致 modCount != expectedModCount 拋出 CME。

六、工具類：Collections 與 Arrays

• Collections.addAll(list, elements...)：高效批量添加，內部調用 list.add()。
• Arrays.asList(array)：返回固定大小的 List（Arrays.ArrayList），不可增刪，修改元素會影響原陣列。

總結：容器選型速查表