13518219792
网站建设资讯

NEWS

网站建设资讯

面试侃集合|LinkedBlockingQueue篇

面试官：好了，聊完了ArrayBlockingQueue，我们接着说说LinkedBlockingQueue吧

Hydra：还真是不给人喘口气的机会，LinkedBlockingQueue是一个基于链表的阻塞队列，内部是由节点Node构成，每个被加入队列的元素都会被封装成下面的Node节点，并且节点中有指向下一个元素的指针：

成都创新互联公司专注为客户提供全方位的互联网综合服务，包含不限于成都网站设计、网站建设、北镇网络推广、成都小程序开发、北镇网络营销、北镇企业策划、北镇品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；成都创新互联公司为所有大学生创业者提供北镇建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

 
 
 
 
    
  
  
  
  
  1. static class Node { 
    2.   
  
  
  
  2.     E item; 
    3.   
  
  
  
  3.     Node next; 
    4.   
  
  
  
  4.     Node(E x) { item = x; } 
    5.   
  
  
  
  5. } 
    6.

LinkedBlockingQueue中的关键属性有下面这些：

 
 
 
 
    
  
  
  
  
  1. private final int capacity;//队列容量 
    2.   
  
  
  
  2. private final AtomicInteger count = new AtomicInteger();//队列中元素数量 
    3.   
  
  
  
  3. transient Node head;//头节点 
    4.   
  
  
  
  4. private transient Node last;//尾节点 
    5.   
  
  
  
  5. //出队锁 
    6.   
  
  
  
  6. private final ReentrantLock takeLock = new ReentrantLock(); 
    7.   
  
  
  
  7. //出队的等待条件对象 
    8.   
  
  
  
  8. private final Condition notEmpty = takeLock.newCondition(); 
    9.   
  
  
  
  9. //入队锁 
    10.   
  
  
  
  10. private final ReentrantLock putLock = new ReentrantLock(); 
    11.   
  
  
  
  11. //入队的等待条件对象 
    12.   
  
  
  
  12. private final Condition notFull = putLock.newCondition(); 
    13.

构造函数分为指定队列长度和不指定队列长度两种，不指定时队列最大长度是int的最大值。当然了，你要是真存这么多的元素，很有可能会引起内存溢出：

 
 
 
 
    
  
  
  
  
  1. public LinkedBlockingQueue() { 
    2.   
  
  
  
  2.     this(Integer.MAX_VALUE); 
    3.   
  
  
  
  3. } 
    4.   
  
  
  
  4. public LinkedBlockingQueue(int capacity) { 
    5.   
  
  
  
  5.     if (capacity <= 0) throw new IllegalArgumentException(); 
    6.   
  
  
  
  6.     this.capacity = capacity; 
    7.   
  
  
  
  7.     last = head = new Node(null); 
    8.   
  
  
  
  8. }  
    9.

还有另一种在初始化时就可以将集合作为参数传入的构造方法，实现非常好理解，只是循环调用了后面会讲到的enqueue入队方法，这里暂且略过。

在LinkedBlockingQueue中，队列的头结点head是不存元素的，它的item是null，next指向的元素才是真正的第一个元素，它也有两个用于阻塞等待的Condition条件对象。与之前的ArrayBlockingQueue不同，这里出队和入队使用了不同的锁takeLock和putLock。队列的结构是这样的：

面试官：为什么要使用两把锁，之前ArrayBlockingQueue使用一把锁，不是也可以保证线程的安全么?

Hydra：使用两把锁，可以保证元素的插入和删除并不互斥，从而能够同时进行，达到提高吞吐量的的效果

面试官：嗯，那还是老规矩，先说插入方法是怎么实现的吧

Hydra：这次就不提父类AbstractQueue的add方法了，反正它调用的也是子类的插入方法offer，我们就直接来看offer方法的源码：

 
 
 
 
    
  
  
  
  
  1. public boolean offer(E e) { 
    2.   
  
  
  
  2.     if (e == null) throw new NullPointerException(); 
    3.   
  
  
  
  3.     final AtomicInteger count = this.count;//队列中元素个数 
    4.   
  
  
  
  4.     if (count.get() == capacity)//已满 
    5.   
  
  
  
  5.         return false; 
    6.   
  
  
  
  6.     int c = -1; 
    7.   
  
  
  
  7.     Node node = new Node(e); 
    8.   
  
  
  
  8.     final ReentrantLock putLock = this.putLock; 
    9.   
  
  
  
  9.     putLock.lock(); 
    10.   
  
  
  
  10.     try { 
    11.   
  
  
  
  11.         //并发情况，再次判断队列是否已满 
    12.   
  
  
  
  12.         if (count.get() < capacity) { 
    13.   
  
  
  
  13.             enqueue(node); 
    14.   
  
  
  
  14.             //注意这里获取的是未添加元素前的对列长度 
    15.   
  
  
  
  15.             c = count.getAndIncrement(); 
    16.   
  
  
  
  16.             if (c + 1 < capacity)//未满 
    17.   
  
  
  
  17.                 notFull.signal(); 
    18.   
  
  
  
  18.         } 
    19.   
  
  
  
  19.     } finally { 
    20.   
  
  
  
  20.         putLock.unlock(); 
    21.   
  
  
  
  21.     } 
    22.   
  
  
  
  22.     if (c == 0) 
    23.   
  
  
  
  23.         signalNotEmpty(); 
    24.   
  
  
  
  24.     return c >= 0; 
    25.   
  
  
  
  25. } 
    26.

