搜不狗

记录学习工作点滴

java.util.ConcurrentModification Exception总结

| Comments

初探

Exception描述

今天又一次发现这个bug,印象原来有发生过这个问题,但是当时没有细细总结现在又发生了。这次就好好总结下,深入理解其中的原理。

  java.util.ConcurrentModificationException
        at java.util.ArrayList$ArrayListIterator.next(ArrayList.java:573)
        at com.linshi.www.linshi.Me.seller.ItemsListAdapter$1.success(ItemsListAdapter.java:63)
        at com.linshi.www.linshi.Me.seller.ItemsListAdapter$1.success(ItemsListAdapter.java:59)
        at retrofit.CallbackRunnable$1.run(CallbackRunnable.java:45)
        at android.os.Handler.handleCallback(Handler.java:733)
        at android.os.Handler.dispatchMessage(Handler.java:95)
        at android.os.Looper.loop(Looper.java:136)
        at android.app.ActivityThread.main(ActivityThread.java:5111)
        at java.lang.reflect.Method.invokeNative(Native Method)
        at java.lang.reflect.Method.invoke(Method.java:515)
        at com.android.internal.os.ZygoteInit$MethodAndArgsCaller.run(ZygoteInit.java:806)
        at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:622)
        at dalvik.system.NativeStart.main(Native Method)

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
    Callback<ItemMessage> deleteCallback = new Callback<ItemMessage>() {
        @Override
        public void success(ItemMessage item, Response response) {
          //wrong 
          //This foreach loop creates an Iterator object in the background.
          for(ItemMessage i:itemMessages){
             if(i.getItemId() == currentItemId){
                 itemMessages.remove(i);
             }
          }

          //Right
          for(int i = 0; i<itemMessages.size(); i++){
              if(itemMessages.get(i).getItemId() == currentItemId){
                  itemMessages.remove(i);
              }
          }


         //wrong
         ListIterator<ItemMessage> itWrong = itemMessages.iterator();
         while(itWrong.hasNext()){
          ItemMessage value = itWrong.next();
           if(value.getItemId() == currentItemId){
               itemMessages.remove(value);
           }
         }

         //right
         ListIterator<ItemMessage> it = itemMessages.listIterator();
         while (it.hasNext()){
          ItemMessage value = it.next();
          if(value.getItemId() == currentItemId){
              it.remove();// This wil remove the element that we just got using the next() method
              it.add(new ItemMessage());// THis inserts the element immediately before the next call to next()
          }
      }

      adapter.notifyDataSetChanged();
      }
      @Override
      public void failure(RetrofitError error) {
          //handle the error
      }
  }

从现象到原理

