集合框架總覽
Collection (介面)
├── List (有序、可重複) → ArrayList, LinkedList, Vector
├── Set (無序、唯一) → HashSet, LinkedHashSet, TreeSet
└── Queue (隊列) → PriorityQueue, ArrayDeque
Map (鍵值映射，不繼承 Collection)
├── HashMap, LinkedHashMap, TreeMap, Hashtable, ConcurrentHashMap
List 實現機制與性能對比
ArrayList：動態數組，隨機訪問王者
- 底層
Object[] elementData，默認容量 10，擴容 1.5倍+1
- 優勢：
get(index) O(1)、set(index) O(1)、末尾 add(e) 攤銷 O(1)、indexOf 緩存友好
- 劣勢：中間插入/刪除 O(n) 需搬移元素、擴容觸發數組複製
- 適用：讀多寫少、頻繁隨機訪問、作為堆疊/隊列尾部操作
LinkedList：雙向鏈表，插刪利器
- 內部類
Node { E item; Node next, prev; }，頭尾哨兵節點
- 優勢：首尾/指定位置插入刪除 O(1) (定位後)、無擴容開銷、實現
Deque 接口支援雙端操作
- 劣勢：隨機訪問 O(n) 需遍歷、記憶體開銷大 (每節點 3 引用)、緩存不友好
- 適用：寫多讀少、頻繁中間插刪、作為隊列/棧/雙端隊列
核心方法複雜度速查表
| 操作 | ArrayList | LinkedList | 備註 |
|---|
| get(index) | O(1) | O(n) | |
| add(e) 尾部 | O(1) 攤銷 | O(1) | |
| add(index, e) | O(n) | O(n) 定位 + O(1) 插入 | |
| remove(index) | O(n) | O(n) 定位 + O(1) 刪除 | |
| remove(Object) | O(n) 查找 + O(n) 搬移 | O(n) 查找 + O(1) 刪除 | |
| set(index, e) | O(1) | O(n) 定位 + O(1) 修改 | |
| indexOf(Object) | O(n) | O(n) | |
| 內存開銷/元素 | ~4 bytes (引用) + 數組頭 | ~24 bytes (3引用+對象頭) | 64位 JVM、CompressedOops 啟用時 |
Set 實現與選型
| 實現 | 底層 | 特性 | 適用場景 |
|---|
| HashSet | HashMap (key=元素, value=PRESENT) | 無序、O(1) 增刪查、非線程安全 | 通用去重、歸屬測試、高性能集合 |
| LinkedHashSet | LinkedHashMap | 保持插入順序迭代、性能接近 HashSet | 需有序去重、LRU 緩存鍵集 |
| TreeSet | TreeMap (紅黑樹) | 自然序/Comparator 排序、O(log n) 增刪查 | 需排序集合、區間查詢、最近鄰搜索 |
Map 實現與選型
| 實現 | 底層 | 特性 | 適用場景 |
|---|
| HashMap | 數組+鏈表/紅黑樹 (JDK8) | 無序、O(1)、非線程安全、支援 null key/value | 通用緩存、計數器、鍵值存儲 |
| LinkedHashMap | HashMap + 雙向鏈表 | 保持插入/訪問順序、可實現 LRU (removeEldestEntry) | LRU 緩存、有序配置映射 |
| TreeMap | 紅黑樹 | 鍵排序、O(log n)、範圍查詢 (subMap) | 排序字典、時間序列索引 |
| ConcurrentHashMap | 分段鎖 (JDK7) / CAS+synchronized (JDK8) | 高併發讀寫、弱一致性迭代器 | 多線程緩存、計數器、共享狀態 |
| Hashtable | 數組+鏈表 + 全鎖 | 同步但性能差、不支援 null、已過時 | 避免使用，改用 CHM 或 Collections.synchronizedMap |
迭代器模式統一遍歷
Iterator：單向、hasNext()/next()/remove()，所有 Collection 支援ListIterator：雙向、hasPrevious()/previous()/add()/set()，僅 List 支援，類似數據庫游標- Fail-fast 機制：結構性修改時拋
ConcurrentModificationException，防止並發遍歷異常
實戰代碼範例
import java.util.*;
public class CollectionDemo {
public static void main(String[] args) {
// List 對比
List arrayList = new ArrayList<>(Arrays.asList(10,20,30));
List linkedList = new LinkedList<>(arrayList);
linkedList.add(40); linkedList.add(50); linkedList.add(60);
// Iterator 單向 + 邊遍歷邊刪除
Iterator it = linkedList.iterator();
while (it.hasNext()) {
Integer v = it.next();
System.out.print(v + " ");
if (v == 50) it.remove(); // 安全刪除
}
System.out.println();
// ListIterator 雙向
ListIterator lit = linkedList.listIterator();
while (lit.hasNext()) System.out.print(lit.next() + " ");
System.out.println();
while (lit.hasPrevious()) System.out.print(lit.previous() + " ");
System.out.println();
// Map 典型用法
Map map = new HashMap<>();
map.put("a1",1); map.put("b2",2); map.put("c3",3);
for (String k : map.keySet()) System.out.println(k + " : " + map.get(k));
System.out.println("contains c3: " + map.containsKey("c3"));
map.remove("c3");
System.out.println("size after remove: " + map.size());
}
}
選型決策樹
- 需要鍵值映射 →
Map 系列 (併發选 ConcurrentHashMap，排序选 TreeMap，LRU 选 LinkedHashMap)。
- 只需存儲元素，要求唯一 →
Set (高性能 HashSet，有序 LinkedHashSet，排序 TreeSet)。
- 需有序、可重複、隨機訪問 →
ArrayList。
- 需有序、可重複、頻繁中間插刪 →
LinkedList。
- 作為隊列/棧/雙端隊列 →
ArrayDeque (非線程安全) 或 LinkedBlockingDeque (併發)。
常見坑與最佳實踐
- 初始化容量：預估大小用
new ArrayList<>(capacity) 避免多次擴容。
- 遍歷中刪除：必須用
Iterator.remove()，不可直接 list.remove() 否則拋 CME。
- 自定義類作 Key/Set 元素：必須重寫
equals() 和 hashCode()，保持一致性契約。
- 線程安全：單線程用非同步集合；多線程讀多寫少用
Collections.synchronizedXxx 或 CopyOnWriteArrayList；高併發用 ConcurrentHashMap/ConcurrentLinkedQueue。
- 避免暴露內部集合**：返回
Collections.unmodifiableList() 或防御性拷貝 new ArrayList<>(internal)。
