ArrayList · LinkedList · ArrayDeque · HashSet · TreeSet · PriorityQueue · DelayQueue · HashMap · TreeMap · 扩容 · 二叉堆 · fail-fast

常用集合怎么选：先问“按什么找”，再问“底下是数组还是节点”

选集合只看两件事。第一，你按什么找数据：按位置找用 List，判断有没有用 Set，按 key 找用 Map，先进先出或者“最早到期的先出”用 Queue。第二，底下是连续的数组，还是一个个散开的节点：数组省内存、遍历快，但在中间插入要挪一大片；节点插入快，可每个元素多占 20 来个字节，找第 i 个还得一路走过去。大部分时候赢家是数组那一边：ArrayList、ArrayDeque、PriorityQueue。

全景：一个订单对象的一生 · 第 8、9 站地图：J01 · 常用集合怎么选上一页：面向对象和泛型实验：JDK 17.0.20 实测

①为什么需要：订单簿里的五种“找法”

在全景第 8 站，这一步要解决的是：订单 9527 new 出来以后要存起来，而且以后要按好几种方式把它找回来：按下单先后列出订单行，按用户 1024 找他所有的订单，判断同一个请求号是不是重复提交，按时间段对账。第 9 站还要从几十万个待付款订单里，每次只拿出最早到期的那一个。一个集合干不好所有的事。

全景第 8、9 站 · 订单 9527 存进来以后，要怎么找回去 订单 9527用户 1024 · 12:00 下单 按先后、按位置订单行 0、1、2… 按 key：用户 1024 的订单给一个 key，直接拿到 有没有：请求号见过吗重复提交只认第一次 最早到期的先出第 9 站：30 分钟没付就取消 按顺序、按范围12:05 到 12:15 下的单 两头进出最近 5 单的滑动窗口 ArrayList HashMap<Long, List> HashSet 第 8 站，订单行 第 8 站，userOrders 幂等 右边两列：PriorityQueue（DelayQueue 里面就是它）、TreeMap、ArrayDeque。六种找法，六种集合。
需求工作要用，也是面试必考：集合是每天写得最多的代码，选错了不报错，只是慢、费内存，等数据量上来才暴露。⑤要能直接抄进交易靶场，⑥先讲最容易踩的坑。

②没有它会怎样：什么都往一个 ArrayList 里放

最省事的写法是只用一个 ArrayList：查用户的订单就从头扫一遍，判重就 contains，找最早到期就每次扫出最小值。数据少时毫无问题，数据一多，每一步都变成“从头数到尾”。

实测 JDK 17，2 核 ARM，同一份数据各做一遍（中位数）。条形按对数刻度画，否则短的那根根本看不见。

按用户查订单 ×1 万1476.8 ms
　改用 HashMap.get0.65 ms
到期先后取出 2 万个511.8 ms
　改用 PriorityQueue4.0 ms
请求号去重 2 万个249.1 ms
　改用 HashSet1.0 ms

反过来的误用也很常见：听说“LinkedList 插入快”，就用它装订单行，再用 get(i) 循环读。2 万个元素按下标读一遍，ArrayList 0.2 ms，LinkedList 151 ms（实测），原因在④-2。

③相邻方案：集合家族一张图，加一条选择规则

