← 返回博客
2026-09-04 11:33:31

Java 集合框架学习笔记：从 ArrayList 到 TreeMap，十个容器一次收束

Java 集合框架学习笔记：从 ArrayList 到 TreeMap，十个容器一次收束

面试问集合，翻来覆去就那几个问题：ArrayList 和 LinkedList 哪个快、HashMap 和 Hashtable 差在哪、HashSet 底层是不是 HashMap。每个单点你都会答，但一旦被问到「现在要存一万个不重复的最近访问记录，你选哪个」，就露怯了。这篇把 List、Set、Queue、Map 四个分支的常用容器放到同一张血缘图里，用底层存储形态回答三件事——要不要顺序、要不要去重、按什么顺序取出，再顺手把不可变集合与活视图的边界说清楚。每一处的复杂度数字和顺序行为都来自本机 JDK 26.0.1 的真实实验，每个结论旁边都贴着复现它的代码与运行输出，可以边读边跑。涉及 HashMap 树化和 ConcurrentHashMap 的底层细节、以及遍历安全模型的机制，分别在上两篇（单元 1-1 HashMap 底层、单元 1-2 三种迭代器）讲透了，这篇只复用结论做对比，不再展开。

先立骨架：Collection 下分 List/Set/Queue，Map 独立成线，五种底层装下全部实现

打开 ArrayList 的源码，往父类一路看，最后停在 AbstractList 和 List 接口上；打开 HashSet，看构造方法，里面 new 了一个 HashMap。Java 的集合类几乎没有从天而降的设计，每一个都是「接口 + 底层存储形态」的组合。把这层关系摊开就是下面的血缘图：

Java 集合框架血缘图：Collection(List/Set/Queue) 与 Map，五种底层存储形态

图分左右两个家族。左边是 Collection，只管「一坨元素」，下分三个子接口：List 保证顺序且允许重复，Set 保证不重复，Queue 决定「按什么顺序往外取」；右边是 Map，管「键到值的映射」，键不能重复。颜色代表五种底层存储形态，这是整篇最重要的一行概念：

接口那一层不用记复杂度，因为接口不承诺实现；真正决定你快慢的是落到叶子上的底层形态。所以面试问选型，本质是让你先回答一句「底层是什么、要什么顺序」——后面所有对比表都是这句话的展开。

List 系纵向：ArrayList 一把梭，LinkedList 当列表是错配，Vector 是文物

先给三个实现排一排放一张纵向对比表，再逐个说适用场景。

维度ArrayListLinkedListVector
底层连续 Object 数组双向链表（节点含前后指针）连续 Object 数组
按下标 get(i)O(1)O(n)，从头或尾就近扫O(1)
尾部 add/remove摊还 O(1)O(1)O(1)（方法带锁）
头部 addO(n) 搬移O(1)O(n)
中间 add(i)/remove(i)O(n) 搬移后半段O(n) 先找再改O(n)
contains/按值找O(n)O(n)O(n)
扩容默认容量 10，之后约 1.5 倍无容量概念默认容量 10，默认 2 倍（或按 capacityIncrement）
内存数组引用，紧凑，缓存友好每个元素多一个 Node 对象加两个指针，缓存不友好同 ArrayList，且方法全部带锁
线程安全否否方法级 synchronized（JDK1 遗留）
使用场景绝大多数 List 需求当纯列表基本不选不要写新代码用它

ArrayList 是默认答案。源码里它是一个 Object[] elementData，get 就是 elementData[index]，所以按下标访问是 O(1)。尾部追加也快——数组末尾没位置时扩容一次，扩容后空间通常能撑很多次 add，均摊下来仍是 O(1)。真正的代价在中间插入：add(i, e) 要把 i 之后的所有元素整体后移一格再写，remove 同理往前搬，都是 O(n)。这段搬移用 System.arraycopy 完成，元素多了肉眼可见地慢。扩容的节奏值得背一组实测数：从空 ArrayList 连续 add，容量按 10→15→22→33→49→73→109 跳变，每步都是 old + (old >> 1)，也就是约 1.5 倍。JDK 的 grow 里写的就是 newCapacity = oldCapacity + (oldCapacity >> 1)，所以当你预估元素量很大时，new ArrayList<>(预估容量) 能省下整串扩容搬移。

LinkedList 的源码是一串 Node { E item; Node prev; Node next; } 用 first/last 串起来。头尾操作是 O(1)，因为它直接改首尾指针；但 get(i) 要从头（或从尾）沿着指针走过去，node(index) 在 JDK 里会判断 index 离头近还是离尾近，挑短的走，最好也是 O(n)。它的内存账也难看：每个元素除了值本身，还要白养一个 Node 对象加两个引用，而且链表上相邻的元素在堆里大概率不挨着，CPU 缓存命中率比数组差一个量级。什么时候才轮得到 LinkedList？仔细想会发现几乎没有——你需要「频繁头尾增删 + 不按下标访问」时，ArrayDeque（循环数组）更快且更省内存；你只是要一个列表，ArrayList 在任何维度都不输。所以现代的结论很干脆：把 LinkedList 当纯 List 用，是拿它的短板去碰别人长处。真要体验链表的插入删除 O(1)，那是遍历时用迭代器 remove（见单元 1-2），也不是 LinkedList 的专利。

