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
– Code-Apprentice, Commented Oct 17, 2014 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
– Code-Apprentice, Commented Oct 17, 2014 at 19:46

Jean Logeart · Accepted Answer · 2014-10-17 19:39:38Z

5

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.

answered Oct 17, 2014 at 19:39

Jean Logeart

54.1k11 gold badges88 silver badges120 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

java.util.ConcurrentModificationException with HashSet

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related