Collection Map List：按位置 Set：有没有 Queue / Deque：谁先出 按 key 找 ArrayList数组 · 首选 LinkedList双向链表 · 很少需要 HashSet哈希表 · 无序 LinkedHashSet哈希表 + 链表 · 插入序 TreeSet红黑树 · 有序、范围 ArrayDeque环形数组 · 队列和栈首选 PriorityQueue二叉堆（数组）· 最小先出 DelayQueue堆 + 锁 · 到期才出 HashMap哈希表 · 下一页 LinkedHashMap插入序 / 访问序（LRU） TreeMap红黑树 · 有序、范围
每个格子下面那行小字是“底下的数据结构”，选集合就是选它。多个线程同时读写的版本（ConcurrentHashMap、CopyOnWriteArrayList、阻塞队列）在 java.util.concurrent，J02 讲。
你要的操作选不选为什么
按先后存、按下标读、遍历ArrayListLinkedList数组连续，下标直接算地址
判重、“见过没有”HashSetList.contains按哈希直接定位，不用从头比
按 key 找HashMapList 全表扫同上
要有序、要按范围查（某时间段）TreeMap / TreeSetHashMap 再排序红黑树一直保持有序
保持插入顺序的去重 / LRU 缓存LinkedHashSet / LinkedHashMapHashSet哈希表外再串一条链
先进先出队列、栈、两头进出ArrayDequeLinkedList、Stack环形数组，两头都是 O(1)，还省内存
每次只要最小（最早到期、最高优先级）PriorityQueue每次排序堆只维护“顶上最小”，进出 O(log n)

选择规则：先按“你按什么找”选接口（List / Set / Map / Queue），再默认选数组那一个实现（ArrayList、ArrayDeque、PriorityQueue），要有序或范围才上 Tree，要保留插入顺序才上 Linked。LinkedList 几乎不用选。

④原理：数组和节点，哈希、树和堆

先知道这些
  • 大 O：O(1) 是“和数据量无关”，O(n) 是“数据量翻倍，时间翻倍”，O(log n) 是“数据量翻倍，只多一步”。100 万个元素，log₂ 约等于 20。
  • 集合里放的是引用：ArrayList<Order> 的数组里每格只是一个指向 Order 的指针，64 位 JVM 开了指针压缩时占 4 字节，Order 本身在堆的别处。见 JVM 内存结构。
  • CPU 缓存行：CPU 从内存读数据，一次搬 64 字节一块，放进缓存。挨在一起的数据，读第一个就把后面的一起带进来了。

④-1ArrayList：一个会自己换大房子的数组

elementData（容量 10）+ size = 7 9527 9529 9532 … … … … 新 [0][size] ← add(x) 放这里，O(1) get(i)地址 = 起点 + i × 4 字节，一步算出，O(1) 满了：换一个 1.5 倍的新数组，整体拷过去 旧：10 格，满 copy 新：15 格（10 + 10 >> 1），旧数组等 GC 回收 在头部插入：后面所有元素都要往后挪一格 新 System.arraycopy 整体右移 size 格，O(n) 5 万次头插：332 ms 实测；ArrayDeque.addFirst 0.7 ms
JDK 17 源码：DEFAULT_CAPACITY = 10，但 new ArrayList<>() 时只给一个空数组，第一次 add 才真正分配 10 格；扩容取 oldCapacity >> 1 作为增量，即 1.5 倍。尾部追加偶尔要拷贝，但拷贝的总量摊到每次 add 上是常数，所以叫“均摊 O(1)”。

④-2LinkedList：每个元素一个节点，靠指针串起来

first → Node · 24 字节prev | item | next Nodeprev | item | next Nodeprev | item | next Nodeprev | item | next ← last get(i)：从 first 或 last（看 i 离哪头近）一个一个走 next / prev，O(n)。在循环里 get(i)，整个循环就成了 O(n²)。 在已知节点旁插入：改 4 个指针，O(1)。可“找到那个节点”这一步本身就是 O(n)，除非你手里正拿着迭代器。

④-3为什么“理论上插入快”的 LinkedList 很少赢

数组ArrayList、ArrayDeque、PriorityQueue

  • 元素引用挨着放，一个 64 字节的缓存行能装 16 个，CPU 顺序读时还会提前把后面的预取进来
  • 每个元素只多 4 字节（一格引用）实测 3.7 字节
  • 对象少，GC 要扫的东西少
  • 中间插入、删除要挪后面所有元素

节点LinkedList

  • 已知位置插入、删除只改指针
  • 节点散在堆里，读下一个就要再跳一次内存，缓存帮不上
  • 每个元素多一个 Node 对象 实测 24 字节，是数组的 6 倍
  • 按下标访问要一路走过去
