Wednesday, January 20, 2016

Is it safe to iterate over an ArrayList and remove its elements at the same time ? When do we get ConcurrentModificationException & hidden Iterator?

Iterator returned by the ArrayList (and many other collection types) is fail-fast. If the list is structurally modified at anytime after the iterator is created, in any way except through the Iterator’s own remove() method, the iterator will throw ConcurrentModificationException and thus fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Structural Modification
A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely changing the values associated with a key that an instance already contains is not a structural modification.” - Java Docs
Further, the structural modification could happen either from single thread or from multiple threads. The behavior of ArrayList would be different in both the cases as mentioned below.
Single Threaded Scenario
Never call list.remove(element) to remove a item from list while traversing it. Rather use Iterator.remove() mehtod.
private List<String> list = new ArrayList<>(asList("first", "second", "third", "fourth"));
public void unsafeMethod() {
    for (String item : list) { // Will throw ConcurrentModificationException
    list.remove(item);
  }
}

public void safeMethod() {
    Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) { // safe to call iterator.remove()
    String item = iterator.next();
    iterator.remove();
 }
}
Multi-Threading Scenario
ArrayList implementation is not thread-safe because it provides no synchronization mechanism for protecting
the shared state of its fields. If multiple threads access an ArrayList instance concurrently, and at least one of
the threads modifies the list structurally, it must be synchronized externally. This is typically accomplished by
synchronizing on some object that naturally encapsulates the list.
If no such object exists, the list should be “wrapped” using the Collections.synchronizedList() method. This is
best done at creation time, to prevent accidental unsynchronized access to the list :
List list = Collections.synchronizedList(new ArrayList(...));
public void safeMethod() {
    synchronized(list) {
    ...rest of the code as shown in previous method
}
Hidden Iterators
There are certain ArrayList methods which uses Iterators in a hidden form the API user. size() and toString()
are few of them. So care must be taken to call these methods from synchronized block in case of multi-threaded scenario.
Java 8 provides a safer method to conditionally remove items from stream using a filter
List<String> names = new ArrayList(asList("munish","ravneesh", "rajneesh"));
names.removeIf(name -> "munish".equalsIgnoreCase(name));
System.out.println("names = " + names);
Though lambda makes removal quite compact, but the operation is not thread-safe and must not be used in multi-threaded environment without explicit synchronization in place.

1 comment:

  1. Do these rules apply to Java 8 Streams as well? Or is there a way to avoid the fail-fast scenario.

    ReplyDelete

Your comment will be published after review from moderator