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

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 是不相关的，因为它删除了 所有 匹配元素并且不返回任何内容
• 假设同步不够好
• CopyOnWriteArrayList 可能会，但 Javadoc 说“高效时……遍历操作远远超过突变”，这在这里绝对不是真的
• 不允许返回同一个元素两次(除非在此期间重新添加)，这在天真地使用CopyOnWriteArrayList时很容易发生
• 返回哪个匹配元素并不重要

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

Answer 1

因为您只需要 add和 findAndRemove方法，某种类型的并发哈希是一个自然的选择，因为自 Java 1.5 以来就有了一个很好的实现(ConcurrentHashMap)。现在因为我们实际上并不需要 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() 的结果。查看该元素是否被实际 删除。对于并发集，这“安全”地工作——即只有实际删除对象的线程才能看到 true。 ，所以这个集合只有在元素被实际移除时才会正确返回该元素，然后没有其他线程能够返回该元素。

它应该满足您的所有要求，并与底层并发映射实现一样好，这在现代 JDK 上“非常好”。

注意使用 Set暗示不允许重复元素。从你的描述中不清楚你是否计划支持重复，但如果你这样做了，你可以使用构建在并发多图¹ 上的相同方法，或者简单地使用 ConcurrentHashMap<E, AtomicInteger> , 其中AtomicInteger value 具有相同键的元素数量的引用计数，add和 findAndRemove方法操纵引用计数²。

---

¹ 然而，在快速搜索中，我找不到明显的并发多图开源实现。请注意，您实际上并不需要大写字母 M Multimap具有所有功能的实现——你真的只需要“一些多重集”能够添加一个元素，迭代可用元素，以及“删除”一个元素(即减少它在集合中的引用计数)。

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