Ошибка java util concurrentmodificationexception

Время на прочтение
4 мин

Количество просмотров 94K

Как известно, ConcurrentModificationException к многопоточности никакого отношения не имеет. Возникает эта гадость, когда мы пытаемся модифицировать коллекцию во время итерирования по ней. Как обычно, это имеет исторические корни: коллекции и итераторы появились в Java 1.2, в те времена избежать явного использования итератора при обходе коллекции было никак нельзя, так что предложение менять коллекцию посредством методов итератора не выглядело совсем ужасным:

Iterator iterator = collection.iterator();

while (iterator.hasNext()) {
    Object element = iterator.next();
    if (iDontLikeThisElement(element)) {
         iterator.remove();
    }
}

Не, всё же выглядело. Но никаких других вариантов не было. Позже в пятой джаве появляется цикл foreach, и использование итераторов становится преимущественно неявным:

for (E element : collection) {
   if (iDonLikeThisElement(element)) {
       collection.remove(element); // облом! ConcurrentModificationException! 
   }
}

«Ишь чего захотели! Юзайте явные итераторы, дорогие кастомеры, и не выделывайтесь» — наверное что-то такое думали разработчики джава платформы работая над пятеркой.

В шестой джаве появляется пакет конкаренси. Теперь можно cделать так:

Set<String> set = Collections.newSetFromMap(new ConcurrentHashMap<>());

И получить set который не кидается ConcurrentModificationException-ами. Но опять же счастье не совсем полное:

1. Oбычно многопоточность нам вовсе не нужна
2. Не подерживаются null ни в качестве элементов, ни ключей, ни значений. Да и ладно, честно сказать.
3. Порядок элементов не определён и может меняться — вот это гораздо хуже. Т.е. если мы бежим по элементам и ведём некий подсчёт с потерей точности, то нас могут поджидать неприятные сюрпризы и разные результаты на одних и тех же наборах данных, что, скажем, не всегда хорошо. Так же бывают задачи, где желательно сохранить именно изначальный порядок данных. Ну и вот такие штуки тоже имеют место быть:

set.add("aaa");
set.add("bbb");
        
for (String s : set) {
    set.add("ddd");
    System.out.println(s);
}

set.add("aaa");
set.add("bbb");
        
for (String s : set) {
    set.add("ccc");
    System.out.println(s);
}

Поэтому сейчас мы сделаем свою собственную коллекцию с чётким порядком. И так, что мы хотим получить:

1. В рамках одного треда можно добавлять и удалять элементы в любой момент без всяких эксепшенов. И конечно же за константное время.
2. Можно хранить null-ы, если вдруг хочется.
3. Элементы обходятся в том порядке в котором были добавлены.

Всё это с легкостью достигается с помощью слегка доработанного двунаправленного списка:

1. Удаляя элемент мы не будем обнулять ссылку на следующий, т. е. eсли итератор стоит на данном элементе, то он сможет пройти дальше.
2. В конце списка поместим фэйковый элемент, который превращается в настоящий когда в список что-нибудь добавляют. Т.е. даже добравшись до конца списка итератор не упирается в null и может продолжить работу если в коллекции появляется новый элемент. Далее в коде этот фейковый элемент называется placeholder.

Посмотрим на картинку.

1. В начале у нас есть элементы A, B, C, D.
2. Затем элементы C и D удаляются.
3. Добавляется новый элемент E.

Можно заметить, что если на момент удалений у нас был итератор указывавший на элемент С, то двигаясь дальше по ссылкам он доберется до вновь добавленного элемента E. Если же никакого итератора не было, то ничто не мешает сборщику мусора освободить память от удаленных элементов.

Ну и для константного времени доступа нам, очевидно, нужен хэшмап:

import java.util.AbstractSet;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

public class LinkedSet<E> extends AbstractSet<E> {
    
    private static class LinkedElement<E> {
        E value;
        
        boolean exists;
        
        LinkedElement<E> prev; 
        LinkedElement<E> next;
    }
    
    private Map<E, LinkedElement<E>> map = new HashMap<>();

    private LinkedElement<E> placeholder = new LinkedElement<>(); 
    private LinkedElement<E> head = placeholder;

    @Override
    public boolean isEmpty() { return head == placeholder; }

    @Override
    public int size() { return map.size(); }