Vector 是 JDK1 时代的文物。它和 ArrayList 一样是数组，默认容量 10，但扩容默认翻倍：实测容量按 10→20→40→80→160 走，除非你构造时给了 capacityIncrement。它每个公开方法都用 synchronized 包了一层，等于不管单线程多线程，先把锁加上再说——单线程下是纯浪费，多线程下它整表锁的性能又远不如 ConcurrentHashMap 那条路。所以三个替代方向要分清：只是想要同步的 List，用 Collections.synchronizedList(new ArrayList<>())，它同样按方法加锁，但你能控制加锁粒度，注意「先查后改」这类复合操作仍要自己在外层加锁；读多写极少的场景，用 CopyOnWriteArrayList（写时复制整组，读不加锁，见单元 1-2 的快照迭代）；没有任何同步需求，就 ArrayList 本尊。Stack 是 Vector 的子类，同样别用了，当栈用 ArrayDeque。

把这两串扩容数自己跑出来并不难，但 ArrayList 和 Vector 的容量是私有的，外部看不到——只能靠反射把 elementData 数组的长度读出来。下面是一份完整可复现的 Demo.java，也作为全文的跑代码脚手架：import 和类壳只此一份，之后每个小节只需把贴出的语句换进 main。

import java.lang.reflect.Field;
import java.util.*;
import java.util.concurrent.*;

public class Demo {
  // ArrayList / Vector 的容量藏在私有 elementData 数组里，反射读出数组长度来观测扩容节点
  static Field arrField(Class<?> c) throws Exception {
    Field f = c.getDeclaredField("elementData");
    f.setAccessible(true);
    return f;
  }

  public static void main(String[] args) throws Exception {
    Field alArr = arrField(ArrayList.class);
    Field vecArr = arrField(Vector.class);
    ArrayList<Object> al = new ArrayList<>();
    Vector<Object> vec = new Vector<>();
    int lastAl = 0, lastVec = 0;
    for (int i = 0; i < 90; i++) {
      al.add(new Object());
      vec.add(new Object());
      int alCap = ((Object[]) alArr.get(al)).length;
      int vecCap = ((Object[]) vecArr.get(vec)).length;
      if (alCap != lastAl) { System.out.println("ArrayList  size=" + al.size() + "  capacity=" + alCap); lastAl = alCap; }
      if (vecCap != lastVec) { System.out.println("Vector     size=" + vec.size() + "  capacity=" + vecCap); lastVec = vecCap; }
    }
  }
}
javac -encoding UTF-8 Demo.java && java --add-opens java.base/java.util=ALL-UNNAMED Demo

--add-opens 只为这一节服务：不放开 java.util 模块的私有访问，反射读不到 elementData。它属于验证手段，不是生产代码该干的事。后面几节的实验都不碰私有字段，把命令里的 --add-opens java.base/java.util=ALL-UNNAMED 去掉也能跑；main 里贴新语句时，import 和类壳都不用动。跑出来：

ArrayList  size=1  capacity=10
Vector     size=1  capacity=10
ArrayList  size=11  capacity=15
Vector     size=11  capacity=20
ArrayList  size=16  capacity=22
Vector     size=21  capacity=40
ArrayList  size=23  capacity=33
ArrayList  size=34  capacity=49
Vector     size=41  capacity=80
ArrayList  size=50  capacity=73
ArrayList  size=74  capacity=109
Vector     size=81  capacity=160

capacity 栏就是扩容后数组的长度：ArrayList 沿 10→15→22→33→49→73→109 跳，每步是 old + (old >> 1)，约 1.5 倍；Vector 沿 10→20→40→80→160 跳，默认翻倍。size=1 那一行还说明一件事：JDK8 起 ArrayList 是第一次 add 才一次性分配默认容量 10，不是 add 到第 10 个才有数组。

Set 系纵向：三个 Set 都是 Map 的马甲，区别只在要不要保顺序

Set 的接口语义就一句话：不重复。实现上的巧劲是——它根本不自己存值，而是把每个元素塞进一个 Map 当 key，value 用一个固定的占位对象。看 JDK 源码，HashSet 内部就是 HashMap，value 一律是那个静态常量 PRESENT；LinkedHashSet 继承 HashSet，构造时调用了一个带 dummy=true 参数的私有构造，让它底层用 LinkedHashMap；TreeSet 底层则是 TreeMap。这意味着前面 Map 那套底层形态、顺序规则、复杂度，原封不动搬到了 Set 上：

维度HashSetLinkedHashSetTreeSet
底层HashMap继承 HashSet，用 LinkedHashMapTreeMap（红黑树）
去重判据hashCode + equalshashCode + equalscompareTo / Comparator
顺序无序（桶的排布决定）保持插入顺序按自然序/比较器排序
contains/add/removeO(1)O(1)O(log n)
附加能力无无first/last、ceiling/floor、subSet/headSet/tailSet
使用场景去重、集合运算、成员判断去重且要保留添加顺序去重且要有序遍历或范围查询

