Why exception would be thrown when deleting element while looping through HashMap in Java

HashMap and other Collection types are frequently used in Java application programming. This post will explain why exception would be thrown when deleting element with Map.remove() while looping through a Map using Iterator. This issue would also occur to other Collection types such as Set, List.

Below is a sample code snippet demonstrating the exception thrown.

Map<String,String> map = Collections.synchronizedMap(new TreeMap<String,String>());
 
map.put("key1","value1");
map.put("key2","value2");
map.put("key3","value3");
 
Set<Entry<String,String>> entries = map.entrySet();
 
Iterator<Entry<String,String>> iter = entries.iterator();
 
while(iter.hasNext()){
    System.out.println(iter.next()); //Will throw ConcurrentModificationException
    map.remove("key2");  
}

To understand why this would happen, let's analyze the source code of HashMap. The key here is the modCount and expectedModCount. modCount is used to track the number of times this HashMap has been structurally modified. Structural modifications are those that change the number of mappings in the HashMap or otherwise modify its internal structure (e.g., rehash).

When an Iterator is initialized, the expectedModCount will be set to modCount.

HashIterator() {
	expectedModCount = modCount;
	Node<K,V>[] t = table;
	current = next = null;
	index = 0;
	if (t != null && size > 0) { // advance to first entry
		do {} while (index < t.length && (next = t[index++]) == null);
	}
}

Thereafter modCount would be changed if there is structural change to the Map such as adding element to the Map or removing element from the Map.

While calling HashIterator.nextNode() method to get the next element, there is a check on whether modCount is the same as expectedModCount, if it's not, a ConcurrentModificationException will be thrown. 

final Node<K,V> nextNode() {
	Node<K,V>[] t;
	Node<K,V> e = next;
	if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
	if (e == null)
		throw new NoSuchElementException();
	if ((next = (current = e).next) == null && (t = table) != null) {
		do {} while (index < t.length && (next = t[index++]) == null);
	}
	return e;
}

When deleting an element using Map.remove(), we could see that modCount is changed but expectedModCount is not.

if (node != null && (!matchValue || (v = node.value) == value ||
					 (value != null && value.equals(v)))) {
	if (node instanceof TreeNode)
		((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
	else if (node == p)
		tab[index] = node.next;
	else
		p.next = node.next;
	++modCount;
	--size;
	afterNodeRemoval(node);
	return node;
}

This is why the exception would be thrown next time when Iterator.nextNode() is called. However, if you call Iterator.remove() while looping through the elements, no exception would be thrown. This is because expectedModCount is reset to modCount when this Iterator.remove() method is called.

public final void remove() {
	Node<K,V> p = current;
	if (p == null)
		throw new IllegalStateException();
	if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
	current = null;
	K key = p.key;
	removeNode(hash(key), key, null, false, false);
	expectedModCount = modCount;
}

Be careful while trying to deleting element from a Map while looping through it. And one final tip is the best way to understand why some behavior happens while running a program is to dig into its source code.