ArrayBlockingQueue和LinkedBlockingQueue有什么区别？

Question

1. 在哪些场景中最好使用ArrayBlockingQueue？什么时候使用LinkedBlockingQueue更好？
2. 如果LinkedBlockingQueue的默认容量等于MAX Integer，那么将其用作具有默认容量的BlockingQueue是否真的有所帮助？

- Java_Jack

---

对于第一点，我猜想原因与 ArrayList vs LinkedList 相同 ;) - sp00m

BlockingQueue 不仅在 put() 上阻塞，当队列为空时，在 take() 上也会阻塞。 - JB Nizet

@sp00m 但是在队列中，我们没有中间插入或删除。因此，在ArrayList和LinkedList的情况下，性能问题是不存在的。 - Java_Jack

@user2375176 我认为如果你可以估计你的队列大小，那么ArrayBlockingQueue更好。但是，如果添加速度变得很快，它将会被阻塞并减少对象的通过。 - Burak Keceli

@JBNizet 实际上，您可以在基于数组的实现中使用起始和结束偏移量进行工作。当起始偏移量大于结束偏移量时，元素必须读取环绕数组边界。因此，在前面插入元素可以通过将其存储在数组末尾并调整起始偏移量而无需进行移位来完成。 - Fabian Barney

Answer 1

ArrayBlockingQueue使用不会改变大小的数组作为后端。将容量设置为Integer.MAX_VALUE将创建一个非常大的数组，占用很高的空间成本。 ArrayBlockingQueue总是有界的。

LinkedBlockingQueue在达到capacity之前动态创建节点。默认情况下，这个值为Integer.MAX_VALUE。使用这样一个大容量没有额外的空间成本。 LinkedBlockingQueue可选地是有界的。

- Fabian Barney

Answer 2

ArrayBlockingQueue :

ArrayBlockingQueue是一个有界的、阻塞队列，它在内部使用数组存储元素。由于它是有界的，意味着它不能无限制地存储元素。它同时只能存储一定数量的元素，这个上限在初始化时设置，并且不能更改。

LinkedBlockingQueue

LinkedBlockingQueue将元素在其内部使用链式结构进行存储（链接节点）。如果需要，该链式结构可以选择具有上限。如果未指定上限，则使用Integer.MAX_VALUE作为上限。

相似之处

ArrayBlockingQueue/LinkedBlockingQueue以FIFO（先进先出）的顺序在内部存储元素。队列的头部是在队列中停留时间最长的元素，而队列的尾部是在队列中停留时间最短的元素。

区别

• 对于插入和删除操作，LinkedBlockingQueue分别使用putLock和takeLock两个锁，而ArrayBlockingQueue则只使用1个锁。
• ArrayBlockingQueue使用单锁双条件算法，而LinkedBlockingQueue是“双锁队列”算法的变体，它具有2个锁和2个条件（takeLock、putLock）。

LinkedBlockingQueue实现使用的是“双锁队列”算法。因此，LinkedBlockingQueue的take和put可以并发工作，但ArrayBlockingQueue不行。使用单锁的原因在于ArrayBlockingQueue需要避免覆盖条目，因此需要知道开始和结束位置。LinkedBlockQueue不需要这样做，因为它让GC（垃圾回收机制）负责清理队列中的节点。

- Ramesh Papaganti

Answer 3

ArrayBlockingQueue<E> 和LinkedBlockingQueue<E> 是BlockingQueue<E>接口的常见实现。

ArrayBlockingQueue由数组支持，Queue强制按照FIFO排序。队列头是最老的元素，队列尾是最年轻的元素。ArrayBlockingQueue是一个大小固定的有界缓冲区，而LinkedBlockingQueue是一个基于链表节点的可选有界队列。

可选的容量绑定构造函数参数可以防止过度扩展队列，因为如果未指定容量，则等于Integer.MAX_VALUE。

更多信息请查看这里。

基准测试：http://www.javacodegeeks.com/2010/09/java-best-practices-queue-battle-and.html

- Ankur Lathi

---

我怀疑 LinkedBlockingQueue 是否具有更高的吞吐量。有支持该说法的基准测试吗？ - Esko Luontola

@EskoLuontola: 你可以在这里找到一个基准测试： http://www.javacodegeeks.com/2010/09/java-best-practices-queue-battle-and.html - Ankur Lathi

因此，基于该基准测试，LinkedBlockingQueue 在生产者-消费者场景中更快，但在前两个基准测试中，ArrayBlockingQueue 稍微快一些。不过，无论如何，Disruptor 都比它们都要好：https://code.google.com/p/disruptor/wiki/PerformanceResults - Esko Luontola

Answer 4

向 ArrayBlockingQueue 中添加元素比向 LinkedBlockingQueue 中添加元素快，因为只需要将引用设置为支持对象数组的元素，而向 LinkedBlockingQueue 添加元素则意味着创建一个 Node 并设置其 item、prev 和 next 字段。此外，当我们从 LinkedBlockingQueue 中删除元素时，被删除的 Node 变成垃圾可能会影响应用程序的性能。

至于内存消耗，即使为空，ArrayBlockingQueue 始终保留具有满容量的 Object 数组。另一方面，LinkedBlockingQueue 中的一个元素是具有 3 个对象字段的 Node。

- Evgeniy Dorofeev

---

这是一个很好的回答，解释了原因，但你提到ArrayBlockingQueue应该更快，我同意你的观点。但是Javadocs说：“与基于数组的队列相比，链接队列通常具有更高的吞吐量，但在大多数并发应用程序中性能不太可预测。”请参见LinkedBlockingQueue.class。 - spiderman

延迟和吞吐量是两个不同的概念。ArrayBlockingQueue 的延迟更好，因为在数组中设置引用更快，而 LinkedBlockingQueue 的吞吐量更好，因为它使用了两个不同的锁来进行 put 和 take 操作，并且只在边缘条件上进行同步。 - Amrish Pandey