    @Override
    public boolean contains(Object o) { return map.containsKey(o); }

    // здесь будут методы для добавления, удаления, итерирования
}

Добавление элемента:

    @Override
    public boolean add(E e) {
        LinkedElement<E> element = map.putIfAbsent(e, placeholder);

        if (element != null) {
            return false;
        }
        
        element = placeholder;
        element.exists = true;
        element.value = e;

        placeholder = new LinkedElement<>();
        placeholder.prev = element;
        
        element.next = placeholder;
        
        return true;
    }

Удаление:

    @Override
    public boolean remove(Object o) {
        LinkedElement<E> removedElement = map.remove(o);
        
        if (removedElement == null) {
            return false;
        }
        
        removeElementFromLinkedList(removedElement);
        
        return true;
    }
    
    private void removeElementFromLinkedList(LinkedElement<E> element) {
        element.exists = false;
        element.value = null;

        element.next.prev = element.prev;
        
        if (element.prev != null) {
            element.prev.next = element.next;
            element.prev = null;
        } else {
            head = element.next;
        }
    }

Итератор:

    @Override
    public Iterator<E> iterator() {
        return new ElementIterator();
    }

    private class ElementIterator implements Iterator<E> {
        LinkedElement<E> next = head;
        LinkedElement<E> current = null;
        
        LinkedElement<E> findNext() {
            LinkedElement<E> n = next;
            
            while (!n.exists && n.next != null) {
                next = n = n.next;
            }
            
            return n;
        }
        
        @Override
        public boolean hasNext() {
            return findNext().exists;
        }

        @Override
        public E next() {
            LinkedElement<E> n = findNext();
            
            if (!n.exists) {
                throw new NoSuchElementException();
            }
            
            current = n;
            next = n.next;
            
            return n.value;
        }

        @Override
        public void remove() {
            if (current == null) {
                throw new IllegalStateException();
            }
            
            if (map.remove(current.value, current)) {
                removeElementFromLinkedList(current);
            } else {
                throw new NoSuchElementException();
            }
        }
    }

Теперь можно делать так:

Set<Integer> set = new LinkedSet<>();
// ... put some numbers
set.stream().filter(v -> v % 2 == 0).forEach(set::remove);

Понятно, что аналогично можно сконструировать и LinkedMap. Вот в общем-то и всё, ещё один велосипед готов. Почему подобным образом не доработали библиотечные LinkedHashMap и LinkedHashSet? Кто знает, возможно чтобы джависты завидовали джаваскриптистам.

Modification of a Collection while iterating through that Collection using an Iterator is not permitted by most of the Collection classes. The Java library calls an attempt to modify a Collection while iterating through it a «concurrent modification». That unfortunately suggests the only possible cause is simultaneous modification by multiple threads, but that is not so. Using only one thread it is possible to create an iterator for the Collection (using Collection.iterator(), or an enhanced for loop), start iterating (using Iterator.next(), or equivalently entering the body of the enhanced for loop), modify the Collection, then continue iterating.

To help programmers, some implementations of those Collection classes attempt to detect erroneous concurrent modification, and throw a ConcurrentModificationException if they detect it. However, it is in general not possible and practical to guarantee detection of all concurrent modifications. So erroneous use of the Collection does not always result in a thrown ConcurrentModificationException.

The documentation of ConcurrentModificationException says:

This exception may be thrown by methods that have detected concurrent modification of an object when such modification is not permissible…

Note that this exception does not always indicate that an object has been concurrently modified by a different thread. If a single thread issues a sequence of method invocations that violates the contract of an object, the object may throw this exception…

Note that fail-fast behavior cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast operations throw ConcurrentModificationException on a best-effort basis.

Note that

• the exception may be throw, not must be thrown
• different threads are not required
• throwing the exception cannot be guaranteed
• throwing the exception is on a best-effort basis
• throwing the exception happens when the concurrent modification is detected, not when it is caused

The documentation of the HashSet, HashMap, TreeSet and ArrayList classes says this:

The iterators returned [directly or indirectly from this class] are fail-fast: if the [collection] is modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the Iterator throws a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

Note again that the behaviour «cannot be guaranteed» and is only «on a best-effort basis».

The documentation of several methods of the Map interface say this:

