Java:在这种特殊情况下如何处理ConcurrentModificationException？

Question

在发布这个问题之前，我阅读了 here 中的帖子。但对于这个特定的问题，我真的不知道如何应用相同的哲学？

在下面的问题中，我的变量 graph具有以下结构:HashMap<Integer, ArrayList<Integer>> 。 和u和v类型为int 。基本上，我想删除值 v在键值为 i 的数组列表中，其中i出现在v的数组列表中。

所以，如果整数 i出现在v的数组列表中，我们得到i的数组列表在图中并删除值 v从中。

这听起来真的很复杂。但我现在被这个 ConcurrentModificationException 困住了一段时间。

public int random_contraction_algo(){
    while(graph.size() > 2){
        int u = select_remaining_edges_at_random(new ArrayList<Integer> (graph.keySet()));
        int v = select_remaining_edges_at_random(graph.get(u));      
        merge(u,v);        
    }
    return -1;
}

// select a pair of vertices from an edge
public int select_remaining_edges_at_random(ArrayList<Integer> vertices){
    int index = (int)(Math.random() * (vertices.size()));
    return vertices.get(index);
}

public void merge(int u, int v){

    graph.get(u).addAll(graph.get(v));

    // remove self-loops
    graph.get(u).removeAll(Collections.singleton(u));
    graph.get(u).removeAll(Collections.singleton(v));

    // make sure all the edges of v are connected to u instead v
    for(Iterator<Integer> iterator = graph.get(v).iterator(); iterator.hasNext();){
        Integer i = iterator.next();
        graph.get(i).remove((Integer) v);
        graph.get(i).add(u);

    }
    // remove key
      graph.remove(v);
}

更新:我非常感谢您的回答。然而，我意识到我忘记向你们展示我的代码中有一个外循环。

我尝试实现您的解决方案，但 ConcurrentModificationException 仍然发生。

这些是错误消息:

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:886)
    at java.util.ArrayList$Itr.next(ArrayList.java:836)
    at HashMapOfArrayList.merge(ArraylistOfArrayList.java:96)
    at HashMapOfArrayList.random_contraction_algo(ArraylistOfArrayList.java:69)
    at RunAlgo.main(ArraylistOfArrayList.java:111)

Answer 1

问题是，当 v == i 时，您正在修改迭代时的同一个列表。

一个简单的解决方案是防止这种情况:

for(Iterator<Integer> it = graph.get(v).iterator(); it.hasNext();) {
    Integer i = it.next();
    if (i == v) {
        it.remove();
    } else {
        graph.get(i).remove((Integer) v);
    }
}