Java ArrayList 迭代与并发操作：性能优化与线程安全深度解析-java教程-PHP中文网

java arraylist 迭代与并发操作：性能优化与线程安全深度解析

本文深入探讨了在迭代 ArrayList 时进行添加、移除和修改操作的正确姿势，旨在避免 ConcurrentModificationException 并优化性能。文章对比了不同迭代方式的效率，重点分析了 Iterator.remove() 与 removeIf() 的区别，并揭示了频繁结构性修改可能导致的二次时间复杂度问题。此外，还详细阐述了 synchronizedList 在多线程环境下的局限性，强调了对可变元素进行全面同步的重要性，以实现真正的线程安全。

理解迭代与修改的本质

在 Java 中，对 ArrayList 进行迭代时同时进行结构性修改（添加或移除元素）是一个常见的挑战，如果不正确处理，很容易导致 ConcurrentModificationException。理解不同操作的底层机制是解决问题的关键。

1. 修改（更新元素内容）

当我们需要在迭代过程中修改 ArrayList 中现有元素的内容时，无论是使用增强型 for 循环（foreach 循环）还是显式 Iterator 循环，其编译后的字节码是基本相同的，因此在性能上没有差异。这种操作不涉及 ArrayList 内部数组结构的改变，只是改变了引用指向的对象的状态。

// 显式 Iterator 示例
for (Iterator<Item> it = items.iterator(); it.hasNext(); ) {
    Item item = it.next();
    item.update(); // 修改 Item 对象内部状态，不影响 ArrayList 结构
}

// 增强型 for 循环示例
for (Item item : items) {
    item.update(); // 修改 Item 对象内部状态，不影响 ArrayList 结构
}

登录后复制

需要注意的是，ArrayList 存储的是对象的引用，而非对象本身。item.update() 操作是针对 Item 对象本身进行的，与 ArrayList 是否包含它无关。一个对象可以同时存在于多个集合中，对其内容的修改会反映在所有引用它的地方。

立即学习“Java免费学习笔记（深入）”；

2. 移除元素

在迭代过程中从 ArrayList 中移除元素，是导致 ConcurrentModificationException 的主要原因之一。这是因为 ArrayList 的迭代器是“快速失败”（fail-fast）的，它会在检测到迭代过程中集合结构被修改（除了通过迭代器自身方法修改外）时抛出此异常。

正确移除方式：Iterator.remove()

使用 Iterator 提供的 remove() 方法是迭代过程中安全移除元素的标准方式。

Iterator<Item> itemIterator = items.iterator();
while (itemIterator.hasNext()) {
    Item item = itemIterator.next();
    // 检查是否需要移除 item
    if (shouldRemove(item)) {
        itemIterator.remove(); // 使用迭代器移除当前元素
    }
}

登录后复制

然而，频繁地使用 Iterator.remove()，尤其是在 ArrayList 的中间位置移除元素时，会导致性能问题。每次移除元素后，ArrayList 都需要将移除点之后的所有元素向前移动一位，这涉及到底层数组的复制操作。如果在一个循环中进行多次这样的操作，其时间复杂度可能达到二次方（O(n^2)）。

高效移除方式：Collection.removeIf()

Java 8 引入的 removeIf() 方法是更高效的移除多个元素的方案。它利用内部迭代，在一次遍历中标记所有需要移除的元素，然后一次性地将剩余元素复制到正确的位置，从而将时间复杂度优化为线性（O(n)）。

// 使用 removeIf() 移除满足条件的元素
items.removeIf(item -> /* 返回 true 表示需要移除 item */);

登录后复制

如果 removeIf() 不适用，或者需要更复杂的逻辑，另一种线性时间复杂度的策略是创建一个新的 ArrayList，只复制那些不需要移除的元素。

3. 添加元素

在迭代 ArrayList 时添加元素比移除更为复杂，因为标准 Iterator 不支持添加操作。

使用 ListIterator.add()

ListIterator 提供了 add() 方法，允许在迭代过程中添加元素。

爱图表

AI驱动的智能化图表创作平台

305

查看详情

ListIterator<Item> itemListIterator = list.listIterator();
while (itemListIterator.hasNext()) {
    // 执行某些操作
    Item item = itemListIterator.next();
    if (shouldAddAfter(item)) {
        itemListIterator.add(newItem); // 在当前位置之后添加新元素
    }
}

登录后复制

与 Iterator.remove() 类似，ListIterator.add() 同样面临性能问题。在 ArrayList 的中间位置频繁添加元素，每次都会导致其后所有元素的后移，同样可能导致二次方时间复杂度。

最佳实践：先收集后添加或构建新列表

对于需要添加大量元素的情况，最佳实践是：

在迭代过程中，将所有需要添加的新元素收集到一个临时列表中。
迭代结束后，使用 addAll() 方法将临时列表中的元素一次性添加到原 ArrayList 中。
或者，直接构建一个新的 ArrayList，在遍历旧列表的同时，根据需要添加旧元素和新元素。

性能考量：避免二次时间复杂度

理解 ArrayList 的底层实现对于性能优化至关重要。ArrayList 是基于数组实现的，其内部存储的是对象的引用。当在数组的中间位置进行插入或删除操作时，为了保持数组的连续性，其后的所有元素都需要被移动。