Non-concurrent implementations should override this method and, on a best-effort basis, throw a ConcurrentModificationException if it is detected that the mapping function modifies this map during computation. Concurrent implementations should override this method and, on a best-effort basis, throw an IllegalStateException if it is detected that the mapping function modifies this map during computation and as a result computation would never complete.

Note again that only a «best-effort basis» is required for detection, and a ConcurrentModificationException is explicitly suggested only for the non concurrent (non thread-safe) classes.

Debugging ConcurrentModificationException

So, when you see a stack-trace due to a ConcurrentModificationException, you can not immediately assume that the cause is unsafe multi-threaded access to a Collection. You must examine the stack-trace to determine which class of Collection threw the exception (a method of the class will have directly or indirectly thrown it), and for which Collection object. Then you must examine from where that object can be modified.

• The most common cause is modification of the Collection within an enhanced for loop over the Collection. Just because you do not see an Iterator object in your source code does not mean there is no Iterator there! Fortunately, one of the statements of the faulty for loop will usually be in the stack-trace, so tracking down the error is usually easy.
• A trickier case is when your code passes around references to the Collection object. Note that unmodifiable views of collections (such as produced by Collections.unmodifiableList()) retain a reference to the modifiable collection, so iteration over an «unmodifiable» collection can throw the exception (the modification has been done elsewhere). Other views of your Collection, such as sub lists, Map entry sets and Map key sets also retain references to the original (modifiable) Collection. This can be a problem even for a thread-safe Collection, such as CopyOnWriteList; do not assume that thread-safe (concurrent) collections can never throw the exception.
• Which operations can modify a Collection can be unexpected in some cases. For example, LinkedHashMap.get() modifies its collection.
• The hardest cases are when the exception is due to concurrent modification by multiple threads.

Programming to prevent concurrent modification errors

When possible, confine all references to a Collection object, so its is easier to prevent concurrent modifications. Make the Collection a private object or a local variable, and do not return references to the Collection or its iterators from methods. It is then much easier to examine all the places where the Collection can be modified. If the Collection is to be used by multiple threads, it is then practical to ensure that the threads access the Collection only with appropriate synchonization and locking.

In Java, concurrentmodificationexception is one of the common problems that programmer faces while programmer works on Collections in java. In this post, we will see why we encountered this exception and how to resolve concurrent modification exception in java.

Here is the table content of the article we will cover these topics.

1. What is concurrentmodificationexception in java?
2. Why concurrent modification exception occurs in java? OR Reason behind the scenes?
3. How to resolve concurrentmodificationexception in java OR avoid concurrentmodificationexception in java?
4. Avoid ConcurrentModificationException in a single-threaded environment
   1. By of Iterator.remove() method
   2. By use of foreach but not Removing During Iteration
   3. Use traditional for loop
   4. Using removeIf() method of Java 8
5. Avoid ConcurrentModificationException in a multi-threaded environment

What is concurrentmodificationexception in java

The concurrentmodificationexception occurs when we try to modify any object concurrently without permission. You may be faced with it when you work with Collection classes of Java. When you try to modify any collection class during the traversal the compiler throw ConcurrentModificationException. You will see the Exception in the main thread “java util concurrent modification exception”. This exception can occur in a multithread environment as well as in a single thread environment.

The Collection classes in java are fail-fast, which means we can’t modify the collection when a thread is traversing over it using an iterator, the iterator.next() will throw ConcurrentModificationException. Don’t get confused when we are talking about threads, because it can create confusion in the developer’s mind that the collection is getting modified by multiple threads and that is not true. It can also occur with multiple threads.

Suppose we have an ArrayList, and we are traversing it and trying to remove any element. If we use enhance for loop and try to remove an element by the remove() method, then it will give the ConcurrentModificationException but if we use Iterator’s remove method, then we will be able to remove the element successfully. We will discuss it separately.

But there are some collections that are fail-safe like CopyOnWriteArrayList, which creates a new copy ArrayList during modification.  Let’s take a concurrentmodificationexception example.

import java.util.ArrayList;
import java.util.List;

public class Record 
{
    public static void main(String arg[])
    {
    	 List<String> listOfBooks = new ArrayList<>();  
         listOfBooks.add("Programming in Java");
         listOfBooks.add("Clean Code");
         listOfBooks.add("Improve Java");
         listOfBooks.add("Complete learning");
         
         // Traversing the list by enhanced for loop
         for(String book: listOfBooks)
         {
        	 System.out.println(book);
        	 // Removing the object if condition is true
             if(book.contains("Clean Code"))
             {
                 listOfBooks.remove(book);
             }     
         }
    }
}

