澳门新葡萄京官网注册 8

Java ArrayList删除特定元素的方法

ArrayList是最常用的一种java集合,在开发中我们常常需要从ArrayList中删除特定元素。有几种常用的方法:

一,fail-fast简介

在JDK的Collection中我们时常会看到类似于这样的话:

ArrayList

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

HashMap

注意,迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。

在这两段话中反复地提到”快速失败”。那么何为”快速失败”机制呢?

fail-fast
机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。

Vector、ArrayList在迭代的时候如果同时对其进行修改就会抛出ConcurrentModificationException异常。下面我们就来讨论以下这个异常出现的原因以及解决办法。

最朴实的方法,使用下标的方式:

二,fail-fast示例

单线程中:

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.add(2);
    Iterator<Integer> iterator = list.iterator();
    while(iterator.hasNext()){
        //报错地方
        Integer integer = iterator.next();
        if(integer == 2)
            list.remove(integer);
    }
}

运行结果:

澳门新葡萄京官网注册 1

多线程中:

public class Fail_Fast {
    private static List<Integer> list = new ArrayList<Integer>();
    //线程1,iterator遍历集合
    private static class thread1 extends Thread{
        public void run() {
            Iterator<Integer> iterator = list.iterator();
            while(iterator.hasNext()){
                //报错地方
                int i = iterator.next();
                System.out.println("Thread1 遍历:" + i);
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    //线程2,满足条件时候修改集合结构
    private static class thread2 extends Thread{  
        public void run(){
            int i = 0;
            while(i < 10){
                System.out.println("Thread2 run:" + i);
                if(i == 4)
                    list.remove(i);//删除一个元素。
                i++;
            }
        }
    }

    public static void main(String[] args) {  
        for(int i = 0 ; i < 10;i++){
            list.add(i);
        }
        new thread1().start();
        new thread2().start();
    }
}

运行结果:

澳门新葡萄京官网注册 2

初步知道fail-fast产生的原因就在于程序在对
collection 进行迭代时,某个线程对该 collection
在结构上对其做了修改,这时迭代器就会抛出ConcurrentModificationException
异常信息,从而产生 fail-fast。

无论是直接迭代还是在Java5.0引入的for-each循环语法中,对容器类进行迭代的标准方式都是使用Iterator。然而,如果有其它线程并发地修改容器,那么即使是使用迭代器也无法避免在迭代期间对容器加锁。在设计同步容器类的迭代器时并没有考虑到并发修改的问题,并且它们表现出的行为是“及时失败”(fail-fast)的。这意味着,当它们发现容器在迭代过程中被修改时,就会抛出一个ConcurrentModificationException异常。

ArrayList<String> al = new ArrayList<String>();
    al.add("a");
    al.add("b");
    //al.add("b");
    //al.add("c");
    //al.add("d");

    for (int i = 0; i < al.size(); i++) {
        if (al.get(i) == "b") {
            al.remove(i);
            i--;
        }
    }

三,ConcurrentModificationException异常出现的原因

ConcurrentModificationException
异常指的是:当方法检测到对象的并发修改,但不允许这种修改时就抛出该异常。同时需要注意的是,该异常不会始终指出对象已经由不同线程并发修改,如果单线程违反了规则,同样也有可能会抛出改异常。

现在来看看ArrayList中迭代器的源代码:

澳门新葡萄京官网注册 3

首先看ArrayList的iterator()方法的具体实现,查看源码发现在ArrayList的源码中并没有iterator()这个方法,那么很显然这个方法应该是其父类或者实现的接口中的方法,我们在其父类AbstractList中找到了iterator()方法的具体实现,下面是其实现代码:

private class Itr implements Iterator<E> {
    int cursor;       // 表示下一个要访问的元素的索引
    int lastRet = -1; // 表示上一个访问的元素的索引
    int expectedModCount = modCount; //表示对ArrayList修改次数的期望值,它的初始值为modCount。
 
    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();
        }
    }
} 

从上面的源代码我们可以看出,迭代器在调用next()、remove()方法时都是调用checkForComodification()方法,该方法主要就是检测modCount
== expectedModCount
是否相等,若不等则抛出ConcurrentModificationException
异常,从而产生fail-fast机制。

expectedModCount
是在Itr中定义的:int expectedModCount =
ArrayList.this.modCount;所以他的值是不可能会修改的。

注意这个modCount变量,modCount是AbstractList类中的一个成员变量,该值表示对List的修改次数

澳门新葡萄京官网注册 4

查看ArrayList的源码:

public boolean add(E e) {
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}
// 将e添加到ArrayList的指定位置
public void add(int index, E element) {
    //判断下标是否数组越界
    rangeCheckForAdd(index);
 
    ensureCapacityInternal(size + 1); 
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}
private void ensureCapacityInternal(int minCapacity) {
    //判断元素数组是否为空数组
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
        // 取较大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    //修改次数+1
    modCount++;
 
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
public E remove(int index) {
    // 检查索引是否合法
    rangeCheck(index);
    // 修改次数+1
    modCount++;
    E oldValue = elementData(index);
    // 需要移动的元素的个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //复制数组
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 赋值为空,有利于进行GC(垃圾回收),避免内存泄漏(否则实际上数组中依然有该引用,gc无法进行垃圾回收)
    elementData[--size] = null; 
    // 返回旧值
    return oldValue;
}
//该方法能够擦除list中值为null的元素!
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;
}
private void fastRemove(int index) {
    // 修改次数+1
    modCount++;
    // 需要移动的元素的个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //复制数组
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 赋值为空,有利于进行GC(垃圾回收),避免内存泄漏(否则实际上数组中依然有该引用,gc无法进行垃圾回收)
    elementData[--size] = null; 
}
//清空数组,把每一个值设为null,方便垃圾回收(不同于reset,数组默认大小有改变的话不会重置)
public void clear() {
    modCount++;
    for (int i = 0; i < size; i++) elementData[i] = null;
    size = 0;
}

从上面的源代码我们可以看出,ArrayList中无论add、remove、clear方法只要是涉及了改变ArrayList元素的个数的方法都会导致modCount的改变澳门新葡萄京官网注册,。这里可以初步判断由于expectedModCount
得值与modCount的改变不同步,导致两者之间不等从而产生fail-fast机制。

如何证明:

回到我们前面单线程的代码上:

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.add(2);
    Iterator<Integer> iterator = list.iterator();
    while(iterator.hasNext()){
        //报错地方
        Integer integer = iterator.next();
        if(integer == 2)
            list.remove(integer);
    }
}

