线程安全地从集合中查找和删除对象

Question

我想知道我怎样才能做类似下面的事情

class MyCollection<E> implements Collection<E> {
    @Nullable E findAndRemove(Predicate<E> predicate) {
        for (E e : this) {
            if (predicate.test(e)) {
                remove(e);
                return e;
            }
        }
        return null;
    }   
}

以线程安全的方式。它实际上不必是 Collection，因为唯一需要的操作是 add 和 findAndRemove。注意

removeIf 是不相关的，因为它删除了 all 匹配元素，并且在 return
假设同步不够好
CopyOnWriteArrayList 可能会，但 Javadoc 说 "efficient when ... traversal operations vastly outnumber mutations"，这在这里绝对不是真的
不允许return同一个元素两次（除非同时重新添加），这很容易在天真地使用CopyOnWriteArrayList时发生
return编辑哪个匹配元素并不重要

关于过早优化和 XY 问题：是的，我知道！我在闲逛某天可能需要或可能不需要的东西时进入了这个，但我发现了这个问题本身很有趣。

Answer 1

集合中可以使用读写锁进行变异，也可以使用ConcurrentHashMap将集合表示为集合。

Set set =Collections.newSetFromMap(new ConcurrentHashMap<Object,Boolean>());

Answer 2

因为你只需要 add 和 findAndRemove 方法，某种类型的并发哈希是一个自然的选择，因为自 Java 1.5。现在因为我们实际上不需要 Map 而是 Set 我们可以只使用（因为 Java 8 无论如何）ConcurrentHashMap.newKeySet() 使用相同的实现创建一个并发集作为并发映射。

然后，给定一个并发集，我们几乎可以使用上面的循环，乐观地删除元素，然后简单地继续搜索失败（这意味着线程并发删除了匹配的元素）：

class MyCollection<E> {

  private Set<E> underlying = ConcurrentHashMap.newKeySet();

  void add(E elem) {
    underlying.add(elem);
  }

  @Nullable E findAndRemove(Predicate<E> predicate) {
    for (E e : underlying) {
        if (predicate.test(e) && remove(e)) {
          return e;
        }
    }
    return null;
  }   
}

与您的示例代码相比，唯一真正的变化是我们检查了 Set.remove() 的结果，以查看该元素是否 实际上 已删除。对于并发集合，这有效 "safely" - 即，只有实际删除对象的线程才能看到 true，因此只有当元素实际被删除时，该集合才会正确地 return 元素，然后没有其他线程能够 return 该元素。

它应该满足您的所有要求，并且与底层并发映射实现一样好，这在现代 JDK 上是 "very well"。

请注意，使用 Set 意味着不允许出现重复元素。从您的描述中不清楚您是否计划支持重复项，但如果您这样做了，您可以使用基于并发 multimap¹ 构建的相同方法，或者简单地使用 ConcurrentHashMap<E, AtomicInteger>，其中AtomicInteger值是具有相同key的元素个数的引用计数，add和findAndRemove方法操作引用计数².

¹ 然而，在快速搜索中，我找不到明显的并发多图开源实现。请注意，您实际上并不需要具有所有功能的大写 M Multimap 实现 - 您实际上只需要 "some multiset" 能够添加元素、迭代可用元素和 "remove" 一个元素（即减少其在集合中的引用计数）。

² 我实际上掩盖了引用计数实现的一些细节，因为在这种情况下，将引用计数递减为零的线程与任何线程之间可能存在竞争为同一元素调用 add 的线程可能会将引用计数增加到零以上（但该条目已被删除）。这可以避免，但我还没有详细说明，因为尚不清楚是否要支持重复项。

线程安全地从集合中查找和删除对象

Thread-safe find and remove an object from a Collection

java

collections

multithreading

thread-safety

java.util.concurrent