java.util.ConcurrentModificationException 与 HashSet

Question

我正在实现 this post 中描述的非确定性有限自动机还有这个other post ，使用Konrad Rudolph's proposed algorithm 。

我没有使用 C++ 多重映射，而是使用 HashSet<Character> [][] transitions数组(这是家庭作业，谷歌的 Guava 库不能使用)。第一维是原始状态，第二维是目标状态，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;
    }
}

我尝试将 HashSet 的每个实例替换为 Collections.synchronizedSet(new HashSet<>()); ，如 Oracle's HashSet documentation 中的建议。

但是在初始化转换时我得到了 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。