工程学习台

主题

集合探针：ArrayList、LinkedList、HashMap 与选择/迭代契约 ​

这是一个单文件、无第三方依赖的 Java 探针，用反射和断言验证几类容易背错的结论：

  1. ArrayList 默认容量不是构造时分配的 10，而是首次 add 时分配；后续按约 1.5 倍增长。
  2. HashMap 默认延迟分配；指定初始容量 1000 时，第一次 put 分配的实际表长是 1024。
  3. 同桶第 8 个节点仍是链表；容量已经达到 64 时，第 9 次插入才转红黑树。
  4. 默认容量下，同桶键要等到第 11 次插入才树化，因为前两次树化尝试先触发了 16 → 32 → 64 的扩容。
  5. 树化后删除节点时，退化时机由树形决定，不由固定节点数 6 决定。

U05 扩展场景（对应集合选择、视图与迭代并发契约正文）：

  1. Map 缺席/映射 null 二义、put 重复键返回旧值、computeIfAbsent 把映射 null 当缺席、merge null 结果删除、ConcurrentHashMap 拒绝 null。
  2. 集合选择：ArrayDeque FIFO/LIFO 与 null 拒绝、PriorityQueue poll/remove、TreeSet 比较器等价键与 tie-breaker、减法比较器溢出、LinkedHashSet 插入序、EnumSet/EnumMap 声明序、IdentityHashMap 引用相等。
  3. 视图与快照：Arrays.asList 定长写回、unmodifiableList 别名 vs List.copyOf 快照、subList、keySet/entrySet/values 写透。
  4. 迭代契约：CME 与迭代器 remove 恢复、removeIf、COW 快照迭代器、ConcurrentHashMap 弱一致遍历（不承诺全局快照）。
  5. resize 拆分：64→128 时旧桶低位/高位拆分与 ≤6 退化阈值实测。

环境基线 ​

项值
本轮运行时（2026-10-24，U05）Oracle JDK 17.0.12（x86_64，macOS 26.7.1）
历史运行时OpenJDK 17.0.12（2026-10-22 原始输出）；Liberica 17.0.19+11 记录见 labs/java-senior U04 证据（另机 arm64），本机不可用
源码基线OpenJDK 17u jdk-17.0.12+7（固定摘录与断言解释基准）
操作系统macOS x86_64
依赖仅 JDK，无第三方库

内部字段名和树化时机属于实现细节，不是 Java API 契约。换 JDK 版本、厂商或实现后必须重新运行，不得把本文输出直接外推。

运行 ​

实验代码bash
# 从仓库根；也可经 labs/java-senior/run.sh collections 调用
cd labs/collections
JAVA_HOME=/Library/Java/JavaVirtualMachines/jdk-17.jdk/Contents/Home ./run.sh

run.sh 校验 JDK17、在唯一临时目录编译 CollectionsProbe.java，把探针标准输出写入 out/collections-probe.txt（U05 恢复该捕获并在重跑后更新为完整新输出）。--add-opens java.base/java.util=ALL-UNNAMED 仅用于反射读取 JDK 内部字段，不是业务代码的常规配置。未知参数或非 JDK17 退出 2。完整命令、stdout/stderr、退出状态与限时记录见 U05 证据。

实测输出 ​

完整原始输出见 out/collections-probe.txt（U05 于 2026-10-24 重跑后更新，运行版本 Oracle JDK 17.0.12 x86_64）。

text
java.version=17.0.12 vm=Java HotSpot(TM) 64-Bit Server VM

== 1. ArrayList growth ==
new ArrayList<>()      capacity=0    size=0
after add #1           capacity=10   size=1
after add #10          capacity=10   size=10
after add #11          capacity=15   size=11
after add #16          capacity=22   size=16
after add #23          capacity=33   size=23

== 2. LinkedList structure ==
first=Node last=Node
Node fields=item,next,prev

== 3. HashMap lazy allocation and resize ==
new HashMap<>()        capacity=0     threshold=0     size=0
after put 1            capacity=16    threshold=12    size=1
after put 12           capacity=16    threshold=12    size=12
after put 13           capacity=32    threshold=24    size=13
new HashMap<>(1000)    capacity=0     threshold=1024  size=0
after first put        capacity=1024  threshold=768   size=1

== 4. Treeification also needs capacity >= 64 ==
after 1 colliding puts     size=1   capacity=16   bucket[1]=Node
after 8 colliding puts     size=8   capacity=16   bucket[1]=Node
after 9 colliding puts     size=9   capacity=32   bucket[1]=Node
after 10 colliding puts    size=10  capacity=64   bucket[1]=Node
after 11 colliding puts    size=11  capacity=64   bucket[1]=TreeNode

