java.util.ConcurrentModificationException with HashSet

Question

I'm implementing the non-deterministic finite automaton described in this post and this other post, using Konrad Rudolph's proposed algorithm.

Instead of using a C++ multimap, I used a HashSet<Character> [][] transitions array (this is homework and Google's guava library cannot be used). The 1st dimension is the origin state, 2nd dimension is the destiny state and the HashSet defines the symbols for transition between origin and destiny states. The constructor for my Automaton class is:

Automaton (int numberOfStates)
{
    this.numberOfStates = numberOfStates;
    alphabet = new HashSet<>();
    finalStates = new HashSet<>();

    transitions = new HashSet[numberOfStates][numberOfStates];

    for (int i = 0; i < numberOfStates; i++)
    {
        for (int j = 0; j < numberOfStates; j++)
        {
            transitions[i][j] = new HashSet<Character>();
        }
    }
}

This is my implementation of Konrad Rudolph's algorithm using this transitions array:

public String readStringInAutomaton (char[] inputString,
            int initialState)
{
    HashSet<Integer> currentStates = new HashSet<>();
    HashSet<Integer> nextStates = new HashSet<>();

    currentStates.add(initialState);

    // for each char in inputString
    for (int charIndex = 0; charIndex < inputString.length; charIndex++)
    {
        char currentTransitionChar = inputString[charIndex];
        // for each state in currentStates
        for (Integer originState : currentStates)
        {
            // for each transition starting from originState, current
            // char
            for (int destinyStateIndex = 0; destinyStateIndex < numberOfStates; destinyStateIndex++)
            {
                if (transitions[originState][destinyStateIndex]
                        .contains(currentTransitionChar))
                {
                    nextStates.add(destinyStateIndex);
                }
            }
        }
        currentStates = nextStates;
    }
}

I've tried replacing every instantiation of HashSet with Collections.synchronizedSet(new HashSet<>());, as recommended in Oracle's HashSet documentation.

But then I get a java.lang.ArrayStoreException: java.util.Collections$SynchronizedSet when initializing transitions.

for (int i = 0; i < numberOfStates; i++)
{
    for (int j = 0; j < numberOfStates; j++)
    {
        transitions[i][j] = Collections
                .synchronizedSet(new HashSet<>());
    }
}

How can I avoid these Concurrency exceptions?

Please provide a complete code example that illustrates the exact problem you are having. Be sure to include the stack trace and show which line causes the exception. — Code-Apprentice, Oct 17 '14 at 19:37
Note that `ConcurrentModificationException` has **nothing** to do with multithreading in this case because you don't have multiple threads here. — Code-Apprentice, Oct 17 '14 at 19:46

score 5 · Accepted Answer · answered Oct 17 '14 at 19:39

Your problem is not about multithreading but about iterating over a Set in which you keep adding elements.

You have currentStates = nextStates and then in your for loop for (Integer originState: currentStates) you do nextStates.add(destinyStateIndex) (while nextStates and currentStates are actualling the same instance!) without re-assigning nextStates.

You should correct your algorithm: nextStates must be re-assigned somewhere in the loop based on the way you use it.

java.util.ConcurrentModificationException with HashSet

1 Answers1

Linked