去重为什么可靠，是面试第一刀。Hash 系走 hashCode + equals：先比 hashCode，相同再比 equals，所以放进 HashSet 的对象必须正确覆写这两个方法，并且保证「equals 相同则 hashCode 相同」。Tree 系不走 equals，走 compareTo（自然序）或构造时传入的 Comparator，所以元素要么实现 Comparable，要么你给比较器，二者都没有会在第一次插入时抛 ClassCastException。这里有个大坑值得写进代码里：放进 Set（或 Map 当 key）之后，不要再修改对象上参与 hashCode/equals/compareTo 的字段。Hash 系改了 hashCode，元素就掉进原来的桶里再也 get 不到；Tree 系改了比较字段，树的位置错乱，按新值找甚至可能死循环。可变对象当去重单元，等于在火山口盖房子。

顺序行为用一组实测讲最清楚。往三个 Set 里依次 add b、a、c、b、a（故意重复），结果：

三个 size 都是 3，重复项被去掉了，验证的是同一件事：Set 保证不重复，但「以什么为序」由底层 Map 决定。

贴进 Demo.java 的 main（删掉旧语句，import 留着），编译运行，用真实输出核对上面的三个结论：

Set<String> hs = new HashSet<>();
Set<String> lhs = new LinkedHashSet<>();
Set<String> ts = new TreeSet<>();
for (String s : new String[]{"b", "a", "c", "b", "a"}) { hs.add(s); lhs.add(s); ts.add(s); }
System.out.println("HashSet       (HashMap, 无序)   " + hs);
System.out.println("LinkedHashSet (LinkedHashMap, 插入序) " + lhs);
System.out.println("TreeSet       (TreeMap, 排序)   " + ts);
System.out.println("输入含重复 b/a -> 三个 Set.size=" + hs.size() + "/" + lhs.size() + "/" + ts.size());
HashSet       (HashMap, 无序)   [a, b, c]
LinkedHashSet (LinkedHashMap, 插入序) [b, a, c]
TreeSet       (TreeMap, 排序)   [a, b, c]
输入含重复 b/a -> 三个 Set.size=3/3/3

故意塞了重复的 b、a，三个 size 仍是 3/3/3——去重三个都做到了。差别只在顺序：HashSet 打印成 [a, b, c] 只是这组字符串的散列巧合（换个输入、换个 JDK 就乱），LinkedHashSet 忠实保留 [b, a, c] 的添加顺序，TreeSet 按字母排好。把某个类换成你怀疑的对象跑同一段，用真实输出说话，比记结论可靠。

什么时候用哪个，跟着需求走：只要「判断存不存在、做去重和集合运算」，HashSet 够快也够省；需要在去重的同时保留添加顺序——比如统计最近访问过的唯一链接、按触发顺序去重的埋点列表——用 LinkedHashSet，代价是它内部多维护一条链表，比 HashSet 略重；需要去重后还能按序遍历、取最大最小、做范围查询，用 TreeSet，把 O(1) 的查找换成 O(log n) 换来排序能力。大部分去重场景都落在 HashSet，这没问题，LinkedHashSet 和 TreeSet 都是「你要的那个额外顺序确实值钱」时才出手。

Queue 系纵向：ArrayDeque 当队列当栈，PriorityQueue 按优先级出队

List、Set 回答「存一坨、要不要去重」，Queue 回答第四件事：按什么顺序往外取。血统上它与 List、Set 平级，都是 Collection 的子接口，但日常用得少，所以只挑两个叶子讲清楚选型就够——ArrayDeque 是队列/栈的正主，PriorityQueue 是「最小优先」的队列。

Queue 的语义是先进先出（FIFO）：offer 从尾部进、poll 从头部出，先入队的先被取走。栈则是后进先出（LIFO）：push 把元素压到顶部、pop 也从顶部取，后入栈的先被取走，和队列正好相反。Deque（double-ended queue）是它的双端版本，头尾都能进出，当队列按 FIFO 用、当栈按 LIFO 用都行；官方文档建议用它取代 Stack（Stack 就是 Vector 子类那套 LIFO 老实现）。落到叶子上的主力实现是 ArrayDeque，底层是一段会扩容的循环数组，head/tail 两个下标绕着数组转圈，头尾 add/remove 都是 O(1)，也没有 get(i)——按下标访问本来就不是队列的诉求。它和 LinkedList 都实现了 Deque，但当队列/栈用没有理由选 LinkedList：少一串节点对象、缓存友好。实测它的双端语义：依次 addLast(尾1)、addFirst(头0)、addLast(尾2) 后迭代序是 [头0, 尾1, 尾2]，pollFirst/pollLast 各取一头；当栈 push a、b 后 pop 出来是 b、a（LIFO）。一句话：频繁头尾增删、只要 FIFO 队列或 LIFO 栈，用 ArrayDeque，别用 LinkedList 也别用 Stack。

这一段同时验证 ArrayDeque 的队列和栈两种身份：