单次移动成本：移动的成本相对较低，因为只涉及引用的复制，而非整个对象的复制。
频繁移动成本：如果在一个循环中，对 ArrayList 进行多次中间位置的插入或删除，每次操作都会触发一次元素移动。假设 ArrayList 有 N 个元素，每次移动的平均成本是 O(N)。如果在循环中执行 N 次这样的操作，总成本将是 O(N^2)，这在 N 较大时会导致严重的性能问题。

因此，当需要进行大量结构性修改时，应优先考虑能够将操作批处理或利用内部优化机制的方法（如 removeIf()），或考虑使用更适合频繁插入/删除的数据结构（如 LinkedList，但其随机访问性能较差），或构建一个新的 ArrayList。

并发与线程安全：超越ConcurrentModificationException

ConcurrentModificationException 是一个“快速失败”机制，它用于在单线程或多线程环境中，当集合在迭代过程中被意外修改时，尽早地抛出异常以防止不确定的行为。它本身不是一个线程安全保证。即使在 synchronized 块中，如果一个线程在迭代，另一个线程在修改（且修改不是通过迭代器自身完成），仍然会抛出此异常。

synchronizedList 的局限性

Collections.synchronizedList() 方法可以返回一个线程安全的 List 包装器。这意味着对 add、remove、get 等方法的调用都将被同步。

List<Item> synchronizedItems = Collections.synchronizedList(new ArrayList<>());

// 即使使用 synchronizedList，迭代时仍需手动同步
synchronized (synchronizedItems) {
    for (Item item : synchronizedItems) {
        // 对 item 的操作
    }
}

登录后复制

然而，synchronizedList 存在一个关键局限性：

它只保护列表的结构操作：synchronizedList 确保了 add、remove、get 等方法在多线程环境下的原子性。
它不保护列表中包含的元素：如果 ArrayList 中存储的是可变对象（如 Item），synchronizedList 无法阻止其他线程在获取到 Item 对象的引用后，对其内部状态进行修改。

例如：

Item item = synchronizedItems.get(someIndex); // 线程安全地获取引用
// 此时，另一个线程可能在 synchronizedItems 之外修改 item 的内容
item.update(); // 这段代码如果不在同步块内，则不是线程安全的

登录后复制

因此，仅仅使用 synchronizedList 并不能保证应用程序的完全线程安全。

全面的线程安全策略

要实现真正的线程安全，需要考虑以下几点：

保护列表结构：使用 synchronizedList 或手动 synchronized 块来保护所有对列表结构（添加、移除、迭代）的操作。
保护可变元素：如果列表中包含的是可变对象，那么所有对这些可变对象内部状态的访问和修改，都必须通过相同的同步机制来保护。这意味着，即使从一个同步的列表中获取了元素，后续对该元素的修改也应该在同步块内进行。
考虑不可变对象：如果可能，使用不可变对象作为集合的元素。这样，一旦元素被添加到集合中，其内容就不能再被修改，从而大大简化了线程安全问题。
使用并发集合：对于高并发场景，可以考虑使用 java.util.concurrent 包中的并发集合类，例如 CopyOnWriteArrayList。
- CopyOnWriteArrayList 在修改（add、set、remove）时会复制底层数组，这保证了迭代器在修改期间不会抛出 ConcurrentModificationException。
- 缺点：每次修改都会产生一个新数组的副本，这对于大型列表或频繁修改的场景来说，性能开销非常大。它更适用于读操作远多于写操作的场景。

总而言之，synchronizedList 在实际的复杂多线程应用中，其优势并不明显。任何非平凡的用例都几乎总是需要手动进行同步或锁定，不仅要保护集合本身，还要保护集合中包含的可变元素。

总结与最佳实践

在 ArrayList 的迭代与并发操作中，以下是核心总结和最佳实践：

修改（更新元素内容）：增强型 for 循环和显式 Iterator 循环在更新元素内容时性能无异。关键在于 ArrayList 存储的是引用，修改的是引用指向的对象。
移除元素：
- 避免在增强型 for 循环或标准 Iterator 循环中直接调用 items.remove()。
- 对于少量、单次移除，使用 Iterator.remove()。
- 对于批量、条件移除，优先使用 items.removeIf()，它提供线性的性能。
- 如果 removeIf() 不适用，可以考虑构建一个新的 ArrayList 来排除不需要的元素。
添加元素：
- 标准 Iterator 不支持添加。
- ListIterator.add() 可以添加，但频繁使用可能导致二次时间复杂度。
- 最佳实践是收集需要添加的元素，在迭代结束后一次性添加（addAll()），或者在迭代时直接构建一个新的 ArrayList。
性能优化：
- 警惕 ArrayList 中间位置的频繁结构性修改（添加/移除），这可能导致二次时间复杂度。
- 优先使用能够批处理操作或避免元素移动的方法（如 removeIf()）。
线程安全：
- ConcurrentModificationException 是快速失败机制，而非线程安全保证。
- synchronizedList 仅保护列表结构操作，不保护可变元素的内容。
- 真正的线程安全要求对所有可变元素的所有访问和修改都使用相同的同步机制。
- 对于高并发且读多写少的场景，可考虑 CopyOnWriteArrayList，但需注意其写操作的性能开销。
- 对于复杂场景，手动同步（synchronized 块或 Lock 接口）通常是更灵活和必要的选择。