【2026.1.5】学习笔记之Java 集合-1

1. ArrayList 的扩容机制：深度拆解

ArrayList 的动态扩容是 Java 面试的必考点，重点在于“为什么”和“怎么做”。

• 默认容量与延迟初始化：当你 new ArrayList() 时，系统并不会立刻分配 10 个空间，而是先给一个空数组。只有在第一次执行 add 操作时，才会真正分配 10 个单位的内存。
• 扩容触发条件：当当前元素个数（size）已经达到了数组的容量上限（length）时，就会触发扩容。
• 核心公式：int newCapacity = oldCapacity + (oldCapacity >> 1)。
• 深度理解 1.5 倍：
  • 位运算优化：使用右移运算符 >> 1 相当于除以 2，这在 CPU 层面执行极快，减少了运算时间。
  • 权衡利弊：扩容倍数选 1.5 是为了平衡“空间浪费”和“扩容频率”。如果倍数太大（如 2 倍）会浪费内存；如果太小（如 1.1 倍）则会导致频繁“搬家”影响性能。
• 搬家代价：扩容涉及创建新数组、通过 Arrays.copyOf 复制老数据、更新引用。在大数据量下，建议初始化时指定 initialCapacity 以减少扩容次数。

2. 线程安全：CopyOnWriteArrayList 的并发之美

这种 List 的设计初衷是为了解决多线程遍历时不抛出 ConcurrentModificationException。

• 写时复制（Copy-On-Write）流程：
  1. 独占写：写操作（如 add）必须加锁（JDK 8 用 ReentrantLock，JDK 11+ 用 synchronized），确保同一时刻只有一个线程在写。
  2. 物理隔离：不直接修改原数组，而是将原数组拷贝一份并让长度加 1。
  3. 引用切换：在新数组上改完后，通过 setArray(newElements) 改变 volatile 指针的指向。
• Volatile 的作用：底层数组被 volatile 修饰，保证了一旦写线程完成引用替换，读线程能立刻感知到新地址。
• 读操作的“无锁化”：读操作（get）完全不加锁，性能极高。
• 致命缺点：内存占用翻倍（写时有两份数组）；数据弱一致性（读线程在写线程完成前可能读到旧数据）。

3. Stream 流常用操作：函数式编程精要

Stream 让集合处理变得像流水线一样高效。

• 常用中间操作（返回 Stream，可级联）：
  • filter(p)：保留符合条件的元素。
  • map(f)：转换元素类型（如将 User 对象转为 String 姓名）。
  • sorted()：排序。
  • distinct()：去重。
• 常用终端操作（关闭流，产出结果）：
  • collect(Collectors.toList())：将结果收集回 List。
  • forEach(c)：逐个处理。
  • count()：统计个数。
  • anyMatch(p)：只要有一个符合条件就返回 true（短路操作）。

4. 数据结构：平衡二叉树 vs 红黑树 (HashMap 为何选后者？)

这是判断候选人对数据结构理解深度的重要题目。

• 平衡二叉树 (AVL)：
  • 特点：严格平衡，左右子树高度差不超过 1。
  • 优势：查询最快（层数最少）。
  • 劣势：插入和删除会导致频繁的“旋转”，维护成本极高。
• 红黑树 (R-B Tree)：
  • 特点：弱平衡，确保没有路径比其他路径长两倍。
  • 优势：它是查找、插入和删除的性能折中方案。
• HashMap 的决策逻辑： HashMap 会频繁进行插入和删除操作。 如果用 AVL，每次 put 可能都要旋转多次，写性能太差。 红黑树保证了最坏情况下的查询时间复杂度也是 O(\log n)，同时减少了维护平衡的开销。

5. 补充点：HashMap 为什么会有完整性破坏？

• 死循环问题：JDK 1.7 以前扩容使用“头插法”，并发下会导致链表成环，导致遍历时 CPU 100%。
• 数据丢失：JDK 1.8 虽然改用“尾插法”解决了死循环，但多线程并发 put 时，由于没有加锁，后一个线程的写入仍可能覆盖前一个线程的写入。
• 解决方案：在并发环境下必须使用 ConcurrentHashMap。它在 JDK 1.8 中通过 volatile + CAS + synchronized 的组合拳，将锁的粒度细化到了每个哈希桶的头节点上。

学习感悟：

今天的复习让我明白，Java 集合的设计核心就在于“在性能、安全和功能之间做取舍”。没有最好的结构，只有最适合场景的工具。