第一步:第一次while循环

调用list.iterator()返回一个Iterator之后,通过Iterator的hashNext()方法判断是否还有元素未被访问,看一下hasNext()方法:

澳门新葡萄京官网注册 5

如果下一个访问的元素下标不等于ArrayList的大小,就表示有元素需要访问,如果下一个访问元素的下标等于ArrayList的大小,则肯定到达末尾了。

再通过iterator.next()方法获取到下标为0的元素,我们看一下next()方法的具体实现:

@SuppressWarnings("unchecked")
public E next() {
    checkForComodification();
    int i = cursor;
    //当下标大于等于List的实际长度时,抛出NoSuchElementException
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    //当下标大于等于elementData数组长度时,抛出ConcurrentModificationException
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

checkForComodification()方法判断modCount==?expectedModCount,显然这时候相等,然后对cursor的值进行加1操作(初始时,cursor为0),返回具体的元素。注意此时,modCount=0,expectedModCount=0

接着往下看,程序中判断当前元素的值是否为2,若为2,则调用list.remove()方法来删除该元素。remove()方法源码如下:

//该方法能够擦除list中值为null的元素!
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;
}
private void fastRemove(int index) {
    // 修改次数+1
    modCount++;
    // 需要移动的元素的个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //复制数组
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 赋值为空,有利于进行GC(垃圾回收),避免内存泄漏(否则实际上数组中依然有该引用,gc无法进行垃圾回收)
    elementData[--size] = null; 
}

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