ArrayDeque<String> dq = new ArrayDeque<>();
dq.addLast("尾1"); dq.addFirst("头0"); dq.addLast("尾2");
System.out.println("addLast(尾1) addFirst(头0) addLast(尾2) -> 迭代序 " + dq);
System.out.println("pollFirst()=" + dq.pollFirst() + "  pollLast()=" + dq.pollLast());
ArrayDeque<String> st = new ArrayDeque<>();
st.push("a"); st.push("b");
System.out.println("当栈 push a、b 后 pop 顺序 -> " + st.pop() + ", " + st.pop());
addLast(尾1) addFirst(头0) addLast(尾2) -> 迭代序 [头0, 尾1, 尾2]
pollFirst()=头0  pollLast()=尾2
当栈 push a、b 后 pop 顺序 -> b, a

addLast/addFirst 让元素按 [头0, 尾1, 尾2] 排好，poll 从两头各取一个；push 走头插、pop 走头取，后进的 b 先出（LIFO）。ArrayDeque 没有 get(i)，正是它不承诺按下标访问的意思。

PriorityQueue 是 Queue 家族里唯一不按先进先出的：它按优先级出队。底层是二叉堆——一棵完全二叉树平铺进数组，只维护一条弱序：父节点总不大于子节点，所以堆顶永远是最小值。offer 把新元素放到末尾再往上浮、poll 把堆顶取走后把末尾元素挪上来往下沉，都是 O(log n)，peek 只看堆顶 O(1)。它不是整体有序，只是保证每次取出的都是当前最小；同优先级的元素相对顺序不保证；不允许 null（实测 offer(null) 抛 NullPointerException）。实测 offer 5、1、9、3 再依次 poll，出队序是 1 3 5 9；new PriorityQueue<>(Comparator.reverseOrder()) 就反过来出 9 5 3 1。需要「边插入边取当前最小/最大」，比如 topK、按优先级调度任务，选它。二叉堆上浮下沉的完整推演、手写 add/poll、Top K 门槛与十亿级海量数据方案，单独成篇在单元 1-4（PriorityQueue 底层与二叉堆），这篇只用到选型这一层。

换个角度验证「按优先级出队」：offer 顺序是 5、1、9、3，看 poll 出什么：

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[]{5, 1, 9, 3}) pq.offer(x);
StringBuilder sb = new StringBuilder();
while (!pq.isEmpty()) sb.append(pq.poll()).append(' ');
System.out.println("offer 5,1,9,3 后依次 poll -> " + sb.toString().trim());
PriorityQueue<Integer> maxpq = new PriorityQueue<>(Comparator.reverseOrder());
for (int x : new int[]{5, 1, 9, 3}) maxpq.offer(x);
StringBuilder sb2 = new StringBuilder();
while (!maxpq.isEmpty()) sb2.append(maxpq.poll()).append(' ');
System.out.println("reverseOrder 后依次 poll   -> " + sb2.toString().trim());
try { pq.offer(null); }
catch (Exception e) { System.out.println("PriorityQueue.offer(null)  -> " + e.getClass().getSimpleName()); }
offer 5,1,9,3 后依次 poll -> 1 3 5 9
reverseOrder 后依次 poll   -> 9 5 3 1
PriorityQueue.offer(null)  -> NullPointerException

同样的输入，默认 PQ 每次出当前最小（1 3 5 9），套 reverseOrder 就每次出当前最大（9 5 3 1）——插入根本没排过序，是堆在替你维护「顶」这一条弱序。offer(null) 直接被拒在门外，抛 NPE。

Map 系纵向：HashMap 之外，另外三个什么时候才值得用

Map 同样先看底层和顺序。血缘图右半边五个叶子，除了 HashMap 是绝对主力，其余四个各有明确的使用前提。先上一张纵向表：

维度HashMapLinkedHashMapTreeMapHashtableConcurrentHashMap
底层数组+链表+红黑树继承 HashMap，加一条双向链表记顺序红黑树数组+链表（JDK1）数组+链表+红黑树（JDK8+）
键的顺序无序插入序或访问序按键排序无序无序
get/put/remove摊还 O(1)摊还 O(1)O(log n)O(1) 但全表锁摊还 O(1)
null 键允许一个允许一个默认不允许（比较 null 抛 NPE，除非给能处理 null 的比较器）不允许不允许
null 值允许允许允许不允许不允许
线程安全否否否方法级 synchronized是（分片 CAS+锁）
使用场景99% 的普通 KV要保顺序 / 做 LRU 缓存要排序遍历、范围查询、找最接近的键别用多线程共享的 KV

HashMap 是默认项，底层细节在单元 1-1 讲过：键先算 hashCode 定位桶，桶里用链表存冲突，链表超过阈值且数组够大就树化成红黑树，负载因子 0.75，size 超过 容量×0.75 就扩容翻倍、重新散列。所以它对 null 是宽容的——允许一个 null 键和任意 null 值，实测 put(null) 后 size=1。