== 5. HashMap treeification with colliding hashes ==
after 8 colliding puts     size=8   capacity=64   bucket[1]=Node
after 9 colliding puts     size=9   capacity=64   bucket[1]=TreeNode
after remove K9            size=8   capacity=64   bucket[1]=TreeNode
after remove K8            size=7   capacity=64   bucket[1]=TreeNode
after remove K7            size=6   capacity=64   bucket[1]=TreeNode
after remove K6            size=5   capacity=64   bucket[1]=Node
after remove K5            size=4   capacity=64   bucket[1]=Node
after remove K4            size=3   capacity=64   bucket[1]=Node
after remove K3            size=2   capacity=64   bucket[1]=Node
after remove K2            size=1   capacity=64   bucket[1]=Node

== 6. Mutating a key after insertion ==
inserted id=1: get=value containsKey=true size=1 bucket=1
after id 1 -> 2: get(same ref)=null containsKey=false size=1
entrySet still contains key=[MutableKey(id=2)]
remove(same ref)=null size=1

第 4 节为节省篇幅省略了第 2–7 次插入，完整逐次输出在原始文件中。U05 扩展场景的结尾行（同样在原始文件中）：

text
PASS map absent/null/duplicate/default/compute/merge-delete/null-rejection/recovery
PASS selection deque FIFO/LIFO/null; priority poll; sorted tie-break; set ordering; Enum order; identity map; comparator overflow repaired
PASS views fixed-size/write-through/snapshot/null; subList valid edit; map backed views; CME + iterator repair + removeIf; COW snapshot; CHM weak traversal (no global snapshot claim)
PASS actual resize split capacity=128 low=5:Node high=4:Node all mappings retained
PASS actual resize split capacity=128 low=6:Node high=7:TreeNode all mappings retained

如何读这份输出 ​

  • ArrayList：capacity=0 说明默认构造只持有共享空数组；第一次 add 后才分配长度 10。之后 10 → 15 → 22 → 33，是 oldCapacity + (oldCapacity >> 1) 的 1.5 倍增长，并按实际最小需求取较大值。
  • LinkedList：Node 同时持有 item、next、prev，每个元素都有额外的节点对象和两个引用；get(index) 必须从头或尾走到目标位置。
  • HashMap 容量：默认表在第一次 put 才分配为 16，阈值为 16 × 0.75 = 12；第 13 个元素触发扩容到 32，阈值 24。
  • new HashMap<>(1000)：构造参数经 tableSizeFor 变成 1024 的阈值，但表仍未分配；第一次 put 才分配 1024。threshold 在分配前暂时承载目标容量。
  • 树化门槛一：容量 64 已满足 MIN_TREEIFY_CAPACITY；前 8 个同哈希键仍在 Node 链表中，第 9 次插入才变成 TreeNode。原因是 putVal 中的 binCount 从 0 开始且不包含头节点，判断条件为 binCount >= TREEIFY_THRESHOLD - 1。
  • 树化门槛二：默认容量下，第 9 次插入触发的是 treeifyBin，但表长 16 < 64，函数改为 resize()；第 10 次再扩到 64；第 11 次插入才真正树化。这说明“桶内达到 8 就树化”省略了容量条件。
  • 退化：删除到 5 个节点时变回 Node。removeTreeNode 用根和近端子节点是否为空判断“树太小”，不是用 size <= 6；UNTREEIFY_THRESHOLD=6 只在扩容拆分 TreeNode.split 时使用。树形受键次序影响，因此不要在面试中把“删除到 6 退化”说成固定规则。
  • 可变键：插入后把参与 hashCode/equals 的 id 从 1 改成 2，同一个对象引用再也查不到，entrySet 却仍能看到它，remove 也删不掉。这是键的可变状态破坏了哈希定位，不是 HashMap 的“bug”。

失败边界 ​

  • 反射读取的是 JDK 私有字段；字段名、内部类和树化阈值的使用方式可能随 JDK 版本变化，不能作为跨版本契约。
  • 本实验只证明当前运行时下的行为，不证明并发安全。HashMap 在并发结构性修改下仍可能丢失更新、读到不一致状态；需要并发映射时应使用 ConcurrentHashMap 或外部同步。
  • 树化后的查找成本还取决于键是否可比较、哈希是否分散；不要从“有红黑树”推导出任何输入下都严格 O(log n)。
  • 本实验不测量吞吐或延迟，不能据此比较 ArrayList 与 LinkedList 的实际性能；选型应结合访问模式、内存占用和基准测试。

工程学习台　阅读讲解，学后自主自测。记录保存在本机浏览器。