集合契约、ArrayList、LinkedList 与 HashMap：从复杂度表到源码分支

结论基线：API 语义以 Java SE 17 为准，实现分析以 OpenJDK 17u jdk-17.0.12+7 为准。字段名、树化时机和内部结构属于实现细节，不是跨 JDK 版本的永久契约。实验在本机 OpenJDK 17.0.12 上实际运行；换版本需重新核对常量与输出。

问题：为什么复杂度表不够

“ArrayList 查询快、LinkedList 插入快、HashMap 查询 O(1)”这三句话都省略了前提。ArrayList.contains(x) 仍要线性扫描；LinkedList 只有在已经定位到节点时插入才是 O(1)，按下标定位仍是 O(n)；HashMap 的 O(1) 是平均期望，碰撞、扩容、树化和哈希质量都会改变实际成本。

集合行为要分三层看：

层	回答的问题	例子
契约	这个接口承诺什么、允许什么	List 有序可重复；Map 键唯一；迭代器 fail-fast 是 best-effort
实现	当前 JDK 用哪种结构、哪些分支	数组扩容、双向链表、桶数组、红黑树
并发协议	多线程交错时哪些结果合法	HashMap 非线程安全；ConcurrentHashMap 的原子操作边界

三者不能互相替代。用实现细节解释契约会过时，用契约解释性能会漏掉数据规模、访问模式和内存布局。本文先固定契约，再逐段读源码，最后用实验核对“实际运行到了哪一步”。

契约层：List、Map 与迭代器承诺什么

List 承诺有序、可重复、可按索引访问；具体实现决定索引访问和中间插入的成本。Map 承诺键唯一、键到值的映射；HashMap 额外允许一个 null 键和多个 null 值，但不保证迭代顺序，也不保证顺序随时间不变。HashMap 的负载因子默认 0.75，阈值通常是 capacity × loadFactor；这些是 API 文档承诺的语义，不是某个版本的偶然行为。

迭代器的 fail-fast 只用于尽早暴露结构性修改，是 best-effort 检测，不是并发控制。HashMap 与 ArrayList 的文档都明确说明：不能依赖 ConcurrentModificationException 保证正确性。单线程下“边遍历边删除”也会触发它；多线程下即使某次没触发，也不代表安全。

几个容易混淆的契约：

• Collections.unmodifiableList(list) 是视图，不是拷贝；原列表变化仍可见，只是不能通过视图修改。
• Arrays.asList(array) 返回固定长度列表，add/remove 可能抛 UnsupportedOperationException，但 set 会写回原数组。
• List.of(...) 返回不可变列表，不接受 null；List.copyOf(...) 做的是浅拷贝。
• subList(from, to) 是视图；对原列表的结构性修改可能让子列表失效。
• Map.keySet()、entrySet()、values() 都是视图，底层映射变化会影响它们。

以上契约的固定源码、实验断言、分层题目与"快照 vs 视图"选型见集合选择、视图与迭代并发契约正文；本文保持集合内部结构主线，不重复展开。Map 缺席/映射 null 与重复键的 compute/merge 分支也在该正文。

ArrayList：数组、容量与 grow 原码

ArrayList 内部是 Object[] elementData，逻辑元素个数是 size。默认构造不会立即分配 10 个槽位，而是共享一个空数组；第一次 add 才分配 DEFAULT_CAPACITY = 10。new ArrayList<>(0) 走另一条路径：它使用 EMPTY_ELEMENTDATA，第一次扩容按所需最小容量分配，通常得到 1，而不是 10；new ArrayList<>(n)（n > 0）则在构造时就分配长度为 n 的数组。

扩容逻辑集中在 grow。

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

原码

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

ArraysSupport.newLength(old, minGrowth, prefGrowth) 的核心是 old + max(minGrowth, prefGrowth)，并检查溢出与软上限。grow 传入的首选增长量是 oldCapacity >> 1，所以常规路径约为 1.5 倍；当所需最小增长更大时，按 minGrowth 满足，不会为了凑 1.5 倍而分配不足。Arrays.copyOf 会分配新数组并复制旧元素，扩容期间同时存在旧数组和新数组，带来峰值内存与 GC 压力。

因此工程上有两个方向：