LinkedHashMap 是「要顺序时的 HashMap」。它继承 HashMap，只在内部额外用一条双向链表把所有条目串起来，从而记住两种顺序：默认 accessOrder=false 记插入顺序；构造传 accessOrder=true 就记访问顺序——每次 get 或 put 命中已有键，都把该条目移到链表尾部，最近没被访问的自然沉到头部。配合重写 removeEldestEntry，它就是 JDK 里现成的 LRU 缓存骨架。实测三行验证了这套语义：构造上限 3 的 LRU，依次 put(1,2,3) → 访问 get(1)（1 被挪到尾部）→ put(4) 超上限，触发 removeEldestEntry 淘汰最久没用的 2，最终 keySet 是 [3, 1, 4]。插入序和 LRU 各有一小段验证代码，就在下面，自己改上限跑一遍就懂淘汰顺序了。

顺序和 LRU 各用一小段验证。先看插入序，再看上限 3 的 LRU 淘汰谁：

Map<Integer, Integer> lhm = new LinkedHashMap<>();
for (int k : new int[]{5, 1, 9, 3}) lhm.put(k, k);
System.out.println("LinkedHashMap(插入序) keySet=" + lhm.keySet());

final LinkedHashMap<Integer, Integer> lru = new LinkedHashMap<>(8, 0.75f, true) {
  protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) { return size() > 3; }
};
for (int k : new int[]{1, 2, 3}) lru.put(k, k);
lru.get(1);            // 1 变成最近访问
lru.put(4, 4);         // 超出上限 -> 淘汰最久没访问的 2
System.out.println("put1,2,3 -> get(1) -> put(4) 之后: " + lru.keySet());
LinkedHashMap(插入序) keySet=[5, 1, 9, 3]
put1,2,3 -> get(1) -> put(4) 之后: [3, 1, 4]

第一行：5、1、9、3 怎么加进去，keySet 就按什么顺序吐出来。第二行：removeEldestEntry 返回 true 表示「该淘汰最老的了」，accessOrder=true 让最近访问的 1 沉到队尾，最久没用的 2 被踢走，剩下 [3, 1, 4]。把上限 3 改成别的数再看淘汰变化，LRU 就通了。

TreeMap 是把「有序」直接焊进底层的 Map：内部是红黑树，键按自然序或构造传入的 Comparator 排列，所有操作都是 O(log n)。它把「比大小」的能力做成了 API——firstKey/lastKey 取首尾，lowerKey/floorKey/ceilingKey/higherKey 找最接近的键，subMap/headMap/tailMap 切范围视图。实测 floorKey(4) 在 [1,3,5,9] 上返回 3，ceilingKey(4) 返回 5，这就是「找第一个不大于 / 第一个不小于目标值的键」的活例子。用它的前提：键必须可比（实现了 Comparable 或你传了比较器）且比较结果不能随键可变——所以键通常得是不可变对象。适合的场景是需要在遍历时按序输出、做范围统计、或者找离某个值最近的键（路由、时间区间、配额按天查）。

按序输出和「找最接近的键」各一行：

Map<Integer, Integer> tm = new TreeMap<>();
for (int k : new int[]{5, 1, 9, 3}) tm.put(k, k);
System.out.println("TreeMap(排序)         keySet=" + tm.keySet()
    + "  floorKey(4)=" + ((TreeMap<Integer,Integer>) tm).floorKey(4)
    + "  ceilingKey(4)=" + ((TreeMap<Integer,Integer>) tm).ceilingKey(4));
TreeMap(排序)         keySet=[1, 3, 5, 9]  floorKey(4)=3  ceilingKey(4)=5

keySet 已按 1、3、5、9 排好；4 不在里面，floorKey(4) 返回小于等于 4 的最大键 3，ceilingKey(4) 返回大于等于 4 的最小键 5——「取前一个 / 取后一个」这类范围查找就是 TreeMap 的主场。

Hashtable 是 JDK1 的老古董，和 Vector 同一批：方法级 synchronized、不允许 null 键和 null 值。实测往 Hashtable put(null) 直接抛 NullPointerException。凡是教 Java 的旧书让你用 Hashtable，现在统一改成两句话处理：单线程用 HashMap；多线程用 ConcurrentHashMap。它的历史位置由 ConcurrentHashMap 接手，代码里不再有新写法。

ConcurrentHashMap 是 Hashtable 的正统继任者，JDK5 引入，JDK8 重写成分片加锁 + CAS 的结构（细节在单元 1-1）。它同样不允许 null 键和 null 值——实测 put(null) 抛 NullPointerException。为什么 HashMap 可以而它不行，是面试加分点：null 在并发 API 里有二义性。get 返回 null 可能是「没这个键」也可能是「这个键的值就是 null」，单线程你还能再查一次区分，并发下两次查询之间状态随时在变，没法可靠区分；所以它干脆把 null 键值一起禁掉，逼你用 putIfAbsent、computeIfAbsent 这些原子方法自己表达「不存在」。多线程共享一个 KV 容器就选它，单线程场景它仍比 HashMap 贵一层，没必要。

三种 Map 对 null 键的态度，一段代码验证完：

