首页 > 其他分享 >从List 删除元素开始说起

从List 删除元素开始说起

时间：2023-02-13 16:22:05浏览次数：74  
标签：删除 iterator 说起 ArrayList list remove modCount ConcurrentModificationException Li

前言

写错过List删除元素的方法，看到过正确方法，老是记错，还是写篇文章记录一下，mark.

 

先看一段代码：

class TestArrayListIterator {
    public static void main(String[] args)  {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(10);
        Iterator<Integer> iterator = list.iterator();
        while(iterator.hasNext()){
            Integer integer = iterator.next();
            if(integer==10) {
                list.remove(integer);   //注意这个地方
            }
        }
    }
}


调试下上面的这个程序，会报运行时异常 ConcurrentModificationException

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.AbstractList$Itr.checkForComodification(Unknown Source)
    at java.util.AbstractList$Itr.next(Unknown Source)
    at  com.notify.TestArrayListIterator.main(TestArrayListIterator.java:17)

 

我们跟进去报错信息, 会发现是在iterator.next() 这一行代码中报的错，这里有两个问题：

1）为什么iterator.hasNext()这段代码执行结果为true? （不为true执行不到next()方法）
2）为什么next方法会报java.util.ConcurrentModificationException这个错误？

 

我们先来讲第二个。

 

1、为什么next方法会报java.util.ConcurrentModificationException这个错误？

我们先看next()方法的代码， 顺带给出ArrayList中的迭代器的定义：

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];
        }
        // ...

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

}


我们看checkForComodification()方法， 正是这个方法抛了ConcurrentModificationException异常。那这个异常条件中的modCount 和 expectedModCount？又是个什么玩意？

modCount到底是干什么的呢？

在ArrayList,LinkedList,HashMap等等的内部实现增，删，改中我们总能看到modCount的身影，modCount字面意思就是修改次数，但为什么要记录modCount的修改次数呢？
大家发现一个公共特点没有，所有使用modCount属性的全是线程不安全的，这是为什么呢？说明这个玩意肯定和线程安全有关系喽，那有什么关系呢

通常地，在集合源码中存在这个modCount变量时，基本上可以说明这个类是线程不安全的。这个变量在集合初始化的时候，就将modCount赋值给exceptCound；在集合迭代器中，对modCount与exceptCount进行比较，如果出现两者不相等，说明有其他线程对该集合进行了修改操作（add或remove）,这个时候系统就会抛出CurrentModifactionException异常，这从逻辑上防止了多线程并发操作集合时，迭代器中数据紊乱的局面。

我们以ArrayList的add()和remove()方法为例，来看一下代码：

 

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;  // 注意这里

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    

    /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        rangeCheck(index);

        modCount++;  // 注意这里
        E oldValue = elementData(index);

        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

        return oldValue;
    }
}

可以看到，在代码中，新增和删除方法过程中都会修改modCount, 这里的modCount有一点版本控制的意思，可以理解成version，在特定的操作下需要对version进行检查，适用于Fail-Fast机制。

这里我们提到了一个fail-Fast机制，这个又是什么呢？买个关子，后面一点再讲


好了，我们知道，add()和remove()方法会修改modCount这个值，那上述那个代码中异常的原因就很清楚了，根据上文ArrayList中的迭代器的定义，
迭代器初始化的时候，字段expectedModCount赋值为modCount， 而在调用list.remove(integer)以后，modCount值被更改，但是迭代器中的expectedModCount没有更改，因此在checkForComodification()方法中校验不通过，会报异常。


那么，正确的删除操作代码是什么呢？，我们把 

list.remove(integer)

替换成

Integer integer = iterator.next();
class TestArrayListIterator {
    public static void main(String[] args)  {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(10);
        list.add(20);
        Iterator<Integer> iterator = list.iterator();
        while(iterator.hasNext()){
            Integer integer = iterator.next();
            if(integer==10) {
                iterator.remove(); //注意这个地方
//                list.remove(integer);   //注意这个地方
            }
        }
        System.out.println(list);
    }
}

 

运行结果为：[20]

可以看到，这次就运行成功了，那么这次为什么不会报java.util.ConcurrentModificationException异常呢？我们看iterator的方法的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();
            }
        }

 

我们发现，在迭代器的remove()方法中，同步修改了expectedModCount的值，因此不会报java.util.ConcurrentModificationException异常。

说到这里，我们可以很好的解释什么叫做fail—fast机制了：

Fail-Fast 机制

我们知道 java.util.ArrayList等 不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了ArrayList ，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是通过 modCount 域，modCount 顾名思义就是修改次数，对ArrayList 内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了 ArrayList .
注意到 modCount 声明为 volatile，保证线程之间修改的可见性。

 

回到最开始的例子，我有一个疑惑就是，这个错误报的是并发修改异常，网上也说，modCount这个字段是为了防止并发修改产生的？
但是上述的例子我自认为并没有发生并发修改，因此，我认为，关于modCount字段更准确的说法是：

modCount只是在增加或者删除结构数据的时候才会记录，更新元素并不会记录。modCount的存在只是为了在遍历过程中删除或添加元素导致遍历不准确的问题，他解决的是关于迭代器Iterator的遍历问题，和多线程无关。多线程中调用的方法中如果有利用Iterator的地方，就会产生java.util.ConcurrentModificationException异常。

因此，list单线程遍历的时候set元素并不会抛出异常，但是add和remove则会。


题外话，iterator记录的是创建iterator实例的时候对象的状态，后续对象的更改不会同步到iterator实例：
例如：下面这个代码也会报java.util.ConcurrentModificationException异常，因为我们在创建迭代器以后又修改了list,

class TestArrayListIterator {
    public static void main(String[] args)  {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(10);
        Iterator<Integer> iterator = list.iterator();
        list.add(20);
//        Iterator<Integer> iterator2 = list.iterator();
        while(iterator.hasNext()){
            Integer integer = iterator.next();
            if(integer==10) {
                System.out.println(integer);
            }
        }
        System.out.println(list);
    }
}

 

读者可以自行断点对比iterator和iterator2的内容。

上述代码也证明了，modCount哥并发编程是无关的，私以为java.util.ConcurrentModificationException异常很有歧义。

 

以上，我们可以看出，凡是利用Iterator的地方，我们都不能对ArrayList进行任何修改操作，因此我们可以看出：

  1. 只能利用Iterator提供的remove进行删除操作
  2. 面对多线程还需要删除的时候，必须把整个迭代循环加锁，否则多个迭代器同时删除，互相的modCount发生改变就会报错。

 

2、为什么iterator.hasNext()这段代码执行结果为true? 

我们先看Java-ArrayList.Itr类（Iterator的实现）

hasNext()的源码为：

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

 

因此，当运行到这一行的时候，cursor = 1 但是size=0，因此校验通过。

标签：删除,iterator,说起,ArrayList,list,remove,modCount,ConcurrentModificationException,Li
From： https://www.cnblogs.com/r1-12king/p/17116688.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99