寻找java.util.Set的无限的,基于队列的并发实现

Question

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

1. 应该并发无法同步锁定; 所以很明显我不想使用Collections.synchronizedSet().
2. 应该保持插入顺序.所以ConcurrentSkipListSet不是首选,因为它使用compareTo()作为equals(),并且需要提供Comparable或Comparator的实现.还有一个ConcurrentLinkedHashMap,尽管有LinkedHashMap,但它不保持插入顺序.
3. 应该是无限的.
4. 建议使用FIFO链表,因为我的操作只对队列的第一个元素进行.

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

变异操作(添加,设置,删除等)很昂贵,因为它们通常需要复制整个底层阵列.

在我的情况下,我有很多插入到队列末尾(set)和批量从队列的头部删除(和读取).那么,有什么建议吗？

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()方法基本上是比较和交换.因此,在添加到队列之前,确保地图中没有任何内容,并且在从队列中删除之前不会从地图中删除.

删除时的竞争条件是从队列中删除项目并将其从地图中删除之间有一段时间.在那段时间内,add会失败,因为它仍然认为该项目在队列中.

这是一个相对较小的竞争条件.一个远远不如从队列中删除项目和实际对该项目执行某些操作之间的时间差距.