Java 集合框架是日常開發中使用最頻繁的 API 之一。正確選擇集合類型，理解其內部實現，對於編寫高效、正確的程式碼至關重要。

集合框架概覽#

graph TD
    subgraph Collection["Collection 介面"]
        L[List<br/>有序、可重複]
        S[Set<br/>無序、不可重複]
        Q[Queue/Deque]
    end

    L --> AL[ArrayList]
    L --> LL[LinkedList]
    L --> V["Vector<br/><i>(已過時)</i>"]

    S --> HS[HashSet]
    S --> LHS[LinkedHashSet]
    S --> TS[TreeSet]

    Q --> AD[ArrayDeque]
    Q --> LL2[LinkedList]
    Q --> PQ[PriorityQueue]

    subgraph Map["Map 介面（鍵值對）"]
        HM[HashMap]
        LHM[LinkedHashMap]
        TM[TreeMap]
        HT["Hashtable<br/><i>(已過時)</i>"]
        CHM[ConcurrentHashMap]
    end

    style Collection fill:#e3f2fd
    style Map fill:#fff3e0
    style V fill:#ffcdd2
    style HT fill:#ffcdd2

Map 不是 Collection 的子類型，但通常被視為集合框架的一部分。

List 實現對比#

ArrayList vs LinkedList vs Vector#

特性ArrayListLinkedListVector
底層結構動態陣列雙向鏈結串列動態陣列
線程安全否否是（synchronized）
隨機訪問O(1)O(n)O(1)
頭部插入O(n)O(1)O(n)
尾部插入均攤 O(1)O(1)均攤 O(1)
擴容策略增加 50%無需擴容增加 100%

Vector 是 Java 早期的線程安全實現，同步開銷大。現代開發中應該使用 Collections.synchronizedList() 或 CopyOnWriteArrayList。

選擇策略#

// 大部分場景：ArrayList
List<String> list = new ArrayList<>();

// 頻繁在頭部/中間插入刪除：LinkedList
Deque<String> deque = new LinkedList<>();

// 需要線程安全且讀多寫少：CopyOnWriteArrayList
List<String> safeList = new CopyOnWriteArrayList<>();
LinkedList 遍歷的效能陷阱

錯誤做法：使用 for 循環遍歷 LinkedList

// 時間複雜度 O(n²)！每次 get(i) 都要從頭遍歷
for (int i = 0; i < linkedList.size(); i++) {
    linkedList.get(i);
}

正確做法：使用迭代器或增強 for 循環

// 時間複雜度 O(n)
for (String item : linkedList) {
    // 處理 item
}

// 或使用迭代器
Iterator<String> it = linkedList.iterator();
while (it.hasNext()) {
    it.next();
}

Map 實現對比#

HashMap 內部結構#

Java 8 的 HashMap 採用陣列 + 鏈結串列 + 紅黑樹的混合結構：

graph LR
    subgraph HashMap["HashMap 內部結構"]
        B0["bucket[0]"] --> N1[Node] --> N2[Node] --> N3[...]
        B1["bucket[1]"] --> NULL[null]
        B2["bucket[2]"] --> T1["TreeNode<br/>(紅黑樹)"]
        B3["..."]
        BN["bucket[n-1]"] --> NN[Node]
    end

    style T1 fill:#ffccbc
    style NULL fill:#f5f5f5

當單個桶中的鏈結串列長度超過 8 且陣列容量達到 64 時，鏈結串列會轉換為紅黑樹（樹化），將查詢複雜度從 O(n) 降為 O(log n)。

HashMap vs Hashtable vs TreeMap#

特性HashMapHashtableTreeMap
線程安全否是否
null 鍵值允許一個 null 鍵不允許不允許 null 鍵
順序無序無序按鍵排序
時間複雜度O(1)O(1)O(log n)

Hashtable 已過時，需要線程安全的 Map 應使用 ConcurrentHashMap。

HashMap 的關鍵參數#

