用于并发映射修改的类似Java迭代器的构造

Question

比如说:

for (X x : some_map.values ())
    doSomething (x);

，其中doSomething()通过几层代码间接地为some_map增加了更多的值。使用迭代器(如上面的示例代码)，我将ConcurrentModificationException扔到我脸上。

我可以使some_map成为LinkedHashMap，即具有可预测的迭代顺序。此外，当向其中添加新项时，它总是在迭代顺序的末尾添加。换句话说，如果ConcurrentModificationException以某种方式没有抛出，循环将只迭代最后新添加的项，即完全可以正常工作。或者，换句话说，我在这里确实有并发修改，但我可以保证它的行为是良好定义的，而不是错误的。

问题:我可以在上面的循环中使用与迭代器"类似"的东西来避免并发修改异常吗?

注意，由于一些额外的约束，我不能使添加的项意识到循环。我也不能把这个改成非地图的东西。这只是一段代码，但some_map也在其他地方使用，并且是一个映射是有原因的。

编辑:

我的问题是，我是否可以迭代(不一定以标准方式)我添加项目的相同地图。很明显，我可以迭代一个副本，在循环之后，将副本与原副本进行比较，找到新的项，迭代这些项，以此类推。问题是，我可以完全避免这个，因为在我的情况下，唯一的问题是ConcurrentModificationException的过度急于抛出。对我来说，回答"不，你做不到"比回答"你能做……"更好。因为我可以自己设计一个替代代码。我只是想知道我是否忽略了一些优雅的解决方案。

Answer 1

我使用的一个技巧是在迭代列表时处理它，当这种处理涉及删除元素时，使用降序索引访问它并在最后删除项。

for(int i=myList.size()-1;i>=0;i--) {
        Object item = myList.get(i);
        if(needsToBeRemoved(item)) {
            myList.remove(i);
        }
}

这样就可以在迭代列表的同时操作它。这对列表是有效的，因为除了迭代器之外，还可以通过索引访问列表中的元素。

在处理映射时也可以应用相同的技术，如果它遵循某种排序，在处理(有序映射)时不会改变。

如果你想要或需要使用迭代器，那么除了复制信息(使用第二个map)没有其他选择

:

还可以使用辅助迭代器(键的列表)。例如:

public static void main(String[] args) {
        Map<Long, String> map = new HashMap<>();
        map.put(1L, "Start");
        map.put(10L, "End");
        // This throws ConcurrentModificationException
        // for (Long value : map.keySet()) {
        // map.put(value + 1, "Other");
        // }
        for (Long value : new ArrayList<Long>(map.keySet())) {
            // This works ok
            map.put(value + 1, "Other");
        }
        System.out.println(map);
        // Prints: {1=Start, 2=Other, 10=End, 11=Other}
    }

Answer 2

这可能有点争议，但是如果您不关心并发修改，为什么不使用LinkedHashMap而忽略ConcurrentModificationException呢?

基本上

:

try {
   myMap.values().forEach(this::doSomething);
}
catch (ConcurrentModificationException ignored) {
}

我认为这将与LinkedHashMap工作，但它显然不是预期的用途。但是，您可以实现适合此类用途的自己的版本。

"正确"的方法是复制你想要迭代的值或键，然后检查是否添加了一些东西。约:

final Set<K> processedKeys = new HashSet<>();
do {
   final Set<K> keysToProcess = new HashSet<>(myMap.keySet());
   keysToProcess.removeAll(processedKeys);
   keysToProcess.forEach(key -> doSomething(myMap.get(key)));
} while (!keysToProcess.isEmpty());

为@doublep和@RealSkeptic更新 -为什么我认为仅仅忽略myMap.values().forEach(this::doSomething);中的异常就可以工作。

请参阅forEach或values()返回的集合在LinkedHashMap中的代码:

    public final void forEach(Consumer<? super V> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e.value);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }

所以forEach遍历链表。如果将值添加到map中，则它们将被添加到链表中，因此for循环将迭代直到到达链表的末尾。该方法首先然后检查修改计数。因此，该操作将有效地应用于所有值，甚至是新添加的值。

Answer 3

迭代索引而不是实际的集合是一种鲜为人知的技巧。您可以使用流API获取第n个元素。我不确定这会有多高效，因为所有的中间对象都被创建了。

LinkedHashMap<String, String> lhm = new LinkedHashMap();        
// fill lhm
for ( int idx=0; idx < lhm.size(); idx++ ) {
    String val = lhm.values().stream().skip(idx).findFirst().get();
    // process val...
}

Answer 4

没有内置的方法，但如果您使用生产者/消费者模式的变体，每次迭代刷新处理队列，则不难:

Map<K, V> map; // assuming
Set<V> processed = new HashSet<>();
while (!map.values().containsAll(processed)) {
    List<V> queue = new ArrayList<>(map.values());
    queue.removeAll(processed);
    V x = queue.get(0);
    processed.add(x);
    doSomething(x);
}