10.1 集合框架入门
先读过数组和接口，就可以从这里开始。
List<String>表示元素类型为 String 的列表，Map<String, Integer>表示 String 键到 Integer 值的映射；完整泛型规则在第12章展开。用约 30 分钟跑完 Java 17 示例后，你应当能根据访问方式、顺序、重复与并发要求，把选择缩小到合适的集合接口和实现。
数组当然能存名字，但长度要在创建时确定。人数超过估计就得换一块更大的数组；人数少又会留下未使用位置。插入中间时，后续元素仍要移动。
集合框架把扩容、查找、去重和队列操作封装成统一 API。它没有消除数据结构的成本。ArrayList.add(0, value) 依旧需要移动已有元素，HashMap 也依赖可靠的 hashCode 与 equals。
1. 数组仍有自己的位置
String[] fixedTeam = new String[3];
fixedTeam[0] = "张三";
fixedTeam[1] = "李四";
fixedTeam[2] = "王五";数组适合长度固定、需要存基本类型，或 API 明确要求数组的场景。集合适合规模变化、需要插入删除，或希望通过接口表达“列表、集合、队列、映射”的场景。
集合泛型不能直接使用基本类型，要写 List<Integer> 而不是 List<int>。这会发生装箱；大量数值计算时，基本类型数组或专用结构可能更合适。
2. 接口地图
Iterable<E>
└── Collection<E>
├── List<E>
│ ├── ArrayList<E>
│ └── LinkedList<E>
├── Set<E>
│ ├── HashSet<E>
│ ├── LinkedHashSet<E>
│ └── SortedSet<E> / NavigableSet<E>
│ └── TreeSet<E>
└── Queue<E>
├── Deque<E>
│ ├── ArrayDeque<E>
│ └── LinkedList<E>
└── PriorityQueue<E>
Map<K, V> // 不继承 Collection
├── HashMap<K, V>
├── LinkedHashMap<K, V>
└── SortedMap<K, V> / NavigableMap<K, V>
└── TreeMap<K, V>四类接口表达不同约束：
| 接口 | 主要问题 | 典型保证 |
|---|---|---|
List | 第几个元素是什么 | 有遭遇顺序、可重复、可按索引访问 |
Set | 这个值是否已经存在 | 按相等性规则不保留重复元素 |
Queue / Deque | 下一个或两端元素是什么 | 按队列策略访问，不提供通用索引 |
Map | 某个键对应什么值 | 每个键至多映射一个值 |
“有序”需要说清是哪种顺序。List 保持元素的遭遇顺序；LinkedHashSet 和默认构造的 LinkedHashMap 保持插入顺序（LinkedHashMap 也可配置为访问顺序）；TreeSet/TreeMap 按自然顺序或 Comparator 排序；HashSet/HashMap 不承诺迭代顺序。
3. 三分钟运行一遍
先准备临时目录：
chapter10_choice_root=$(mktemp -d)
readonly chapter10_choice_root
mkdir -p "$chapter10_choice_root/out"
cd "$chapter10_choice_root"保存为 CollectionChoiceDemo.java：
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
public class CollectionChoiceDemo {
public static void main(String[] args) {
List<String> claims = new ArrayList<>();
claims.add("张三");
claims.add("李四");
claims.add("张三");
Set<String> uniquePeople = new LinkedHashSet<>(claims);
Queue<String> waiting = new ArrayDeque<>();
waiting.offer("张三");
waiting.offer("李四");
Map<String, Integer> stock = new LinkedHashMap<>();
stock.put("零件", 50);
stock.put("木材", 30);
stock.merge("零件", -2, Integer::sum);
checkEquals(List.of("张三", "李四", "张三"), claims);
checkEquals(List.of("张三", "李四"), List.copyOf(uniquePeople));
checkEquals("张三", waiting.poll());
checkEquals(48, stock.get("零件"));
System.out.println("领料记录：" + claims);
System.out.println("去重人员：" + uniquePeople);
System.out.println("下一位：" + waiting.peek());
System.out.println("库存：" + stock);
System.out.println("集合选型检查通过");
}
static void checkEquals(Object expected, Object actual) {
if (!Objects.equals(expected, actual)) {
throw new AssertionError("expected=" + expected + ", actual=" + actual);
}
}
}编译并运行：
javac --release 17 -encoding UTF-8 -Xlint:all -d out CollectionChoiceDemo.java
java -cp out CollectionChoiceDemo预期输出：
领料记录：[张三, 李四, 张三]
去重人员：[张三, 李四]
下一位：李四
库存：{零件=48, 木材=30}
集合选型检查通过保存需要的输出后清理：
cd
ls -ld -- "$chapter10_choice_root"
rm -r -- "$chapter10_choice_root"示例只演示集合操作，库存的非负校验、整数溢出和并发扣减都需要额外契约。这里刻意使用 LinkedHash 实现，让输出顺序成为契约。若换成 HashSet 或 HashMap，测试应比较内容而不是字符串显示顺序。
4. 先选接口，再选实现
变量通常声明为需要的最窄接口：
List<String> names = new ArrayList<>();
Map<String, Integer> stock = new HashMap<>();调用方若只需要 List，就不应依赖 ArrayList 的特有方法。以后更换实现时，受影响代码会更少。需要 NavigableMap 的范围查询时，则应声明出这个能力，不能把类型缩到只剩 Map。
按顺序问这些问题：
- 通过 key 查 value，还是按元素本身遍历？前者选 Map。
- 重复元素是否有意义？没有则选 Set。
- 需要索引、FIFO、LIFO，还是优先级？分别考虑 List、Queue/Deque、PriorityQueue。
- 迭代顺序是否属于业务结果？需要插入顺序用 LinkedHash，需要排序与范围查询用 Tree/Navigable。
- 是否允许
null？不同实现契约不同，ArrayDeque 和List.of都拒绝 null。 - 是否存在并发写入？普通集合不自动成为线程安全容器。
5. 常见实现的成本模型
下表的 Set/Map 成本指单次查找、添加或删除，不包括遍历全体元素。它列出 Java 17 常见实现的典型复杂度，前提是数据结构未被并发破坏、哈希分布合理、比较器成本可控：
| 需求 | 常见选择 | 典型成本与边界 |
|---|---|---|
| 按索引读取 | ArrayList | get O(1)，中间插入/删除 O(n) |
| 两端队列 | ArrayDeque | 两端操作摊销 O(1)，不允许 null |
| 链表两端操作 | LinkedList | 端点 O(1)，按索引定位 O(n) |
| 无排序去重 | HashSet | 期望 O(1)，迭代顺序未定义 |
| 保持插入顺序去重 | LinkedHashSet | 期望 O(1)，维护链接有额外开销 |
| 排序去重/范围 | TreeSet | O(log n)，相等性由比较结果决定 |
| 键查找 | HashMap | 期望 O(1)，顺序未定义 |
| 有序键与范围 | TreeMap | O(log n)，提供 NavigableMap 操作 |
大 O 不等于固定耗时。连续内存、对象分配、缓存命中、比较器和数据规模都会影响实际结果。需要性能结论时用代表性数据与 JMH 测量，不能复制某台机器的一组毫秒数。
6. Queue 的两组方法
Queue 为容量不足或队列为空提供两组方法；非法元素、类型不匹配等其他错误仍可能抛异常，offer 并不表示“绝不抛错”：
| 操作 | 返回特殊值 | 失败时抛异常 |
|---|---|---|
| 入队 | offer | add |
| 出队 | poll | remove |
| 查看队首 | peek | element |
空队列的 poll/peek 返回 null。ArrayDeque 禁止存 null，因而 null 可以明确表示“没有元素”。有界队列中，offer 还能用 false 表示容量已满。
用作栈时优先声明 Deque<E>，调用 push、pop、peek；遗留的 Stack 继承 Vector，API 与同步模型都不适合新设计。
PriorityQueue 的 poll 返回当前最小元素（或由 Comparator 定义的最高优先级），但直接迭代 PriorityQueue 不保证整体排序。需要排序输出时应逐个 poll 副本，或另行排序。
7. 遍历与修改要分开考虑
for (String claim : claims) {
System.out.println(claim);
}
for (Map.Entry<String, Integer> entry : stock.entrySet()) {
System.out.println(entry.getKey() + " = " + entry.getValue());
}
stock.forEach((item, count) ->
System.out.println(item + " -> " + count));遍历 Map 的键和值时，entrySet 能同时取得两者。只需要键时用 keySet，只需要值时用 values。
增强 for 遍历 Iterable 时使用 Iterator，遍历数组时则按索引访问。遍历期间直接调用集合自身的结构性修改方法，常见实现会快速失败并抛 ConcurrentModificationException。这是一种尽力检测程序错误的机制，不是线程安全保证。删除规则在下一篇展开。
8. 可变性、null 与并发不是统一规则
“Java 集合允许 null”这句话不成立。HashMap 允许一个 null key 和多个 null value，TreeMap 在自然排序下拒绝 null key，ArrayDeque 拒绝 null，List.of/Set.of/Map.of 也拒绝 null。
同样，接口不保证可修改：List.of 返回不可修改列表；Arrays.asList 返回固定大小的数组视图；Collections.unmodifiableList 返回只读包装，但底层列表仍可能被其他引用修改。
普通 ArrayList、HashMap 等不支持无同步的并发写入。需要并发语义时先定义复合操作，再选择 ConcurrentHashMap、阻塞队列、外部锁或不可变快照。给每个方法套同步不一定能保护“检查后写入”这一整段逻辑。
9. 语言边界
Python 的 list 支持动态增长；在常见 CPython 实现中，它使用动态数组，头部队列通常用 collections.deque；Python 3.7 起 dict 保持插入顺序，但不按 key 自动排序。
C++ 的 vector、deque、list、unordered_map 与 Java 类型只能做概念对照。迭代器失效、内存所有权和并发契约都不同。本章只验证 Java 17 示例。
最后检查容器契约
为一份领料记录分别尝试 List、Set 和 Queue，写下每次更换后丢失或新增的操作能力。再确认集合是否允许 null，以及交给调用方后是否仍可修改。
查阅 Java 17 的正式契约
- Java Collections Framework 概览：接口层次、可选操作和常见实现。
Collection与Map：两条彼此独立的接口主线。Queue与Deque：返回特殊值和抛异常的两组操作。- OpenJDK JMH：需要比较实现性能时，用基准测试验证真实工作负载。
下一步：整理 List 账本
下一篇继续整理领料记录。你会实际检查 ArrayList 与 LinkedList 的成本、subList 和 Arrays.asList 的共享关系，以及遍历删除为什么会失败。