Java LinkedBlockingQueue的链表结构优势
Java LinkedBlockingQueue概述
在Java并发编程领域，LinkedBlockingQueue是一个重要的类，它位于java.util.concurrent包下。LinkedBlockingQueue是一个基于链表结构的有界阻塞队列，其内部实现采用链表来存储元素，这使得它在处理高并发场景下的元素插入和删除操作时，展现出独特的优势。
LinkedBlockingQueue提供了线程安全的队列操作，它的设计目的是为了在多线程环境下高效地处理任务队列。该队列按照FIFO（先进先出）的原则对元素进行排序，新元素会被插入到队列的尾部，而从队列头部获取并移除元素。
链表结构基础
链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的引用（在双向链表中还包含指向前一个节点的引用）。与数组不同，链表的内存分配是动态的，不需要预先分配连续的内存空间。这使得链表在插入和删除元素时具有更高的灵活性，因为不需要移动大量元素，只需要调整节点之间的引用关系。
在LinkedBlockingQueue中，使用的是双向链表结构。双向链表的每个节点包含三个部分：存储的数据、指向前一个节点的引用（prev）和指向后一个节点的引用（next）。这种结构允许在队列的两端进行高效的插入和删除操作。
LinkedBlockingQueue的链表结构优势
内存动态分配与灵活性
-
动态内存分配：与数组相比，数组在创建时需要指定固定的大小，这意味着如果在运行时需要扩展数组的容量，可能需要进行复杂的内存复制操作。而
LinkedBlockingQueue的链表结构在运行时动态分配内存，每当有新元素加入队列时，就创建一个新的节点，不需要预先分配大量的连续内存空间。这种动态分配机制使得LinkedBlockingQueue在处理元素数量不确定的场景时更加高效和灵活。 -
灵活性：链表结构允许在队列的任意位置插入和删除元素（虽然
LinkedBlockingQueue主要在两端操作，但链表的特性决定了它理论上可以在任意位置操作）。在LinkedBlockingQueue中，插入元素到队列尾部（offer方法）和从队列头部移除元素（poll方法）只需要修改少数几个节点的引用关系，而不需要像数组那样移动大量元素。例如，当使用数组实现队列时，如果队列已满且需要添加新元素，可能需要重新分配一个更大的数组，并将原数组中的元素复制到新数组中，这是一个相对耗时的操作。而LinkedBlockingQueue的链表结构则不存在这样的问题，它可以轻松地动态添加新节点来容纳新元素。
高效的插入和删除操作
- 队列头部操作：从队列头部移除元素（
poll方法）时，LinkedBlockingQueue的链表结构只需要将头节点的next引用指向原头节点的下一个节点，并将原头节点的next引用置为null（以便垃圾回收）。在双向链表中，还需要将新头节点的prev引用置为null。这个过程的时间复杂度为O(1)，因为无论队列中有多少个元素，移除头节点的操作始终只涉及到少数几个引用的修改。例如：
public E poll() {
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();
try {
if (count == 0)
return null;
E x = dequeue();
if (itrs != null)
itrs.elementDequeued();
return x;
} finally {
takeLock.unlock();
}
}
private E dequeue() {
// assert takeLock.isHeldByCurrentThread();
// assert head.item == null;
Node<E> h = head;
Node<E> first = h.next;
h.next = h; // help GC
head = first;
E x = first.item;
first.item = null;
first.prev = null;
--count;
return x;
}
- 队列尾部操作：插入元素到队列尾部（
offer方法）时，同样只需要修改少数几个引用。在双向链表中，创建一个新节点，将原尾节点的next引用指向新节点，新节点的prev引用指向原尾节点，然后将尾节点更新为新节点。这个操作的时间复杂度也是O(1)。例如：
public boolean offer(E e) {
if (e == null) throw new NullPointerException();
final AtomicInteger count = this.count;
if (count.get() == capacity)
return false;
int c = -1;
Node<E> node = new Node<E>(e);
final ReentrantLock putLock = this.putLock;
putLock.lock();
try {
if (count.get() < capacity) {
enqueue(node);
c = count.getAndIncrement();
if (c + 1 < capacity)
notFull.signal();
}
} finally {
putLock.unlock();
}
if (c == 0)
signalNotEmpty();
return c >= 0;
}
private void enqueue(Node<E> node) {
// assert putLock.isHeldByCurrentThread();
// assert last.next == null;
last = last.next = node;
}
支持高并发操作
- 锁分离：
LinkedBlockingQueue采用了锁分离技术，通过使用两把锁（putLock和takeLock）分别控制插入和移除操作。这意味着在高并发场景下，插入操作和移除操作可以同时进行，只要它们不竞争同一把锁。例如，一个线程可以在执行offer方法（使用putLock）的同时，另一个线程执行poll方法（使用takeLock），而不会相互阻塞。这种锁分离机制大大提高了队列在多线程环境下的并发性能。
private final ReentrantLock putLock = new ReentrantLock();
private final Condition notFull = putLock.newCondition();
private final ReentrantLock takeLock = new ReentrantLock();
private final Condition notEmpty = takeLock.newCondition();
- 原子性操作：在
LinkedBlockingQueue中，涉及到队列元素数量的操作（如count的增减）使用了AtomicInteger类型。AtomicInteger提供了原子性的自增和自减操作，这保证了在多线程环境下，对队列元素数量的统计是准确的，并且不会出现竞态条件。例如，在offer方法中，使用count.getAndIncrement()来原子性地增加队列元素数量，确保在多线程并发调用offer方法时，count的更新是正确的。
内存管理优势
- 垃圾回收友好：由于
LinkedBlockingQueue的链表结构采用动态内存分配，当节点从队列中移除（例如通过poll方法）时，该节点所占用的内存可以很快被垃圾回收器回收。因为节点的引用关系被调整，不再有其他对象持有对该节点的强引用，垃圾回收器可以在适当的时候将其回收。这与数组实现的队列不同，数组即使元素被移除，数组本身所占用的内存可能仍然不会被释放，除非整个数组对象不再被引用。 - 减少内存碎片：链表结构在内存分配上相对灵活，不会像数组那样在频繁的插入和删除操作后产生大量的内存碎片。数组在删除元素后，可能会在数组中间留下空洞，而后续的插入操作可能无法有效地利用这些空洞，导致内存碎片的产生。而链表的节点是独立分配内存的，插入和删除操作只会影响相邻节点的引用关系，不会产生内存碎片问题。
与其他队列结构对比
与数组队列对比
- 固定容量与动态容量：数组队列在创建时需要指定固定的容量，如果在运行时需要扩展容量，可能需要进行复杂的数组复制操作。例如，
ArrayDeque在容量不足时会进行翻倍扩容，这个过程需要创建一个新的更大的数组，并将原数组中的元素复制到新数组中，这是一个相对耗时的操作。而LinkedBlockingQueue的链表结构可以动态分配内存，不需要预先指定容量（虽然它也可以设置有界容量），在处理元素数量不确定的场景时更加灵活。 - 插入和删除效率：数组队列在插入和删除元素时，可能需要移动大量元素，尤其是在队列头部或中间插入和删除元素时。例如，在
ArrayList中，如果要在头部插入元素，需要将后面的所有元素向后移动一位，时间复杂度为O(n)。而LinkedBlockingQueue的链表结构在队列头部和尾部插入和删除元素的时间复杂度均为O(1)，这使得它在高并发场景下处理频繁的插入和删除操作时效率更高。
与优先队列对比
- 排序方式：优先队列（如
PriorityQueue）根据元素的自然顺序或自定义比较器对元素进行排序，元素从队列中取出的顺序是按照优先级来的，而不是FIFO顺序。LinkedBlockingQueue则始终按照FIFO顺序处理元素，新元素插入到队列尾部，从队列头部获取元素。这使得LinkedBlockingQueue在处理需要按照顺序处理任务的场景时更加适用，例如生产者 - 消费者模型中，任务需要按照提交的顺序依次处理。 - 数据结构与性能：
PriorityQueue通常使用堆数据结构来实现，插入和删除操作的时间复杂度为O(log n)，其中n是队列中的元素数量。而LinkedBlockingQueue的链表结构在插入和删除操作上具有O(1)的时间复杂度（在队列两端操作），这使得它在处理大量元素的频繁插入和删除时性能更优。
代码示例
简单的生产者 - 消费者模型
import java.util.concurrent.LinkedBlockingQueue;
public class ProducerConsumerExample {
private static final int QUEUE_CAPACITY = 5;
private static final LinkedBlockingQueue<Integer> queue = new LinkedBlockingQueue<>(QUEUE_CAPACITY);
public static void main(String[] args) {
Thread producerThread = new Thread(new Producer());
Thread consumerThread = new Thread(new Consumer());
producerThread.start();
consumerThread.start();
try {
producerThread.join();
consumerThread.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
static class Producer implements Runnable {
@Override
public void run() {
for (int i = 0; i < 10; i++) {
try {
System.out.println("Producing: " + i);
queue.put(i);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
static class Consumer implements Runnable {
@Override
public void run() {
while (true) {
try {
Integer value = queue.take();
System.out.println("Consuming: " + value);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
在这个示例中，Producer线程不断向LinkedBlockingQueue中插入数据，Consumer线程从队列中取出数据并处理。LinkedBlockingQueue的链表结构保证了在多线程环境下高效的插入和删除操作，并且通过put和take方法实现了线程安全的阻塞操作。当队列满时，producer线程会被阻塞，直到队列有空间；当队列空时，consumer线程会被阻塞，直到队列有数据。
多生产者 - 多消费者模型
import java.util.concurrent.LinkedBlockingQueue;
public class MultiProducerConsumerExample {
private static final int QUEUE_CAPACITY = 5;
private static final LinkedBlockingQueue<Integer> queue = new LinkedBlockingQueue<>(QUEUE_CAPACITY);
public static void main(String[] args) {
Thread producer1 = new Thread(new Producer(1));
Thread producer2 = new Thread(new Producer(2));
Thread consumer1 = new Thread(new Consumer(1));
Thread consumer2 = new Thread(new Consumer(2));
producer1.start();
producer2.start();
consumer1.start();
consumer2.start();
try {
producer1.join();
producer2.join();
consumer1.join();
consumer2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
static class Producer implements Runnable {
private final int id;
Producer(int id) {
this.id = id;
}
@Override
public void run() {
for (int i = 0; i < 10; i++) {
try {
System.out.println("Producer " + id + " producing: " + i);
queue.put(i);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
static class Consumer implements Runnable {
private final int id;
Consumer(int id) {
this.id = id;
}
@Override
public void run() {
while (true) {
try {
Integer value = queue.take();
System.out.println("Consumer " + id + " consuming: " + value);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
这个示例展示了多生产者和多消费者同时操作LinkedBlockingQueue的场景。多个生产者线程可以同时向队列中插入数据，多个消费者线程可以同时从队列中取出数据。LinkedBlockingQueue的链表结构和线程安全机制保证了在这种高并发场景下的正确运行，并且链表结构的优势使得插入和删除操作能够高效地执行。
总结
LinkedBlockingQueue的链表结构在Java并发编程中具有显著的优势。它的动态内存分配和灵活性使得在处理元素数量不确定的场景时更加高效，高效的插入和删除操作以及锁分离技术使其在高并发环境下表现出色。与其他队列结构相比，它在内存管理和操作效率上都有独特的优势。通过实际的代码示例，我们可以看到LinkedBlockingQueue在生产者 - 消费者模型等多线程场景中的应用，充分体现了其链表结构的优势。在实际的项目开发中，当需要处理高并发的任务队列，并且对插入和删除操作的效率有较高要求时，LinkedBlockingQueue是一个非常不错的选择。