ConcurrentHashMap中的entrySet().removeIf的行为

Question

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

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

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

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

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

1. 地图包含映射: 'A'->0
2. 删除线程开始执行 map.entrySet().removeIf(entry->entry.getValue()==0)
3. 删除线程调用.iteratator()内部removeIf呼叫,并获得迭代器反映了收集的当前状态
4. 另一个线程执行 map.put('A', 1)
5. 删除线程仍然看到'A'->0映射(迭代器反映旧状态),因为0==0它是true,它决定从地图中删除A键.
6. 地图现在包含'A'->1但删除线程看到旧值,0并且'A' ->1条目被删除,即使它不应该.地图是空的.

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

Answer 1

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

    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.

Answer 2

在用户Zielu与Zielu的回答讨论之后,我已经深入了解了ConcurrentHashMap代码并发现:

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

用v替换节点值,条件是匹配cv if*non-null.

• 在问题中提到的ConcurrentHashMap .entrySet()被调用,它返回EntrySetView类.然后返回的removeIf方法调用..iterator()EntryIterator
• EntryIterator扩展BaseIterator并继承remove调用map.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();
    }
}