EntrySet（）.removeIf 在 ConcurrentHashMap 中的行为

multithreading java java.util.concurrent concurrentmodification concurrenthashmap

2022-09-01 19:17:50

我想使用 ConcurrentHashMap 让一个线程定期从映射中删除一些项目，让其他线程同时从映射中放置和获取项目。

我在删除线程中使用。我想知道我能对它的行为做出什么假设。我可以看到该方法使用迭代器来遍历映射中的元素，检查给定的条件，然后在需要时使用.map.entrySet().removeIf(lambda)removeIfiterator.remove()

文档提供了有关 ConcurrentHashMap 迭代器行为的一些信息：

类似地，迭代器、拆分器和枚举返回的元素反映了在创建迭代器/枚举时或自创建以来哈希表的状态。嘿，不要抛出 ConcurrentModificationException。但是，迭代器设计为一次只能由一个线程使用。

由于整个调用发生在一个线程中，我可以确保迭代器当时没有被多个线程使用。我仍然想知道下面描述的事件过程是否可能：removeIf

地图包含映射：'A'->0
删除线程开始执行map.entrySet().removeIf(entry->entry.getValue()==0)
删除调用内部的 Thread 调用，并获取反映集合当前状态的迭代器.iteratator()removeIf
另一个线程执行map.put('A', 1)
删除线程仍然看到映射（迭代器反映旧状态），并且由于是真的，它决定从映射中删除A键。'A'->00==0
地图现在包含但删除线程看到的旧值，并且条目被删除，即使它不应该是。地图为空。'A'->10'A' ->1

我可以想象，实现可能会以多种方式阻止这种行为。例如：迭代器可能不反映 put/remove 操作，但总是反映值更新，或者迭代器的 remove 方法在对键调用 remove 之前检查整个映射（键和值）是否仍存在于映射中。我找不到有关发生的任何这些事情的信息，我想知道是否有某些东西使该用例安全。

答案 1

我还设法在我的机器上重现了这种情况。我认为，问题在于（由返回）继承了它的实现，它看起来像：EntrySetViewConcurrentHashMap.entrySet()removeIfCollection

    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            // `test` returns `true` for some entry
            if (filter.test(each.next())) { 
               // entry has been just changed, `test` would return `false` now
               each.remove(); // ...but we still remove
               removed = true;
            }
        }
        return removed;
    }

以我的拙见，这不能被视为的正确实现。ConcurrentHashMap

答案 2

在与用户Zielu在Zielu的答案下面的评论中讨论后，我更深入地研究了ConcurrentHashMap代码，发现：

ConcurrentHashMap 实现提供了调用remove(key, value)replaceNode(key, null, value)
replaceNode在删除之前检查键和值是否仍然存在于映射中，因此使用它应该没问题。文档说它

将节点值替换为 v，条件是如果 * 非空，则以 cv 匹配为条件。

在问题中提到的情况中，ConcurrentHashMap被称为哪个返回类。然后调用返回 ..entrySet()EntrySetViewremoveIf.iterator()EntryIterator
EntryIterator扩展并继承调用的实现，该实现禁用条件删除并始终删除密钥。BaseIteratorremovemap.replaceNode(p.key, null, null)

如果迭代器总是迭代“当前”值，并且如果修改了某些值，则永远不会返回旧值，则仍然可以防止事件的负过程。我仍然不知道这是否会发生，但下面提到的测试用例似乎验证了整个事情。

我认为这创建了一个测试用例，表明我的问题中描述的行为确实可能发生。如果我在代码中有任何错误，请纠正我。

代码启动两个线程。其中之一（DELETING_THREAD）删除映射到“false”布尔值的所有条目。另一个（ADDING_THREAD）将或值随机放入地图中。如果它输入值，则期望该条目在选中时仍然存在，如果不是，则引发异常。当我在本地运行时，它会快速引发异常。(1, true)(1,false)true

package test;

import java.util.Random;
import java.util.concurrent.ConcurrentHashMap;

public class MainClass {

    private static final Random RANDOM = new Random();

    private static final ConcurrentHashMap<Integer, Boolean> MAP = new ConcurrentHashMap<Integer, Boolean>();

    private static final Integer KEY = 1;

    private static final Thread DELETING_THREAD = new Thread() {

        @Override
        public void run() {
            while (true) {
                MAP.entrySet().removeIf(entry -> entry.getValue() == false);
            }
        }

    };

    private static final Thread ADDING_THREAD = new Thread() {

        @Override
        public void run() {
            while (true) {
                boolean val = RANDOM.nextBoolean();

                MAP.put(KEY, val);
                if (val == true && !MAP.containsKey(KEY)) {
                    throw new RuntimeException("TRUE value was removed");
                }

            }
        }

    };

    public static void main(String[] args) throws InterruptedException {
        DELETING_THREAD.setDaemon(true);
        ADDING_THREAD.start();
        DELETING_THREAD.start();
        ADDING_THREAD.join();
    }
}