注意此时各个变量的值:

Iterator

其expectedModCount为0,cursor的值为1。

list

modCount为1(修改了一次),size为0(删除了一个为2的元素)。

第二步:第二次while循环

调用hasNext()方法判断,由于此时cursor=1,而size=0,那么返回true,所以继续执行while循环,然后继续调用iterator的next()方法:

在next()方法中会调用checkForComodification()方法,用于判断modCount==?expectedModCount,如果不等于,则抛出ConcurrentModificationException异常。方法如下:

澳门新葡萄京官网注册 6

很显然,此时modCount=1,而expectedModCount=0,因此程序就抛出了ConcurrentModificationException异常。到这里,想必大家应该明白为何上述代码会抛出ConcurrentModificationException异常了。关键点就在于:调用list.remove()方法导致modCount和expectedModCount的值不一致。

这种“及时失败”的迭代器并不是一种完备的处理机制,而只是“善意地”捕获并发错误,因此只能作为并发问题的预警指示器。它们采用的实现方式是,将计数器的变化与容器关联起来:如果在迭代期间计数器被修改,那么hasNext或next将抛出ConcurrentModificationException。然而,这种检查是在没有同步的情况下进行的,因此可能会看到失效的计数值,而迭代器可能并没有意识到已经发生了修改。这是一种设计上的权衡,从而降低并发修改操作的检测代码对程序性能带来的影响。

在代码中,删除元素后,需要把下标减一。这是因为在每次删除元素后,ArrayList会将后面部分的元素依次往上挪一个位置(就是copy),所以,下一个需要访问的下标还是当前下标,所以必须得减一才能把所有元素都遍历完

四,如何避免fail-fast错误

1,在单线程环境下避免

其实在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();
    }
}

在这个方法中,删除元素实际上调用的就是list.remove()方法,但是它多了一个操:expectedModCount =
modCount;

因此,在迭代器中如果要删除元素的话,需要调用Itr类的remove方法。更改后的代码如下:

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    Iterator<Integer> iterator = list.iterator();
    while(iterator.hasNext()){
        Integer integer = iterator.next();
        if(integer == 2)
            iterator.remove();
    }
}

2,在多线程环境下避免

上面的解决办法在单线程环境下适用,但是在多线程下可就不好使,例如:

public class Fail_Fast {
    private static List<Integer> list = new ArrayList<Integer>();
    //线程1,iterator遍历集合
    private static class thread1 extends Thread{
        public void run() {
            Iterator<Integer> iterator = list.iterator();
            while(iterator.hasNext()){
                int i = iterator.next();
                System.out.println("Thread1 遍历:" + i);
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    //线程2,满足条件时候修改集合结构
    private static class thread2 extends Thread{  
        public void run(){
            Iterator<Integer> iterator = list.iterator();
            while(iterator.hasNext()){
                int i = iterator.next();
                System.out.println("Thread2 遍历:" + i);
                if(i == 2){
                    iterator.remove();
                }
            }
        }
    }

    public static void main(String[] args) {  
        for(int i = 0 ; i < 5;i++){
            list.add(i);
        }
        new thread1().start();
        new thread2().start();
    }
}

运行结果:

澳门新葡萄京官网注册 7

多线程中一般有2种解决办法:

1)在使用iterator迭代的时候使用synchronized或者直接使用Collections.synchronizedList()。

2)使用并发容器CopyOnWriteArrayList代替ArrayList和Vector。

ConcurrentModificationException异常出现的原因

先看下面这段代码:

public class Test { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<Integer>(); list.add; Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext { Integer integer = iterator.next(); if (integer == 2) list.remove; } }}

执行结果:

Exception in thread “main” java.util.ConcurrentModificationExceptionat
java.util.ArrayList$Itr.checkForComodification(Unknown Source)at
java.util.ArrayList$Itr.next(Unknown Source)at Test.main(Test.java:9)

从异常信息可以发现,异常出现在checkForComodification()方法中。

