列表上的集合Java并发队列效率

Question

我正在阅读Brian Goetz等人在第5章中所著的《Java并发实践》

"The Queue classes were added because eliminating the random-access requirements of List admits more efficient concurrent implementations".

有人能解释一下这是什么意思吗

Answer 1

提及的随机访问要求与以下操作有关：

• T get(int)
• void add(int, T)
• int indexOf(T)
• 等等

问题在于，更新列表时，列表中元素的位置可能会发生变化。例如，如果我写下：

int pos = list.indexOf("fred");
list.add(pos, "jim");

在多线程应用程序中，其他线程可能会更新列表，那么我需要同步操作序列

synchronized (list) {
    int pos = list.indexOf("fred");
    list.add(pos, "jim");
}

注意indexOf和add操作通常都是O（N）操作，如果列表很长，这可能会导致列表被长时间锁定¹。如果其他线程同时需要访问该列表，它们将被阻止

相比之下，队列API不支持随机访问操作，并发队列不需要锁定太长时间。这意味着更少的阻塞。。。以及更好的吞吐量

---

^{1-即使。。。假设。。。您有一个“并发”列表类，其中单个操作不会长时间阻止其他线程}