寻找一个无界的，基于队列，并实现为java.util.Set

的

我正在寻找java.util.Set中的实现，具有以下特点：寻找一个无界的，基于队列，并实现为java.util.Set

绝不应该是并行的同步锁定;所以很明显，我不想使用Collections.synchronizedSet（）。
应保持广告订单。所以ConcurrentSkipListSet并不可取，因为它使用compareTo（）作为equals（），并且要求提供Comparable或Comparator的实现。还有一个ConcurrentLinkedHashMap尽管是LinkedHashMap，但不保留广告订单。
应该是无界的。
建议使用FIFO链表，因为我的操作只对队列的第一个元素完成。

至于我能找到的唯一正确IMPL是CopyOnWriteArraySet，但该文件中指出：

可变操作（添加，设置，删除，等），因为它们价格昂贵通常需要复制整个底层阵列。

在我的情况下，我有很多插入到队列（集合）结束和很多从队列头部删除（和读取）。那么，有什么建议？

来源

2011-08-17 Mohsen

我想你可能不得不实施你自己的。 –

“保持插入顺序”听起来不像集合。你确定你想要一个Set而不是一个Queue吗？ –

嗯，这不是一个普遍的需求吗？ – Mohsen

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

但是，它使用标准的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()本质上是一个比较和交换。因此，在添加到队列中之前，请确保在地图中没有任何内容，并且在从队列中移除之前不要从地图中删除。

删除时的竞争条件是，将项目从队列中移出并将其从地图中删除后会有一段时间。在那段时间内，添加会失败，因为它仍然认为该项目在队列中。

这是一个相对较小的竞争条件。从远离队列的项目到实际执行项目之间的时间差距远没有那么重要。

来源

2011-08-17 17:47:49 parsifal

这两种方法都需要锁定。 – Mohsen

@Mohsen - 你是说当前代码需要添加锁，还是你在谈论ConcurrentHashMap和ConcurrentLinkedQueue中固有的锁？如果前者，答案是否定的。如果是后者，答案是“祝你好运”。 – parsifal

对不起，你是对的。调用put-add和remove-remove的顺序是有用的。我正在谈论你的两种方法的锁。顺便说一句，你能解释更多关于removeFirst方法的竞争条件。它何时发生？ – Mohsen

寻找一个无界的，基于队列，并实现为java.util.Set

回答

相关问题