java.util 集合根接口：Collection（單列）與 Map（雙列）。Collection 下分 List（有序、可重複）、Set（無序、唯一）、Queue（佇列）。并發集合位於 java.util.concurrent。
Collection<Integer> c = new ArrayList<>();
c.add(1); c.addAll(List.of(2,3));
c.contains(1); c.containsAll(List.of(1,2));
c.remove(1); c.removeAll(List.of(2,3));
c.retainAll(List.of(1)); // 交集
c.clear(); c.isEmpty(); c.size();
Object[] arr = c.toArray(); // 或 c.toArray(new Integer[0])
Iterator<Integer> it = c.iterator(); // 唯一遍歷方式
// foreach 底層調用 iterator()
for (Integer i : c) { ... }| 實現 | 底層結構 | 線程安全 | 隨機訪問 | 插入刪除 | 典型場景 |
|---|---|---|---|---|---|
| ArrayList | 動態數組 | 否 | O(1) ✓ | 尾部 O(1)，中間 O(n) | 默認首選，頻繁讀、少寫 |
| LinkedList | 雙向鏈表 | 否 | O(n) ✗ | 首尾 O(1)，中間 O(n) | 頻繁首尾增刪、佇列/棧 |
| Vector | 動態數組 | 是 (synchronized) | O(1) | 同 ArrayList | 遺留代碼，性能差，推薦 Collections.synchronizedList 或 CopyOnWriteArrayList |
| CopyOnWriteArrayList | 數組 + COW | 是 (寫時復制) | O(1) | O(n) 複制整個數組 | 讀多寫少、遍歷佔比高、無鎖讀 |
默認初始容量 10，擴容 1.5 倍（newCapacity = oldCapacity + (oldCapacity >> 1)）。ensureCapacity 可預分配減少拷貝。
Deque<String> deque = new LinkedList<>();
deque.addFirst("a"); deque.addLast("b");
deque.push("c"); // 棧
deque.pop();
deque.offer("d"); // 隊列
deque.poll();| 實現 | 底層 | 有序性 | Null 支持 | 線程安全 | 時間複雜度 |
|---|---|---|---|---|---|
| HashSet | HashMap | 無序 | 允許 1 個 | 否 | O(1) |
| LinkedHashSet | LinkedHashMap | 插入序 | 允許 1 個 | 否 | O(1) |
| TreeSet | TreeMap (紅黑樹) | 自然序/Comparator | 不允許 | 否 | O(log n) |
| CopyOnWriteArraySet | COW ArrayList | 插入序 | 允許 | 是 | O(n) |
| ConcurrentSkipListSet | 跳表 | 自然序 | 不允許 | 是 | O(log n) |
依賴 hashCode() 定桶位，equals() 精確比較。不可變對象作為元素最安全。若元素可變且參與 hashCode/equals，修改後會導致「找不到元素」。
class MyKey { int id; @Override public boolean equals(Object o) { return this.id == ((MyKey)o).id; } @Override public int hashCode() { return id; } }Set<Student> set = new TreeSet<>(Comparator.comparing(Student::getScore).reversed()
.thenComparing(Student::getName));
set.add(new Student("A", 90));
set.add(new Student("B", 90)); // 同分按名字序| 實現 | 底層 | 有序性 | Null Key/Value | 線程安全 | JDK 8+ 優化 |
|---|---|---|---|---|---|
| HashMap | 數組+鏈表/紅黑樹 | 無序 | 允許 1 null key，多 null value | 否 | 鏈表轉紅黑樹 (TREEIFY_THRESHOLD=8) |
| LinkedHashMap | HashMap + 雙向鏈表 | 插入序/訪問序 | 允許 | 否 | 支持 LRU (accessOrder=true) |
| Hashtable | 數組+鏈表 | 無序 | 不允許 null | 是 (synchronized) | 無 |
| TreeMap | 紅黑樹 | 自然序/Comparator | 不允許 null key | 否 | 無 |
| ConcurrentHashMap | 數組+鏈表/紅黑樹 + CAS/synchronized | 無序 | 不允許 null | 是 (分段鎖/細粒度鎖) | JDK 8 放棄 Segment，採用 Node 首節點 CAS + synchronized |
| ConcurrentSkipListMap | 跳表 | 自然序 | 不允許 null | 是 | 無鎖範圍查詢 |
loadFactor (默認 0.75)：空間換時間，過大導致碰撞，過小浪費空間。threshold = capacity * loadFactor：觸發擴容門檻。JDK 7：Segment 分段鎖（默認 16 段），寫鎖段，讀無鎖（volatile）。
JDK 8+：放棄 Segment，採用 synchronized (tab[i]) 鎖首節點 + CAS 操作，細粒度更細，擴容支持多線程協助 (ForwardingNode)。
List<String> unmod = Collections.unmodifiableList(list); // 只讀視圖
List<String> sync = Collections.synchronizedList(new ArrayList<>()); // 同步包裝
List<String> empty = Collections.emptyList(); // 共享空列表
Collections.shuffle(list); // 洗牌
Collections.sort(list, Comparator.naturalOrder()); // 排序
int idx = Collections.binarySearch(sortedList, key); // 二分查找List.of("a", "b"); Set.of(1,2,3); Map.of("k1",1,"k2",2); Map.ofEntries(entry("k1",1), entry("k2",2));| 問題 | 陷阱 | 正解 |
|---|---|---|
| ArrayList vs Vector | Vector 線程安全就用它 | Vector 鎖粒度粗、擴容 2 倍、已淘汰；用 Collections.synchronizedList 或 CopyOnWriteArrayList |
| HashMap 多線程 put | 死循環 (JDK 7 擴容鏈表倒序) | JDK 8 不會死循環但會數據丟失/覆蓋；必須用 ConcurrentHashMap |
| 遍歷時刪除 | for-each 中 remove → ConcurrentModificationException | 用 Iterator.remove() / ListIterator / removeIf / Stream.filter |
| Map 遍歷方式 | keySet 循環 get | entrySet 遍歷 / forEach((k,v)->...) / keySet 只有 key 時 |
| Arrays.asList | 以為可增刪 | 返回固定長度 List，增刪拋異常；用 new ArrayList<>(Arrays.asList(...)) |
Java 集合框架設計精妙，掌握底層數據結構（數組、鏈表、紅黑樹、哈希表、跳表）、擴容機制、線程安全策略，能寫出高性能、無 Bug 的業務代碼。日常開發首選 ArrayList、HashMap、HashSet、ArrayDeque，並發場景首選 ConcurrentHashMap、CopyOnWriteArrayList、ConcurrentLinkedQueue，善用 Collections、Stream、List.of 簡化代碼。
