ArrayList 遍历删除

发表于 2019-08-02 更新于 2019-08-03 本文字数： 1.4k 阅读时长 ≈ 5 分钟

list的遍历分为3种:

普通遍历, for(int i=0;i<list.size();i++)
增强for循环, for(Object x:list)
iterator遍历, Iterator<String> it = list.iterator(); while(it.hasNext()){}

同时ArrayList和线程安全的CopyOnWriteArrayList不同遍历下变现也不同，下面分类展示各种情况。

ArrayList

普通for循环遍历

// list {0, 1, 2, 3, 4}
for (int i = 0; i < list.size(); i++) {
  // index and number
  System.out.print(i + " " + list.get(i));
  if (list.get(i) % 2 == 0) {
    list.remove(list.get(i));
    System.out.print(" delete");
    i--; // 索引改变!
  }
}

/*
0 0 delete
0 1
1 2 delete
1 3
2 4 delete
*/

删除某个元素后，list的大小发生了变化，而你的索引也在变化，平时编程不注意可能会在遍历时导致一些访问越界的问题，因此不是特别推荐。

增强型for循环遍历

// list {0, 1, 2, 3, 4}
for (Integer num : list) {
  // number
  System.out.print(num);
  if (num % 2 == 0) {
    list.remove(num);
    System.out.print(" delete");
  }
}

删除第一个元素时是没有问题的，但删除后继续执行遍历过程的话就会抛出ConcurrentModificationException的异常。

使用iterator遍历

// list {0, 1, 2, 3, 4}
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    // index and number
    int num = it.next();
    System.out.print(num);
    if (num % 2 == 0) {
      it.remove();
      System.out.print(" delete");
    }
}

可以看到顺利的执行了遍历并删除的操作，因此最推荐的做法是使用iterator执行遍历删除操作。但要注意的是，使用iterator的remove方法，如果用list的remove方法同样会报上面提到的ConcurrentModificationException错误。

问题产生原因

fail-fast 机制

在JDK的集合类中有这样一段描述：

注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭代器的快速失败行为应该仅用于检测 bug。

“快速失败”也就是 fail-fast，它是 Java 集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。记住是有可能，而不是一定。例如：假设存在两个线程（线程 1、线程 2），线程 1 通过 Iterator 在遍历集合 A 中的元素，在某个时候线程 2 修改了集合 A 的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生 fail-fast 机制。

首先我们看看：

private class Itr implements Iterator<E> {
    int cursor;
    int lastRet = -1;
    int expectedModCount = ArrayList.this.modCount;
    public boolean hasNext() {
        return (this.cursor != ArrayList.this.size);
    }
    public E next() {
        checkForComodification();
        /** 省略此处代码 */
    }
    public void remove() {
        if (this.lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        /** 省略此处代码 */
    }
    final void checkForComodification() {
        if (ArrayList.this.modCount == this.expectedModCount)
            return;
        throw new ConcurrentModificationException();
    }
}

迭代器在调用 next()、remove() 方法时都是调用 checkForComodification() 方法，该方法主要就是检测 modCount == expectedModCount ? 若不等则抛出 ConcurrentModificationException 异常，从而产生 fail-fast 机制。

expectedModCount 是在 Itr 中定义的：int expectedModCount = ArrayList.this.modCount;所以他的值是不可能会修改的，所以会变的就是 modCount。modCount 是在 AbstractList 中定义的，为全局变量：

1	protected transient int modCount = 0;

ArrayList 中无论 add、remove、clear 方法只要是涉及了改变 ArrayList 元素的个数的方法都会导致 modCount 的改变。

有两个线程（线程 A，线程 B），其中线程 A 负责遍历 list、线程B修改 list。线程 A 在遍历 list 过程的某个时候（此时 expectedModCount = modCount=N），线程启动，同时线程B增加一个元素，这是 modCount 的值发生改变（modCount = N + 1）。线程 A 继续遍历执行 next 方法时，通告 checkForComodification 方法发现 expectedModCount = N ，而 modCount = N + 1，两者不等，这时就抛出ConcurrentModificationException 异常，从而产生 fail-fast 机制。

CopyOnWriteArrayList

CopyOnWriteArrayList 是 ArrayList 的一个线程安全的变体，其中所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的。该类产生的开销比较大，但是在两种情况下，它非常适合使用。1：在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时。2：当遍历操作的数量大大超过可变操作的数量时。遇到这两种情况使用 CopyOnWriteArrayList 来替代 ArrayList 再适合不过了。

普通for循环

和ArrayList相同，list的大小发生了变化，索引也在变化，在遍历时也有可能导致一些访问越界的问题，因此不是特别推荐。

增强型for循环

CopyOnWriterArrayList 的方法没有像 ArrayList 中使用 checkForComodification 方法来判断 expectedModCount 与 modCount 是否相等, 既CopyOnWriterArrayList 不会产生 ConcurrentModificationException 异常，它使用迭代器不会产生 fail-fast 机制。

为什么呢？我们以 add 方法为例：

public boolean add(E paramE) {
    ReentrantLock localReentrantLock = this.lock;
    localReentrantLock.lock();
    try {
        Object[] arrayOfObject1 = getArray();
        int i = arrayOfObject1.length;

        //CopyOnWriterArrayList 的 add 方法与 ArrayList 的 add 方法
        Object[] arrayOfObject2 = Arrays.copyOf(arrayOfObject1, i + 1);
        arrayOfObject2[i] = paramE;
        setArray(arrayOfObject2);
        //最大的不同之处

        int j = 1;
        return j;
    } finally {
        localReentrantLock.unlock();
    }
}

final void setArray(Object[] paramArrayOfObject) {
    this.array = paramArrayOfObject;
}

CopyOnWriterArrayList 所代表的核心概念就是：任何对 array 在结构上有所改变的操作（add、remove、clear 等），CopyOnWriterArrayList 都会 copy 现有的数据，再在 copy 的数据上修改，这样就不会影响 COWIterator 中的数据了，修改完成之后改变原有数据的引用即可。同时这样造成的代价就是产生大量的对象，同时数组的 copy 也是相当有损耗的。

iterator遍历

和 ArrayList 不同, CopyOnWriteArrayList不支持iterator遍历, 创建迭代器时复制一份数组拷贝(快照)，在迭代期间数组不会被改变，调用remove、set、add方法抛出UnsupportedOperationException异常。