我们不忙看checkForComodification()方法的具体实现,我们先根据程序的代码一步一步看ArrayList源码的实现:

首先看ArrayList的iterator()方法的具体实现,查看源码发现在ArrayList的源码中并没有iterator()这个方法,那么很显然这个方法应该是其父类或者实现的接口中的方法,我们在其父类AbstractList中找到了iterator()方法的具体实现,下面是其实现代码:

public Iterator<E> iterator() { return new Itr();}

从这段代码可以看出返回的是一个指向Itr类型对象的引用,我们接着看Itr的具体实现,在AbstractList类中找到了Itr类的具体实现,它是AbstractList的一个成员内部类,下面这段代码是Itr类的所有实现:

private class Itr implements Iterator<E> { int cursor = 0; int lastRet = -1; int expectedModCount = modCount; public boolean hasNext() { return cursor != size(); } public E next() { checkForComodification(); try { E next = get; lastRet = cursor++; return next; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } } public void remove() { if (lastRet == -1) throw new IllegalStateException(); checkForComodification(); try { AbstractList.this.remove; if (lastRet < cursor) cursor--; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException e) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }}

首先我们看一下它的几个成员变量:

1)cursor:表示下一个要访问的元素的索引,从next()方法的具体实现就可看出;

2)lastRet:表示上一个访问的元素的索引;

3)expectedModCount:表示对ArrayList修改次数的期望值,它的初始值为modCount;

4)modCount是AbstractList类中的一个成员变量。

protected transient int modCount = 0;

该值表示对List的修改次数,查看ArrayList的add()和remove()方法就可以发现,每次调用add()方法或者remove()方法就会对modCount进行加1操作。

好了,到这里我们再看看上面的程序:

当调用list.iterator()返回一个Iterator之后,通过Iterator的hashNext()方法判断是否还有元素未被访问,我们看一下hasNext()方法,hashNext()方法的实现很简单:

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

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

然后通过Iterator的next()方法获取到下标为0的元素,我们看一下next()方法的具体实现:

public E next() { checkForComodification(); try { E next = get; lastRet = cursor++; return next; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); }}

这里是非常关键的地方:首先在next()方法中会调用checkForComodification()方法,然后根据cursor的值获取到元素,接着将cursor的值赋给lastRet,并对cursor的值进行加1操作。初始时,cursor为0,lastRet为-1,那么调用一次之后,cursor的值为1,lastRet的值为0。注意:此时modCount为1,expectedModCount也为1(因为调用了一次ArrayList的add方法)。

接着往下看,程序中判断当前元素的值是否为2,若为2,则调用list.remove()方法来删除该元素。

我们看一下在ArrayList中的remove()方法做了什么:

public boolean remove { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove; return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove; return true; } } return false;} 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; // Let gc do its work}

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

那么注意此时各个变量的值:对于iterator,其expectedModCount为1,cursor的值为1,lastRet的值为0。

对于list,其modCount为2,size为0。

接着看程序代码,执行完删除操作后,继续while循环,调用hasNext()方法判断,由于此时cursor为1,而size为0,那么返回true,所以继续执行while循环,然后继续调用iterator的next()方法。

注意,此时要注意next()方法中的第一句:checkForComodification()。

在checkForComodification方法中进行的操作是:

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

如果modCount不等于expectedModCount,则抛出ConcurrentModificationException异常。

很显然,此时modCount为2,而expectedModCount为1,因此程序就抛出了ConcurrentModificationException异常。

到这里,想必大家应该明白为何上述代码会抛出ConcurrentModificationException异常了。关键点就在于:调用list.remove()方法导致modCount和expectedModCount的值不一致。

还有另外一种方式:

什么是CopyOnWriteArrayList

CopyOnWriteArrayList是ArrayList
的一个线程安全的变体,其中所有可变操作(add、set
等等)都是通过对底层数组进行一次新的复制来实现的
该类产生的开销比较大

但是在两种情况下,它非常适合使用:

1、在不能或不想进行同步遍历,但又需要从并发线程中排除冲突时。