Output: Programming in Java
Clean Code
Exception in thread “main” java.util.ConcurrentModificationException
at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1042)
at java.base/java.util.ArrayList$Itr.next(ArrayList.java:996)
at Record.main(Record.java:15)

In the above example you can see the exception even if we are not working in multithreading we just have one thread, that is the main thread. The enhanced for loop internally uses the iterator. The compiler is throwing an error because we are using the remove method of collection instead of the iterator.  See the reason here.

.Hence, Let’s take a different example and different methods of the transversal. We will see the working of each traversal method and find in which method it creates the problem.

Let’s take an example of ArrayList and transverse the ArrayList by use of for loop.

import java.util.ArrayList;
import java.util.List;

public class Record 
{
    public static void main(String arg[])
    {
    	List<String> listOfNames = new ArrayList<String>();
		listOfNames.add("Hi");
		listOfNames.add("Java");
		listOfNames.add("Goal");
		listOfNames.add(".com");
		listOfNames.add("Website");
		
		// Traversing the names from ArrayList
		for(int i = 0; i < listOfNames.size(); i++)
		{
			System.out.println(listOfNames.get(i));
			// Modifying the ArrayList if condition is true
			if(listOfNames.get(i).equals("Hi"))
				listOfNames.remove(listOfNames.get(i)); 
		}
    }
}

Output: Hi
Goal
.com
Website

This might be a surprising thing for you because it has run successfully, and it does not throw an exception because here we are not using iterator. The ConcurrentModificationException directly belongs to the Iterator not to remove the method of ArrayList. We will see the reason below section.

Let’s take the example of ArrayList and transverse the ArrayList by use of Iterator.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Record 
{
    public static void main(String arg[])
    {
    	 List<String> listOfBooks = new ArrayList<>();  
         listOfBooks.add("Programming in Java");
         listOfBooks.add("Clean Code");
         listOfBooks.add("Improve Java");
         listOfBooks.add("Complete learning");
         
         // Traversing the list by Iterator
         Iterator<String> it = listOfBooks.iterator();
         while(it.hasNext())
         {
        	 String book = it.next();
        	 System.out.println(book);
        	 // Removing the object if condition is true
             if(book.contains("Clean Code"))
             {
                 listOfBooks.remove(book);
             }     
         }
    }
}

Output: Programming in Java
Clean Code
Exception in thread “main” java.util.ConcurrentModificationException at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1042) at java.base/java.util.ArrayList$Itr.next(ArrayList.java:996) at Record.main(Record.java:19)

This is also showing the exception because we are using an iterator and trying to modify the collection by removing the method of collection.  

Why concurrent modification exception occurs in java? OR Reason behind the scenes?

The ConcurrentModificationException occurs when we iterate the collection class by Iterator and modify the collection during the iteration. The ConcurrentModificationException belongs to the Iterator, not to the Collection classes.

Now let’s see why Iterator gives an exception. Take the simple example of the ArrayList class. The ArrayList class internally implements the Iterator interface. Let’s have a look at the code, here you can see it:

1. There is a nested class that implemented the Iterator interface and here modCount variable is assigned to expectedModCount. The modCount is a variable that tells the number of times this ArrayList has been structurally modified. Structural modifications means those modifications that can change the size of the list. Whenever we modify the ArrayList, like add or remove any object then its modCount gets updated automatically. 

2. When the next() method of iterator invokes the checkForComodification() method that checks whether the ArrayList has modified during iteration or not.

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

If modCount doesn’t match with expectedModCount then it throws ConcurrentModificationException.

How to resolve concurrentmodificationexception in java OR avoid concurrentmodificationexception in java?

Let’s see how we can resolve ConcurrentModificationException or avoid ConcurrentModificationException. It can occur in a single thread or in multiple threads. Let’s discuss it one by one.

Avoid ConcurrentModificationException in a single-threaded environment

1. By of Iterator.remove() method

