4

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

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

据我所知，唯一合适的 impl 是CopyOnWriteArraySet，但它在文档中指出：

可变操作（添加、设置、删除等）代价高昂，因为它们通常需要复制整个底层数组。

就我而言，我有很多插入到队列末尾（集合）和很多从队列头部删除（和读取）。那么，有什么推荐吗？

4

1 回答 1

6

以下解决方案在移除时存在竞争条件。它的行为也与标准 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()方法本质上是一种比较和交换。因此，在添加到队列之前，请确保地图中没有任何内容，并且在从队列中移除之前不要从地图中移除。

remove 的竞争条件是从队列中删除项目和从地图中删除它之间有一段时间。在那段时间里，添加将失败，因为它仍然认为该项目在队列中。

这是 imo 一个相对较小的比赛条件。一个远不如从队列中删除项目和实际使用该项目之间的时间间隔重要。

于 2011-08-17T17:47:49.467 回答