2、当遍历操作的数量大大超过可变操作的数量时。遇到这两种情况使用CopyOnWriteArrayList来替代ArrayList再适合不过了。

那么为什么CopyOnWriterArrayList可以替代ArrayList呢?

1、CopyOnWriterArrayList的无论是从数据结构、定义都和ArrayList一样。它和ArrayList一样,同样是实现List接口,底层使用数组实现。在方法上也包含add、remove、clear、iterator等方法。

2、CopyOnWriterArrayList根本就不会产生ConcurrentModificationException异常,也就是它使用迭代器完全不会产生fail-fast机制。请看内部的迭代器的实现:

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}
 
static final class COWIterator<E> implements ListIterator<E> {
    /** 省略此处代码 */ 
    @SuppressWarnings("unchecked")
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }
    /** 省略此处代码 */ 
}

CopyOnWriteArrayList的add()方法:

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        //不同点
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

澳门新葡萄京官网注册 8

这三句代码使得CopyOnWriterArrayList不会抛ConcurrentModificationException异常。首先copy原来的array,再在copy数组上进行add操作,这样做就完全不会影响COWIterator中的array了。

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

在单线程环境下的解决办法

既然知道原因了,那么如何解决呢?

其实很简单,细心的朋友可能发现在Itr类中也给出了一个remove()方法:

public void remove() { if (lastRet == -1) throw new IllegalStateException(); checkForComodification(); try { AbstractList.this.remove; if (lastRet < cursor) cursor--; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException e) { throw new ConcurrentModificationException(); }}

在这个方法中,删除元素实际上调用的就是list.remove()方法,但是它多了一个操作:

expectedModCount = modCount;

因此,在迭代器中如果要删除元素的话,需要调用Itr类的remove方法。

将上述代码改为下面这样就不会报错了:

public class Test { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<Integer>(); list.add; Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext { Integer integer = iterator.next(); if (integer == 2) iterator.remove(); } }}
ArrayList<String> al = new ArrayList<String>();
    al.add("a");
    al.add("b");
    al.add("b");
    al.add("c");
    al.add("d");

    for (String s : al) {
        if (s.equals("a")) {
            al.remove(s);
        }
    }

在多线程环境下的解决方法

上面的解决办法在单线程环境下适用,但是在多线程下适用吗?看下面一个例子:

public class Test { static ArrayList<Integer> list = new ArrayList<Integer>(); public static void main(String[] args) { list.add; list.add; list.add; list.add; list.add; Thread thread1 = new Thread() { public void run() { Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext { Integer integer = iterator.next(); System.out.println; try { Thread.sleep; } catch (InterruptedException e) { e.printStackTrace(); } } }; }; Thread thread2 = new Thread() { public void run() { Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext { Integer integer = iterator.next(); if (integer == 2) iterator.remove(); } }; }; thread1.start(); thread2.start(); }}

运行结果:

1 Exception in thread “Thread-0”
java.util.ConcurrentModificationExceptionat
java.util.ArrayList$Itr.checkForComodification(Unknown Source)at
java.util.ArrayList$Itr.next(Unknown Source)at
Test$1.run(Test.java:15)

有可能有朋友说ArrayList是非线程安全的容器,换成Vector就没问题了,实际上换成Vector还是会出现这种错误。

原因在于,虽然Vector的方法采用了synchronized进行了同步,但是由于Vector是继承的AbstarctList,因此通过Iterator来访问容器的话,事实上是不需要获取锁就可以访问。那么显然,由于使用iterator对容器进行访问不需要获取锁,在多线程中就会造成当一个线程删除了元素,由于modCount是AbstarctList的成员变量,因此可能会导致在其他线程中modCount和expectedModCount值不等。

就比如上面的代码中,很显然iterator是线程私有的,

初始时,线程1和线程2中的modCount、expectedModCount都为0,

当线程2通过iterator.remove()删除元素时,会修改modCount值为1,并且会修改线程2中的expectedModCount的值为1,