As we have discussed the reason for the exception is the next() method of Iterator. If you are not familiar with reading it first. So, we can use the remove() method of the Iterator to remove the object during the iteration. The remove() method of Iterator assigns the value of modCount to the expectModCount. That’s why the next() method doesn’t throw exceptions. Let’s have a look at the code of the remove method:

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

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Record 
{
    public static void main(String arg[])
    {
    	 List<String> listOfBooks = new ArrayList<>();  
         listOfBooks.add("Programming in Java");
         listOfBooks.add("Clean Code");
         listOfBooks.add("Improve Java");
         listOfBooks.add("Complete learning");
         
         // Traversing the list by Iterator for loop
         Iterator<String> it = listOfBooks.iterator();
        while(it.hasNext())
         {
        	 String book = it.next();
        	 System.out.println(book);
        	 // Removing the current object if condition is true
             if(book.contains("Clean Code"))
             {
                 it.remove();
             }     
         }
        
        System.out.println("After remove: "+ listOfBooks);
    }
}

Output: Programming in Java
Clean Code
Improve Java
Complete learning
After remove: [Programming in Java, Improve Java, Complete learning]

But there are two problems to use the Iterator: the first problem, you can remove the same object and not any other object from the list. Second problem, if we use Nested Iterator that creates confusion for the programmer. So, there may be a chance when we want to use the enhanced for loop. We will discuss it below.

2. By use of foreach but not Removing During Iteration

Suppose you are working on the existing project and you don’t want to change the existing code. So, you can keep it as it is, but you can perform a remove operation after the completion of an iteration.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Record 
{
    public static void main(String arg[])
    {
    	 List<String> listOfBooks = new ArrayList<>();  
         listOfBooks.add("Programming in Java");
         listOfBooks.add("Clean Code");
         listOfBooks.add("Improve Java");
         listOfBooks.add("Complete learning");
         
         List<String> toRemove = new ArrayList<String>();

         for (String book : listOfBooks) 
         {
        	 System.out.println(book);
             if(book.equals("Clean Code"))
                 toRemove.add(book);
         }
         listOfBooks.removeAll(toRemove);
                
         System.out.println(listOfBooks);
    }
}

Output: Programming in Java
Clean Code
Improve Java
Complete learning
[Programming in Java, Improve Java, Complete learning]

3. Use traditional for loop

You can simply use the traditional for to avoid it. Because this exception belongs to Iterator and traditional for loop doesn’t use the Iterator, unlike a for-each loop.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Record 
{
    public static void main(String arg[])
    {
    	 List<String> listOfBooks = new ArrayList<>();  
         listOfBooks.add("Programming in Java");
         listOfBooks.add("Clean Code");
         listOfBooks.add("Improve Java");
         listOfBooks.add("Complete learning");
         
         for (int i = 0; i < listOfBooks.size(); i++) 
         {
        	 String book = listOfBooks.get(i);
        	 System.out.println(book);
             if(book.equals("Clean Code"))
            	 listOfBooks.remove(i);
         }
                
         System.out.println(listOfBooks);
    }
}

Output: Programming in Java
Clean Code
Improve Java
Complete learning
[Programming in Java, Improve Java, Complete learning]

4. Using removeIf() method of Java 8

Let’s see how we can remove concurrentmodificationexception java 8 introduced a new method in the Collection interface that removes the element if a given condition is true. It takes the parameter of Predicate type, if you are not familiar with functional programming, then read it from here.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Record 
{
    public static void main(String arg[])
    {
    	 List<String> listOfBooks = new ArrayList<>();  
         listOfBooks.add("Programming in Java");
         listOfBooks.add("Clean Code");
         listOfBooks.add("Improve Java");
         listOfBooks.add("Complete learning");
         
         System.out.println("Before :" + listOfBooks);
         
         listOfBooks.removeIf(name -> name.equals("Clean Code"));
         
         System.out.println("After :" +listOfBooks);

    }
}

Output: Before :[Programming in Java, Clean Code, Improve Java, Complete learning]
After :[Programming in Java, Improve Java, Complete learning]

Avoid ConcurrentModificationException in a multi-threaded environment

1. We can convert the ArrayList to Array and then perform the operation but this is not a good suit for many cases. It is good when we have a small-size list because if the list size is big then it creates performance issues.
2. By the use of synchronization in java, we can achieve this task. We can use the lock concept. In this approach, one thread will wait when another is having the lock. But it prevents multithreading concepts.
3. You can also use the concurrent collections of java.