Java 集合框架深度解析：List、Set、Map 核心實現與選型指南

集合框架總覽：一張圖看懂繼承體系

Collection (介面)
├── List (有序、可重複)
│   ├── ArrayList (動態陣列, 非同步)
│   ├── LinkedList (雙向鏈表, 非同步)
│   ├── Vector (動態陣列, 同步)
│   │   └── Stack (後進先出棧)
│   └── CopyOnWriteArrayList (並發安全)
└── Set (無序、唯一)
    ├── HashSet (HashMap 底層, 非同步)
    ├── LinkedHashSet (保持插入順序)
    ├── TreeSet (紅黑樹, 有序)
    └── CopyOnWriteArraySet (並發安全)

Map (介面, 不繼承 Collection)
├── HashMap (非同步, 允許 null)
├── LinkedHashMap (保持插入/訪問順序)
├── TreeMap (紅黑樹, 有序)
├── Hashtable (同步, 不允許 null)
├── WeakHashMap (弱引用 Key, 適合緩存)
├── ConcurrentHashMap (高並發, 分段鎖/CAS)
└── IdentityHashMap (用 == 比較 Key)

一、Collection 與 Iterator 基礎

所有集合實現類必須提供兩個構造器：無參構造器建立空集合、帶 Collection 參數的複製構造器。遍歷統一使用 iterator() 返回 Iterator，支援 hasNext()、next()、remove()。

二、List 介面與四大實現類深度對比

1. ArrayList：隨機訪問之王

• 底層：動態擴容的 Object[] 陣列
• 優勢：get/set O(1)，記憶體緊湊，CPU 緩存友好
• 劣勢：中間插入/刪除 O(n) 需搬移元素，擴容需複製陣列
• 擴容機制：1.5 倍增長 (newCapacity = oldCapacity + (oldCapacity >> 1))
• 適用場景：頻繁隨機讀取、末尾追加、元素量可預估（可用 ensureCapacity 預分配）

2. LinkedList：頻繁增刪首選

• 底層：雙向鏈表，每節點含 prev/next/item
• 優勢：頭尾增刪 O(1)，實現 Deque 可作棧/隊列
• 劣勢：隨機訪問 O(n)，記憶體開銷大（節點對象），GC 壓力高
• 適用場景：頻繁頭尾操作、實現隊列/棧、元素量大但少隨機訪問

3. Vector 與 Stack：歷史遺留的同步類

• Vector：方法級 synchronized，效率低；迭代器為快速失效，併發修改拋 ConcurrentModificationException
• Stack：繼承 Vector，提供 push/pop/peek，但官方推薦用 Deque (ArrayDeque) 替代
• 現代替代：單線程用 ArrayList，多線程用 Collections.synchronizedList 或 CopyOnWriteArrayList

4. 效能對比表

三、Set 介面：唯一性的守門員

• HashSet：底層 HashMap，add/contains/remove 平均 O(1)，無序，允許一個 null
• LinkedHashSet：雙向鏈表維護插入順序，遍歷有序，性能略低於 HashSet
• TreeSet：底層 TreeMap (紅黑樹)，自然順序或 Comparator 排序，操作 O(log n)
• 核心契約：equals() 與 hashCode() 必須一致，否則無法正確去重

四、Map 介面：鍵值映射的核心

1. HashMap (JDK 8+)：高性能標準實現

• 結構：陣列 + 鏈表 + 紅黑樹 (鏈表長度 > 8 且陣列長度 ≥ 64 樹化)
• 擴容：負載因子 0.75，容量翻倍，高位參與雜湊減少碰撞
• Key 要求：正確重寫 hashCode()/equals()，不可變對象最佳
• 非同步：多線程環境用 ConcurrentHashMap 或 Collections.synchronizedMap

2. Hashtable：過時的同步映射

• 所有 public 方法 synchronized，單鎖競爭激烈
• 不允許 null key/value
• 已被 ConcurrentHashMap 完全取代

3. WeakHashMap：緩存場景的利器

• Key 為弱引用 (WeakReference)，GC 時 Key 無強引用則自動移除條目
• 適合「Key 生命週期由外部控制」的緩存，如 ClassLoader 緩存、監聽器映射

五、選型決策樹：如何快速選擇正確集合

1. 需要 Key-Value 映射？ → Map 系
   • 高並發讀寫 → ConcurrentHashMap
   • 需有序遍歷 → LinkedHashMap (插入序) / TreeMap (排序)
   • 一般場景 → HashMap
2. 只存值，需唯一？ → Set 系
   • 高性能去重 → HashSet
   • 保持插入序 → LinkedHashSet
   • 需排序 → TreeSet
3. 只存值，允許重複，需索引訪問？ → List 系
   • 頻繁隨機讀/尾部加 → ArrayList
   • 頻繁頭尾增刪/作隊列棧 → LinkedList / ArrayDeque
   • 多線程讀多寫少 → CopyOnWriteArrayList

六、最佳實踐原則

• 面向介面編程：宣告類型用 List/Set/Map，實例化具體實現，便於後續替換
• 指定初始容量：預估元素量時用 new ArrayList<>(capacity)、new HashMap<>(capacity) 避免頻繁擴容
• 不可變集合：JDK 9+ List.of()、Set.of()、Map.of() 創建只讀集合，線程安全且節省記憶體
• 避免在循環中修改集合：使用 Iterator.remove() 或併發安全集合

掌握集合底層原理與特性，才能在高併發、大數據量場景下寫出高效穩健的代碼。下次選集合時，先問自己：「訪問模式是什麼？併發需求如何？是否需要有序？」