Java集合遍历时遇到的坑

黑洞代码

发布于 2021-01-14 15:36:55

6190

发布于 2021-01-14 15:36:55

文章被收录于专栏：落叶飞翔的蜗牛

面试常见问题之集合遍历时遇到的坑ConcurrentModificationException解析

面试题中可能会被问到对Java集合的了解情况，并深入集合底层的源码，以及使用集合的时候有没有遇到坑——这时候其实是想考察大家在日常工作中是否细心，一般不建议说，没有遇到坑，因为这样会给面试官感觉大家在工作中不细心，不仔细。

今天ConcurrentModificationException应该是比较常见的一个异常。尤其是对一些刚参加工作的同学，可能会经常遇见。那么，各位同学有没有详细了解过这个异常的底层原因呢？

画外音，如果各位同学在面试过程中回答上了这个问题，极有可能面临跟深层次的关于Java集合的面试。

1. 简单的demo

我们写一个简单的集合遍历的demo，来造成一个会出现ConcurrentModificationException异常的场景。

/** * @Author 无双 * @Date 2018/8/25 * @Description ConcurrentModificationException异常讲解 */ public class ConcurrentModificationExceptionDemo { public static void main(String[]args) { //定义一个list List<String> list = new ArrayList<>(); //添加一些元素 list.add("张三"); list.add("李四"); list.add("王五"); list.add("赵六"); //得到迭代器 Iterator<String> iterator = list.iterator(); //遍历list中的元素 while (iterator.hasNext()) { //集合中的每个元素 String element = iterator.next(); //删除李四 if ("李四".equals(element)) { list.remove(element); } } } }

运行demo，会得到如下的异常：

2. 异常原因解密

2.1 ArrayList.iterator()

首先看下ArrayList类的iterator()方法的实现，源码如下：

/**
 * Returns an iterator over the elements in this list in proper sequence.
 *
 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 *
 * @return an iterator over the elements in this list in proper sequence
 */
public Iterator<E> iterator() {
    return new Itr();
}

从源码可以看出，iterator()方法是返回了一个Itr类的对象。下面看下Itr的具体实现如下：

/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

Itr这个类不是很很复杂，Itr类是ArrayList类中的一个私有内部类。所以可以说，ArrayList的iterator()方法是通过Itr类的对象来工作的。

2.2 内部类Itr解析

Itr类成员变量解析：

·cursor：表示下一个要访问的元素的索引，从next()方法的具体实现就可看出。

·lastRet：表示上一个访问的元素的索引。

·expectedModCount：表示对ArrayList修改次数的期望值，它的初始值等于modCount。

·modCount是AbstractList类中的一个成员变量。PS： ArrayList集成了AbstractList；Itr是ArrayList类的内部类。

protected transient int modCount = 0;

这个值表示对ArrayList的修改次数，可以发现在add()和remove()方法中，都会修改modCount。

Itr类中hasNext()方法分析：

public boolean hasNext() {
    return cursor != size;
}

如果下一个访问的元素下标不等于ArrayList的大小，就表示有元素需要访问，这个很容易理解，如果下一个访问元素的下标等于ArrayList的大小，则说明到达ArrayList末尾了。

Itr类中next()方法分析：

public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

这里是非常关键的地方：首先在next()方法中会调用checkForComodification()方法，然后根据cursor的值获取到元素，并对cursor的值进行加1操作，接着将cursor+1之前的原值的值赋给lastRet，。初始时，cursor为0，lastRet为-1，那么调用一次之后，cursor的值为1，lastRet的值为0。

对应本例中，进入了next()方法后的状态如下图：注意此时，modCount为4，expectedModCount也为4。

2.3 ArrayList.remove()

ArrayList.remove()方法的源码如下：

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

从源码可以看到，直接执行元素删除的地方不在这个方法中，而是在fastRemove()中。下面看下fastRemove()方法的源码：

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

在fastRemove()方法中，首先对modCount进行加1操作（因为对集合修改了一次），然后接下来就是删除元素的操作，最后将size进行减1操作，并将引用置为null以方便垃圾收集器进行回收工作。

那么在本例中，程序运行了remove()方法后，注意此时各个变量的值：对于iterator，其expectedModCount为4，cursor的值为1，lastRet的值为2。

2.4 checkForModification()

执行完list.remove()后，会再次进入while循环，迭代下一个元素。

PS：注意！此时，Itr中的 expectedModCount是4，但是，ArrayList继承的AbstractList中的modCount = 5了！

看下checkForComodification()方法的实现如下：

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

源码很简单，就是modCount和expectedModCount不相等的时候就抛一个ConcurrentModificationException异常。

总结：调用list.remove()方法导致modCount和expectedModCount的值不一致。注意，像使用for-each进行迭代实际上也会出现这种问题。

3. 解决方案

Itr类中也有一个remove()方法，用这个方法就不会有问题。看下这个方法的实现如下：

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

这个方法最其实还是调用ArrayList的remove()方法，但是最关键的地方在于：这个方法执行最后一行，expectedModCount = modCount修改了两者的等价关系。

因此，在迭代器中如果要删除元素的话，需要调用Itr类的remove方法。下面给出正确的示范：

4. 扩展

第3节中解决方案是可以解决单线程下的问题，但是在做线程情况下，同样还是会出现异常，多线程演示demo代码如下：

分别用两个线程遍历list，其中线程2对list进行了删除操作，看下测试的结果如下：

结论是：多线程情况下，使用iterator.remove()还是会抛出ConcurrentModificationException异常。

有可能有同学说ArrayList是非线程安全的容器，换成Vector就没问题了，实际上换成Vector还是会出现这种错误。虽然Vector的方法采用了synchronized进行了同步，但是由于Vector是继承的AbstarctList，因此通过Iterator来访问容器的话，事实上是不需要获取锁就可以访问。那么显然，由于使用iterator对容器进行访问不需要获取锁，在多线程中就会造成当一个线程删除了元素，由于modCount是AbstarctList的成员变量，因此可能会导致在其他线程中modCount和expectedModCount值不等。有兴趣的同学可以自己尝试用Vector改造一下，这里给出相关类图，就不再用代码进行演示了。