带有HashSet的java.util.ConcurrentModificationException

Question

我正在使用Konrad Rudolph提出的算法实现本文和另一篇文章中描述的非确定性有限自动机.

我没有使用C++多图,而是使用了一个HashSet<Character> [][] transitions数组(这是家庭作业,Google的番石榴库不能使用).第一维是原始状态,第二维是命运状态,而HashSet定义原点和命运状态之间转换的符号.我的Automaton类的构造函数是:

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>();
        }
    }
}

这是我使用此过渡数组实现的Konrad Rudolph算法:

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;
    }
}

我已经尝试用Oracle的HashSet文档中的Collections.synchronizedSet(new HashSet<>());建议替换HashSet的每个实例化.

但是在初始化转换时我得到了一个java.lang.ArrayStoreException:java.util.Collections $ SynchronizedSet.

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

如何避免这些并发异常？

Answer 1

你的问题不是关于多线程,而是关于迭代Set你不断添加元素的问题.

你有currentStates = nextStates,然后在你的for循环中for (Integer originState: currentStates)做nextStates.add(destinyStateIndex)(虽然nextStates并且currentStates正在实现相同的实例!)而无需重新分配nextStates.

您应该更正您的算法:nextStates必须根据您使用它的方式在循环中的某处重新分配.