决定胜负的约束：内存比 CPU 慢得多，真正贵的是“去内存里取下一个”。大 O 只数步数，不管每一步要不要等内存。所以同样是 O(n) 的遍历，ArrayList 1.6 ms，LinkedList 3.8 ms；而 LinkedList 唯一占优的“在中间插入”，真实代码里很少有手里正握着那个节点的情况。要两头进出，ArrayDeque 也是 O(1)，还省内存。JDK 的作者 Joshua Bloch 自己也说过，他写了 LinkedList，但从来不用它。

④-4Set 和 Map：哈希表直接定位，红黑树保持有序

HashSet / HashMap按哈希分桶

用 key 的 hashCode() 算出桶的下标，直接去那个桶里用 equals 比。平均 O(1)，不保证顺序。HashSet 就是一个只用 key 的 HashMap：源码里每个 value 都是同一个 PRESENT 对象。哈希怎么算、桶满了怎么扩容、链表什么时候变树：下一页讲。

实测 每个元素约 41.5 字节（一个 32 字节的 Node 加桶数组的一格）。

TreeSet / TreeMap红黑树

一棵自平衡的二叉搜索树：左边都比我小，右边都比我大，树高始终在 2·log₂n 以内。查、插、删都是 O(log n)，遍历天然有序，所以能做 subMap(12:05, 12:15)、firstKey()、ceilingKey() 这种范围查询。

判断“是不是同一个”用的是 compareTo / Comparator 返回 0，不是 equals（坑见⑥）。实测 每个元素约 40 字节。

④-5Queue：环形数组和二叉堆

PriorityQueue<CancelTask>：按到期时间（这里写成分钟）组织的二叉堆 30 33 31 40 35 38 32 堆顶：永远是最小，peek() O(1) 它其实存在一个数组里：queue[] 30 33 31 40 35 38 32 [0] 下标 i 的孩子：2i+1、2i+2；父亲：(i−1)/2 只保证一件事：每个节点 ≤ 它的两个孩子 offer(x)：放到数组末尾，和父亲比，比父亲小就交换， 一路往上浮，最多 log₂n 次。 poll()：拿走 [0]，把末尾那个挪到 [0]，和较小的孩子 比，比它大就交换，一路往下沉，最多 log₂n 次。 兄弟之间、不同分支之间没有顺序，所以数组 [30,33,31,40…] 不是排好序的，遍历、toString 都是乱的（⑤里实测）。 DelayQueue = 这个堆 + 一把 ReentrantLock + 一个 Condition： take() 看堆顶，没到期就睡到它到期为止（第 9 站）。
ArrayDeque 是另一种数组队列：环形数组加 head、tail 两个下标，头尾进出都只是挪下标，满了才扩容（JDK 17：容量小于 64 时翻倍再加 2，之后每次加 50%，PriorityQueue 也是这个规则）。它不允许放 null，因为 null 被用来表示“空格”。
为什么用堆，不用一直排好序的列表？超时取消只关心“最早的那一个”。一直保持全部有序（有序数组插入 O(n)，红黑树 O(log n) 但每个元素 40 字节、指针满天飞）是在做多余的事。堆只维护“顶上最小”这一条，放在一个连续数组里，进出都是 O(log n)。实测 2 万个任务依次取出：PriorityQueue 4.0 ms，TreeMap 9.6 ms，每次扫最小值 512 ms。

④-6先猜，再看实测

先选一个场景。

实测 数字来自⑤的 Bench 和 Memory：JDK 17.0.20，2 核 ARM，-Xms1g -Xmx1g，每项热身 5 轮、测 7 轮取中位数，不是 JMH，只看量级。整套跑了两遍，几十毫秒以上的项两次相差在 10% 以内，3 毫秒以下的项最多差到 1.7 倍。

最少语法

