java `iterator` 接口的 `remove()` 方法提供了一种安全且高效的方式，用于在遍历集合时移除元素。本文将深入探讨 `arraylist` 中 `iterator.remove()` 的内部实现原理，包括其如何利用 `lastret` 追踪元素索引、处理并发修改异常，并分析其时间复杂度，帮助开发者更好地理解和运用这一关键功能，从而避免常见的并发修改问题。
在Java集合框架中，Iterator 接口是遍历集合元素和安全移除元素的标准方式。尤其是在 ArrayList 等非线程安全的集合中，直接在循环中使用集合自身的 remove() 方法往往会导致 ConcurrentModificationException。Iterator.remove() 方法正是为了解决这一问题而设计的。
1. Iterator.remove() 的基本概念与使用
Iterator.remove() 方法允许开发者在迭代过程中从底层集合中移除当前迭代器指向的元素。它必须在调用 next() 方法之后，且在同一次 next() 调用和下一次 next() 调用之间只能被调用一次。
考虑以下示例代码，它展示了如何使用 Iterator.remove() 从 ArrayList 中移除偶数：
import java.util.ArrayList;
import java.util.Iterator;
public class IteratorRemoveExample {
public static void main(String[] args) {
ArrayList list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println("原始列表: " + list); // 输出: 原始列表: [1, 2, 3, 4]
Iterator it = list.iterator();
while (it.hasNext()) {
int x = it.next();
if (x % 2 == 0) {
it.remove(); // 移除偶数
} else {
System.out.print(x + " "); // 打印奇数
}
}
// 预期输出: 1 3
System.out.println("\n处理后的列表: " + list); // 输出: 处理后的列表: [1, 3]
}
} 上述代码的输出是 1 3，并且 ArrayList 中只剩下 1 和 3。这表明 it.remove() 成功地从 ArrayList 中移除了偶数元素。
立即学习“Java免费学习笔记（深入）”；
为什么不直接使用 list.remove(index) 或 list.remove(object)？
如果在上述 while 循环中，我们尝试使用 list.remove(x) 或 list.remove(someIndex)，将会抛出 ConcurrentModificationException。这是因为 ArrayList 的迭代器实现了“快速失败”（fail-fast）机制。当迭代器创建后，如果集合在迭代器之外被修改（即 modCount 不等于 expectedModCount），迭代器会在下一次操作时抛出此异常，以防止不确定的行为。Iterator.remove() 是 Iterator 接口提供的一种“安全”的修改方式，它会更新 expectedModCount，从而避免 ConcurrentModificationException。
2. ArrayList 中 Iterator.remove() 的内部机制
为了理解 Iterator.remove() 如何工作，我们需要深入查看 ArrayList 内部迭代器 Itr 的实现。ArrayList 内部有一个名为 Itr 的私有内部类，它实现了 Iterator 接口。Itr 类中的 remove() 方法是实现关键逻辑的地方：
// 简化后的 ArrayList.Itr.remove() 源码 private class Itr implements Iterator{ int cursor; // 下一个要返回的元素的索引 int lastRet = -1; // 上一个由 next() 返回的元素的索引，如果未调用 next() 或已移除，则为 -1 int expectedModCount = modCount; // 迭代器期望的修改次数 public void remove() { if (lastRet < 0) { // 如果在 next() 之前调用 remove()，或连续调用 remove() throw new IllegalStateException(); } checkForComodification(); // 检查是否有其他地方修改了集合 try { // 调用 ArrayList 外部类的 remove 方法，移除 lastRet 索引处的元素 ArrayList.this.remove(lastRet); // 移除后，cursor 指向的位置可能已经改变，需要更新 cursor = lastRet; // 将 lastRet 重置为 -1，防止多次移除同一个元素 lastRet = -1; // 更新 expectedModCount 以匹配当前的 modCount，防止后续操作抛出 ConcurrentModificationException expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { // 如果 ArrayList.this.remove 抛出异常，说明集合结构已损坏 throw new ConcurrentModificationException(); } } // ... 其他方法如 next(), hasNext(), checkForComodification() }
关键字段和方法解释：
- lastRet：这是一个非常重要的内部变量。它存储了上一次调用 next() 方法时返回的元素的索引。当 remove() 方法被调用时，它会使用 lastRet 来确定要移除哪个元素。如果 lastRet 为 -1，表示 next() 尚未被调用或该元素已被移除，此时调用 remove() 会抛出 IllegalStateException。
- cursor：表示下一个将要由 next() 方法返回的元素的索引。当元素被移除后，cursor 会被更新为 lastRet 的值，因为移除操作会使后续元素前移。
- modCount：这是 ArrayList 类的成员变量，记录了 ArrayList 结构被修改的次数（如添加、删除元素）。
- expectedModCount：这是 Itr 类的成员变量，在迭代器创建时被初始化为当前的 modCount。每次迭代器执行 next() 或 remove() 操作时，都会先调用 checkForComodification() 来检查 modCount 是否与 expectedModCount 相等。如果不等，则说明集合在迭代器之外被修改，会抛出 ConcurrentModificationException。
- ArrayList.this.remove(lastRet)：这是实际执行元素移除操作的地方。它调用的是 ArrayList 外部类的 remove(int index) 方法。此方法会将 lastRet 索引处的元素移除，并将该索引之后的所有元素向左移动一位，以填补空缺。
- lastRet = -1：在成功移除元素后，lastRet 被重置为 -1。这是为了确保在下次调用 next() 之前不能再次调用 remove()。
- expectedModCount = modCount：在 remove() 操作成功完成并更新了 ArrayList 的 modCount 后，迭代器会将其自身的 expectedModCount 更新为新的 modCount。这样，迭代器就“知道”了这次修改，并允许后续的迭代操作继续进行。
3. 时间复杂度分析
Iterator.remove() 方法的时间复杂度主要取决于其内部调用的 ArrayList.this.remove(lastRet) 方法。
ArrayList 的 remove(int index) 方法在移除指定索引的元素后，需要将其后的所有元素向前移动一位。如果 ArrayList 中有 n 个元素，并且我们移除了索引为 lastRet 的元素，那么需要移动的元素数量大约是 n - 1 - lastRet。
- 最坏情况：当 lastRet 为 0（即移除了第一个元素）时，需要移动 n-1 个元素，时间复杂度为 O(n)。
- 最好情况：当 lastRet 为 n-1（即移除了最后一个元素）时，不需要移动任何元素，时间复杂度为 O(1)。
- 平均情况：平均而言，lastRet 位于列表的中间，需要移动大约 n/2 个元素，时间复杂度为 O(n)。
因此，对于 ArrayList 而言，Iterator.remove() 方法的平均时间复杂度是 O(n)。在循环中频繁调用 remove() 可能会导致性能问题，尤其是在列表较大时。
4. 注意事项与最佳实践
在使用 Iterator.remove() 时，需要牢记以下几点以避免常见的错误：
- 调用顺序：remove() 方法必须在调用 next() 方法之后调用。如果 next() 尚未被调用，或者在上次 next() 调用后已经调用过 remove()，再次调用 remove() 会抛出 IllegalStateException。
- 一次 next() 对应一次 remove()：每次 next() 调用只能对应一次 remove() 调用。
- 避免并发修改：Iterator.remove() 是在单线程环境中安全修改集合的推荐方式。如果在迭代过程中，除了通过 Iterator.remove() 之外，还通过集合自身的 add()、remove() 或 clear() 等方法修改了集合，迭代器会抛出 ConcurrentModificationException。
- 线程安全集合：对于多线程环境，如果需要在迭代过程中进行修改，应考虑使用 java.util.concurrent 包下的线程安全集合，例如 CopyOnWriteArrayList。这些集合通常提供弱一致性迭代器，或者其修改操作本身就是线程安全的，不会抛出 ConcurrentModificationException。
示例：错误的使用方式
ArrayListlist = new ArrayList<>(); list.add(1); list.add(2); list.add(3); Iterator it = list.iterator(); it.remove(); // 错误！在 next() 之前调用，抛出 IllegalStateException
ArrayListlist = new ArrayList<>(); list.add(1); list.add(2); list.add(3); Iterator it = list.iterator(); while (it.hasNext()) { Integer x = it.next(); if (x == 2) { list.remove(x); // 错误！通过集合自身修改，抛出 ConcurrentModificationException } }
总结
Iterator.remove() 方法是 Java 集合框架中一个强大且重要的功能，它为开发者提供了一种在迭代过程中安全修改集合的机制。通过深入理解其内部工作原理，特别是 ArrayList 中 Itr 类的实现，以及 lastRet、cursor 和 modCount 等关键字段的作用，我们可以更好地掌握其使用方式，避免 IllegalStateException 和 ConcurrentModificationException 等常见问题。尽管其在 ArrayList 中的时间复杂度为 O(n)，但在需要边遍历边删除的场景下，它仍然是首选的解决方案。正确地运用 Iterator.remove() 是编写健壮、高效 Java 代码的关键一环。
