工程学习台

主题

主要章节

集合选择、视图与迭代并发契约：从访问模式到运行时协议 ​

结论基线：API 语义以 Java SE 17 为准，实现分析以 OpenJDK 17u jdk-17.0.12+7 为准。字段名与实现分支属于实现细节；实验在本机 Oracle JDK 17.0.12（x86_64）实际运行。ArrayList/LinkedList/HashMap 的内部结构、扩容与树化见集合内部结构正文，本文不重复。

选择：先按访问模式与键约束选型 ​

选集合前先回答三个问题：按什么访问（索引/键/两端/优先级）？键的身份用什么定义（equals、比较器还是引用）？null 与重复是否合法？这三问比"ArrayList 快、LinkedList 快"的口诀更能决定选型，复杂度表只覆盖第三优先的问题。

需求首选关键契约
索引访问、尾部追加ArrayList摊还 O(1) 追加；预分配见集合正文
双端进出（栈/队列）ArrayDeque拒绝 null；比 LinkedList 少每元素节点开销
优先级出队PriorityQueue头是最小元素（按比较器）；remove() 空抛 NoSuchElementException，poll() 返回 null
去重、不关心顺序HashSet迭代顺序无承诺，且可能随扩容变化
去重、保持插入序LinkedHashSet额外链表维护插入序；迭代顺序确定
排序遍历/范围查询TreeSet/TreeMap"重复"由比较器定义，不是 equals
枚举键/值EnumMap/EnumSet按枚举声明序迭代，不是插入序
按 == 而非 equals 区分键IdentityHashMap引用相等；不是通用 Map 实现

排序集合的身份规则最容易踩错：TreeMap.put 走到 cmp == 0 时直接替换值并返回旧值，不调用 equals。两个业务上"不同"的对象只要比较器判 0，就只能留下一个。

原码连续摘录（仅统一公共缩进，截取方法局部）：TreeMap.java，jdk-17.0.12+7，L782–L806。

