ConcurrentModificationException during putting new element into HashMap

Question

I have some code:

Map<String, Integer> letters = new HashMap<String, Integer>();
letters.put(String.valueOf(input.charAt(0)),
            numberOfLettersInWord(input,input.charAt(0)));
for (int i = 0; i < input.length(); i++) {
   for (String key : letters.keySet()) {
      if (!letters.containsKey(String.valueOf(input.charAt(i)))) {
         letters.put(String.valueOf(input.charAt(i)),
                     numberOfLettersInWord(input,input.charAt(i)));
      } else continue;
      System.out.println(letters);
   }
   System.out.println(1);
}
System.out.println(2);

The main idea in the code - there is some word in String input(not empty, not null, with no non-letter symbols), need to count how many times each letter can be found there. Counting works OK (in the numberOfLettersInWord method) but when I try to add letters and digits to HashMap<String, Integer> some problems happens - it adds all letters and their numbers correctly but some error pops up. For this code it will show:

1
1
{a=4, b=4}
1
1
1
1
{a=4, b=4, c=3}
Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java:1579)
    at java.base/java.util.HashMap$KeyIterator.next(HashMap.java:1602)
    at LetterCounter.count(LetterCounter.java:25)
    at LetterCounter.main(LetterCounter.java:11)

Process finished with exit code 1

From what I see there is something happens when there are no new letters to be added. Can you explain why this happens and how to solve this?

It supposed to have some more digit outputs after the {a=4, b=4, c=3} was shown but it ends with the exception (it is not really necessary, just an indicator where it stops working...)

The word used in this run was String input = "aabbabcccba";

numberOfLettersInWord returns Integer value of how many times letter input.charAt(i) was found in word input(this works ok)

line 2 in code fragment was used just to make the HashMap contain at least one line (null and empty checks already done by this moment and work well)

I saw people had problems with hashmap.remove() in Why is a ConcurrentModificationException thrown and how to debug it but I am not sure this is the same-same thing that can be solved with that answer. Also I am not sure this answer is applicable for my case ConcurrentModificationException - HashMap

Answer 1

ok, i think i solved it:

Map<String, Integer> letters = new HashMap<String, Integer>();
letters.put(String.valueOf(input.charAt(0)),numberOfLettersInWord(input,input.charAt(0)));
for(int i = 0; i < input.length(); i++) {
   letters.putIfAbsent(String.valueOf(input.charAt(i)),numberOfLettersInWord(input,input.charAt(i)));
}

i removed some extra code and it started work, even all tests passed

Answer 2

Why the ConcurrentModificationException?

You're getting a ConcurrentModificationException because you are structurally modifying the map while iterating its key set.

Documentation

Here's what the documentation of HashMap says on the subject:

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw 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.

Those "collection view methods" it mentions are the following:

1. HashMap#keySet(), which returns a Set<K>.

2. HashMap#values(), which returns a Collection<V>.

3. HashMap#entrySet(), which returns a Set<Map.Entry<K, V>>.

For-Each Loops

If you aren't aware, a for-each loop uses an Iterator behind the scenes. In other words, something like this:

List<String> list = List.of("one", "two", "three");
for (String element : list) {
    System.out.println(element);
}

Is compiled down to:

List<String> list = List.of("one", "two", "three");
for (Iterator<String> iterator = list.iterator(); iterator.hasNext(); ) {
    String element = iterator.next();
    System.out.println(element);
}

Your Code

You have a for-each loop iterating over the key set of your map. Inside this for-each loop you have a call to put, which is a structurally-modifying operation, on the same map.

for (String key : letters.keySet()) {
   if (!letters.containsKey(String.valueOf(input.charAt(i)))) {
      letters.put(String.valueOf(input.charAt(i)),
                  numberOfLettersInWord(input,input.charAt(i)));
   } else continue;
   System.out.println(letters);
}

Thus, a ConcurrentModificationException is likely to be thrown. In your case it's all but guaranteed.

---

Solution

You are apparently trying to count the frequencies of each letter in a string. This does not require you to loop over the key set of the map. The fact you don't actually use the key variable anywhere inside the for-each loop is a good indicator of this. This means you can simply get rid of the for-each loop and your code should work just fine.

Map<String, Integer> letters = new HashMap<String, Integer>();
letters.put(String.valueOf(input.charAt(0)), numberOfLettersInWord(input,input.charAt(0)));
for (int i = 0; i < input.length(); i++) {
    if (!letters.containsKey(String.valueOf(input.charAt(i)))) {
        letters.put(String.valueOf(input.charAt(i)), numberOfLettersInWord(input,input.charAt(i)));
    }
}

Note that call to put if the map does not already contain the key could be replaced with a call to computeIfAbsent. That method takes the key and a Function that computes the value if the key is not already contained in the map (or if the key is currently mapped to null). It would look something like this:

Map<String, Integer> letters = new HashMap<String, Integer>();
letters.put(String.valueOf(input.charAt(0)), numberOfLettersInWord(input,input.charAt(0)));
for (int i = 0; i < input.length(); i++) {
    letters.computeIfAbsent(String.valueOf(input.charAt(i)), key -> numberOfLettersInWord(input, key));
}

^{Note: The second argument the above computeIfAbsent call is a Function implemented via a lambda expression.}

Potential Improvements

There may be a couple of improvements you could make to your code.

Change Key Type to Character

Given you're counting the frequency of characters, it would make sense to represent that in the code by using a Map<Character, Integer> instead of a Map<String, Integer>.

Count as You Go

I can only assume that numberOfLettersInWord loops over the input string and counts how many times the given character occurs in said string. This means you loop over the string for each character in the string, resulting in an inefficient algorithm. Though you do have optimization where you only compute the frequency of a character if you haven't already done so for that character, so that improves things a little.

However, you're already looping over all the characters in the input string. You might as well count the frequency of each character as you go. It could look something like:

String input = ...;

Map<Character, Integer> frequencies = new HashMap<>();
for (int i = 0; i < input.length(); i++) {
    Character key = input.charAt(i);

    Integer value = frequencies.get(key);
    if (value == null) {
        frequencies.put(key, 1);
    } else {
        frequencies.put(key, value + 1);
    }
}

Use compute to Count

The body of that for loop can be replaced with a call to compute:

String input = ...;

Map<Character, Integer> frequencies = new HashMap<>();
for (int i = 0; i < input.length(); i++) {
    frequencies.compute(input.charAt(i), (key, value) -> {
        if (value == null) {
            return 1;
        } else {
            return value + 1;
        }
    });
}

And that lambda expression (implementing a BiFunction) can be "simplified" even more:

(key, value) -> value == null ? 1 : value + 1

Use merge to Count

Another option is to use merge:

frequencies.merge(input.charAt(i), 1, Integer::sum);

^{Note: The Integer::sum is a method reference implementing a BiFunction.}

Answer 3

letters.keySet() is returning a set which is backed by the keys of the HashMap, which you then alter by calling put(). So the conflict here is between the keySet and the keys of the map. You would need to use an iterator, or extract the keys into a separate collection, by copying the keySet each time through the outer loop. Honestly, the algorithm is sounding kind of expensive, though I haven't really tried to work out a better approach...