List<OrderLine> lines = new ArrayList<>(n);                 // 知道大小就给容量
Map<Long, List<Order>> byUser = new HashMap<>();
byUser.computeIfAbsent(1024L, k -> new ArrayList<>()).add(order);
Set<String> seen = new HashSet<>();
if (!seen.add(requestId)) return;                            // add 返回 false = 已经有了
Deque<Long> recent = new ArrayDeque<>();  recent.addLast(id);  recent.removeFirst();
PriorityQueue<CancelTask> q = new PriorityQueue<>();        // 元素实现 Comparable，或传 Comparator
q.offer(task);  q.peek();  q.poll();
NavigableMap<Instant, List<Order>> byTime = new TreeMap<>();
byTime.subMap(from, true, to, false);                        // 范围查询

不可变集合（List.of、List.copyOf）、Arrays.asList、遍历时删除、JDK 21 的 SequencedCollection：放到第⑥步。

⑤亲眼看到：交易靶场的订单簿

OrderBook 一个类，五种找法各用一种集合：userOrders、seenRequests、cancelQueue、byTime、recent。下 8 单（其中一单重复提交），然后按用户查、按时间段查、两次扫超时，最后演示四个坑。完整代码和 Bench、Memory 两个粗测：study-labs/java/javase/collections-choose →

1OrderBook.java 节选，JDK 17
// 第 8 站：按用户找 → Map；同一用户按先后 → List
Map<Long, List<Order>> userOrders = new HashMap<>();
// 重复提交只认第一次 → Set
Set<String> seenRequests = new HashSet<>();
// 第 9 站：最早到期先出 → 堆
PriorityQueue<CancelTask> cancelQueue = new PriorityQueue<>();
// 对账：按时间范围 → 红黑树；同一时刻可能多单
NavigableMap<Instant, List<Order>> byTime = new TreeMap<>();
// 最近 5 单 → 两头进出
Deque<Long> recent = new ArrayDeque<>();

Optional<Order> place(String req, long uid,
                      List<OrderLine> lines, Instant now) {
  if (!seenRequests.add(req)) return Optional.empty();
  List<OrderLine> copy = new ArrayList<>(lines.size());
  copy.addAll(lines);
  Order o = new Order(nextId++, uid, List.copyOf(copy), now);
  userOrders.computeIfAbsent(uid, k -> new ArrayList<>()).add(o);
  cancelQueue.offer(new CancelTask(o.id(),
                    now.plus(Duration.ofMinutes(30))));
  byTime.computeIfAbsent(now, k -> new ArrayList<>()).add(o);
  recent.addLast(o.id());
  if (recent.size() > 5) recent.removeFirst();
  return Optional.of(o);
}

List<Long> expire(Instant now) {
  List<Long> out = new ArrayList<>();
  while (!cancelQueue.isEmpty()
         && !cancelQueue.peek().deadline().isAfter(now))
    out.add(cancelQueue.poll().orderId());
  return out;
}
2运行 JDK 17.0.20，2 核 ARM
$ cd java && mvn -q -pl javase/collections-choose compile
$ java -cp javase/collections-choose/target/classes \
    labs.javase.collections_choose.OrderBook
== 下单 ==
  req-1 → 9527
  req-1 再提交一次 → 重复，忽略
  用户 1024 的订单号：[9527, 9529, 9532]
  最近 5 单：[9530, 9531, 9532, 9533, 9534]
== 按时间范围查（TreeMap.subMap）==
  12:05:00Z → [9530]
  12:08:00Z → [9534]
  12:14:00Z → [9533]
== 超时取消（PriorityQueue）==
  toString 看到的顺序（不是排好序的！）：
    [9527, 9531, 9532, 9534, 9530, 9529, 9533, 9528]
  堆顶 peek()：9527，到期 12:30:00Z
  12:40 扫一次，取消：[9527, 9532, 9531, 9529, 9530, 9534]
  12:50 扫一次，取消：[9533, 9528]