而此时线程1中的expectedModCount值为0,虽然modCount不是volatile变量,不保证线程1一定看得到线程2修改后的modCount的值,但是也有可能看得到线程2对modCount的修改,这样就有可能导致线程1中比较expectedModCount和modCount不等,从而抛出异常。

因此一般有2种解决办法:

1)在使用iterator迭代的时候使用synchronized或者Lock进行同步;

2)使用并发容器CopyOnWriteArrayList代替ArrayList和Vector。

此处使用元素遍历的方式,当获取到的当前元素与特定元素相同时,即删除元素。从表面上看,代码没有问题,可是运行时却报异常:

隐藏迭代器

虽然加锁可以防止迭代器抛出ConcurrentModificationException,但你必须要记住在所有对共享容器进行迭代的地方都需要加锁。实际情况要更加复杂,因为在某些情况下,迭代器会隐藏起来。

看下面的这段代码:

public class HiddenIterator { private final Set<Integer> set = new HashSet<Integer>(); public synchronized void add(Integer i) { set.add; } public synchronized void remove(Integer i) { set.remove; } public void addTenThing() { Random r = new Random(); for (int i=0; i<10; i++) add(r.nextInt; System.out.println("DEBUG: added ten elements to " + set); }}

在HiddenIterator中没有显式的迭代操作,但在System.out.println("DEBUG: added ten elements to " + set);这句代码中将执行迭代操作。编译器将字符串的连接操作转换为调用StringBuilder.append,而这个方法又会调用容器的toString方法,标准容器的toString方法将迭代容器,并在元素上调用toString来生成容器内容的格式化表示。

Exception in thread "main" java.util.ConcurrentModificationException
        at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:886)
        at java.util.ArrayList$Itr.next(ArrayList.java:836)
        at com.mine.collection.TestArrayList.main(TestArrayList.java:17)

从异常堆栈可以看出,是ArrayList的迭代器报出的异常,说明通过元素遍历集合时,实际上是使用迭代器进行访问的。可为什么会产生这个异常呢?打断点单步调试进去发现,是这行代码抛出的异常:

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

modCount是集合修改的次数,当remove元素的时候就会加1,初始值为集合的大小。迭代器每次取得下一个元素的时候,都会进行判断,比较集合修改的次数和期望修改的次数是否一样,如果不一样,则抛出异常。查看集合的remove方法:

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
}

可以看到,删除元素时modCount已经加一,但是expectModCount并没有增加。所以在使用迭代器遍历下一个元素的时候,会抛出异常。那怎么解决这个问题呢?其实使用迭代器自身的删除方法就没有问题了

ArrayList<String> al = new ArrayList<String>();
al.add("a");
al.add("b");
al.add("b");
al.add("c");
al.add("d");

Iterator<String> iter = al.iterator();
while (iter.hasNext()) {
    if (iter.next().equals("a")) {
        iter.remove();
    }
}

查看迭代器自身的删除方法,果不其然,每次删除之后都会修改expectedModCount为modCount。这样的话就不会抛出异常

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();
        }
}

建议以后操作集合类的元素时,尽量使用迭代器。可是还有一个地方不明白,modCount和expectedModCount这两个变量究竟是干什么用的?为什么集合在进行操作时需要修改它?为什么迭代器在获取下一个元素的时候需要判断它们是否一样?它们存在总是有道理的吧

其实从异常的类型应该是能想到原因:ConcurrentModificationException.同时修改异常。看下面一个例子

List<String> list = new ArrayList<String>();
// Insert some sample values.
list.add("Value1");
list.add("Value2");
list.add("Value3");

// Get two iterators.

Iterator<String> ite = list.iterator();

Iterator<String> ite2 = list.iterator();
 // Point to the first object of the list and then, remove it.

ite.next();

ite.remove();
/* The second iterator tries to remove the first object as well. The object does not exist and thus, a ConcurrentModificationException is thrown. */

ite2.next();

ite2.remove();

同样的,也会报出ConcurrentModificationException。

发表评论

电子邮件地址不会被公开。 必填项已用*标注