ConcurrentModificationException异常以及iterator迭代器的使用原理

异常出现前提&＃xff1a;公司的Android项目中有一个功能是获取通讯录中某个部门下的所有成员&＃xff0c;因为该部门下的可能会有子部门&＃xff0c;但是子部门又可能还有子部门&＃xff0c;因此该问题就可转化成一个遍历一棵树所有节点的问题。之前的做法是写了一个方法&＃xff0c;用递归的方式求得一个部门下所有成员&＃xff0c;代码如下&＃xff1a;

/*** * &＃64;param groupId* &＃64;return*/private List> getGroupContact(String deptId) {List> selectContactList &＃61; ObjectFactory.newArrayList();List> childGroups &＃61; ContactsDB.getInstance(mContext).selectChildGroup(deptId);// 将部门下的联系人加入选中列表for (Map contactMap : childGroups) {String childGroupId &＃61; MapUtil.getString(contactMap, Tag.DEPTID);selectContactList.addAll(getGroupContact(childGroupId));}List> childContacts &＃61; ObjectFactory.newLinkedList();if (((CreateGroupChatActivity) mContext).isFromWebView) {childContacts &＃61; ContactsDB.getInstance(mContext).selectGroupContactById(deptId);} else {childContacts &＃61; ContactsDB.getInstance(mContext).selectGroupContactNotNullById(deptId);}selectContactList.addAll(childContacts);return selectContactList;}

selectGroupContactById和selectGroupContactNotNullById这两个方法都是通过deptId字段获得所有联系人信息&＃xff0c;这个递归方法没有问题&＃xff0c;可以获得结果&＃xff0c;但是之后却发现其效率无比低下&＃xff0c;于是只好想着把递归改为循环&＃xff0c;于是出现了下面的方法&＃xff1a;

public List selectAllChildDeptId(String parendId) {List childAllDeptIdList &＃61; ObjectFactory.newLinkedList();// 首先获得直系子部门的deptIdchildAllDeptIdList &＃61; mDataBase.selectChildDeptId(parendId);for (String deptId:childAllDeptIdList) {childAllDeptIdList.addAll(mDataBase.selectChildDeptId(deptId));}return childAllDeptIdList;}

自然而然地当运行到这里时就出现了ConcurrentModificationException异常&＃xff0c;原因是在java中对集合进行迭代&＃xff0c;遍历的过程中&＃xff0c;如果修改该集合的数据&＃xff1a;添加或者删除等操作时&＃xff0c;就会出现这个异常&＃xff0c;那么为什么会出现这个异常呢&＃xff0c;先看下面一段代码&＃xff1a;

//ConcurrentModificationException异常测试方法public static void iteratorTest(){ArrayList list &＃61; new ArrayList();list.add(2);Iterator iterator &＃61; list.iterator();while(iterator.hasNext()){Integer integer &＃61; iterator.next();if(integer&＃61;&＃61;2)list.remove(integer);}}

运行后异常为&＃xff1a;

从异常信息可以发现&＃xff0c;异常出现在checkForComodification()方法中。

　　我们不忙看checkForComodification()方法的具体实现&＃xff0c;我们先根据程序的代码一步一步看ArrayList源码的实现&＃xff1a;

　　首先看ArrayList的iterator()方法的具体实现&＃xff0c;查看源码发现在ArrayList的源码中的terator()这个方法如下&＃xff1a;

从这段代码可以看出返回的是一个指向Itr类型对象的引用&＃xff0c;我们接着看Itr的具体实现&＃xff1a;

/*** An optimized version of AbstractList.Itr*/private class Itr implements Iterator {int cursor; // index of next element to returnint lastRet &＃61; -1; // index of last element returned; -1 if no suchint expectedModCount &＃61; modCount;public boolean hasNext() {return cursor !&＃61; size;}&＃64;SuppressWarnings("unchecked")public E next() {checkForComodification();int i &＃61; cursor;if (i >&＃61; size)throw new NoSuchElementException();Object[] elementData &＃61; ArrayList.this.elementData;if (i >&＃61; elementData.length)throw new ConcurrentModificationException();cursor &＃61; i &＃43; 1;return (E) elementData[lastRet &＃61; i];}public void remove() {if (lastRet <0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.remove(lastRet);cursor &＃61; lastRet;lastRet &＃61; -1;expectedModCount &＃61; modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}final void checkForComodification() {if (modCount !&＃61; expectedModCount)throw new ConcurrentModificationException();}}

　首先我们看一下它的几个成员变量&＃xff1a;

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

　　lastRet&＃xff1a;表示上一个访问的元素的索引

　　expectedModCount&＃xff1a;表示对ArrayList修改次数的期望值&＃xff0c;它的初始值为modCount。

　　modCount是AbstractList类&＃xff08;ArrayList的父类&＃xff09;中的一个成员变量

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

　　好了&＃xff0c;到这里我们再看看上面的程序&＃xff1a;

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

public boolean hasNext() {return cursor !&＃61; size();
}
如果下一个访问的元素下标不等于ArrayList的大小&＃xff0c;就表示有元素需要访问&＃xff0c;这个很容易理解&＃xff0c;如果下一个访问元素的下标等于ArrayList的大小&＃xff0c;则肯定到达末尾了。

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

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


这里是非常关键的地方&＃xff1a;首先在next()方法中会调用checkForComodification()方法&＃xff0c;然后判断是否越界&＃xff0c;接着将cursor的值赋给lastRet&＃xff0c;并对cursor的值进行加1操作。初始时&＃xff0c;cursor为0&＃xff0c;lastRet为-1&＃xff0c;那么调用一次之后&＃xff0c;cursor的值为1&＃xff0c;lastRet的值为0。注意此时&＃xff0c;modCount为0&＃xff0c;expectedModCount也为0。

但是当程序循环运行到我们进行remove&＃xff08;&＃xff09;方法时却报错了&＃xff0c;下面我们看下remove&＃xff08;&＃xff09;进行的操作&＃xff1a;

/*** Removes the first occurrence of the specified element from this list,* if it is present. If the list does not contain the element, it is* unchanged. More formally, removes the element with the lowest index* i such that* (o&＃61;&＃61;null ? get(i)&＃61;&＃61;null : o.equals(get(i)))* (if such an element exists). Returns true if this list* contained the specified element (or equivalently, if this list* changed as a result of the call).** &＃64;param o element to be removed from this list, if present* &＃64;return true if this list contained the specified element*/public boolean remove(Object o) {if (o &＃61;&＃61; null) {for (int index &＃61; 0; index /** Private remove method that skips bounds checking and does not* return the value removed.*/private void fastRemove(int index) {modCount&＃43;&＃43;;int numMoved &＃61; size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index&＃43;1, elementData, index,numMoved);elementData[--size] &＃61; null; // Let gc do its work}

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

那么注意此时各个变量的值&＃xff1a;对于iterator&＃xff0c;其expectedModCount为0&＃xff0c;cursor的值为1&＃xff0c;lastRet的值为0。

　　对于list&＃xff0c;其modCount为1&＃xff0c;size为0。

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

　　注意&＃xff0c;此时要注意next()方法中的第一句&＃xff1a;checkForComodification()。

　　在checkForComodification方法中进行的操作是&＃xff1a;

final void checkForComodification() {if (modCount !&＃61; expectedModCount)throw new ConcurrentModificationException();
}

如果modCount不等于expectedModCount&＃xff0c;则抛出ConcurrentModificationException异常。

　　很显然&＃xff0c;此时modCount为1&＃xff0c;而expectedModCount为0&＃xff0c;因此程序就抛出了ConcurrentModificationException异常。

　　到这里&＃xff0c;想必大家应该明白为何上述代码会抛出ConcurrentModificationException异常了。

　　关键点就在于&＃xff1a;调用list.remove()方法导致modCount和expectedModCount的值不一致。

　　注意&＃xff0c;像使用for-each进行迭代实际上也会出现这种问题。

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

public void remove() {if (lastRet &＃61;&＃61; -1)throw new IllegalStateException();checkForComodification();try {AbstractList.this.remove(lastRet);if (lastRet }
在这个方法中&＃xff0c;删除元素实际上调用的就是list.remove()方法&＃xff0c;但是它多了一个操作&＃xff1a;

expectedModCount &＃61; modCount;

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

　　将上述代码改为下面这样就不会报错了&＃xff1a;

public class Test {public static void main(String[] args) {ArrayList list &＃61; new ArrayList();list.add(2);Iterator iterator &＃61; list.iterator();while(iterator.hasNext()){Integer integer &＃61; iterator.next();if(integer&＃61;&＃61;2)iterator.remove(); //注意这个地方}}
}

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

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

运行结果&＃xff1a;

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

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

　　就比如上面的代码中&＃xff0c;很显然iterator是线程私有的&＃xff0c;

　　初始时&＃xff0c;线程1和线程2中的modCount、expectedModCount都为0&＃xff0c;

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

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

　　因此一般有2种解决办法&＃xff1a;

　　1&＃xff09;在使用iterator迭代的时候使用synchronized或者Lock进行同步&＃xff1b;

　　2&＃xff09;使用并发容器CopyOnWriteArrayList代替ArrayList和Vector。

最后还有一点&＃xff0c;大家可能会发现&＃xff0c;iterator没有add方法&＃xff0c;只有remove&＃xff0c;那该怎么办呢&＃xff0c;这时候就要用到ListIterator了&＃xff0c;如下&＃xff1a;

/*** 通过上级部门ID,查找所有子部门信息(只提取子部门的deptId)* * &＃64;param parendId*/public List selectAllChildDeptId(String parendId) {List childAllDeptIdList &＃61; ObjectFactory.newLinkedList();// 首先获得直系子部门的deptIdchildAllDeptIdList &＃61; mDataBase.selectChildDeptId(parendId);ListIterator iterator &＃61; childAllDeptIdList.listIterator();while (iterator.hasNext()) {String deptId &＃61; iterator.next();List childDeptList &＃61; mDataBase.selectChildDeptId(deptId);for (String childDeptId : childDeptList) {iterator.add(childDeptId);}}return childAllDeptIdList;}