第 13 章 / 共 20 章
集合框架
List / Set / Map / Queue 与主流实现、选型与遍历陷阱
集合框架全景
Java 集合框架（java.util）由几个核心接口 + 各自实现组成。理解接口的语义和实现的取舍是高效写 Java 的基础。
Collection (顶层)
├── List 有序、可重复、按索引访问
│ ├── ArrayList 数组实现，随机访问快（90% 用它）
│ └── LinkedList 链表实现，头尾插入快
├── Set 不重复、一般无序
│ ├── HashSet 哈希表，O(1) 查找，最常用
│ ├── LinkedHashSet 保留插入顺序
│ └── TreeSet 红黑树，自动排序
└── Queue 队列，FIFO / 优先队列 / 双端队列
├── ArrayDeque 双端队列，作栈/队列都好用
├── LinkedList 也实现了 Queue
└── PriorityQueue 二叉堆，按优先级出队
Map (独立体系)
├── HashMap 哈希表，O(1)，最常用
├── LinkedHashMap 保留插入顺序（或访问顺序，做 LRU）
├── TreeMap 红黑树，按 key 自然排序
└── ConcurrentHashMap 并发安全，多线程必备List：ArrayList 主力
应用场景：99% 的"我要一个动态数组"——保存订单列表、查询结果、配置项。LinkedList 只在头尾频繁插入、不随机访问的少数场景下有优势，日常很少用。
// ListDemo.java
import java.util.ArrayList;
import java.util.List;
public class ListDemo {
public static void main(String[] args) {
List<String> users = new ArrayList<>();
users.add("Alice");
users.add("Bob");
users.add(1, "Carol"); // 在索引 1 插入
System.out.println(users); // [Alice, Carol, Bob]
System.out.println(users.get(0)); // Alice
System.out.println(users.size()); // 3
System.out.println(users.contains("Bob")); // true
System.out.println(users.indexOf("Bob")); // 2
users.remove("Carol");
users.set(0, "ALICE");
System.out.println(users);
// 子列表（视图，改它会影响原表）
List<String> sub = users.subList(0, 1);
System.out.println(sub);
}
}Set：去重三剑客
三种 Set 的应用场景：HashSet（最常用，只需要"去重"）；LinkedHashSet（去重且保留插入顺序，做"唯一列表"）；TreeSet（去重并自动排序，做"排行榜"）。
// SetDemo.java
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
public class SetDemo {
public static void main(String[] args) {
Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("go");
tags.add("java"); // 重复，不会再加
System.out.println(tags); // 顺序不保证
Set<String> ordered = new LinkedHashSet<>();
ordered.add("b"); ordered.add("a"); ordered.add("c");
System.out.println(ordered); // [b, a, c]
Set<Integer> sorted = new TreeSet<>();
sorted.add(3); sorted.add(1); sorted.add(2);
System.out.println(sorted); // [1, 2, 3]
}
}Map：键值存储
应用场景：用 ID 查用户、用 IP 查地理位置、用 key 缓存计算结果、统计词频。HashMap 是工作主力；LinkedHashMap 用于 LRU 缓存；TreeMap 用于范围查询（subMap / floorKey）；ConcurrentHashMap 用于多线程共享。
// MapDemo.java
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class MapDemo {
public static void main(String[] args) {
Map<String, Integer> stock = new HashMap<>();
stock.put("apple", 5);
stock.put("pear", 3);
System.out.println(stock.get("apple")); // 5
System.out.println(stock.getOrDefault("melon", 0)); // 0
System.out.println(stock.containsKey("apple")); // true
// 不存在则放入（避免覆盖）
stock.putIfAbsent("apple", 999);
System.out.println(stock.get("apple")); // 仍是 5
// 统计词频的经典写法
Map<String, Integer> freq = new HashMap<>();
for (String w : new String[]{"a", "b", "a", "c", "b", "a"}) {
freq.merge(w, 1, Integer::sum);
}
System.out.println(freq); // {a=3, b=2, c=1}
// 遍历
for (Map.Entry<String, Integer> e : stock.entrySet()) {
System.out.println(e.getKey() + "=" + e.getValue());
}
// TreeMap 范围查询
TreeMap<Integer, String> grades = new TreeMap<>();
grades.put(60, "D"); grades.put(70, "C"); grades.put(80, "B"); grades.put(90, "A");
System.out.println(grades.floorEntry(75)); // <=75 的最大 key：70=C
System.out.println(grades.headMap(80)); // [<80) 的子图
}
}Queue 与 Deque
应用场景：广度优先搜索（BFS）、任务排队、撤销栈、消息缓冲。ArrayDeque 既能当队列（FIFO）又能当栈（LIFO），性能比 Stack 类更好，是主力。PriorityQueue 按优先级出队，做"待办按截止日期排序"或 Dijkstra。
// QueueDemo.java
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;
public class QueueDemo {
public static void main(String[] args) {
// FIFO 队列
Deque<String> q = new ArrayDeque<>();
q.offer("a"); q.offer("b"); q.offer("c");
while (!q.isEmpty()) {
System.out.println(q.poll()); // a b c
}
// 栈用法（用 push/pop）
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2); stack.push(3);
while (!stack.isEmpty()) {
System.out.println(stack.pop()); // 3 2 1
}
// 优先队列：默认小顶堆
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(3);
while (!pq.isEmpty()) {
System.out.println(pq.poll()); // 1 3 5
}
}
}不可变集合 List.of / Map.of（Java 9+）
应用场景：配置常量、传递只读视图、避免下游修改。List.of()、Set.of()、Map.of() 返回真正不可变的集合（add/remove 抛异常）；元素不能为 null。
// Immutable.java
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Immutable {
static final List<String> PROFILES = List.of("dev", "staging", "prod");
static final Map<String, Integer> LIMITS = Map.of(
"free", 100,
"pro", 10_000,
"max", Integer.MAX_VALUE
);
public static void main(String[] args) {
System.out.println(PROFILES);
System.out.println(LIMITS);
// PROFILES.add("x"); // 抛 UnsupportedOperationException
// 想从可变集合做一个不可变副本：
List<Integer> source = new java.util.ArrayList<>(List.of(1, 2, 3));
List<Integer> readonly = List.copyOf(source);
System.out.println(readonly);
}
}遍历与 ConcurrentModificationException 陷阱
在 for-each 遍历过程中调集合的 add/remove 会抛 ConcurrentModificationException。要边遍历边删，用迭代器自己的 remove() 方法，或者用 removeIf()。
// IterationTrap.java
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class IterationTrap {
public static void main(String[] args) {
List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5));
// ❌ 抛 ConcurrentModificationException
// for (int n : nums) {
// if (n % 2 == 0) nums.remove(Integer.valueOf(n));
// }
// ✅ 用 Iterator.remove()
Iterator<Integer> it = nums.iterator();
while (it.hasNext()) {
if (it.next() % 2 == 0) it.remove();
}
System.out.println(nums); // [1, 3, 5]
// ✅ 更简洁：removeIf (Java 8+)
List<Integer> nums2 = new ArrayList<>(List.of(1, 2, 3, 4, 5));
nums2.removeIf(n -> n % 2 == 0);
System.out.println(nums2); // [1, 3, 5]
}
}Collections 工具类
Collections（注意是"复数"）是个工具类，提供排序、查找、最大最小、洗牌、反转、不可变包装等静态方法。Java 8 后部分功能在 List.sort / stream 上有更顺手的写法。
// CollectionsUtil.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class CollectionsUtil {
public static void main(String[] args) {
List<Integer> nums = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6));
Collections.sort(nums);
System.out.println(nums); // 升序
Collections.sort(nums, Comparator.reverseOrder());
System.out.println(nums); // 降序
System.out.println(Collections.max(nums));
System.out.println(Collections.min(nums));
Collections.shuffle(nums);
Collections.reverse(nums);
System.out.println(nums);
List<String> readonly = Collections.unmodifiableList(new ArrayList<>(List.of("a", "b")));
// readonly.add("c"); // UnsupportedOperationException
}
}