offer方法中，首先判断队列是否已满，未满情况下将元素封装成Node对象，尝试获取插入锁，在获取锁后会再进行一次队列已满判断，如果已满则直接释放锁。在持有锁且队列未满的情况下，调用enqueue入队方法。

enqueue方法的实现也非常的简单，将当前尾节点的next指针指向新节点，再把last指向新节点：

 
 
 
 
    
  
  
  
  
  1. private void enqueue(Node node) { 
    2.   
  
  
  
  2.     last = last.next = node; 
    3.   
  
  
  
  3. } 
    4.

画一张图，方便你理解：

在完成入队后，判断队列是否已满，如果未满则调用notFull.signal()，唤醒等待将元素插入队列的线程。

面试官：我记得在ArrayBlockingQueue里插入元素后，是调用的notEmpty.signal()，怎么这里还不一样了?

Hydra：说到这，就不得不再提一下使用两把锁来分别控制插入和获取元素的好处了。在ArrayBlockingQueue中，使用了同一把锁对入队和出队进行控制，那么如果在插入元素后再唤醒插入线程，那么很有可能等待获取元素的线程就一直得不到唤醒，造成等待时间过长。

而在LinkedBlockingQueue中，分别使用了入队锁putLock和出队锁takeLock，插入线程和获取线程是不会互斥的。所以插入线程可以在这里不断的唤醒其他的插入线程，而无需担心是否会使获取线程等待时间过长，从而在一定程度上提高了吞吐量。当然了，因为offer方法是非阻塞的，并不会挂起阻塞线程，所以这里唤醒的是阻塞插入的put方法的线程。

面试官：那接着往下看，为什么要在c等于0的情况下才去唤醒notEmpty中的等待获取元素的线程?

Hydra：其实获取元素的方法和上面插入元素的方法是一个模式的，只要有一个获取线程在执行方法，那么就会不断的通过notEmpty.signal()唤醒其他的获取线程。只有当c等于0时，才证明之前队列中已经没有元素，这时候获取线程才可能会被阻塞，在这个时候才需要被唤醒。上面的这些可以用一张图来说明：

由于我们之前说过，队列中的head节点可以认为是不存储数据的标志性节点，所以可以简单的认为出队时直接取出第二个节点，当然这个过程不是非常的严谨，我会在后面讲解出队的过程中再进行补充说明。

面试官：那么阻塞方法put和它有什么区别?

Hydra：put和offer方法整体思路一致，不同的是加锁是使用的是可被中断的方式，并且当队列中元素已满时，将线程加入notFull等待队列中进行等待，代码中体现在：

 
 
 
 
    
  
  
  
  
  1. while (count.get() == capacity) { 
    2.   
  
  
  
  2.     notFull.await(); 
    3.   
  
  
  
  3. } 
    4.

这个过程体现在上面那张图的notFull等待队列中的元素上，就不重复说明了。另外，和put方法比较类似的，还有一个携带等待时间参数的offer方法，可以进行有限时间内的阻塞添加，当超时后放弃插入元素，我们只看和offer方法不同部分的代码：

 
 
 
 
    
  
  
  
  
  1. public boolean offer(E e, long timeout, TimeUnit unit){ 
    2.   
  
  
  
  2.     ... 
    3.   
  
  
  
  3.     long nanos = unit.toNanos(timeout);//转换为纳秒 
    4.   
  
  
  
  4.     ... 
    5.   
  
  
  
  5.     while (count.get() == capacity) { 
    6.   
  
  
  
  6.         if (nanos <= 0) 
    7.   
  
  
  
  7.             return false; 
    8.   
  
  
  
  8.         nanos = notFull.awaitNanos(nanos); 
    9.   
  
  
  
  9.     } 
    10.   
  
  
  
  10.     enqueue(new Node(e));     
    11.   
  
  
  
  11.     ... 
    12.   
  
  
  
  12. } 
    13.