Map<String, String> hm = new HashMap<>();
hm.put(null, "ok"); System.out.println("HashMap 允许一个 null 键 -> size=" + hm.size());
try { new Hashtable<String, String>().put(null, "x"); }
catch (Exception e) { System.out.println("Hashtable.put(null)            -> " + e.getClass().getSimpleName()); }
try { new ConcurrentHashMap<String, String>().put(null, "x"); }
catch (Exception e) { System.out.println("ConcurrentHashMap.put(null)    -> " + e.getClass().getSimpleName()); }
HashMap 允许一个 null 键 -> size=1
Hashtable.put(null)            -> NullPointerException
ConcurrentHashMap.put(null)    -> NullPointerException

同一个 put(null)：HashMap 收下（size=1），Hashtable 和 ConcurrentHashMap 在入口就拒绝。后两者不许 null 是并发语义下「get 返回 null 无法区分键不存在还是值就是 null」的选择，不是忘了实现。

Map 的活视图：keySet、entrySet、values 不是快照，是同一个 Map 的三副眼镜

面试还有一个高频追问：遍历一个 Map，到底该遍历 keySet 再 get，还是遍历 entrySet？要答清楚，先明白这三个方法的返回值是什么。

它们返回的都是视图（view）而不是副本。JDK 文档原话：返回的 set 是被 map 支撑的，map 的修改会反映到这个视图上，反过来在视图上删元素也删到 map 里。实测最能说明问题——先拿到 keySet，之后才往 map 里 put 新键，这个早已持有的 keySet 的 size 会跟着变大，也能立刻 contains 到新键；用 entrySet 的迭代器删掉一个键，map 里就真的少了它；再用先前那个 keySet 直接 remove 另一个键，map 同样少了。一句话：这三兄弟背后站的是同一个 map，你任何时候通过它们看到的内容，都和 map 实时同步。

既然都是看同一个 map，为什么遍历时优先 entrySet？看你要取什么：

在视图上删除是合法且常用的操作，但要注意「怎么删」。三种姿势要分清：迭代器自己的 iterator.remove() 删当前元素，这是遍历中删除唯一安全的方法；removeIf 是 JDK8 起推荐的一次性删法，底层帮你处理好了迭代；直接在视图上按键删，比如 map.keySet().remove(key)，也能删到 map，但如果发生在正在遍历该视图的循环里，就会触发 fail-fast 异常（HashMap 系）或依赖弱一致容忍（ConcurrentHashMap 系）——这一整块机制单元 1-2 用三类实验讲透了，这里只提醒：循环里删，永远走迭代器或 removeIf，别在 for-each 里直接调 map.remove。

把「视图不是快照」用一段可复现的实验钉死。顺序是：先拿到 keySet → 再 put → 用 entrySet 迭代器删一个 → 再拿旧 keySet 删一个，全程只 new 了一个 map：

Map<String, Integer> m = new HashMap<>();
Set<String> ks = m.keySet();     // 在 put 之前就拿到
m.put("a", 1);
System.out.println("put 前持有的 keySet 在 put 后 size=" + ks.size()
    + ", 能看到新 key=" + ks.contains("a"));
m.put("b", 2); m.put("c", 3);
for (Iterator<Map.Entry<String, Integer>> it = m.entrySet().iterator(); it.hasNext(); ) {
  Map.Entry<String, Integer> e = it.next();
  if (e.getKey().equals("a")) it.remove();   // 迭代器里删
}
System.out.println("entrySet 迭代器里删掉 a 后 map.keySet=" + m.keySet());
ks.remove("b");
System.out.println("先前持有的 keySet.remove(b) 后 map.keySet=" + m.keySet());
put 前持有的 keySet 在 put 后 size=1, 能看到新 key=true
entrySet 迭代器里删掉 a 后 map.keySet=[b, c]
先前持有的 keySet.remove(b) 后 map.keySet=[c]

第一行：keySet 在 put 之前就拿到了，put 之后它的 size 跟着变大、还能 contains 到新键。后两行：无论从 entrySet 的迭代器删、还是拿那个旧 keySet 直接删，删的都是 map 本身。想想如果返回的是副本，这三行会是什么样子——这就是视图和快照的分野。

活视图的反面：要「改不了」，用 of() 或 unmodifiable*

keySet/entrySet/values 是活的，map 一变它们跟着变。反过来有一类需求是「谁也别想改」——把一份配置集合暴露给别的模块、只想让调用方读不想让它写。Java 给两套，语义差得很远：

选型一句话：只想表达「给你读、但你不许改」，用 unmodifiable* 包一层；想要「这份数据永远冻结、也不受任何来源牵连」，用 of()（或 List.copyOf(collection) 拷一份再冻结）。活视图和不可变正好是相反的两种承诺：前者承诺「实时跟到底」，后者承诺「谁也别想动」。Set.of 还有一条要记：它不承诺顺序——同组 a、b、c，我几次运行打印顺序各不相同——[a,b,c]、[b,a,c]、[a,c,b]、[b,c,a] 都出现过，别把它当有序集合。

「包装 vs 副本」的差别，直接跑一遍最直观——同一个 orig，分别包成 unmodifiableList 的 ro 和 List.of 的 imm，再回头看 orig 变了会怎样：