• 已知元素规模时预分配，减少复制次数，但会提前占用内存；
• 默认构造省启动内存，但前几次扩容要复制，且 size 与 capacity 不是一回事。

trimToSize() 只把数组缩到当前 size，减少闲置容量；ensureCapacity(n) 只保证至少能放 n 个元素，不改变 size。两者都不改变元素和顺序。

图中容量时间线与实验输出一一对应：0 → 10 → 15 → 22 → 33。注意箭头上的“add #11”只是触发点，真正的判断是 size + 1 是否超过当前数组长度。

LinkedList：双向链表与按索引定位

LinkedList 内部是双向链表，每个节点持有 item、next、prev，列表持有 first、last。addFirst、addLast 以及在已知节点处删除是 O(1)；但 get(index) 必须先找到节点。源码明确从较近的一端遍历：

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

原码

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

所以 get(i) 是 O(min(i, n-i))，不是 O(1)。add(index, e) 也要先 node(index)，只有已经持有迭代器位置或首尾节点时，改链才是常数时间。LinkedList 的每个元素额外带一个 Node 对象和两个引用，缓存局部性差；顺序遍历的常数通常也比数组大。

操作	ArrayList	LinkedList
get(i)	O(1)	O(min(i, n-i))
尾部追加	摊还 O(1)，扩容复制	O(1)，分配 Node
中间插入/删除（已定位）	O(n) 移动元素	O(1) 改链
按值查找	O(n)	O(n)
每元素额外开销	一个数组引用	Node 对象 + 两个引用
缓存局部性	好	差

需要双端队列时，ArrayDeque 往往比 LinkedList 更合适；但最终仍应以实际访问模式、分配采样和基准测试为准，而不是只背表。

HashMap：hash 与 putVal 的完整分支

HashMap 的核心是 Node<K,V>[] table。表长度始终是 2 的幂；默认构造延迟到第一次 put 才分配 16 个桶。定位分两步：先扰动哈希，再用掩码取索引。

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

原码

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

h ^ (h >>> 16) 把高 16 位异或进低位，让高位的差异也能影响小表的桶索引。容量是 2 的幂时，(n - 1) & hash 等价于对 n 取模，但只使用低位；扩容时也只需检查新增的那一位，不必重新计算完整哈希。null 键的 hash 按 0 处理，落在 0 号桶。

putVal 把定位、覆盖、树化与扩容串在一条主路径上。

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

原码

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            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;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

按分支读：

1. 表为空或长度为 0：先 resize()，默认分配 16。
2. 目标桶为空：直接放新 Node，结束。
3. 桶首节点 hash 相同且 key 相等：覆盖值，onlyIfAbsent 为 true 时保留旧值。
4. 桶首是 TreeNode：走 putTreeVal，树内查找/插入。
5. 否则遍历链表：找到相等 key 就覆盖；到链尾就追加；追加后若 binCount >= TREEIFY_THRESHOLD - 1，调用 treeifyBin。
6. 只有新增映射才 ++modCount 和 ++size；size > threshold 时扩容。

binCount 从 0 开始且不包含头节点，所以“桶里已有 8 个节点，第 9 次插入”才触发树化检查。这个细节决定了默认容量下要第 11 次插入才真正树化，后文用实验核对。

构造参数不是“精确分配”。new HashMap<>(1000) 把 1000 经 tableSizeFor 向上取到 1024，并暂存到 threshold；第一次 put 才分配长度为 1024 的表，随后阈值变为 1024 × 0.75 = 768。因此它只保证“表长至少是 1024”，不等于“装 1000 个元素不会扩容”：第 769 个元素就会触发扩容。

扩容：resize 与树桶拆分

扩容时容量翻倍，每个节点不需要重新计算完整哈希，只需要看 hash & oldCap：结果为 0 留在原索引 j，非 0 移动到 j + oldCap。原因是容量是 2 的幂，扩容只多使用一位哈希。

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

原码

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

resize 先算新容量与新阈值：已有表且未到上限就翻倍；oldThr > 0 表示构造时把初始容量暂存在阈值里；两者都没有才用默认 16。分配新表后逐桶迁移：