== 坑 ==
  for-each 里 remove → ConcurrentModificationException
  改用 removeIf → 剩 [9529, 9532]
  Arrays.asList(...).add → UnsupportedOperationException
  List.of 放 null → NullPointerException
  TreeSet 按价格比较，放两件不同商品 → size = 1

时间输出略去了日期。两次 expire 取出的顺序就是到期先后，而 toString 打出的是堆数组的原样顺序。

到这里已经能交差了：交易靶场的订单簿按“怎么找”选好了集合，重复提交被挡掉，超时任务按到期先后取出，时间段对账走红黑树。
已知还没处理的细节：遍历时删除（⑥-1）、PriorityQueue 不能拿来遍历（⑥-1）、TreeSet 的比较器吞元素（⑥-1）、多线程同时写这些集合（J02）、内存里的队列重启就丢（⑥-3）。

⑥细节·规范·优化

第一圈

注意事项：不知道就会出事故

坑 1for-each 里 remove，抛 ConcurrentModificationException← ④-1 数组下标
现象
遍历用户的订单，把已取消的删掉，直接抛异常；有时又不抛，却漏删了一个。⑤ 坑段
根源
for-each 用的是迭代器，它记着一个游标。你绕过迭代器删元素，后面的元素整体前移，游标就对不上了。所以集合维护一个修改计数 modCount，迭代器每走一步都核对它，对不上就立刻抛（fail-fast）。“有时不抛”是删的恰好是倒数第二个，hasNext() 直接返回 false，循环结束了。
做法
list.removeIf(o -> …)，或者显式用 Iterator 并调它的 remove()。
坑 2LinkedList 配 get(i) 循环，O(n²)← ④-2 节点
现象
接口返回的 List 是 LinkedList，下游用 for (int i…) list.get(i) 读，2 万条就要 151 ms，10 万条要几秒。实测
根源
每次 get(i) 都从一头走到第 i 个。
做法
遍历一律用 for-each；对外返回 ArrayList 或不可变 List；必须按下标访问时先 instanceof RandomAccess。
坑 3以为 PriorityQueue 是排好序的← ④-5 堆只管堆顶
现象
打日志、for-each 遍历待取消订单，顺序是乱的；拿遍历出来的第一个当“最早到期”，有时对、有时错。⑤ 实测
根源
堆只保证父亲不大于孩子，兄弟之间、分支之间没有顺序。
做法
只用 peek / poll；要有序列表就 poll 到空，或者另外排序一份。要“有序还能遍历”就用 TreeSet / TreeMap。
坑 4TreeSet 的比较器把不同元素当成重复← ④-4 compareTo 判等
现象
按价格比较的 TreeSet，放进两件同价不同商品，只剩一件，静默丢数据。⑤ 实测 size = 1
根源
红黑树里“相等”就是比较结果为 0，它根本不调 equals。
做法
比较器要和“是不是同一个”一致：comparing(OrderLine::price).thenComparing(OrderLine::skuId)。
坑 5Arrays.asList 和 List.of 不是普通 ArrayList历史原因
现象
Arrays.asList(…).add 抛 UnsupportedOperationException；List.of 放 null 抛 NPE，contains(null) 也抛。⑤ 实测
根源
Arrays.asList 是包在原数组外面的定长视图（JDK 1.2 起），能 set 不能增删，改它就是改原数组；List.of（JDK 9）是不可变集合，设计上就拒绝 null。
做法
要能改就 new ArrayList<>(Arrays.asList(…))；对外返回用 List.copyOf，表明“别改”。
坑 6拿 ArrayList 当队列，remove(0)← ④-1 头部要挪
现象
“最近 N 单”的窗口用 ArrayList，每来一单 remove(0)，窗口一大就慢。
根源
删头部要把后面全部前移，和头插一样 O(n)。
做法
ArrayDeque 的 addLast / pollFirst，两头都是 O(1)。
第二圈

使用规范

默认选数组那一个

List 用 ArrayList，队列和栈用 ArrayDeque，不用 LinkedList 和 Stack（Stack 继承 Vector，每个方法都加了锁）。

