How to fix 'java.util.ConcurrentModificationException' with double iterator on HashMap

Question

I want to 'merge' elements of the same hashmap if they verify a condition between each other.

'Merge' means: sum their own attributes.

If 2 Items get merged, we should remove the second one from the hashmap, since it has been integrated into the first one.

This operation has to be efficient since the map may contain a high number of elements.

public static void main(String[] args) {
    Map<Long, Item> itemMap = new HashMap(){
        {
            put(0L, new Item(2558584));
            put(1L, new Item(254243232));
            put(2L, new Item(986786));
            put(3L, new Item(672542));
            put(4L, new Item(48486));
            put(5L, new Item(76867467));
            put(6L, new Item(986786));
            put(7L, new Item(7969768));
        }
    };

    Iterator it_I = itemMap.entrySet().iterator();
    while (it_I.hasNext()) {
        Map.Entry pair_I = (Map.Entry)it_I.next();
        Item tempItem_I = (Item)pair_I.getValue();

        System.out.println("I:" + tempItem_I);

        Iterator it_J = itemMap.entrySet().iterator();
        while (it_J.hasNext()) {
            Map.Entry pair_J = (Map.Entry)it_J.next();
            Item tempItem_J = (Item)pair_J.getValue();

            if (!pair_J.getKey().equals(pair_I.getKey())) {
                boolean isSame = tempItem_I.isSame(tempItem_J);
                if(isSame){
                    tempItem_I.merge(tempItem_J);
                    it_J.remove();
                }

            }
        }
    }
}




public class Item {
    long id;

    public Item(long id) {
        this.id = id;
    }

    public boolean isSame(Item item) {
        if(this.id == item.id) return true;
        else return false;
    }

    public void merge(Item item) {
        this.id += item.id;
    }

    public String toString() {
        return String.valueOf(this.id);
    }
}

Only the 2 Items containing the id: 986786 can be merged together, since they verify the condition to be merged (same id).

However it is not possible to remove it:

Exception in thread "main" java.util.ConcurrentModificationException

   I:2558584
   I:254243232
        at java.util.HashMap$HashIterator.nextNode(HashMap.java:1445)
    I:986786
        at java.util.HashMap$EntryIterator.next(HashMap.java:1479)
        at java.util.HashMap$EntryIterator.next(HashMap.java:1477)
        at Main.main(Main.java:23)

Answer 1

The basic problem is that you are running two iterators concurrently, this means that they are processing mapItem at the same time.

But why did I got this error?

Because, when one iterator removes an item from mapItem, it cannot be reflected in the other iterator, they get out of sync and that is why you get that concurrent modification exception.

The solution proposed by @Joakim Danielson it is not thread safe. This means, the access to shared data is not protected from race conditions if multiple thread consume the method.

A possible alternative will be convert the itemMap into a ConcurrentHashMap instance. This will allow us to use a for-each loop and maintain our code thread safe. Instead of use an Iterator.

private static void solutionFor(Map<Long, Item> itemMap)
{
    Map<Long, Item> fooMap = itemMap
            .entrySet()
            .stream()
            .collect(Collectors.toConcurrentMap(Map.Entry::getKey, e -> new Item(e.getValue().getId())));
    Map<Long, Long> valueMapper = new HashMap<>();

    System.out.println("Before deletion: ");
    System.out.println(fooMap);

    Set<Map.Entry<Long, Item>> entries = fooMap.entrySet();
    for (Map.Entry<Long, Item> entry : entries) {
        Long index = valueMapper.get(entry.getValue().getId());
        if (index != null) {
            Item accumulator = fooMap.get(index);
            accumulator.merge(entry.getValue());
            fooMap.remove(entry.getKey());
        } else {
            valueMapper.put(entry.getValue().getId(), entry.getKey());
        }
    }

    System.out.println("After deletion: ");
    System.out.println(fooMap);
}

Alternative

I tried here to implement an optimized solution. Using Stream.collect() method to create a new map with the values filtered.

public static void main(String[] args)
{
    Map<Long, Item> itemMap = Stream.of(
            entry(0L, new Item(2558584)),
            entry(1L, new Item(254243232)),
            entry(2L, new Item(986786)),
            entry(3L, new Item(672542)),
            entry(4L, new Item(4846)),
            entry(5L, new Item(76867467)),
            entry(6L, new Item(986786)),
            entry(7L, new Item(7969768)),
            entry(8L, new Item(68868486)),
            entry(9L, new Item(923)),
            entry(10L, new Item(986786)),
            entry(11L, new Item(549768)),
            entry(12L, new Item(796168)),
            entry(13L, new Item(868421)),
            entry(14L, new Item(923)),
            entry(15L, new Item(986786)),
            entry(16L, new Item(549768)),
            entry(17L, new Item(4846)),
            entry(18L, new Item(4846)),
            entry(19L, new Item(76867467)),
            entry(20L, new Item(986786)),
            entry(21L, new Item(7969768)),
            entry(22L, new Item(923)),
            entry(23L, new Item(4846)),
            entry(24L, new Item(986786)),
            entry(25L, new Item(549768))
    ).collect(entriesToMap());

    Map<Long, Item> fooMap = itemMap
            .entrySet()
            .stream()
            .collect(Collectors.toMap(Map.Entry::getKey, e -> new Item(e.getValue().getId())));
    Map<Long, Long> valueMapper = new HashMap<>();

    System.out.println("Before deletion: ");
    System.out.println(fooMap);

    Map<Long, Item> result = fooMap.entrySet()
            .stream()
            .filter(entry -> {
                Long index = valueMapper.get(entry.getValue().getId());
                if (index != null) {
                    Item item = fooMap.get(index);
                    item.merge(entry.getValue());
                    return false;
                } else {
                    valueMapper.put(entry.getValue().getId(), entry.getKey());
                }
                return true;
            })
            .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

    System.out.println("After deletion: ");
    System.out.println(result);
}

public static <K, V> Map.Entry<K, V> entry(K key, V value)
{
    return new AbstractMap.SimpleEntry<>(key, value);
}

public static <K, U> Collector<Map.Entry<K, U>, ?, Map<K, U>> entriesToMap()
{
    return Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue);
}

Answer 2

Here is a more linear way to solve this using an extra Map to keep track if Item identifiers

Map<Long, Long> reversed = new HashMap<>();
Iterator<Map.Entry<Long, Item>> iterator = itemMap.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<Long, Item> pair = iterator.next();
    Long itemKey = reversed.get(pair.getValue().id);
    if (itemKey != null) {
        Item item = itemMap.get(itemKey);
        item.merge(pair.getValue());
        iterator.remove();
    } else {
        reversed.put(pair.getValue().id, pair.getKey());
    }
}

Answer 3

You have two separate iterators running concurrently, processing the same map items. If one iterator removes an item, it is not reflected in the other iterator so they get out of sync. Thus you get a concurrent modification exception.

Without knowing the significance of the key I would just make the Item the key. As I go thru my list of items check to see if the key exists. if it does, remove it, add this item to the current one and then readd it to the map.

And if the class really represents your Item you should eliminate your isSame method and override both equals and hashCode.