List<String> orig = new ArrayList<>(Arrays.asList("a", "b"));
List<String> ro = Collections.unmodifiableList(orig);
List<String> imm = List.of("a", "b");
orig.add("c");
System.out.println("unmodifiableList 是只读包装: 底层 orig.add(c) 后 ro.size=" + ro.size());
System.out.println("List.of 是独立副本:         底层变化后 imm.size=" + imm.size());
try { ro.add("x"); } catch (Exception e) { System.out.println("unmodifiableList.add(x) -> " + e.getClass().getSimpleName()); }
try { imm.add("x"); } catch (Exception e) { System.out.println("List.of.add(x)          -> " + e.getClass().getSimpleName()); }
try { List.of("a", null); } catch (Exception e) { System.out.println("List.of(a, null)        -> " + e.getClass().getSimpleName()); }
Set<String> ims = Set.of("a", "b", "c");
System.out.println("Set.of 迭代序(不保证, 某次运行)=" + ims);
unmodifiableList 是只读包装: 底层 orig.add(c) 后 ro.size=3
List.of 是独立副本:         底层变化后 imm.size=2
unmodifiableList.add(x) -> UnsupportedOperationException
List.of.add(x)          -> UnsupportedOperationException
List.of(a, null)        -> NullPointerException
Set.of 迭代序(不保证, 某次运行)=[b, c, a]

同为「不许改」，差别全在前两行：ro 是包装，底层 orig 一 add，它跟着长到 3；imm 是独立副本，orig 怎么变它都停在 2。add 都抛 UnsupportedOperationException。Set.of 那行这次打印 [b, c, a]——同一组 a、b、c，换一次运行顺序就可能变，这正是它不承诺顺序的现场证据。

横向总表：别按家族背，按「要什么」来找容器

纵向看完四个分支，横向才是选型真正容易错的地方。很多人背熟了「HashMap 无顺序、TreeMap 有顺序」，可真遇到「要顺序」却不知道去 LinkedHashSet 还是 LinkedHashMap。横向主线其实只落在 List / Set / Map 三者之间：同样一句话需求，落到哪个家族，取决于你要不要去重、要不要键值对。队列那条轴（FIFO / 栈 / 按优先级取）不走这三列，Queue 一节已经单独接走。

需求允许重复 + 有顺序 → List去重 + 有顺序 → Set键唯一 + 有顺序 → Map
只要插入顺序，不排序ArrayListLinkedHashSetLinkedHashMap（accessOrder=false）
要按大小/字典排序ArrayList 拿 Collections.sortTreeSetTreeMap
要按最近访问排序（LRU）无天然对应，自己维护无LinkedHashMap（accessOrder=true）
只是存一堆、不care顺序ArrayListHashSetHashMap
线程安全且多线程共享CopyOnWriteArrayListCopyOnWriteArraySetConcurrentHashMap

再给一张「使用场景 → 首选」的收口表，把本文每一个使用场景压缩成一行，面试或写代码时直接查：

使用场景首选备选 / 为什么
存一组对象，主要按下标随机访问或遍历ArrayList99% 的 List 场景就是它
频繁头尾增删，且不需要下标访问ArrayDeque比 LinkedList 省内存、更快；LinkedList 当纯列表不选
需要一个 LIFO 栈ArrayDeque不要用继承 Vector 的 Stack
需要一个 FIFO 队列ArrayDequeoffer 从尾进、poll 从头出，头尾 O(1)；当队列别用 LinkedList
要按优先级取当前最小/最大PriorityQueue二叉堆，offer/poll O(log n)；不能放 null；同优先级次序不保证
判断不重复、做集合运算，O(1)HashSet大部分去重场景
去重且保留添加顺序LinkedHashSet最近访问链接去重、埋点去重
去重且要有序输出或范围查询TreeSet把 O(1) 换成 O(log n) 换排序
存键值对，默认选择HashMapnull 键/值允许
键值对且要保插入顺序LinkedHashMap顺序稳定的输出、复刻顺序
做一个容量上限的 LRU 缓存LinkedHashMapaccessOrder=true + removeEldestEntry
键要排序遍历、找最接近的键TreeMapfloorKey/ceilingKey/subMap 范围查询
多线程共享键值对ConcurrentHashMapnull 键值一律禁止
读多写极少的共享列表/集合CopyOnWriteArrayList / CopyOnWriteArraySet快照迭代不抛并发异常
暴露一份只许读、不许改的集合List.of / Map.of / unmodifiable*of() 独立冻结副本；unmodifiable* 是只读包装（见活视图反面对比）
遍历 Map 同时取键和值entrySet 遍历别 keySet 再 get 二次查找

反过来，把这几年见到的问题代码收成一张「别写」清单，命中的都能直接改：new Vector()、new Hashtable()、new Stack() 全换掉；用 LinkedList 当普通列表，换成 ArrayList；拿 LinkedList 当队列/栈，换成 ArrayDeque；遍历 keySet 再挨个 get 拿值，换成 entrySet；循环遍历里直接 map.remove/list.remove，换成迭代器 remove 或 removeIf（机制见单元 1-2）；把可变对象塞进 HashSet 或当 HashMap 的 key 之后又改它的字段；往 ConcurrentHashMap 塞 null。

面试速答

Q：ArrayList 和 LinkedList 的区别，什么时候用哪个？

