Java 集合框架是日常開發最高頻 API，深入理解 List/Set 實現原理、性能特徵、適用場景，能避免 90% 的集合誤用導致的性能與並發問題。本文系統梳理 ArrayList、LinkedList、HashSet、TreeSet、LinkedHashSet 核心機制與選型決策樹。
一、集合體系總覽
Collection (介面)
├── List (有序、可重複)
│ ├── ArrayList (動態數組)
│ ├── LinkedList (雙向鏈表)
│ └── Vector (同步、舊版)
└── Set (無序、唯一)
├── HashSet (哈希表)
├── LinkedHashSet (鏈表+哈希，保持插入序)
└── TreeSet (紅黑樹，有序)
Map (鍵值對) - 另文詳解
二、List 族詳解
ArrayList：隨機訪問之王
- 底層：
transient Object[] elementData 動態數組。
- 擴容機制：
newCapacity = oldCapacity + (oldCapacity >> 1)（1.5 倍），Arrays.copyOf 複制。
- 性能特徵：
| 操作 | 時間複雜度 | 說明 |
|---|
| get/set | O(1) | 數組下標直接訪問 |
| add(E) | O(1) 攤還 | 末尾添加，偶爾觸發擴容 |
| add(index, E) | O(n) | 需搬移後續元素 |
| remove(index) | O(n) | 需搬移後續元素 |
| contains | O(n) | 線性掃描 |
- 適用場景：頻繁隨機訪問、末尾增刪、作為堆疊。預估大小用
new ArrayList<>(capacity) 避免擴容。
LinkedList：首尾增刪之王
- 底層：雙向鏈表，
Node first, last，每節點含 prev, next, item。
- 性能特徵：
| 操作 | 時間複雜度 | 說明 |
|---|
| addFirst/addLast | O(1) | 直接操作頭尾指針 |
| getFirst/getLast | O(1) | 直接返回頭尾節點 |
| removeFirst/removeLast | O(1) | 直接調整頭尾指針 |
| get(index) | O(n) | 從較近端遍歷（index < size/2 從頭，否則從尾） |
| add/remove 中間 | O(n) | 需先定位節點 |
- 額外能力：實現
Deque 介面，天然支持棧、隊列、雙端隊列。
- 記憶體開銷：每個元素額外 2 個引用（prev/next），小對象存儲開銷大約 3 倍於 ArrayList。
Vector / Stack：遺產代碼，勿用於新項目
Vector 方法同步，單線程性能差；多線程場景用 Collections.synchronizedList 或並發包 CopyOnWriteArrayList。Stack 繼承 Vector，同步開銷大；棧操作用 ArrayDeque（非同步、性能優）。
三、Set 族詳解
HashSet：O(1) 查找去重
- 底層：包裝
HashMap，key 存元素，value 共享 PRESENT = new Object()。
- 核心契約：元素必須正確覆寫
hashCode() 和 equals()，否則去重失效。
- 性能：add/remove/contains 平均 O(1)，負載因子 0.75 觸發擴容（2倍+1）。
- 順序：無序，遍歷順序與插入順序無關，擴容後順序可能改變。
LinkedHashSet：有序去重
- 底層：
LinkedHashMap = HashMap + 雙向鏈表維護插入順序。
- 特點：擁有 HashSet 的 O(1) 查找，**遍歷順序 = 插入順序**。
- 適用：需要去重且保持用戶輸入順序（如購物車、標籤系統）。
TreeSet：有序集合與範圍查詢
- 底層：
TreeMap = 紅黑樹（自平衡 BST）。
- 特點：元素按自然順序 或 Comparator 排序，遍歷有序。
- 性能：add/remove/contains O(log n)。
- 強大功能：
first() / last()：最小/最大元素lower(e) / higher(e)：嚴格小於/大於 e 的最大/最小元素subSet(from, to) / headSet(to) / tailSet(from)：範圍視圖
- 前提：元素實現
Comparable 或構造時提供 Comparator。
四、選型決策樹
需要鍵值對？ → Map 族
否：
需要去重？
是：
需要有序遍歷？
是：
按插入順序 → LinkedHashSet
按排序順序 → TreeSet (需 Comparable/Comparator)
否 → HashSet (最高性能)
否：
頻繁隨機訪問/末尾增刪？ → ArrayList
頻繁首尾增刪/作為隊列棧？ → LinkedList / ArrayDeque
需要線程安全？ → 並發包 (CopyOnWriteArrayList, ConcurrentHashMap.keySet())
五、最佳實踐清單
- 介面編程：
List<User> users = new ArrayList<>(); 而非 ArrayList<User> users。
- 指定初始容量：
new ArrayList<>(expectedSize)，new HashSet<>((int)(expectedSize/0.75f)+1) 避免擴容/重哈希。
- 不可變集合：Java 9+
List.of()、Set.of()，線程安全、記憶體緊湊、拒絕修改。
- 並發場景：
- 讀多寫少：
CopyOnWriteArrayList、CopyOnWriteArraySet
- 寫多：
Collections.synchronizedList + 手動同步、或拆分鎖段
- 避免在循環中修改集合：使用
Iterator.remove() 或串流 filter 收集新集合。
- 自定義類用於 Set/Map Key 時：必須覆寫 equals/hashCode，且僅基於不可變字段。
六、常見誤區辨析
| 誤區 | 正確認知 |
|---|
| ArrayList 線程安全 | 非線程安全，多線程寫入會導致數據錯誤或 ArrayIndexOutOfBoundsException |
| HashSet 保持插入順序 | 不保持，用 LinkedHashSet |
| TreeSet 比 HashSet 快 | 單操作 O(log n) 慢於 O(1)；僅在需要有序/範圍查詢時選 TreeSet |
| for-each 循環中 remove | 拋 ConcurrentModificationException，用 Iterator.remove() |
| List.set 可擴容 | 僅替換現有索引元素，索引越界拋異常，不擴容 |
集合選型無銀彈，只有場景匹配。掌握底層數據結構（動態數組、雙向鏈表、哈希表、紅黑樹）的時空權衡，才能在海量數據、高併發、低延遲的實戰中做出最優決策。