awaitNanos方法在await方法的基础上，增加了超时跳出的机制，会在循环中计算是否到达预设的超时时间。如果在到达超时时间前被唤醒，那么会返回超时时间减去已经消耗的时间。无论是被其他线程唤醒返回，还是到达指定的超时时间返回，只要方法返回值小于等于0，那么就认为它已经超时，最终直接返回false结束。

面试官：费这么大顿功夫才把插入讲明白，我先喝口水，你接着说获取元素方法

Hydra：……那先看非阻塞的poll方法

 
 
 
 
    
  
  
  
  
  1. public E poll() { 
    2.   
  
  
  
  2.     final AtomicInteger count = this.count; 
    3.   
  
  
  
  3.     if (count.get() == 0)//队列为空 
    4.   
  
  
  
  4.         return null; 
    5.   
  
  
  
  5.     E x = null; 
    6.   
  
  
  
  6.     int c = -1; 
    7.   
  
  
  
  7.     final ReentrantLock takeLock = this.takeLock; 
    8.   
  
  
  
  8.     takeLock.lock(); 
    9.   
  
  
  
  9.     try { 
    10.   
  
  
  
  10.         if (count.get() > 0) {//队列非空 
    11.   
  
  
  
  11.             x = dequeue(); 
    12.   
  
  
  
  12.             //出队前队列长队 
    13.   
  
  
  
  13.             c = count.getAndDecrement(); 
    14.   
  
  
  
  14.             if (c > 1) 
    15.   
  
  
  
  15.                 notEmpty.signal(); 
    16.   
  
  
  
  16.         } 
    17.   
  
  
  
  17.     } finally { 
    18.   
  
  
  
  18.         takeLock.unlock(); 
    19.   
  
  
  
  19.     } 
    20.   
  
  
  
  20.     if (c == capacity) 
    21.   
  
  
  
  21.         signalNotFull(); 
    22.   
  
  
  
  22.     return x; 
    23.   
  
  
  
  23. } 
    24.

出队的逻辑和入队的非常相似，当队列非空时就执行dequeue进行出队操作，完成出队后如果队列仍然非空，那么唤醒等待队列中挂起的获取元素的线程。并且当出队前的元素数量等于队列长度时，在出队后唤醒等待队列上的添加线程。

出队方法dequeue的源码如下：

 
 
 
 
    
  
  
  
  
  1. private E dequeue() { 
    2.   
  
  
  
  2.     Node h = head; 
    3.   
  
  
  
  3.     Node first = h.next; 
    4.   
  
  
  
  4.     h.next = h; // help GC 
    5.   
  
  
  
  5.     head = first; 
    6.   
  
  
  
  6.     E x = first.item; 
    7.   
  
  
  
  7.     first.item = null; 
    8.   
  
  
  
  8.     return x; 
    9.   
  
  
  
  9. } 
    10.

之前提到过，头节点head并不存储数据，它的下一个节点才是真正意义上的第一个节点。在出队操作中，先得到头结点的下一个节点first节点，将当前头结点的next指针指向自己，代码中有一个简单的注释是help gc，个人理解这里是为了降低gc中的引用计数，方便它更早被回收。之后再将新的头节点指向first，并返回清空为null前的内容。使用图来表示是这样的：

面试官：(看看手表)take方法的整体逻辑也差不多，能简单概括一下吗

Hydra：阻塞方法take方法和poll的思路基本一致，是一个可以被中断的阻塞获取方法，在队列为空时，会挂起当前线程，将它添加到条件对象notEmpty的等待队列中，等待其他线程唤醒。

面试官：再给你一句话的时间，总结一下它和ArrayBlockingQueue的异同，我要下班回家了

Hydra：好吧，我总结一下，有下面几点：

1、队列长度不同，ArrayBlockingQueue创建时需指定长度并且不可修改，而LinkedBlockingQueue可以指定也可以不指定长度

2、存储方式不同，ArrayBlockingQueue使用数组，而LinkedBlockingQueue使用Node节点的链表

3、ArrayBlockingQueue使用一把锁来控制元素的插入和移除，而LinkedBlockingQueue将入队锁和出队锁分离，提高了并发性能

4、ArrayBlockingQueue采用数组存储元素，因此在插入和移除过程中不需要生成额外对象，LinkedBlockingQueue会生成新的Node节点，对gc会有影响


本文名称：面试侃集合|LinkedBlockingQueue篇
文章网址：http://www.scjierui.cn/article/djioich.html

其他资讯