Java中是否有一个并发的循环链队列集合？

Question

我需要以循环并发的方式从队列中获取数据。我正在寻找一个实现这种行为的集合。经过一些搜索，我找不到一个合适的集合。我该如何实现呢？ 我看了ConcurrentLinkedQueue，但我不确定如何使它成为循环的。我需要这个集合的性能非常高。

我猜我可以使用ConcurrentLinkedDeque来完成。通过使用迭代器，我应该能够迭代到最后，一旦到达末尾，我就可以重新创建我的迭代器并从开头开始。

=============================更新===========================

在初始化阶段，多个线程将向此类集合添加元素。并发集合的状态将对将逐个从中消耗一个项目的使用者线程正确可见。一旦应用程序处于运行状态，将不会向集合添加元素。每个线程按循环方式迭代和消耗一个元素。

- Ihor M.

---

为什么它必须是循环的？ - Martin'sRun

那是一个要求。 - Ihor M.

你所描述的不是一个队列。既然不是，你需要更清楚地解释所需的行为。新元素是否被添加？旧元素是否被删除？如果元素被添加/删除，这如何影响轮询获取的过程？ - Stephen C

此外，我怀疑这里可能存在一些“早期优化”。您是否有任何确凿证据表明集合需要具有高性能/集合很可能会存在争用？ - Stephen C

@StephenC 请看一下我的更新 - Ihor M.

Answer 1

根据你修改后的问题，这是我建议的方法：

在初始化阶段，使用并发的Queue或Deque来积累元素。任何实现都可以。

一旦该阶段完成，从队列对象创建以下RoundRobin类的实例，并使用其get方法循环遍历其元素。

public class RoundRobin <E> {
    private final AtomicInteger next = new AtomicInteger(0);
    private final E[] elements;

    public RoundRobin(Collection<E> queue, Class<E> clazz) {
        this.elements = queue.toArray(Array.newInstance(clazz, 0));
    }

    public E get() {
        return elements[next.getAndIncrement() % elements.length];
    }
}

RoundRobin 类是线程安全的，get 方法可以并发执行。

如果在构建 RoundRobin 时更改了 elements 集合，则得到的 RoundRobin 状态可能与 queue 的最终状态不同。根据您所述的要求，这是可以接受的。

- Stephen C

---

好，但是当一个元素实际上被添加到队列中时，我必须重新创建RoundRobin。我知道，我说过有初始化阶段，在这个阶段大多数元素会被添加，但也有可能有一些元素不会在初始化阶段被添加。这让我想到了CopyOnWriteArrayList是否更适合。你认为建议的ConcurrentLinkedDeque实现怎么样？ - Ihor M.

我设计了“RoundRobin”，基于只需要创建一次的假设。对于你的提议，我没有任何评论。最佳方法将取决于需求，而这些需求会不断变化。 - Stephen C

你是正确的，你的答案基于问题中所述的要求。 - Ihor M.

Answer 2

您所描述的内容与链表相符，而不是队列或双端队列。使用链表，您可以将最后一个元素的“下一个”节点指向第一个元素。但是，在查看 LinkedList的Javadoc时，没有办法更改最后一个元素指向的位置。

请注意，如果有办法，您可以通过调用 Collections.synchronizedList（）来创建该数据结构的同步视图，如下所示：

List<String> list = Collections.synchronizedList(new LinkedList<>());

对于标准的Java API，我认为您无法实现您想要的功能。一个选项是实现自己的数据结构，该结构扩展了List并允许您更改每个节点指向的位置，从而可以使其成为循环结构。然后使用Collections.synchronizedList()来创建线程安全的视图。

请注意，Collections.synchronizedList()的Javadoc说：“当迭代它时，必须手动在返回的列表上同步”，并包括以下示例：

List list = Collections.synchronizedList(new ArrayList());
    ...
synchronized (list) {
    Iterator i = list.iterator(); // Must be in synchronized block
    while (i.hasNext())
        foo(i.next());
}

- Kaan

---

我知道这些都不太合适，但ConcurrentLinkedDeque看起来像是一个赢家。相比于同步集合，它们更慢。并发类更具性能，因为它们阻塞较少。 - Ihor M.

并发类更高效，但您的使用情况是否实际需要额外的性能？也许需要。使用ConcurrentLinkedDeque和重复迭代器可以工作，但每次创建新迭代器都有成本-无论您的性能标准是什么，您都需要考虑到这一点。我认为没有任何满足您要求的所有要求的好选择，因此您需要做出最适合的权衡。另一个想法：最好获得正确的、可工作的版本，然后在需要更快时进行分析和加速。 - Kaan