Java 集合 (19) -- 阻塞队列之 LinkedBlockingQueue 类

1. 简介

public class LinkedBlockingQueue<E> extends AbstractQueue<E>implements BlockingQueue<E>, java.io.Serializable {
    }

LinkedBlockingQueue 是 JUC 包下一个以单链表实现的阻塞队列，它是线程安全的；它通过采用两把锁的锁分离技术来实现入队 、出队互不阻塞；它是无界阻塞队列，但可以指定上限，不传入容量时默认为最大整型值，即 2^31 - 1，但是为了避免队列过大造成机器负载或者内存爆满的情况出现，我们在使用的时候建议手动传一个队列的大小。

LinkedBlockingQueue 与 ArrayBlockingQueue 的对比？

1. 后者入队出队采用一把锁，导致入队出队相互阻塞，效率低下；
2. 前者入队出队采用两把锁，入队出队互不干扰，效率较高；
3. 队列大小有所不同，ArrayBlockingQueue是有界的初始化必须指定大小，而LinkedBlockingQueue可以是有界的也可以是无界的(Integer.MAX_VALUE)，对于后者而言，当添加速度大于移除速度时，在无界的情况下，可能会造成内存溢出等问题；(LinkedBlockingQueue 是一个有上限的无界阻塞队列，我们可以把它看做是一个有界阻塞队列，而且我们使用时，是推荐指定其上限的)
4. 数据存储容器不同，ArrayBlockingQueue采用的是数组作为数据存储容器，而LinkedBlockingQueue采用的则是以Node节点作为连接对象的链表；
5. 由于ArrayBlockingQueue采用的是数组的存储容器，因此在插入或删除元素时不会产生或销毁任何额外的对象实例，而LinkedBlockingQueue则会生成一个额外的Node对象。这可能在长时间内需要高效并发地处理大批量数据的时，对于GC可能存在较大影响。

2. 继承体系

3. 字段

// 容量
private final int capacity;// 元素数量
private final AtomicInteger count = new AtomicInteger();// 链表头
transient Node<E> head;// 链表尾
private transient Node<E> last;// take锁，入队、出队使用两个不同的锁控制，锁分离，提高效率
private final ReentrantLock takeLock = new ReentrantLock();// notEmpty条件
// 当队列无元素时，take锁会阻塞在notEmpty条件上，等待其它线程唤醒
private final Condition notEmpty = takeLock.newCondition();// 放锁，入队、出队使用两个不同的锁控制，锁分离，提高效率
private final ReentrantLock putLock = new ReentrantLock();// notFull条件
// 当队列满了时，put锁会会阻塞在notFull上，等待其它线程唤醒
private final Condition notFull = putLock.newCondition();

4. 内部类

//典型的单链表结构
static class Node<E> {
    E item;Node<E> next;Node(E x) {
     item = x; }
}

5. 构造器

1. 如果没传容量，就使用最大int值初始化其容量

   public LinkedBlockingQueue() {
         this(Integer.MAX_VALUE);
   }
   

2. 指定容量

   public LinkedBlockingQueue(int capacity) {
         if (capacity <= 0) throw new IllegalArgumentException();this.capacity = capacity;// 初始化head和last指针为空值节点last = head = new Node<E>(null);
   }
   

6. 常用方法

1. public void put(E e) throws InterruptedException：添加元素到末尾，当没有空间时会阻塞等待，大致的流程：使用putLock加锁；如果队列满了就阻塞在notFull条件上；否则就入队；如果入队后元素数量小于容量，唤醒其它阻塞在notFull条件上的线程；释放锁；如果放元素之前队列长度为0，就唤醒notEmpty条件。
2. public E take() throws InterruptedException：去除队首元素，当没有元素时会阻塞等待，大致的流程：使用takeLock加锁；如果队列空了就阻塞在notEmpty条件上；否则就出队；如果出队前元素数量大于1，唤醒其它阻塞在notEmpty条件上的线程；释放锁；如果取元素之前队列长度等于容量，就唤醒notFull条件；
3. public boolean offer(E e)：入队，当队列没有可用空间的时候，不同于put方法的阻塞等待，offer方法直接方法false
4. public boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException：该方法只是对offer方法进行了阻塞超时处理
5. public E poll()：同上理
6. public poll(long timeout, TimeUnit unit) throws InterruptedException：同上理
7. public E peek()：加锁后，获取到head节点的next节点，如果为空返回null，如果不为空，返回next节点的item值
8. public boolean remove(Object o)：因为remove方法使用两个锁全部上锁，所以其他操作都需要等待它完成，而该方法需要从head节点遍历到尾节点，所以时间复杂度为O(n)