原码java
    private V put(K key, V value, boolean replaceOld) {
        Entry<K,V> t = root;
        if (t == null) {
            addEntryToEmptyMap(key, value);
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else {
                    V oldValue = t.value;
                    if (replaceOld || oldValue == null) {
                        t.value = value;
                    }
                    return oldValue;
                }

cmp == 0 分支就是"比较器等价即同一键"。修复手段是给比较器加 tie-breaker（如 thenComparingInt(Job::id)），让身份不同的对象不再比较为 0；不能靠"对象 equals 不相等"来争辩，TreeMap 根本不问 equals。

第二个高频错误是"减法比较器"：(a, b) -> a - b 在 Integer.MIN_VALUE 与 Integer.MAX_VALUE 上溢出变号，排序结果与预期相反。Integer.compare(a, b) 才是安全写法。ArrayDeque 则在入口拒绝 null：

原码连续摘录（仅统一公共缩进，截取方法局部）：ArrayDeque.java，jdk-17.0.12+7，L301–L308。

原码java
    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        final Object[] es = elements;
        es[tail] = e;
        if (head == (tail = inc(tail, es.length)))
            grow(1);
    }

同样的"null 不是合法元素"约束也出现在 List.of、Set.of、Map.of 与 List.copyOf；而 LinkedList、HashMap 的键值允许 null。null 契约属于类型级差异，选型表里必须当一行看，不能等运行时才发现。

Map 的缺席、null 与重复键契约 ​

Map 的四个高频 API 各有一个"存在性"分支，口诀记不住，直接读 HashMap 的实现分支最可靠。

get 返回 null 有两种含义：键不存在，或键映射到 null。containsKey 才能区分；getOrDefault 只对"缺席"给默认值，对"映射到 null"返回 null 本身。统计计数时这种二义会直接造成错误：counts.get(key) + 1 对缺席和 null 值都会 NPE。

覆盖与重复键：put 对已有键替换值并返回旧值（返回 null 表示此前没有映射）；putIfAbsent 只有键不存在或映射 null 时才放。C01 的重复键案例在这里分岔：批处理里"同 id 两条记录"用 put 会静默覆盖，用 computeIfAbsent/merge 才有机会显式合并或拒绝。

computeIfAbsent 把三种情况分开处理，源码分支：

原码连续摘录（仅统一公共缩进，截取方法局部）：HashMap.java，jdk-17.0.12+7，L1187–L1223。

原码java
    public V computeIfAbsent(K key,
                             Function<? super K, ? extends V> mappingFunction) {
        if (mappingFunction == null)
            throw new NullPointerException();
        int hash = hash(key);
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        if (size > threshold || (tab = table) == null ||
            (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((first = tab[i = (n - 1) & hash]) != null) {
            if (first instanceof TreeNode)
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
            V oldValue;
            if (old != null && (oldValue = old.value) != null) {
                afterNodeAccess(old);
                return oldValue;
            }
        }
        int mc = modCount;
        V v = mappingFunction.apply(key);
        if (mc != modCount) { throw new ConcurrentModificationException(); }
        if (v == null) {
            return null;

三个分支按序读：已有非 null 映射时不执行计算函数直接返回旧值；已有映射但旧值是 null（或键缺席）时执行计算；计算返回 null 时不插入任何条目。也就是说"映射到 null"被当作缺席对待——这正是与 getOrDefault 语义对齐的实现选择。还有一条易漏的边界：计算函数里再改同一张 map 会命中 mc != modCount 检查抛 ConcurrentModificationException。

merge 是"存在则合并、缺席则放入"的完整版，且明确支持"合并结果为 null → 删除"：

原码连续摘录（仅统一公共缩进，截取方法局部）：HashMap.java，jdk-17.0.12+7，L1352–L1396。

原码java
    public V merge(K key, V value,
                   BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        if (value == null || remappingFunction == null)
            throw new NullPointerException();
        int hash = hash(key);
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        if (size > threshold || (tab = table) == null ||
            (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((first = tab[i = (n - 1) & hash]) != null) {
            if (first instanceof TreeNode)
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
        }
        if (old != null) {
            V v;
            if (old.value != null) {
                int mc = modCount;
                v = remappingFunction.apply(old.value, value);
                if (mc != modCount) {
                    throw new ConcurrentModificationException();
                }
            } else {
                v = value;
            }
            if (v != null) {
                old.value = v;
                afterNodeAccess(old);
            }
            else
                removeNode(hash, key, null, false, true);
            return v;

value == null 在入口就被拒绝（NPE）；合并结果为 null 时调用 removeNode 删除条目——"null 结果表示删除"是 API 契约，不是实现巧合。并发场景的两个差异必须记住：ConcurrentHashMap 拒绝 null 键与 null 值（用 null 表达"没有"在并发读取下不可区分），且其 compute/merge 对同一键是原子的，HashMap 则要求外部同步。跨键不变量（如"总量守恒"）任何容器都不保证，需要外部协调。

视图、固定大小与快照 ​

"改不动的列表"有三种，防护对象完全不同：

形态本质原容器变化自身写入null 元素
Arrays.asList(array)定长视图，包装原数组set 写回原数组add/remove 抛 UnsupportedOperationException允许
Collections.unmodifiableList(list)只读视图，别名原列表变化可见一切写抛 UOE允许
List.of(...)/List.copyOf(...)不可变快照（浅拷贝一层）不影响返回列表一切写抛 UOE拒绝（NPE）

Arrays.asList 的"写回"分支在源码里一目了然：

原码连续摘录（仅统一公共缩进，截取方法局部）：Arrays.java，jdk-17.0.12+7，L4128–L4175。

原码java
    private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable
    {
        @java.io.Serial
        private static final long serialVersionUID = -2764017481108945198L;
        @SuppressWarnings("serial") // Conditionally serializable
        private final E[] a;

        ArrayList(E[] array) {
            a = Objects.requireNonNull(array);
        }

        @Override
        public int size() {
            return a.length;
        }

        @Override
        public Object[] toArray() {
            return Arrays.copyOf(a, a.length, Object[].class);
        }

        @Override
        @SuppressWarnings("unchecked")
        public <T> T[] toArray(T[] a) {
            int size = size();
            if (a.length < size)
                return Arrays.copyOf(this.a, size,
                                     (Class<? extends T[]>) a.getClass());
            System.arraycopy(this.a, 0, a, 0, size);
            if (a.length > size)
                a[size] = null;
            return a;
        }

        @Override
        public E get(int index) {
            return a[index];
        }

        @Override
        public E set(int index, E element) {
            E oldValue = a[index];
            a[index] = element;
            return oldValue;
        }

        @Override

set 直接写 a[index]，所以修改会出现在原数组上；add/remove 没有被覆写，落到 AbstractList 的默认实现抛 UOE。"定长"不等于"只读"，这是两个概念。

subList(from, to) 同样是视图：通过子列表增删写透父列表；但对父列表做绕过子列表的结构性修改后，子列表的使用规范未定义（当前实现快速失败）。Map 的三个集合视图 keySet()、entrySet()、values() 全部写透：键视图 remove 删除条目，键视图 add 无意义抛 UOE；entrySet 迭代器的 setValue 写回映射；values().remove(v) 删除对应条目。视图是"看同一个容器"，快照是"复制一层引用"——把 unmodifiableList 当快照交给别人，对方仍能通过原引用改数据。

迭代契约：fail-fast 是检测，不是保护 ​

集合内部结构正文已给出 ArrayList.Itr 与 HashMap 迭代器的固定源码：结构性修改使 modCount 偏离迭代器保存的 expectedModCount，下一次 next() 抛 ConcurrentModificationException（CME）。本文补三条实践边界：

  1. 迭代器自己的 remove() 是安全的：删除后把 expectedModCount 同步回新值；但在没有 next() 之前调用抛 IllegalStateException。修正"边遍历边删"的正确姿势之一就是统一走 it.remove()。
  2. removeIf(predicate) 是批量条件删除的替代：内部处理结构与计数，不要求调用方管迭代器；对 ArrayList 还有减少搬移的实现优化。
  3. for-each 循环体里直接 list.remove(...) 仍会触发 CME——for-each 底层就是迭代器。CME 是 best-effort 检测，文档明确不保证；并发下"没抛 CME"不等于安全，它是调试信号而不是并发协议。

并发读协议：COW 快照与 CHM 弱一致 ​

CopyOnWriteArrayList 的迭代器不引用列表，而是捕获构造时刻的底层数组：

原码连续摘录（仅统一公共缩进，截取方法局部）：CopyOnWriteArrayList.java，jdk-17.0.12+7，L1023–L1026。

原码java
    public Iterator<E> iterator() {
        return new COWIterator<E>(getArray(), 0);
    }

原码连续摘录（仅统一公共缩进，截取方法局部）：CopyOnWriteArrayList.java，jdk-17.0.12+7，L1077–L1087。

原码java
    static final class COWIterator<E> implements ListIterator<E> {
        /** Snapshot of the array */
        private final Object[] snapshot;
        /** Index of element to be returned by subsequent call to next.  */
        private int cursor;

        COWIterator(Object[] es, int initialCursor) {
            cursor = initialCursor;
            snapshot = es;
        }

快照语义的代价：迭代开始后的修改看不到（实验可证）；remove/set/add 不支持；每次写操作复制整个数组，O(n) 内存与复制成本，写者之间互斥。它适合"读极多、写极少、列表小"的监听器/规则列表，不适合频繁追加的大列表。

ConcurrentHashMap 的迭代器是弱一致：不抛 CME，也不承诺一次性快照。Traverser.advance 展示了它如何在遍历中处理并发扩容：

原码连续摘录（仅统一公共缩进，截取方法局部）：ConcurrentHashMap.java，jdk-17.0.12+7，L3353–L3384。

原码java
        final Node<K,V> advance() {
            Node<K,V> e;
            if ((e = next) != null)
                e = e.next;
            for (;;) {
                Node<K,V>[] t; int i, n;  // must use locals in checks
                if (e != null)
                    return next = e;
                if (baseIndex >= baseLimit || (t = tab) == null ||
                    (n = t.length) <= (i = index) || i < 0)
                    return next = null;
                if ((e = tabAt(t, i)) != null && e.hash < 0) {
                    if (e instanceof ForwardingNode) {
                        tab = ((ForwardingNode<K,V>)e).nextTable;
                        e = null;
                        pushState(t, i, n);
                        continue;
                    }
                    else if (e instanceof TreeBin)
                        e = ((TreeBin<K,V>)e).first;
                    else
                        e = null;
                }
                if (stack != null)
                    recoverState(n);
                else if ((index = i + baseSize) >= n)
                    index = ++baseIndex; // visit upper slots if present
            }
        }

遍历期间遇到 ForwardingNode（该桶已被搬到新表）就切到 nextTable 继续——所以扩容不破坏遍历。弱一致的含义要按 API 文档口径说：创建迭代器之后的修改可能反映、可能不反映，元素不会重复返回（尽力），没有任何"当前完整快照"的承诺。需要一致快照就显式复制；需要复合操作原子就用 compute/merge；Collections.synchronizedMap 迭代时仍要手动持锁。这三个是不同诉求的不同答案，不能互换。

设计案例：规则缓存与订单榜单（算例，非实测） ​

以下数字是假设算例，用于比较方案的成本与恢复责任，不是性能实测。

负载假设：审核服务 2000 请求/s，每请求读一次规则表；规则 500 条、平均 2KB/条，全表约 1MB；规则平台每 5s 发布一次新版本（0.2 写/s）。不变量：单个请求内看到的规则必须来自同一版本；榜单键必须唯一且金额可对账。

方案 A：不可变快照 + volatile 引用替换。 发布线程用 Map.copyOf 建新快照后整体替换引用。读路径零锁、版本自洽天然成立（引用一换就是新版本）；成本：每 5s 复制 500 个引用 + 包装对象，约几 KB/次，可忽略；读取方持有跨请求旧引用时会用旧版本，需要版本号字段让日志可追溯。恢复：发布失败保留旧引用即自动回滚，回滚成本≈0。责任：发布者负责构建完整快照并校验后再替换。

方案 B：ConcurrentHashMap 逐条 put/compute 增量更新。 成本：无整表复制，内存占用低；但发布过程中请求可能读到"新版本第 3 条 + 旧版本第 499 条"的混合状态，版本自洽不变量被破坏。若业务要求自洽，必须加版本字段并在读侧校验/重试，或改为双缓冲。恢复：更新中断后表内是半新半旧，需要重新发布整版，恢复成本高于 A。

榜单统计与重复键：sales.stream().collect(toMap(Sale::id, Sale::amount)) 在上游重复 id 时抛 IllegalStateException，这是 fail-fast；预期有重复时必须显式给合并函数 toMap(..., Integer::sum) 或改 groupingBy。假设上游 5% 重复率，5000 条订单约 250 组重复——静默 put 覆盖会丢失其中一组金额且无任何信号；显式合并的可对账不变量是"Σ 收集结果 == Σ 原始金额"，由管道作者负责验证。谁负责恢复：数据管道作者，不是容器。

条件变化与边界 ​

条件变化需要复核的点
换 JDK 版本/厂商TreeMap/ArrayDeque/HashMap 的实现分支与实验输出；API 契约以对应版本文档为准
读侧并发强度上升COW 写成本、CHM 扩容期遍历行为；需要实测而非本文外推
键来自外部输入哈希碰撞与树化边界见集合正文；TreeSet 比较器必须处理不可信顺序
数据源为远程/分页"快照"只是某一时刻，跨页一致性要靠版本号或请求内固定引用
需要跨键事务容器不提供；回到业务协议与外部存储约束

实验：输入、步骤、预期与边界 ​

实验目录：labs/collections。单文件、无第三方依赖；公开入口是仓库根的 labs/java-senior/run.sh collections（或直接 labs/collections/run.sh），运行 CollectionsProbe；本轮新增 map 契约、选择、视图/迭代、resize 拆分场景。

实验代码bash
cd <仓库根>
JAVA_HOME=/Library/Java/JavaVirtualMachines/jdk-17.jdk/Contents/Home \
  bash labs/java-senior/run.sh collections

U05 关键实测（完整原始输出见 out/collections-probe.txt，本轮运行版本 Oracle JDK 17.0.12，x86_64）：

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

场景与预期：重复键 put 返回旧值；computeIfAbsent 对映射 null 当缺席计算、返回 null 不插入，修正后恢复；merge 合并、null 结果删除、null 输入 NPE、ConcurrentHashMap 拒绝 null 值；减法比较器对 MIN/MAX 溢出、Integer.compare 修复；TreeSet 比较器等价键 size()==1、tie-breaker 后为 2；LinkedHashSet 保持插入序而 HashSet 只承诺成员关系；List.of(null) NPE；Arrays.asList set 写回/add UOE；视图别名可见原变化、List.copyOf 快照独立且拒 null；CME 后迭代器 remove 恢复、removeIf 批量删除；COW 迭代器看不到并发新增且不支持 remove；CHM 弱一致遍历无 CME 但不承诺快照。

边界：实验是单线程行为契约加有限并发读观察，不证明并发安全强度，不提供吞吐数据；反射读取内部字段的场景依赖 JDK 内部结构（见集合正文），换版本重跑；out/collections-probe.txt 的历史输出（2026-10-22，OpenJDK 17.0.12）与本轮输出独立保存。

追问链 ​

第一层：为什么 TreeSet 不用 equals 判重？ ​

排序容器只依赖全序。要求 equals 一致会让"可排序"与"相等"强耦合：很多业务对象的全序是复合字段（分数+时间），与逻辑相等（id）不同源。代价是选型时必须显式决定身份语义并写 tie-breaker；SortedMap/SortedSet 的文档把这一点写在 put/add 契约里，不是实现怪癖。

第二层：视图和快照在评审代码时怎么区分？ ​

看返回路径是否触达原容器：Arrays.asList/subList/keySet/unmodifiableXxx 都是别名，调用方拿到的是"另一个引用，同一个数据"；List.copyOf/toUnmodifiableList 是复制一层引用的快照。评审时追两个问题：谁还持有原引用？元素本身可变吗？只答对第一个还会漏掉"快照里装着 StringBuilder"这类元素级可变问题（详见类型正文防御复制段）。

第三层：COW、CHM、synchronizedMap 怎么选？ ​

先问访问模式：读极多写极少且列表小 → COW；并发读写、键级原子性 → CHM + compute/merge；已有外部锁、只需串行安全 → synchronizedMap（遍历手动持锁）。再问不变量：跨键一致、跨容器一致、版本自洽都不属于容器能力，需要业务协议。最后用实验口径验证：弱一致不是快照，快照不是实时。

第四层：computeIfAbsent 的映射函数里还能改 map 吗？ ​

HashMap 的实现通过 modCount 检查把这种自嵌套当作并发修改拒绝（CME）；ConcurrentHashMap 则对同一键的 mapping function 有更严格约束（递归更新同一映射可能死锁或抛 IllegalStateException）。正确写法是映射函数只算值不改容器；跨键编排放外面。

来源与版本 ​

来源版本用途
Java SE 17 java.util 包摘要Java SE 17各实现选择契约、null 与顺序约定
Java SE 17 Map APIJava SE 17get 二义、computeIfAbsent/merge 存在性契约
Java SE 17 CopyOnWriteArrayListJava SE 17快照迭代器与写入成本
Java SE 17 ConcurrentHashMapJava SE 17弱一致、null 拒绝、检索原子性边界
OpenJDK 17u TreeMap 源码jdk-17.0.12+7比较器等价键分支（L782）
OpenJDK 17u HashMap 源码jdk-17.0.12+7computeIfAbsent（L1187）、merge（L1352）
OpenJDK 17u Arrays 源码jdk-17.0.12+7Arrays$ArrayList 定长视图（L4128）
OpenJDK 17u CopyOnWriteArrayList 源码jdk-17.0.12+7iterator 快照（L1023）、COWIterator（L1077）
OpenJDK 17u ConcurrentHashMap 源码jdk-17.0.12+7Traverser.advance 弱一致遍历（L3353）
本地 CollectionsProbe 实验Oracle JDK 17.0.12本轮契约行为实测输出

访问日期：2026-10-24。源码行号以 jdk-17.0.12+7 标签为准；实验运行版本为 Oracle 17.0.12（x86_64），与 U04 的 Liberica 17.0.19（arm64，另机）独立记录。

闭卷验收 ​

本页 10 道闭卷题收进了下方自测面板：先回忆，再展开参考答案与评分点，最后给三档自评。

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