节点开销、缓存不友好、无谓的锁。

知道大概多少，就给初始容量

new ArrayList<>(lines.size())；HashMap 要放 n 个，容量给 n / 0.75 + 1（JDK 19 起可以直接 HashMap.newHashMap(n)）。

一路扩容的拷贝和临时垃圾。实测 100 万个：默认 18.5 ms，预设 14.5 ms。

对外返回不可变集合

getter 返回 List.copyOf(lines) 或 Collections.unmodifiableList，参数收进来时复制一份。

调用方改了你的内部状态（上一页的封装）。

集合里不放 null

不可变集合、ArrayDeque、ConcurrentHashMap 都拒绝 null；map.get(k) == null 也分不清是“没有”还是“值为 null”。

NPE 和语义含糊。

key 和 Set 元素用不可变类型

用 Long、String、record 做 key；按 id 判等的实体，不要按会变的字段算 hashCode。

放进去以后改了字段，再也找不到（上一页坑 6，下一页细讲）。

多线程共享时换并发集合

本页这些都不是线程安全的。全景第 8 站的 userOrders 被多个 Tomcat 线程同时写，就要换 ConcurrentHashMap。

丢数据、死循环（J02 讲）。

第三圈

深处

为什么扩容是 1.5 倍，不是每次加 10 格

每次只加固定格数，n 次追加要拷贝 1 + 2 + … ≈ n²/(2×10) 次，是 O(n²)。按比例扩容，拷贝总量是 n + n/1.5 + n/1.5² + … ≈ 3n，摊到每次 add 是常数，这才有了“均摊 O(1)”。

比例选 1.5 而不是 2，是在“拷贝次数”和“浪费的空闲格子”之间取的折中：翻倍最多空着一半，1.5 倍最多空着三分之一。代价是 ArrayList 默认情况下平均多占一些（实测 一路扩容 5.2 字节/元素，预设容量 3.7）。

DelayQueue 怎么做到“到期才出”

JDK 17 源码：一个 PriorityQueue、一把 ReentrantLock、一个 Condition available、一个 Thread leader。take() 看堆顶：到期就 poll；没到期，第一个等待的线程当 leader，awaitNanos(剩余时间) 精确地睡到堆顶到期，其他线程无限期等，避免一群线程同时醒来空转。新放进来的任务如果成了新堆顶，就唤醒等待的线程重新算。

它全在内存里：进程重启，几十万个待取消任务全丢。生产上要么定时扫库（WHERE status = 'CREATED' AND deadline < now()），要么用消息队列的延迟消息（J08）。

版本差异：这几年集合多了什么

JDK 8removeIf、computeIfAbsent、forEach、Stream；ArrayList 默认先给空数组，第一次 add 才分配
JDK 9List.of、Set.of、Map.of 不可变集合；ArrayDeque 重写，容量不再强制是 2 的幂
JDK 10List.copyOf、Collectors.toUnmodifiableList
JDK 16stream.toList()（⑤ 里用的，返回不可变 List）
JDK 19HashMap.newHashMap(n) 按元素个数建
JDK 21SequencedCollection（JEP 431）：getFirst()、getLast()、reversed()，List、Deque、LinkedHashSet 统一有了“头和尾”

Set 和 Map 的三种“顺序”

  • HashSet / HashMap：没有顺序，遍历顺序随容量和哈希变，不能依赖，换个 JDK 版本或多放几个元素就可能变。
  • LinkedHashSet / LinkedHashMap：在哈希表外再串一条双向链表，按插入顺序遍历；LinkedHashMap 构造时传 accessOrder = true 就按访问顺序，再覆盖 removeEldestEntry，十几行就是一个 LRU 缓存。
  • TreeSet / TreeMap：按 key 的大小，支持范围查询。
面试官会怎么问
ArrayList 和 LinkedList 有什么区别？什么时候用 LinkedList？