• 单节点：直接按 e.hash & (newCap - 1) 放到新索引。
• 树桶：调用 TreeNode.split，按 hash & bit 拆成低位/高位两棵，某侧数量 <= UNTREEIFY_THRESHOLD 时退化为链表。
• 链表：用 loHead/loTail 与 hiHead/hiTail 保持相对顺序，结束时清空尾节点的 next，分别放到 j 和 j + oldCap。

扩容的成本不只是“复制数组”：还要分配新表、遍历旧桶、重建链/树，并产生额外 GC 压力。已知元素规模时，可以用 expectedSize / 0.75 + 1 估算初始容量，再让 tableSizeFor 向上取整；这会用更多内存换取更少扩容次数。反过来，初始容量过大或负载因子过低会增加迭代成本，因为 HashMap 的迭代时间与“容量 + 元素数”成正比。

HashMap 不是线程安全的。并发结构性修改可能导致更新丢失、size 不一致或读到中间状态；即使某个版本没有出现死循环，也不能把“没报错”当作安全。并发场景应使用 ConcurrentHashMap，或用 Collections.synchronizedMap 包一层，并对复合操作做客户端同步。

图中左半部分是链表拆分，右半部分是树化/退化条件。核对时把 oldCap 位测试与源码 hash & oldCap 对齐，不要把“移动到 j + oldCap”理解成重新计算所有哈希。

树化与退化：8、64、6 不是一条规则

相关常量：

常量	值	作用
TREEIFY_THRESHOLD	8	桶内链表达到阈值后尝试树化
UNTREEIFY_THRESHOLD	6	扩容拆分树桶时，某一侧不超过该值则退化
MIN_TREEIFY_CAPACITY	64	表长小于该值时，优先扩容而不是树化

“桶里有 8 个节点就树化”是不完整的。putVal 在链尾追加后判断 binCount >= TREEIFY_THRESHOLD - 1，而 binCount 不包含头节点；因此容量已经达到 64 时，第 9 次插入才触发树化。若表长小于 64，treeifyBin 会改为 resize()，本次不树化。

树化入口的实际分支：

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

原码

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

treeifyBin 只做两件事：表太小时扩容；否则把桶内节点替换成 TreeNode 并建立树。它不保证“任何输入下都是严格 O(log n)”。

树桶拆分时，split 分别统计 lc、hc，某侧数量 <= 6 就退化：

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

原码

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

删除路径又不遵守 6。removeTreeNode 根据根和近端子节点是否为空判断树是否过小，源码注释明确“触发点依树形在 2 到 6 之间”：

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

原码