// 預設初始容量：16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// 預設負載因子：0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 樹化閾值：8
static final int TREEIFY_THRESHOLD = 8;

// 反樹化閾值：6
static final int UNTREEIFY_THRESHOLD = 6;

如果事先知道資料量，建議指定初始容量以避免擴容：

// 預計存放 100 個元素，考慮負載因子
Map<String, Object> map = new HashMap<>(128);
HashMap 的 hash 演算法最佳化

HashMap 不直接使用 hashCode()，而是進行擾動處理：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

這樣做是為了讓高位也參與運算，減少碰撞。因為定位桶的運算是：

index = (n - 1) & hash

當 n 較小時，只有低位參與運算，高位資訊會被忽略。

Set 實現對比#

實現特點時間複雜度
HashSet無序，基於 HashMapO(1)
LinkedHashSet保持插入順序O(1)
TreeSet自然排序或自定義排序O(log n)
// HashSet 實際上是 HashMap 的馬甲
public class HashSet<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();

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

TreeSet 底層使用 TreeMap 實現，HashSet 底層使用 HashMap 實現。它們只使用了 Map 的 key，value 都是同一個 dummy 物件。

線程安全的集合#

Collections.synchronized 系列#

List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Map<String, Object> syncMap = Collections.synchronizedMap(new HashMap<>());
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());

synchronized 包裝器採用粗粒度鎖，效能較差。遍歷時仍需手動同步：

synchronized (syncList) {
    for (String s : syncList) {
        // 處理
    }
}

ConcurrentHashMap#

Java 8 的 ConcurrentHashMap 採用 CAS + synchronized 實現細粒度鎖：

// 初始化時使用 CAS
private final Node<K,V>[] initTable() {
    while ((tab = table) == null || tab.length == 0) {
        if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            // 初始化
        }
    }
}

// 插入時只鎖定單個桶
synchronized (f) {
    // 插入操作
}
Java 7 vs Java 8 的 ConcurrentHashMap

Java 7：分段鎖（Segment）

  • 將整個 Map 分成 16 個 Segment
  • 每個 Segment 獨立加鎖
  • 理論最大並行度為 16

Java 8：CAS + synchronized

  • 取消 Segment，直接鎖定桶
  • 粒度更細，並行度更高
  • 引入紅黑樹最佳化

ConcurrentHashMap 的常見誤用

// 錯誤：非原子操作
if (!map.containsKey(key)) {
    map.put(key, value);
}

// 正確：使用原子方法
map.putIfAbsent(key, value);
map.computeIfAbsent(key, k -> createValue());

CopyOnWriteArrayList#

適用於讀多寫少的場景：

// 每次寫操作都會複製整個陣列
public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        Object[] newElements = Arrays.copyOf(es, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    }
}

CopyOnWriteArrayList 適合作為事件監聽器列表、黑白名單等讀操作遠多於寫操作的場景。

Java 8+ 集合增強#

Stream API#

List<String> filtered = list.stream()
    .filter(s -> s.startsWith("A"))
    .map(String::toUpperCase)
    .sorted()
    .collect(Collectors.toList());

工廠方法（Java 9+）#

// 不可變集合
List<String> list = List.of("a", "b", "c");
Set<Integer> set = Set.of(1, 2, 3);
Map<String, Integer> map = Map.of("a", 1, "b", 2);

List.of() 等方法創建的集合是不可變的，不支援 add、remove 操作。

實踐建議#

  1. 預設選擇 ArrayList 和 HashMap：大多數場景的最佳選擇
  2. 需要排序用 TreeMap/TreeSet：自動維護有序狀態
  3. 需要保持插入順序用 LinkedHashMap/LinkedHashSet
  4. 並行場景用 ConcurrentHashMap：避免使用 Hashtable
  5. 讀多寫少用 CopyOnWriteArrayList：注意寫操作的開銷
  6. 指定初始容量：避免頻繁擴容帶來的效能損耗
Backward 類型與物件 並行編程 Forward