ConcurrentHashMap中entrySet().removeIf的行为 [英] Behavior of entrySet().removeIf in ConcurrentHashMap

问题描述

我想使用ConcurrentHashMap来让一个线程定期从地图中删除某些项目，而让其他线程同时从地图中删除项目.

I would like to use ConcurrentHashMap to let one thread delete some items from the map periodically and other threads to put and get items from the map at the same time.

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

I'm using map.entrySet().removeIf(lambda) in the removing thread. I'm wondering what assumptions I can make about its behavior. I can see that removeIf method uses iterator to go through elements in the map, check the given condition and then remove them if needed using iterator.remove().

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

Documentation gives some info about ConcurrentHashMap iterators behavior:

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

Similarly, Iterators, Spliterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration. hey do not throw ConcurrentModificationException. However, iterators are designed to be used by only one thread at a time.

由于整个removeIf调用发生在一个线程中，因此我可以确定一次没有多个线程使用该迭代器.我仍然想知道下面描述的事件的过程是否可能:

As the whole removeIf call happens in one thread I can be sure that the iterator is not used by more than one thread at the time. Still I'm wondering if the course of events described below is possible:

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

1. Map contains mapping: 'A'->0
2. Deleting Thread starts executing map.entrySet().removeIf(entry->entry.getValue()==0)
3. Deleting Thread calls .iteratator() inside removeIf call and gets the iterator reflecting the current state of the collection
4. Another thread executes map.put('A', 1)
5. Deleting thread still sees 'A'->0 mapping (iterator reflects the old state) and because 0==0 is true it decides to remove A key from the map.
6. The map now contains 'A'->1 but deleting thread saw the old value of 0 and the 'A' ->1 entry is removed even though it shouldn't be. The map is empty.

我可以想象该行为可以通过多种方式阻止.例如:迭代器可能不反映放置/删除操作，但始终反映值更新，或者迭代器的remove方法可能会在对键调用remove之前检查整个映射(键和值)是否仍然存在于映射中.我找不到任何正在发生的事情的信息，我想知道是否有什么可以使用例变得安全.

I can imagine that the behavior may be prevented by the implementation in many ways. For example: maybe iterators are not reflecting put/remove operations but are always reflecting value updates or maybe the remove method of the iterator checks if the whole mapping (both key and value) is still present in the map before calling remove on the key. I couldn't find info about any of those things happening and I'm wondering if there's something which makes that use case safe.

推荐答案

我也设法在计算机上重现了这种情况. 我认为问题在于EntrySetView(由ConcurrentHashMap.entrySet()返回)从Collection继承其removeIf实现，并且看起来像:

I also managed to reproduce such case on my machine. I think, the problem is that EntrySetView (which is returned by ConcurrentHashMap.entrySet()) inherits its removeIf implementation from Collection, and it looks like:

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

In my humble opinion, this cannot be considered as a correct implementation for ConcurrentHashMap.

这篇关于ConcurrentHashMap中entrySet().removeIf的行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！