A：ArrayList 底层连续数组，按下标随机访问 O(1)、尾部追加摊还 O(1)、中间插入删除 O(n) 要搬移元素，内存紧凑缓存友好；LinkedList 底层双向链表，头尾增删 O(1)，但按下标访问 O(n)、每个元素多一个节点对象加两个指针、缓存不友好。绝大多数场景用 ArrayList；真需要频繁头尾增删又不按下标访问时，用 ArrayDeque 都比 LinkedList 更优。把 LinkedList 当纯列表用，是常见错误。

Q：ArrayList 扩容是多少倍？

A：约 1.5 倍。JDK 源码是 newCapacity = oldCapacity + (oldCapacity >> 1)，实测容量序列 10→15→22→33→49→73→109。预估量大时用 new ArrayList<>(n) 预先给足容量，避免反复扩容搬移。

Q：Vector 和 ArrayList 的区别？为什么 Vector 被淘汰？

A：Vector 是 JDK1 遗留类，每个方法 synchronized，扩容默认翻倍或按 capacityIncrement，迭代同样 fail-fast；ArrayList 无锁、扩容约 1.5 倍。Vector 所有方法都上锁，单线程是纯开销，多线程整表锁又远不如 ConcurrentHashMap 的分片思路，所以新代码不写 Vector。真要同步 List，用 Collections.synchronizedList 包一层并自己管复合操作的锁；读多写少用 CopyOnWriteArrayList。

Q：HashSet 怎么保证不重复？

A：HashSet 底层是 HashMap，元素作为 key、value 是固定占位对象。添加时先算 hashCode 定位桶，桶里再用 equals 比较；只有 hashCode 相同且 equals 为真才判重复。所以放进 HashSet 的对象必须正确覆写 hashCode 和 equals，且 equals 相等时 hashCode 必相等。放入后不要改参与 hashCode/equals 的字段，否则元素会丢失。

Q：LinkedHashSet 和 TreeSet 的区别？

A：LinkedHashSet 继承 HashSet、底层 LinkedHashMap，去重同时保持插入顺序，contains O(1)；TreeSet 底层 TreeMap（红黑树），去重同时按键的自然序或 Comparator 排序，contains O(log n)，并提供 first/last、ceiling/floor、subSet 等有序操作。去重要保插入序选 LinkedHashSet，去重要排序或范围查询选 TreeSet。

Q：什么时候用 ArrayDeque？它和 LinkedList、Stack 什么关系？

A：需要 FIFO 队列或 LIFO 栈、也就是频繁头尾增删时，用 ArrayDeque。它底层是循环数组，头尾 add/remove 都 O(1)，没有 get(i)，比 LinkedList 当队列/栈省内存、缓存友好。LinkedList 虽然也实现了 Deque，但没有必要用它当队列；Stack 是 Vector 的子类、方法带锁，官方建议直接用 Deque 取代。

Q：PriorityQueue 底层是什么，复杂度多少？

A：底层是二叉堆（完全二叉树平铺进数组），只保证堆顶是当前最小（默认）或按比较器的极值，不保证整体有序，所以它按优先级出队而不是 FIFO。offer/poll 都是 O(log n)（插入上浮、删除下沉），peek O(1)。不允许 null，同优先级的元素相对顺序不保证。

Q：List.of 和 Collections.unmodifiableList 有什么区别？

A：List.of 生成的是独立冻结副本，之后与来源数据再无关系，不允许 null；unmodifiableList 只把传入的集合包成只读视图，不复制——原集合一变它也变。要「绝对不可变且独立」用 of()（或 List.copyOf 拷一份），要「只读包装但共享底层」用 unmodifiable*。

Q：HashMap、Hashtable、ConcurrentHashMap 三者区别？

A：HashMap 单线程，允许一个 null 键和任意 null 值，无序，摊还 O(1)；Hashtable 是 JDK1 遗留，方法级 synchronized，不允许 null，被淘汰；ConcurrentHashMap 是线程安全的正统方案，JDK8 起分片加锁加 CAS，迭代弱一致，同样不允许 null 键值——因为并发下 get 返回 null 无法区分「键不存在」和「值就是 null」，所以用 putIfAbsent 这类原子方法表达。

Q：遍历 Map，为什么推荐 entrySet 而不是 keySet 再 get？

A：keySet、entrySet、values 都是 map 的活视图，不是快照。要同时拿键和值时，entrySet 一次迭代拿到一对 Entry，避免 keySet 后再做第二次查找（HashMap 多一次 hashCode 和寻址，TreeMap 多一次 O(log n)），多线程下还避免「拿到的键和值不是同一时刻状态」的错位。只拿键用 keySet，只拿值用 values。

Q：Map 的 keySet/entrySet/values 返回的是副本吗？

A：不是。它们返回被 map 支撑的视图，map 的任何修改都会实时反映到视图上，反过来在视图（或其迭代器）上删元素也真的删进 map。这也是为什么遍历中删除要用迭代器 remove 或 removeIf，而不要在 for-each 里直接调 map.remove——后者会破坏 fail-fast 的约定，机制见单元 1-2。