石河子市网站建设_网站建设公司_企业官网_seo优化

目录

1. ArrayList 的扩容机制：它凭什么能“自动变大”？

2. 线程安全的 List：CopyOnWriteArrayList 的“写时复制”黑科技

3. Stream 流：从“遍历”到“加工”的飞跃

4. 数据结构的抉择：红黑树 vs 平衡二叉树 (AVL)

5. 补充：并发环境下的 Map 选择

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 集合的设计核心就在于“在性能、安全和功能之间做取舍”。没有最好的结构，只有最适合场景的工具。