数组和双向链表。ArrayList 按下标 O(1)、尾插均摊 O(1)、中间插删 O(n)；LinkedList 按下标 O(n)、已知节点插删 O(1)。但因为缓存局部性和每个元素 24 字节的节点开销，实际几乎总是 ArrayList 快；要两头进出用 ArrayDeque。真正适合 LinkedList 的，只有“拿着迭代器在中间大量插删”这种少见场景（④-3）。

ArrayList 怎么扩容？

第一次 add 分配 10 格；满了按 1.5 倍（old + old >> 1）建新数组，Arrays.copyOf 拷过去。按比例扩容保证了尾插均摊 O(1)（⑥-3）。

PriorityQueue 底层是什么？遍历是有序的吗？

数组实现的二叉小顶堆，offer、poll O(log n)，peek O(1)。遍历不有序，只有堆顶是最小的（④-5）。

为什么遍历时删除会抛 ConcurrentModificationException？

fail-fast：集合维护 modCount，迭代器创建时记下它，每次 next 都核对；不经迭代器的结构修改会让它对不上。用 Iterator.remove 或 removeIf（坑 1）。注意它只是尽力检测，不是线程安全的保证。

下一圈

↺回到⑤：改造你的订单簿

1. 修掉比较器的坑

把⑤里按价格比较的 TreeSet 改成 comparing(price).thenComparing(skuId)，看 size 变回 2。

用到：坑 4

2. 一个 LRU 缓存

用 LinkedHashMap（accessOrder = true 加 removeEldestEntry）给订单簿加一个“最近查过的 100 个用户”缓存，验证第 101 个进来时最久没查的那个被挤掉。

用到：⑥-3 三种顺序

3. 让取消能撤回

用户付款后，要把他的 CancelTask 从队列里拿掉。PriorityQueue.remove(obj) 是 O(n) 的，想想有没有更好的办法（提示：取出时再检查订单状态，跳过已付款的）。

用到：④-5 堆

自测

1. 用一句话说出这页的精华。

先按“怎么找”选接口（List / Set / Map / Queue），再默认选数组实现；数组靠连续内存赢在常数和内存，节点只在少见场景占优。

2. 什么都放 ArrayList，最疼在哪？

按 key 找、判重、找最小都变成从头扫，O(n) 乘以次数；实测按用户查慢 2000 多倍（②）。

3. for-each 里 remove 抛异常，根源是哪条原理？

迭代器靠游标走数组，绕过它改结构会让游标错位，所以用 modCount 检测并 fail-fast（④-1，坑 1）。

4. 预测：把⑤的 cancelQueue 换成 TreeSet<CancelTask>（还按 deadline 比较），两单在同一秒下单会怎样？

两个 CancelTask 的 deadline 相同，compareTo 返回 0，TreeSet 当成重复，后一个放不进去，那一单永远不会被超时取消（④-4，坑 4）。PriorityQueue 允许相等元素，没这个问题。

5. 预测：订单行 100 万条时，用 LinkedList 代替 ArrayList，内存大约多多少？

每个元素多一个 24 字节的 Node，而 ArrayList 只要 4 字节一格，大约多 20 MB，多 100 万个要 GC 扫描的对象（④-3，实测 24.0 vs 3.7 字节）。

6. 放回全景：第 8、9 站前后各发生了什么？这一页讲的东西选错了，整条链路会怎样？

前面是第 7 站扣完库存、INSERT 订单，后面是第 10 站 Jackson 序列化、第 11 站写回网络。第 8 站如果把 userOrders 写成一个大 List，“查我的订单”接口就是全表扫，订单越多越慢；第 9 站如果每次排序找最早到期，后台取消线程会把 CPU 吃满，拖慢所有 Tomcat 线程。更隐蔽的是：PriorityQueue 被当成有序列表遍历，会取消错订单。还有全景已经指出的：这两个集合只放不删、不是线程安全的，前者会让堆涨满（J03），后者在并发下单时丢数据（J02）。