ConcurrentHashMap中的entrySet（） . removeIf的行为-Java 学习之路

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

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

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

类似地，Iterators，Spliterators和Enumerations在迭代器/枚举的创建时或之后的某个时刻返回反映哈希表状态的元素 . 嘿不要抛出ConcurrentModificationException . 但是，迭代器设计为一次只能由一个线程使用 .

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

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

我可以想象，实施可以通过多种方式防止这种行为 . 例如：可能迭代器不反映put / remove操作，但总是反映值更新，或者迭代器的remove方法可能会检查整个映射（键和值）是否仍然存在于映射中，然后才调用键上的remove . 我找不到任何有关这些事情的信息，我想知道是否有一些东西可以使用例安全 .

2 回答

我还设法在我的机器上重现这种情况 . 我认为，问题是 EntrySetView （由 ConcurrentHashMap.entrySet() 返回）从 Collection 继承了 removeIf 实现，它看起来像：

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 的正确实施 .

回复于 2024-04-26T00:17:04+08:00

9
在用户Zielu与Zielu的回答讨论之后，我已经深入了解了ConcurrentHashMap代码并发现：
- ConcurrentHashMap实现提供 remove(key, value) 方法，该方法调用 replaceNode(key, null, value)
- replaceNode 检查在删除之前 Map 中是否仍然存在键和值，因此使用它应该没问题 . 文档说它
用v替换节点值，条件是匹配cv if * non-null .
- 在问题中提到的ConcurrentHashMap的 .entrySet() 被调用，返回 EntrySetView 类 . 然后 removeIf 方法调用 .iterator() ，返回 EntryIterator .
- EntryIterator extends BaseIterator 并继承调用 map.replaceNode(p.key, null, null) 的 remove 实现，该实现禁用条件删除并始终删除密钥 .
如果迭代器总是迭代“当前”值并且如果某些值被修改则永远不返回旧值，则仍然可以阻止事件的负面过程 . 我仍然不知道是否发生了这种情况，但下面提到的测试用例似乎验证了整个问题 .

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

代码启动两个线程 . 其中一个（DELETING_THREAD）删除映射到'false'布尔值的所有条目 . 另一个（ADDING_THREAD）随机将 (1, true) 或 (1,false) 值放入 Map 中 . 如果它将 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();
    }
}
```
回复于 2024-04-26T00:17:04+08:00

ConcurrentHashMap中的entrySet（） . removeIf的行为

2 回答

相关问题