java - 寻找 java.util.Set 的无界、基于队列的并发实现

Question

我正在寻找具有以下特性的 java.util.Set 的实现:

1. 应该是并发的而不是同步锁；所以很明显我不想使用 Collections.synchronizedSet ().
2. 应保持广告顺序。所以 ConcurrentSkipListSet 不是可取的，因为它使用 compareTo() 作为 equals()，并且需要提供 Comparable 或 Comparator 的实现。还有一个ConcurrentLinkedHashMap尽管有 LinkedHashMap，但它不保持插入顺序。
3. 应该是无界的。
4. 推荐使用 FIFO 链表，因为我的操作只对队列的第一个元素进行。

据我所知，唯一正确的含义是 CopyOnWriteArraySet ，但它在文档中指出:

Mutative operations (add, set, remove, etc.) are expensive since they usually entail copying the entire underlying array.

在我的例子中，我有很多插入队列(集合)的末尾和很多从队列头部删除(和读取)的操作。那么，有什么建议吗？

Answer 1

以下解决方案在移除时存在竞争条件。它的行为也与标准 JDK Set 实现有些不同。

但是，它使用标准的 JDK 对象，并且是一个简单的实现。只有您可以决定这种竞争条件是否可以接受，或者您是否愿意花时间寻找/实现没有竞争的解决方案。

public class FifoSet<T>
{
    private ConcurrentHashMap<T,T> _map;
    private ConcurrentLinkedQueue<T> _queue;

    public void add(T obj)
    {
       if (_map.put(obj,obj) != null)
          return;
       _queue.add(obj);
    }

    public T removeFirst()
    {
       T obj = _queue.remove();
       _map.remove(obj);
       return obj;
    }
}

更多解释:ConcurrentHashMap 仅作为 ConcurrentLinkedList 的守卫存在；它的 put() 方法本质上是一个比较和交换。因此，您要确保在添加到队列之前 map 中没有任何内容，并且在从队列中删除之前不要从 map 中删除。

移除时的竞争条件是从队列中移除项目和将其从 map 中移除之间存在时间空间。在那段时间内，add 将失败，因为它仍然认为该项目在队列中。

我认为这是一个相对较小的竞争条件。一个远不如从队列中删除项目和实际处理该项目之间的时间间隔重要。