从ArrayList.remove方法想到的

 

引子

前几天一位同学在找bug时候，发现了自己犯下了一个基本错误，程序原型如下

       List<String> source = new ArrayList<String>();

       source.add("one");

       source.add("two");

       source.add("three");

       source.add("four");

       source.add("five");

 

       for (int i = 0; i < source.size(); i++) {

           String s = source.get(i);

           if (s.equals("two")||s.equals("three"))

              source.remove(s);

       }

       System.out.println("output result after delete:");

       for(String s : source)

          System.out.println(s);

功能是将列表中值为“two”与“three”的项删除，然后打印出剩余的项，

以上程序的输出为：

--------------------------

    output result after delete:

    one

    three

    four

    five

 

--------------------------

“three”没有被删除，原因也是比较明显，就是在遍历过程时，当删除了当前项后，ArrayList会对内部数据进行整理，导致索引与size的变化，造成“漏删”的情况。

那么，如何解决？

一种方法如下：

--------------------------

       for (int i = source.size()-1; i >= 0; i--) {

           String s = source.get(i);

           if (s.equals("two")||s.equals("three"))

              source.remove(s);

   }

--------------------------

以上程序将索引从前往后的遍历方式变更为从后往前，OK，问题解决了，那么，还有更简单的办法吗？这时，这位同学提出一个想法，也是本文要讨论的重点：

能否使用java5的for-each语法遍历列表，并删除目标项？

 

好，我们来尝试一下，将程序修改为：

--------------------------

       for(String s : source){

           if (s.equals("two")||s.equals("three"))

              source.remove(s);

   }

--------------------------

看起来还不错，语法更简单了，阅读更容易了，运行一下吧；

结果输出：

 

Exception in thread "main" java.util.ConcurrentModificationException

    at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)

    at java.util.AbstractList$Itr.next(AbstractList.java:343)

    at remove.TestRemove.main(TestRemove.java:31)

 

这？为什么？ConcurrentModificationException？并发修改错误！在单线程中，也会有并发的错误？

 

过程

    在解释上面看似令人费解的现象之前，我们先明确如下两点事实：

    1、java5内置的for-each语法实际上是Iterable的变体，也就是说，只有实现了Iterable接口的类的对象，才适用for-each语法，因此，我们可以将上面的程序修改为：

       for(Iterator<String> it = source.iterator();it.hasNext();){

           String s = it.next();

           if (s.equals("two")||s.equals("three"))

              source.remove(s);

       }

上述程序本质上与使用for-each语法并无差别。

    2、ArrayList并非线程安全，只有在单线程的情形下才可以保证状态一致，当调用者调用iterator()方法对ArrayList进行遍历的过程期间，是不允许进行任何的元素新增与删除的，一旦在遍历期间发现有任何变化（在next方法中检查），则抛出ConcurrentModificationException异常，以便调用者知晓。

    上述约束是这样实现的：

    在ArrayList中中维护了一个私有变量modCount，类似于版本的变更版本号；

protected transient int modCount = 0;

在对象构建时，该变量初始值为0，之后，在调用者调用add或remove方法时，modCount会进行自增来标识版本的变更；当调用者调用iterator()方法时，ArrayList会构造一个全新的Iterator对象返回给调用者，以便调用者通过操作该Iterator对ArrayList进行遍历；

    public Iterator<E> iterator() {

        return new Itr();

}

 

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

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

              if (lastRet < cursor)

                   cursor--;

                  lastRet = -1;

                  expectedModCount = modCount;

                } catch (IndexOutOfBoundsException e) {

                  throw new ConcurrentModificationException();

                }

           }

 

        final void checkForComodification() {

            if (modCount != expectedModCount)

              throw new ConcurrentModificationException();

        }

 }

关键是这一句：int expectedModCount = modCount;

在构建Itr时，会把ArrayList当前的modCount赋予Itr，并由Itr内部使用expectedModCount进行保存，并且，在Itr的实例返回给调用者后，expectedModCount的值不会变化，当调用者调用Itr的next方法进行遍历时，会在next方法内部调用checkForComodification方法进行条件检查，checkForComodification方法会比较当前ArrayList的modCount与Itr的expectedModCount是否相等，如果相等，则可以继续操作，如果不相等，则说明在调用者遍历的过程中，内部数据元素已经被修改过，则抛出ConcurrentModificationException异常。

 

上述两点事实是我们分析的基础，具体到我们的程序，正是因为在调用者遍历Itr的过程中，调用了ArrayList的remove方法，导致ArrayList内部的modCount自增，然后Itr的expectedModCount并没有变化，之后调用者再调用next时，导致抛出ConcurrentModificationException异常，这就是之前奇怪现象的原因。

 

接下来，我们的功能需求有一些变化：只删除值为“four”的项。

我们把程序改一改，但仍然使用之前的遍历与删除方式：

       for(Iterator<String> it = source.iterator();it.hasNext();){

           String s = it.next();

           if (s.equals("four"))

              source.remove(s);

    }

       System.out.println("output result after delete:");

       for(String s : source)

       System.out.println(s);

结果会如何？按刚才的分析，抛出ConcurrentModificationException异常，对吧？

可结果是：

    output result after delete:

    one

    two

    three

five

 

输出是正确的！

 

问题出在哪儿？很简单，调用者在调用next方法之前，会先调用hasNext进行检测是否存在下一个元素，如果存在，则继续调用next，如果不存在，说明之前已经遍历了所有的元素，可以结束了；

在看看Itr中hasNext的实现：

        public boolean hasNext() {

            return cursor != size();

        }

它会根据当前的遍历游标与ArrayList的size进行比较，如果不相等才认为下一个节点存在，而我们的“four”元素是倒数第二个元素，而刚才之前又调用了ArrayList的remove方法，导致size减1，正好让cursor与size()相等，因此，调用者就不会继续调用next方法了，也就不会检查modCount，自然不会抛出ConcurrentModificationException异常了，且输出的结果也是正确的；

这是巧合，又是合理的。

 

总结

问题的原因我们清楚了，就该指导实践了。

下面是总结的经验：

如果想在遍历时删除ArrayList中的元素，可以通过下面几种方法：

1、“从后往前”通过索引值进行遍历，并通过当前索引值对元素进行删除；

2、使用显式的Iterator对ArrayList进行遍历，并通过iterator.remove方法对元素进行删除，而不要使用ArrayList的remove方法；例子：

       for(Iterator<String> it = source.iterator();it.hasNext();){

           String s = it.next();

           if (s.equals("two")||s.equals("three"))

              it.remove();

    }

         切忌：不要使用for-each对ArrayList进行遍历，并调用ArrayList的remove方法对元素进行删除（如果对类似CopyOnWriteArrayList这样的并发集合进行for-each，并调用其自身的remove方法，是没有问题的，原因是该类集合专门对并发环境的使用进行了调整，本文只关注ArrayList）。