集合与泛型
HashMap 的 Javadoc 写得很干：基本 get/put 均摊常量时间，前提是哈希把元素打散。迭代时间和「容量 + 实际条目」成正比，所以初始容量开太大，迭代会变慢。负载因子默认 0.75。允许 null key、null value。非线程安全。
这些不是经验之谈，是类文档的承诺。Hashtable 不允许 null，方法带 synchronized，迭代 fail-fast。ConcurrentHashMap 不允许 null（null 被用来表示「现在没有」），迭代 weakly consistent。三种 Map 不能互相当「就是个 map」换着用。
一、接口怎么长
Iterable
Collection Map
List HashMap / LinkedHashMap / TreeMap / EnumMap
Set ConcurrentHashMap
Queue / DequeCollection 是「一堆元素」；Map 不是 Collection。keySet()/values()/entrySet() 是视图，改视图就是改 map。keySet().remove(k) 等于 map.remove(k)。迭代 entrySet 时 setValue 改的是 map 里那条，不是副本。
1、List
有下标，允许重复。
ArrayList 是可变数组。OpenJDK 21：
DEFAULT_CAPACITY = 10- 无参构造把
elementData指到共享的DEFAULTCAPACITY_EMPTY_ELEMENTDATA（空数组）。第一次 add 才扩到 10。new ArrayList<>(0)用的是另一份EMPTY_ELEMENTDATA，第一次 add 按minCapacity长，不会直接跳到 10。两份空数组就是为了区分「默认容量还没inflate」和「用户就是要 0」。 - 再往后
grow：ArraysSupport.newLength(old, minGrowth, old >> 1)，也就是大约 1.5 倍，不是 HashMap 那种翻倍。 - 中间
add(index, e)要System.arraycopy搬元素。随机读 O(1)，中间插 O(n)。
LinkedList 是双向链表，按下标访问是走链表，不是数组。随机读用 ArrayList。LinkedList 实现 Deque，当队列用可以，当 List 按下标切不要。
List.of(...)（9）不可变、不允许 null、不允许 add。Arrays.asList 是数组视图，set 可以，add 不行。两者经常被混。
2、Set
equals 意义下不重复。HashSet 是包着 HashMap，value 是一份共享的 PRESENT 哨兵。LinkedHashSet 保插入序。TreeSet 靠 compareTo/Comparator，不是 equals——两者不一致就会出现「Set 里两个 equals 为 true 的元素」这种违反 Set 契约的状态。
EnumSet 是位图，只装同一个 enum。比 HashSet 快、更省。
3、Queue / Deque
ArrayDeque 作栈/队列都比 Stack（继承 Vector）和 LinkedList 干净。环形数组，两头都能进。迭代无 ConcurrentModification 以外的惊喜，但仍然 fail-fast。
PriorityQueue 是堆，迭代无序，只保证堆顶最小（或比较器最小）。poll 才是按顺序出。offer(null) 抛 NPE。
不要用 Vector、Hashtable、Stack 写新代码。要同步，用 Collections.synchronizedX 或并发容器，不要靠 1.0 那套每个方法一把锁。Collections.synchronizedList 迭代仍要自己 synchronized (list) 包住，文档写了，漏了就不是线程安全。
二、HashMap 实际怎么放
1、常量，OpenJDK 21 源码原文
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;源码注释写明：MIN_TREEIFY_CAPACITY 至少是 4 * TREEIFY_THRESHOLD，避免扩容阈值和树化阈值打架。
2、hash 和下标
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}下标：tab[(n - 1) & hash]。n 保持 2 的幂，位与代替取模。高 16 位异或进低位，避免只低位变化时全撞一个桶。null key 的 hash 是 0，落在桶 0。
hashCode 差的 key（很多哈希只低位变）全挤一个桶，树化是后路，不是借口。自己写 key 的 hashCode 要把字段搅开，Objects.hash 可以，别只 return 一个低位变化的 id。
3、会错的程序：hash 恒 1，连续 put
final class Bad {
final String name;
Bad(String name) { this.name = name; }
@Override public int hashCode() { return 1; }
@Override public boolean equals(Object o) {
return o instanceof Bad b && name.equals(b.name);
}
}
HashMap<Bad, Integer> m = new HashMap<>();
for (int i = 0; i < 11; i++) {
m.put(new Bad("k" + i), i);
}hash(key) = 1 ^ (1 >>> 16) = 1。下标 (n - 1) & 1，n 是 2 的幂时永远是桶 1。lo/hi 那一位 1 & oldCap：16、32 都是 0，扩容 不拆链，整串仍在新表的桶 1。这才能把「第几次才 treeifyBin、表多长才真树化」逼到台面上。均匀哈希几乎走不到下面这张表。
4、putVal / treeifyBin 源码（OpenJDK 21）
链表尾插时 binCount 从 0 起。把 putVal 里这段循环按「桶里已有几个、这次加第几个」展开。p 是当前走到的节点，一开始是桶头。
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}桶里已有 1 个（只有头），加第 2 个：第一次循环 p.next==null，binCount 还是 0，0 ≥ 7？否。已有 8 个，加第 9 个：循环走到头的后继 7 次，binCount 加到 7，7 ≥ 7，才 treeifyBin。注释 -1 for 1st 指的就是这个：阈值按「加上之后至少 8 个」，所以 第 8 次 put 还不调。
treeifyBin 第一句不是树化：
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // 64
resize();
else { /* 链表换成 TreeNode，hd.treeify(tab) */ }resize 翻倍后，每个旧桶按 hash & oldCap 拆成 lo（下标 j）和 hi（j + oldCap）。hashCode 恒 1 时 1 & 16 == 0、1 & 32 == 0，整串跟着 lo 走，扩容不拆链。1.8 尾插不再成环，多线程仍会丢数据。
5、逐步表：下一行执行完 table 是什么
new HashMap<>() 之后 table==null，threshold 还不是 12，第一次 putVal 才 resize() 出 16 格、threshold=12。
| 步骤 | 刚执行完 | n | 桶 1 形态 | size | threshold | treeifyBin？ |
|---|---|---|---|---|---|---|
| put k0 | table 从 null 分配 16 格，桶 1 一个节点 | 16 | k0 | 1 | 12 | 否 |
| put k1 … k7 | 尾插。加 k7（第 8 个）时 binCount=6，6≥7？否 | 16 | k0→…→k7（8 个） | 8 | 12 | 否 |
| put k8 | binCount=7≥7，调 treeifyBin。16<64，只 resize | 32 | 仍链表 9 个（1&16=0，不拆） | 9 | 24 | 调了，没树化 |
| put k9 | 再调 treeifyBin。32<64，resize | 64 | 仍链表 10 个（1&32=0） | 10 | 48 | 调了，没树化 |
| put k10 | treeifyBin，64≥64，replacementTreeNode + treeify | 64 | 红黑树 11 个，仍留 next | 11 | 48 | 真树化 |
size > threshold 这条扩容，在这串 put 里一次都没先开火：树化检查比它更早撞上。哈希均匀时 #9 那次 resize 会把链拆到两个桶，binCount 掉下去，永远到不了最后一行。
改一行：把 hashCode 改成 return name.hashCode();。k0 和 k1 多半不在同一桶，#9 的 treeifyBin 不会发生。表只剩「第一次 resize 到 16、size 过 12 再翻倍」——那是正常路径，不是树化路径。
new HashMap<>(100) 不是容量 100，向上取到 128。要装 N 个还不扩容，初始容量至少 N / 0.75 再取 2 的幂。
6、LinkedHashMap、IdentityHashMap、WeakHashMap
LinkedHashMap 多一条双向链表，保插入序或访问序（accessOrder=true 时 get 也会把节点搬到链尾）。重写 removeEldestEntry 可当 LRU：return size() > MAX;。它继承 HashMap，非线程安全。
IdentityHashMap 用 == 和 System.identityHashCode，违反 Map 的 equals 契约，只给框架内部用（序列化、注解处理）。业务代码别用。
WeakHashMap 的 key 是弱引用，GC 后条目消失，适合「谁还握着这个 key 对象，条目就还在」的缓存。value 是强引用，value 如果反向引用 key，弱引用失效，条目永远清不掉——这是它最常见的坑。value 用 WeakReference 包一层，或干脆别用它当业务缓存。
三、ConcurrentHashMap 不是「加了锁的 HashMap」
1、文档承诺
和 Hashtable 一样 不允许 null key/value。get 读到的非 null 值，与当初的插入/更新有 happens-before。批量操作（forEach、reduce）反映的是这些单元素关系的组合，不保证对整张表原子。迭代器 weakly consistent：不抛 ConcurrentModificationException，可能看见也可能看不见并发插入，不会对你抛结构损坏。
Java 8 起不是 1.7 那种 Segment 分段锁。实现是桶数组 + 链表/红黑树，扩容时桶可以逐个转移，未转移的桶仍可读写。sizeCtl 控制初始化、扩容协助。面试还答「Segment 默认 16」是在答 1.7。
size() 在并发下是估计。计数用类似 LongAdder 的分段，不精确。要精确快照，没有无锁的免费午餐。mappingCount() 返回 long，避免 size 超过 Integer.MAX_VALUE 时截断。
2、复合操作
不要用 chm.get(k); if (null) chm.put(k,v)。用 putIfAbsent / computeIfAbsent。文档给的频率统计写法是：
ConcurrentHashMap<String, LongAdder> freqs = new ConcurrentHashMap<>();
freqs.computeIfAbsent(key, k -> new LongAdder()).increment();compute* 系列对这条 key 串行。计算函数里不要再进同一张 map，否则可能重入、IllegalStateException，文档写了 The remapping function must not modify this map during computation。
computeIfAbsent 的 mapping function 返回 null，表示不插入。CHM 不允许 null value，返回 null 就是「算了」。HashMap 的 computeIfAbsent 同样：返回 null 不插入。
putIfAbsent 返回旧值（没有则 null）。replace(k, old, neu) 按 Objects.equals 比旧值。record 当 value、状态机用 replace 做 CAS，实战篇会用。
3、putVal 走一遍：CAS 空桶、锁桶头、协助扩容
OpenJDK 21 的 spread：(h ^ (h >>> 16)) & 0x7fffffff。比 HashMap 多一个 & HASH_BITS——最高位清零，因为负 hash 被 MOVED(-1)、TREEBIN(-2)、RESERVED(-3) 占了当标记。
putVal 主循环（简化）：
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable(); // CAS sizeCtl 抢初始化
else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
if (casTabAt(tab, i, null, new Node<>(h, key, value)))
break; // 空桶：CAS 挂上，无锁
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f); // 撞上 ForwardingNode，来帮搬
else {
synchronized (f) { // 只锁这条桶的头结点
if (tabAt(tab, i) == f) {
// fh >= 0 走链表尾插 / 覆盖；f instanceof TreeBin 走红黑树
}
}
}
}
addCount(1L, binCount); // 分段计数，顺便看要不要扩容逐格看「下一步状态」：
| 撞到的桶 | 做什么 | 锁 |
|---|---|---|
| 空 | casTabAt(null → 新节点) | 无锁，CAS |
链表头（fh >= 0） | synchronized (f) 后尾插或覆盖 | 只锁这一条桶 |
fh == MOVED（ForwardingNode） | helpTransfer 去搬其它桶 | 协助扩容 |
fh == TREEBIN | synchronized (f) 走红黑树 | 只锁这一条桶 |
锁粒度是「一条桶的头结点」，不是整表。别的桶照常读写。这是 8 相对 7 分段锁的进化：粒度从「16 段」细到「每个桶」。
sizeCtl 一个 int 编码四种状态：-1 正在初始化；负且非 -1 的值高位是 resize 戳、低位是「多少线程在协助扩容」；正数是下次扩容阈值；0 是默认。扩容时把旧表拆成一段段，每个线程 transfer 认领一段桶往新表搬，搬完的旧桶放一个 ForwardingNode（hash=MOVED）。别的线程 put 撞上 ForwardingNode，就 helpTransfer 一起搬——扩容是多线程协作的，不是一个线程闷头搬别人干等。
addCount 用类似 LongAdder 的 CounterCell[] 分段累加，size() 求和是估计。要长整数用 mappingCount()。
面试把 CHM 答成「把 HashMap 的方法都加 synchronized」是错的：锁的是桶头不是方法，扩容是协作的，计数是分段的，读多数时候无锁（get 全程不加锁，靠 volatile 的 Node.val 和 tabAt 的 acquire 语义）。
四、泛型：擦除，不是 C++ 模板
1、运行时没有 List<String> 这个类
List<String> a = new ArrayList<>();
List<Integer> b = new ArrayList<>();
System.out.println(a.getClass() == b.getClass()); // true，都是 ArrayList类型参数被擦成边界（没写就是 Object，写了 T extends Number 就是 Number）。所以：
- 不能
new T()、不能new T[]（数组要记运行时分量类型，擦掉就没了） - 不能写
List<int>，只能List<Integer> instanceof List<String>非法，只能instanceof List<?>- 重载
void f(List<String>)和void f(List<Integer>)擦完签名相同，编译失败 - 不能
catch (T e)，不能class Fail<T> extends Exception
反射能拿到签名里的类型参数（getGenericSuperclass），那是 class 文件里的 Signature 属性，给编译器和工具看的，运行时检查不靠它。ArrayList<String> 的 get(0) 字节码是 checkcast String，这层 cast 是编译器插的。
2、不变、协变、逆变
List<String> 不是 List<Object> 的子类型（不变）。否则 List<Object> 引用指向 List<String>，add(Integer) 会在运行时把整型塞进只该装 String 的结构——数组协变已经犯过这错，泛型不跟。
要「只读」用 List<? extends Number>：能 get 成 Number，不能 add（除了 null）。要「只写」用 List<? super Integer>：能 add(Integer)，get 只能当 Object。这是 PECS：Producer Extends, Consumer Super。
void copy(List<? extends Number> src, List<? super Number> dst) {
for (Number n : src) dst.add(n);
}src 是生产者，dst 是消费者。List<?> 等于 List<? extends Object>，几乎只能读成 Object、加 null。
3、桥方法、堆污染、@SafeVarargs
桥方法：class Box implements Comparable<Box> 的 compareTo(Box)，编译器再生成一个 compareTo(Object) 转调，满足擦除后的接口。你在反射里会看见两个方法，不是源码写了两份。
堆污染：List 原始类型（raw type）和参数化类型混用，运行时可能把 Integer 塞进「以为是 String」的 List，下次 get 的 checkcast 炸。
List raw = new ArrayList<String>();
raw.add(1); // 警告，运行时塞进去了
List<String> typed = raw;
String s = typed.get(0); // ClassCastException不要用 raw type。新代码看见 List 不写 <> 就是事故。
@SafeVarargs 只抑制警告，不让 varargs 和泛型突然变成具体化。可变参数是数组，数组和泛型叠在一起仍会有堆污染。能不用就不用。方法必须 static 或 final 或 private 才能标这个注解——否则子类覆盖还能把堆污染扩大。
型变、通配符捕获、类型推断、递归泛型、反射拿真实类型参数，单独在 泛型与类型系统 里走读。这里只需记住：容器的类型参数擦成 Object，安全靠 get 处的 checkcast。
五、迭代与 fail-fast
ArrayList / HashMap 的迭代器：结构修改（不是通过迭代器自己的 remove）之后，next 可能抛 ConcurrentModificationException。实现是比较 modCount 和迭代器创建时的 expectedModCount。这是 尽力检测，不是契约保证每次都抛。单线程 for-each 里 list.add 必炸；多线程「没炸」不代表安全。
for (String s : list) {
if (s.isEmpty()) list.remove(s); // CME
}
list.removeIf(String::isEmpty); // 对for (E e : coll) 是 iterator。list.remove(e) 在循环里改结构，走 fail-fast。要删，用 iterator.remove() 或 removeIf。按索引倒着删 for (int i = list.size()-1; i >= 0; i--) 不走迭代器，不会 CME，但可读性差，且只对 List 下标成立。
CopyOnWriteArrayList 迭代的是快照，不会 CME，写入拷贝整组，适合读多写极少。写多了分配会打爆。快照是写那一刻的数组，迭代开始之后的写入看不见——这是它的语义，不是 bug。
增强 for 不能拿来改 List 结构，下标 for 可以，但 ConcurrentModification 管不到你用下标时的并发。并发下标遍历 ArrayList 是 data race。
六、改一行：hash 均匀之后那张表塌掉
上面的表依赖 hashCode 恒 1。改成 return name.hashCode(); 再 put 11 次：k0、k1 几乎不在同一桶，binCount 到不了 7，treeifyBin 一次不调。剩下的只有 size > threshold 的翻倍（8 个左右时 16→32）。面试答「超过 8 就树化」少了两句：① 第 9 个进同一桶才调 treeifyBin；② 表长 < 64 只扩容。两句都在源码里，不在口口相传里。
七、CHM 的 sizeCtl、ArrayList 怎么长、modCount 为什么「尽力」
1、CHM 扩容不是整表一把锁
Java 8 起没有 Segment。sizeCtl 是一个 int，负值表示正在初始化或扩容（高位记「多少 worker 在协助」一类编码），正值是下次扩容阈值。扩容时旧表的桶可以逐个转移到新表：某个线程 put 撞上转发节点，会帮着搬几个桶再干自己的活。面试答「分段锁 16」是 1.7。
size() 走类似 LongAdder 的计数，并发下是估计。mappingCount() 返回 long。精确快照没有无锁免费午餐。
2、ArrayList.grow
无参构造：elementData 指向共享空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。第一次 add，oldCapacity==0 且是这份空数组，直接 new Object[Math.max(10, minCapacity)]。new ArrayList<>(0) 用另一份 EMPTY_ELEMENTDATA，第一次按 minCapacity 长，不跳到 10。
之后：ArraysSupport.newLength(old, minGrowth, old >> 1)，优先涨约 50%。不是 HashMap 翻倍。中间 add(i, e) 要 arraycopy，随机插是 O(n)。ensureCapacity 在默认空表且 minCapacity <= 10 时故意不 inflate——避免 ensureCapacity(8) 把默认表扩到 8 而不是 10。
3、modCount 是尽力，不是契约
结构修改（add/remove 导致容量或 size 变，HashMap 的 put 新 key）++modCount。只改 HashMap 的 value 不加。迭代器创建时记下 expectedModCount，next 发现不一致就 CME。
规范 / Javadoc：best-effort。单线程 for-each 里 list.add 必炸。多线程一个在遍历一个在 add，可能 CME，可能把数组读成错的而不抛——检测靠的是一个不加锁的 int，不是 happens-before。没抛 CME 不等于线程安全。subList 的 fail-fast 看的是父 list 的 modCount，父结构变了子视图也炸。
下一篇把 checked 异常、try-with-resources、NIO.2、ByteBuffer 钉完。容器会抛的那些异常，规则在异常篇，不在这里编。