Java集合类性能测试与对比分析

ArrayList随机访问为O(1)，LinkedList为O(n)，因前者基于数组后者为链表；频繁索引遍历时ArrayList快3–10倍；仅头部/中间高频增删且无随机访问需求时才选LinkedList。

ArrayList 和 LinkedList 的随机访问性能差异明显

随机访问（比如 get(int index)）时，ArrayList 是 O(1)，LinkedList 是 O(n)。这不是理论推演，而是底层结构决定的：前者基于数组，后者靠双向链表逐个跳节点。

实操中容易误以为“链表插入快，所以通用更快”，但只要代码里有类似 list.get(i) 的循环遍历，LinkedList 往往比 ArrayList 慢 3–10 倍（JDK 17，百万元素级测试）。

• 用 ArrayList 替代 LinkedList 做索引遍历时，性能提升通常立竿见影
• 若真需要频繁在头部/中间插入删除，且不依赖随机访问，才考虑 LinkedList；否则优先选 ArrayList
• LinkedList 的 get() 在 JDK 9+ 有小幅优化（从头或尾择近遍历），但无法改变渐进复杂度

HashMap 的扩容触发条件与负载因子影响实际吞吐

HashMap 不是“一直快”。当元素数量超过 capacity × loadFactor（默认 0.75）时，会触发 rehash —— 重建哈希表、重散列所有键，这个过程是 O(n) 且阻塞操作。

常见错误是初始化时不预估大小，比如已知要放 10 万条记录，却用默认构造函数 new HashMap<>()（初始容量 16），结果触发约 16 次扩容，大量内存拷贝和 hash 重计算拖慢整体性能。

• 明确大小时，用 new HashMap<>(initialCapacity)，且 initialCapacity 应 ≥ 预期总数 ÷ 0.75，向上取最近 2 的幂（如 10 万 → 至少 131072）
• 负载因子设为 0.75 是时间与空间的权衡；调低（如 0.5）减少冲突但浪费内存；调高（如 0.9）节省内存但碰撞增多，get/put 可能退化为链表遍历
• JDK 8 中，当桶内链表长度 ≥ 8 且 table.length ≥ 64，链表转红黑树 —— 这个阈值不能改，但可通过合理初始容量避免过早进入树化路径

ConcurrentHashMap 的迭代器不抛 ConcurrentModificationException，但不保证强一致性

这是最容易被文档误导的一点：ConcurrentHashMap 的 keySet().iterator() 确实不会抛 ConcurrentModificationException，但它也不承诺“看到所有已提交的修改”。迭代过程可能跳过某些刚 put 的条目，也可能重复看到某些条目（取决于分段锁/Node 节点状态）。

很多业务代码把它当“线程安全版 ArrayList 迭代”用，结果在统计类场景出错 —— 比如并发写入 + 后台定时 dump 全量 key，发现总数对不上。

• 如果需要精确快照，用 mappingCount() 获取当前估算大小，或改用 new ConcurrentHashMap<>().keySet().toArray()（会加锁并复制，代价高但一致）
• 不要在迭代器上做依赖“全量可见”的逻辑，比如“遍历所有 key 并发调用远程服务”，应先收集 key 列表再处理
• forEach()、reduce() 等方法内部使用了更稳定的批量操作协议，比手动迭代器更可靠

性能测试必须绕开 JVM 预热和 GC 干扰

直接写个 for 循环跑 1000 次 put() 测 HashMap 速度？结果基本无效。HotSpot JVM 有 JIT 编译延迟，前几百次调用走的是解释执行，后面才优化成机器码；同时 GC 可能在任意时刻介入，导致某次耗时突增 10ms，拉垮平均值。

真实对比必须用 JMH（Java Microbenchmark Harness），它自动处理预热、fork JVM 进程、统计置信区间等。

public class MapBenchmark {
    @State(Scope.Benchmark)
    public static class MyState {
        HashMap map = new HashMap<>(10000);
    }

    @Benchmark
    public void put(Blackhole blackhole, MyState state) {
        state.map.put(ThreadLocalRandom.current().nextInt(), "v");
        blackhole.consume(state.map);
    }
}

• 不用 JMH 就别谈“XX 比 XX 快 20%”，那只是噪声
• 测试集合类时，确保 key/value 类型、hashCode 实现、数据分布（是否全相同 hash？）贴近真实场景
• GC 日志（-Xlog:gc*）必开，确认 benchmark 过程中没发生 full GC