/**
 * Removes the given node, that must be present before this call.
 * This is messier than typical red-black deletion code because we
 * cannot swap the contents of an interior node with a leaf
 * successor that is pinned by "next" pointers that are accessible
 * independently during traversal. So instead we swap the tree
 * linkages. If the current tree appears to have too few nodes,
 * the bin is converted back to a plain bin. (The test triggers
 * somewhere between 2 and 6 nodes, depending on tree structure).
 */
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                          boolean movable) {
    int n;
    if (tab == null || (n = tab.length) == 0)
        return;
    int index = (n - 1) & hash;
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    if (pred == null)
        tab[index] = first = succ;
    else
        pred.next = succ;
    if (succ != null)
        succ.prev = pred;
    if (first == null)
        return;
    if (root.parent != null)
        root = root.root();
    if (root == null
        || (movable
            && (root.right == null
                || (rl = root.left) == null
                || rl.left == null))) {
        tab[index] = first.untreeify(map);  // too small
        return;
    }

实验会展示：9 个同哈希键树化后删除到 5 个节点才退化。因此“删除到 6 一定退化”是错的；6 是 split 的阈值，删除路径按树形判断。

树化可以缓解碰撞攻击，但不是免费防护：

• 树节点约占普通节点的两倍空间；
• 构造大量同哈希键仍要消耗 CPU、内存和树操作成本；
• 若哈希全部相同且键不可比较，TreeNode.find 在无法比较时会递归搜索两侧子树，最坏仍可能线性；
• 对外部可控的键空间，还应限制输入规模、使用高质量哈希，并避免把不可信对象直接作为长期缓存键。

键契约与可变键反例

Object.equals 的默认实现是引用相等；重写 equals 时通常必须重写 hashCode，并满足“两个对象 equals 相等，则 hashCode 必须相等”。HashMap 先用 hash 找桶，再用 equals 确认逻辑键；两步中任何一步被可变字段破坏，映射就会失配。

实验中的故障链是：

插入 MutableKey(id=1) -> 落在 bucket 1
把同一个对象的 id 改成 2
get/containsKey -> 按 hash=2 去找，bucket 1 里找不到
entrySet 遍历 -> 仍能看到这个节点（它还在旧桶）
remove -> 同样找不到，节点删不掉

这不是 HashMap 的 bug，而是键的可变状态违反了哈希容器的身份契约。修复方式：使用不可变键（如 String、Long、record）；如果业务身份必须变化，先删除旧键，再以新状态重新插入；不要把可变实体对象直接作为键。

record 也不是自动安全的键：组件引用是 final，但引用的 List 仍可变，生成的 equals/hashCode 会随列表内容变化。真正不可变需要防御性复制并约束嵌套数据。BigDecimal 的 equals 与 compareTo 语义不同，金额单位、规模和规范化必须按契约选择；不能一律用浮点或字符串代替。

迭代与并发协议

ArrayList 的迭代器按索引前进，next() 先检查 modCount 是否等于创建时的 expectedModCount；Itr.remove() 调用列表删除后会把 expectedModCount 同步回新值，所以迭代器自己的删除是安全的。直接 list.remove(...) 会改变 modCount，下一次 next() 抛 ConcurrentModificationException。

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

原码

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    // prevent creating a synthetic constructor
    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

HashMap 的迭代器先沿桶内链表走，再扫描下一个非空桶；它也检查 modCount：

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

原码

final Node<K,V> nextNode() {
    Node<K,V>[] t;
    Node<K,V> e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    if ((next = (current = e).next) == null && (t = table) != null) {
        do {} while (index < t.length && (next = t[index++]) == null);
    }
    return e;
}

这条实现解释了迭代成本：要扫描桶数组，再遍历桶内节点，所以与 capacity + size 相关；初始容量过大，即使元素很少，迭代也要扫过更多空桶。也解释了为什么 map.put 新键、map.remove 会导致遍历中的 CME，而仅替换已有键的值不一定改变 modCount。

fail-fast 只是检测，不是同步协议。并发场景：

• 读多写少、需要原子复合操作：用 ConcurrentHashMap 的 compute、merge 等接口，而不是“先 get 再 put”；
• 需要整体同步：用 Collections.synchronizedMap 包一层，并在遍历时对 map 加锁；
• 需要一致快照：复制或使用并发容器提供的弱一致迭代，并明确“弱一致”意味着什么；
• 不要把 ConcurrentHashMap 当成“所有复合操作自动原子”；跨键不变量仍需外部协调。

COW 快照迭代器、CHM 弱一致遍历的固定源码与实测、迭代中删除的两种修复方式（迭代器 remove 与 removeIf）在集合选择、视图与迭代并发契约正文展开；本文的 Itr/nextNode 源码保持 fail-fast 机制的权威讲解。

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

实验目录：labs/collections。单文件、无第三方依赖，本机运行版本为 OpenJDK 17.0.12；U05（2026-10-24）扩展场景后用本机 Oracle JDK 17.0.12 重跑并更新了 out/collections-probe.txt，本文第 1–6 节断言保持不变。

实验代码

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

run.sh 编译并运行 CollectionsProbe，原始输出写入 out/collections-probe.txt。--add-opens java.base/java.util=ALL-UNNAMED 只用于反射读取 JDK 私有字段，不是业务代码配置。

关键实测结果：

== 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 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 K7            size=6   capacity=64   bucket[1]=TreeNode
after remove K6            size=5   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 节只截取首次出现的关键行；完整输出见文件。）

实验证明了什么：

• ArrayList 的默认 10 是首次插入才分配；10 → 15 → 22 → 33 是约 1.5 倍增长。
• HashMap 的构造参数只决定阈值，表在首次插入才分配；1000 被向上取整为 1024，阈值 768。
• 容量 64 时第 9 次同桶插入树化；默认容量时要到第 11 次，因为中间发生了两次扩容。
• 删除到 5 个节点时已经退化，说明删除路径不遵守“6 才退化”。
• 可变键改变 id 后，get/containsKey/remove 都失败，entrySet 仍能看到旧节点。

实验不证明什么：不证明并发安全，不证明跨 JDK 版本行为一致，也不提供吞吐/延迟数据。反射依赖内部字段，换版本必须重跑；第 4 节截取省略了中间行，完整证据以输出文件为准。

追问链

第一层：为什么默认负载因子是 0.75？

这是时间与空间的折中，不是数学定理。JDK 源码注释用泊松分布解释：在随机哈希和 0.75 阈值下，桶内节点数达到 8 的概率极低，因此树化是异常路径而非常态。实际系统仍应测量自己的哈希分布、内存预算和尾延迟，不能把 0.75 当作所有负载的最优值。

第二层：如果哈希分布极差，红黑树能救多少？

树化能把“桶内链表”的最坏路径从线性降为对数，但前提是键可比较或哈希不同。若大量键哈希相同且不可比较，find 在无法比较时会搜索两侧子树，查找仍可能退化；同时树节点约占普通节点两倍空间，构造树本身也要 CPU。防护应包括限制不可信键的数量、使用高质量哈希、监控桶冲突和单请求资源预算，而不是只依赖树化。

第三层：设计一个高并发本地规则缓存，你会怎么选？

先明确事实源和一致性：规则配置以数据库/配置中心为事实源，本地只保存不可变快照；键用稳定的 ruleId 或版本号，不用可变实体。容器选 ConcurrentHashMap 或成熟缓存库（如 Caffeine），设置有界容量、过期和刷新策略；更新时构建新快照再整体替换，读路径不加锁。监控命中率、加载耗时、淘汰、内存和旧版本残留；缓存不可用时降级到事实源或保守策略，并说明降级边界。这里没有“万能集合”，只有与一致性、容量和故障模型匹配的选择。

技术案例

以下场景用于分析技术选型与故障边界，可使用实验数据验证，无需填写个人项目经历。

• 审核任务列表：批量查库后顺序遍历、按下标分页，优先 ArrayList；按查询上限预设容量，减少扩容复制。证据可以是接口的分配采样、GC 日志或压测中的 P99，而不是“感觉更快”。
• 审核规则缓存：按 ruleId 查找，使用不可变规则快照 + ConcurrentHashMap/volatile 引用替换；不要用可变规则实体作键。记录快照版本、加载耗时、命中率和更新后的旧版本清理。
• 消息模板/积分账户：读多写少、需要容量上限时，评估 Caffeine 等有界缓存；普通 HashMap 只适合单线程或外部已同步的短生命周期场景。多线程共享写入必须换并发容器，跨实例一致性仍由数据库/Redis 等外部机制保证。
• 故障复盘：如果遇到“缓存越用越大、删不掉”的问题，优先检查键是否可变、是否重写了 equals/hashCode、是否无界增长；用堆直方图、JFR 分配采样和 entrySet 抽样形成证据链。

来源与版本

来源	版本	用途
Java SE 17 HashMap API	Java SE 17	null、顺序、负载因子、非同步、fail-fast 契约
OpenJDK 17u HashMap 源码	jdk-17.0.12+7	hash（L336）、putVal（L623）、resize（L675）、treeifyBin（L753）、迭代器（L1593）、removeTreeNode（L2171）、split（L2289）
Java SE 17 ArrayList API	Java SE 17	非同步、fail-fast、容量语义
OpenJDK 17u ArrayList 源码	jdk-17.0.12+7	DEFAULT_CAPACITY（L118）、grow（L231）、Itr（L953）
Java SE 17 LinkedList API	Java SE 17	双端队列与列表语义
OpenJDK 17u LinkedList 源码	jdk-17.0.12+7	node(index) 从近端遍历（L570）、Node 结构（L974）
Java SE 17 Object API	Java SE 17	equals/hashCode 契约
本地 CollectionsProbe 实验	OpenJDK 17.0.12	容量、树化、可变键实测输出

访问日期：2026-10-22。源码行号以 jdk-17.0.12+7 标签为准；实验运行版本为 17.0.12。若升级 JDK，请重新核对常量、分支和实验输出。

闭卷验收

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