这是一个遍历List的同时,判断条件然后对List进行修改。 我们测试代码结果,

  • 用Iterator遍历,但是当用依然调用List的remove()方法的时候还是会出现java.util.ConcurrentModificationException

  • 用for(i:dataList)循环是会触发java.util.ConcurrentModificationException,因为foreach loop 会自动默默创建一个Iterator。

  • 用for(int i = 0; i<itemMessages.size(); i++)遍历可以避免这个问题。

  • 用Iterator遍历,同时用ListIterator的remove()方法不会出现这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
    //A counter for changes to the list.
    protected transient int modCount;

    java.util.ArrayList
    @Override public boolean remove(Object object) {
        Object[] a = array;
        int s = size;
        if (object != null) {
            for (int i = 0; i < s; i++) {
                if (object.equals(a[i])) {
                    System.arraycopy(a, i + 1, a, i, --s - i);
                    a[s] = null;  // Prevent memory leak
                    size = s;
                    modCount++;
                    return true;
                }
            }
        } else {
            for (int i = 0; i < s; i++) {
                if (a[i] == null) {
                    System.arraycopy(a, i + 1, a, i, --s - i);
                    a[s] = null;  // Prevent memory leak
                    size = s;
                    modCount++;
                    return true;
                }
            }
        }
        return false;
    }

    //只是修改了modCount,因此modCount将与expectedModCount的值不一致 



    //而ArrayList的私有类 ArrayListIterator的remove是这样实现的

    //保证了modCount和expectedModCount的值的一致性,避免抛出ConcurrentModificationException异常

        private class ArrayListIterator implements Iterator<E> {
        //Number of elements remaining in this iteration
        private int remaining = size;

        //Index of element that remove() would remove, or -1 if no such elt
        private int removalIndex = -1;

        //The expected modCount value 
        private int expectedModCount = modCount;

        public void remove() {
            Object[] a = array;
            int removalIdx = removalIndex;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (removalIdx < 0) {
                throw new IllegalStateException();
            }
            System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
            a[--size] = null;  // Prevent memory leak
            removalIndex = -1;
            expectedModCount = ++modCount;
        }

StackOverFlow一些解释

Java Collection classes are fail-fast which means that if the Collection will be changed while some thread is traversing over it using iterator, the iterator.next() will throw a ConcurrentModificationException.

This situation can come in case of multithreaded as well as single threaded environment. 更具体的例子看这里

You can’t modify a List in a for/each loop, which is syntactic sugar around the Iterator as an implementation detail. You can only safely call .remove() when using the Iterator directly.

fail-fast机制

从API中可以看到List等Collection的实现并没有同步化,如果在多 线程应用程序中出现同时访问,而且出现修改操作的时候都要求外部操作同步化;调用Iterator操作获得的Iterator对象在多线程修改Set的时 候也自动失效,并抛出java.util.ConcurrentModificationException。这种实现机制是fail-fast,对外部 的修改并不能提供任何保证。

Iterator 是工作在一个独立的线程中,并且拥有一个 mutex 锁。Iterator在工作的时候,是不允许被迭代的对象被改变的。

Iterator被创建的时候,建立了一个内存索引表(单链表),这个索引表指向原来的对象,当原来的对象数量改变的时候,这个索引表的内容没有同步改变,所以当索引指针往下移动的时候,便找不到要迭代的对象,所以按照 fail-fast 原则 Iterator 会马上抛出 java.util.ConcurrentModificationException 异常。

List、Set等是动态的,可变对象数量的数据结构,但是Iterator则是单向不可变,只能顺序读取,不能逆序操作的数据结构,当 Iterator指向的原始数据发生变化时,Iterator自己就迷失了方向。

所以 Iterator 在工作的时候是不允许被迭代的对象被改变的,但你可以使用 Iterator 本身的方法 remove() 来删除对象, Iterator.remove() 方法会在删除当前迭代对象的同时维护索引的一致性。

结论

不能用被迭代对象的remove()方法,而可以用Iterator.remove().

To Avoid ConcurrentModificationException in single-threaded environment: You can use the iterator remove() function to remove the object from underlying collection object. But in this case you can remove the same object and not any other object from the list.

进阶:multi-threaded场景

在互联网的世界难免高并发,并发的情况下上面的方法还可以吗? 显然是不行的。根据之前的分析,Iterator 在工作的时候是不允许被迭代的对象被改变的。计算我们在自己的线程里面用了Iterator.remove()也不能保证其他线程去修改这个被迭代的对象(集合)。

To Avoid ConcurrentModificationException in multi-threaded environment:

  1. You can convert the list to an array and then iterate on the array. This approach works well for small or medium size list but if the list is large then it will affect the performance a lot. 因为创建数组需要预留空间,成本很搞。而且数组查找容易O(1),但是做修改不容易O(n)。

  2. You can lock the list while iterating by putting it in a synchronized block. This approach is NOT recommended because it will cease the benefits of multithreading.

  3. If you are using JDK1.5 or higher then you can use ConcurrentHashMap and CopyOnWriteArrayList classes. It is the recommended approach.

同步代码块

1
2
3
4
5
6
7
8
9
 Iterator<String> iterator = list.iterator();
  synchronized(synObject) {
      while(iterator.hasNext()) {
          String str = iterator.next();
          if(del.contains(str)) {
               iterator.remove();
          }
      }
  }

synchronized语句还需要复习下,再抽机会总结吧。

java.util.concurrent包

举个栗子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

  import java.util.Iterator;
  import java.util.List;
  import java.util.Map;
  import java.util.concurrent.ConcurrentHashMap;
  import java.util.concurrent.CopyOnWriteArrayList;

  public class ThreadSafeIteratorExample {

      public static void main(String[] args) {

              List<String> myList = new CopyOnWriteArrayList<String>();

              myList.add("1");
          myList.add("2");
              myList.add("3");
          myList.add("4");
          myList.add("5");

          Iterator<String> it = myList.iterator();
               while(it.hasNext()){
                   String value = it.next();
                   System.out.println("List Value:"+value);
              if(value.equals("3")){
                    myList.remove("4");
                    myList.add("6");
                   myList.add("7");
              }
          }
          System.out.println("List Size:"+myList.size());

          Map<String,String> myMap =
             new ConcurrentHashMap<String,String>();
          myMap.put("1", "1");
          myMap.put("2", "2");
          myMap.put("3", "3");

          Iterator<String> it1 = myMap.keySet().iterator();
          while(it1.hasNext()){
              String key = it1.next();
              System.out.println("Map Value:"+myMap.get(key));
              if(key.equals("1")){
                  myMap.remove("3");
                  myMap.put("4", "4");
                  myMap.put("5", "5");
              }
          }

           System.out.println("Map Size:"+myMap.size());
      }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 List Value:1
  List Value:2
  List Value:3
  List Value:4
  List Value:5

  List Size:6

  Map Value:1
  Map Value:null
  Map Value:4
  Map Value:2

  Map Size:4

From the above example its clear that:

  1. Concurrent Collection classes can be modified avoiding ConcurrentModificationException.

  2. In case of CopyOnWriteArrayList, iterator doesn’t accomodate the changes in the list and works on the original list.

观察结果输出了1 2 3 4 5

而不是 1 2 3 5 6 7

说明了在运行时候,迭代器不会自适应迭代CopyOnWriteArrayList的变化,而是记录了修改之前的原始值。

  1. In case of ConcurrentHashMap, the behavior is not always the same. ConcurrentHashMap结果不稳定?

ConcurrentHashMap

ConcurrentHashMap还是需要有空再专门开一篇博客总结。这里先引用一个结论。

So if you are using ConcurrentHashMap then avoid adding new objects as it can be processed depending on the keyset. Note that the same program can print different values in your system because HashMap keyset is not in any order.

参考链接

带栗子的英文文章,很清晰http://www.javacodegeeks.com/2011/05/avoid-concurrentmodificationexception.html#ixzz1plFiXfzz

一篇比较详细的中文解释 http://www.cnblogs.com/dolphin0520/p/3933551.html

http://stackoverflow.com/questions/19702461/java-util-concurrentmodificationexception-in-for-loop

http://stackoverflow.com/questions/19660673/how-to-fix-a-java-util-concurrentmodificationexception

http://stackoverflow.com/questions/5113016/getting-a-concurrentmodificationexception-thrown-when-removing-an-element-from-a

http://stackoverflow.com/questions/9806421/concurrentmodificationexception-when-adding-inside-a-foreach-loop-in-arraylist

Comments