Java：ArrayBlockingQueue与LinkedBlockingQueue的区别

Question

我认为，在大多数情况下，ArrayBlockingQueue 比 LinkedBlockingQueue 性能更好。但是，只有在数组中始终有足够的空间时才是这种情况... 如果它被填满了，就很难预测它是否会表现得那么好，因为它会阻塞试图将数据推入队列的线程...

那么，我的问题是：是否有任何中间实现的 BlockingQueue？比如一个 ArrayListBlockingQueue 或 BucketListBlockingQueue？像是一系列数组，这样队列可以动态增加容量，同时仍然从使用数组中获得合理的效益以最终存储数据？

- Eduardo Bezerra

---

一个数组列表不会提高性能...为什么会呢？而且，你为什么担心性能？你真的遇到问题了吗？你进行过性能分析吗？ - Dariusz

我正在思考内存局部性。如果使用一个跳转到随机内存地址的链表，你很可能会遇到缓存失效和类似的问题。而且，要从内存中获取数据，你必须先获取下一个元素的地址，然后再获取该地址的内容... 而对于数组，你只需要执行 address++ 来获取下一个元素的地址。在数组列表中，你会有一些折衷方案来实现这两种方法... 你觉得呢？ - Eduardo Bezerra

我认为一个数组列表既没有原始集合的优势，你仍然需要分配内存，并且根据数组的大小，它会变得更加碎片化或不那么碎片化。如果你正确地编写基于数组的集合的调整大小算法，你将只需要少量调整大小操作并且迭代非常快。至于内存局部性 - 集合存储对象的引用和这些对象本身可能位于内存中的任何位置，因此你从使用一种集合或另一种集合中也许不会获得任何优势。 - Dariusz

Answer 1

1. LinkedBlockingQueue（LinkedList实现，但不完全是JDK中LinkedList的实现。它使用static inner class Node来维护元素之间的链接）

Constructor for LinkedBlockingQueue
public LinkedBlockingQueue(int capacity) 
{
        if (capacity < = 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        last = head = new Node< E >(null);   // Maintains a underlying linkedlist. ( Use when size is not known )
}

Node 类用于维护链接

static class Node<E> {
    E item;
    Node<E> next;
    Node(E x) { item = x; }
}

2. ArrayBlockingQueue（数组实现）

ArrayBlockingQueue的构造函数

public ArrayBlockingQueue(int capacity, boolean fair) 
{
            if (capacity < = 0)
                throw new IllegalArgumentException();
            this.items = new Object[capacity]; // Maintains a underlying array
            lock = new ReentrantLock(fair);
            notEmpty = lock.newCondition();
            notFull =  lock.newCondition();
}

ArrayBlockingQueue和LinkedBlockingQueue之间最大的区别可以从构造函数中看出，一个使用Array作为基础数据结构，另一个使用LinkedList。

ArrayBlockingQueue使用单锁双条件算法，而LinkedBlockingQueue是“双锁队列”算法的一种变体，它有2个锁和2个条件（takeLock，putLock）。

到目前为止，我已经给出了这两种实现之间的比较。回到最初的问题，类似的问题在并发邮件列表上被问到，在这里Doug Lea谈到了DynamicArrayBlockingQueue，它是Dawid Kurzyniec提供的实现。

- Vipin

---

我在这里看到了一个反对票，如果您不同意这个答案，请提供评论，这样我就可以改进或纠正任何错误的地方。请注意，不要更改原始意思。 - Vipin

更明确地说，ArrayBlockingQueue 使用循环数组作为其底层结构。 - Mike Herasimov

Answer 2

我的两分钱：

首先，这里的关键是你并不真正关心这里的区别，因为即使你使用普通的LinkedBlockingQueue，在传递一些微秒级别的系统时，性能已经足够好了。因此，这里的性能差异并不是很大。

如果您正在编写一个关键任务的高性能系统，并且您正在使用队列在线程之间传递消息，您可以通过 [队列大小] = [最大可接受延迟] * [最大消息速率] 来估计所需的队列大小。任何超出此容量的内容都意味着您遭受了缓慢消费者问题。在关键任务应用程序中，这样的延迟意味着您的系统出现故障。可能需要一些手动流程来确保系统正常运行。

如果您的系统不是关键任务，您可以简单地暂停（阻塞）发布者，直到有一些消费者可用。

- Alex Suo