日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
面試侃集合|LinkedBlockingQueue篇

面試官：好了，聊完了ArrayBlockingQueue，我們接著說說LinkedBlockingQueue吧

Hydra：還真是不給人喘口氣的機(jī)會，LinkedBlockingQueue是一個(gè)基于鏈表的阻塞隊(duì)列，內(nèi)部是由節(jié)點(diǎn)Node構(gòu)成，每個(gè)被加入隊(duì)列的元素都會被封裝成下面的Node節(jié)點(diǎn)，并且節(jié)點(diǎn)中有指向下一個(gè)元素的指針：

成都創(chuàng)新互聯(lián)公司專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、北鎮(zhèn)網(wǎng)絡(luò)推廣、成都小程序開發(fā)、北鎮(zhèn)網(wǎng)絡(luò)營銷、北鎮(zhèn)企業(yè)策劃、北鎮(zhèn)品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎；成都創(chuàng)新互聯(lián)公司為所有大學(xué)生創(chuàng)業(yè)者提供北鎮(zhèn)建站搭建服務(wù)，24小時(shí)服務(wù)熱線：13518219792，官方網(wǎng)址：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中的關(guān)鍵屬性有下面這些：

 
 
 
 
    
  
  
  
  
  1. private final int capacity;//隊(duì)列容量 
    2.   
  
  
  
  2. private final AtomicInteger count = new AtomicInteger();//隊(duì)列中元素?cái)?shù)量 
    3.   
  
  
  
  3. transient Node head;//頭節(jié)點(diǎn) 
    4.   
  
  
  
  4. private transient Node last;//尾節(jié)點(diǎn) 
    5.   
  
  
  
  5. //出隊(duì)鎖 
    6.   
  
  
  
  6. private final ReentrantLock takeLock = new ReentrantLock(); 
    7.   
  
  
  
  7. //出隊(duì)的等待條件對象 
    8.   
  
  
  
  8. private final Condition notEmpty = takeLock.newCondition(); 
    9.   
  
  
  
  9. //入隊(duì)鎖 
    10.   
  
  
  
  10. private final ReentrantLock putLock = new ReentrantLock(); 
    11.   
  
  
  
  11. //入隊(duì)的等待條件對象 
    12.   
  
  
  
  12. private final Condition notFull = putLock.newCondition(); 
    13.

構(gòu)造函數(shù)分為指定隊(duì)列長度和不指定隊(duì)列長度兩種，不指定時(shí)隊(duì)列最大長度是int的最大值。當(dāng)然了，你要是真存這么多的元素，很有可能會引起內(nèi)存溢出：

 
 
 
 
    
  
  
  
  
  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.

還有另一種在初始化時(shí)就可以將集合作為參數(shù)傳入的構(gòu)造方法，實(shí)現(xiàn)非常好理解，只是循環(huán)調(diào)用了后面會講到的enqueue入隊(duì)方法，這里暫且略過。

在LinkedBlockingQueue中，隊(duì)列的頭結(jié)點(diǎn)head是不存元素的，它的item是null，next指向的元素才是真正的第一個(gè)元素，它也有兩個(gè)用于阻塞等待的Condition條件對象。與之前的ArrayBlockingQueue不同，這里出隊(duì)和入隊(duì)使用了不同的鎖takeLock和putLock。隊(duì)列的結(jié)構(gòu)是這樣的：

面試官：為什么要使用兩把鎖，之前ArrayBlockingQueue使用一把鎖，不是也可以保證線程的安全么?

Hydra：使用兩把鎖，可以保證元素的插入和刪除并不互斥，從而能夠同時(shí)進(jìn)行，達(dá)到提高吞吐量的的效果

面試官：嗯，那還是老規(guī)矩，先說插入方法是怎么實(shí)現(xiàn)的吧

Hydra：這次就不提父類AbstractQueue的add方法了，反正它調(diào)用的也是子類的插入方法offer，我們就直接來看offer方法的源碼：

 
 
 
 
    
  
  
  
  
  1. public boolean offer(E e) { 
    2.   
  
  
  
  2.     if (e == null) throw new NullPointerException(); 
    3.   
  
  
  
  3.     final AtomicInteger count = this.count;//隊(duì)列中元素個(gè)數(shù) 
    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.         //并發(fā)情況，再次判斷隊(duì)列是否已滿 
    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方法中，首先判斷隊(duì)列是否已滿，未滿情況下將元素封裝成Node對象，嘗試獲取插入鎖，在獲取鎖后會再進(jìn)行一次隊(duì)列已滿判斷，如果已滿則直接釋放鎖。在持有鎖且隊(duì)列未滿的情況下，調(diào)用enqueue入隊(duì)方法。

enqueue方法的實(shí)現(xiàn)也非常的簡單，將當(dāng)前尾節(jié)點(diǎn)的next指針指向新節(jié)點(diǎn)，再把last指向新節(jié)點(diǎn)：

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

畫一張圖，方便你理解：

在完成入隊(duì)后，判斷隊(duì)列是否已滿，如果未滿則調(diào)用notFull.signal()，喚醒等待將元素插入隊(duì)列的線程。

面試官：我記得在ArrayBlockingQueue里插入元素后，是調(diào)用的notEmpty.signal()，怎么這里還不一樣了?

Hydra：說到這，就不得不再提一下使用兩把鎖來分別控制插入和獲取元素的好處了。在ArrayBlockingQueue中，使用了同一把鎖對入隊(duì)和出隊(duì)進(jìn)行控制，那么如果在插入元素后再喚醒插入線程，那么很有可能等待獲取元素的線程就一直得不到喚醒，造成等待時(shí)間過長。

而在LinkedBlockingQueue中，分別使用了入隊(duì)鎖putLock和出隊(duì)鎖takeLock，插入線程和獲取線程是不會互斥的。所以插入線程可以在這里不斷的喚醒其他的插入線程，而無需擔(dān)心是否會使獲取線程等待時(shí)間過長，從而在一定程度上提高了吞吐量。當(dāng)然了，因?yàn)閛ffer方法是非阻塞的，并不會掛起阻塞線程，所以這里喚醒的是阻塞插入的put方法的線程。

面試官：那接著往下看，為什么要在c等于0的情況下才去喚醒notEmpty中的等待獲取元素的線程?

Hydra：其實(shí)獲取元素的方法和上面插入元素的方法是一個(gè)模式的，只要有一個(gè)獲取線程在執(zhí)行方法，那么就會不斷的通過notEmpty.signal()喚醒其他的獲取線程。只有當(dāng)c等于0時(shí)，才證明之前隊(duì)列中已經(jīng)沒有元素，這時(shí)候獲取線程才可能會被阻塞，在這個(gè)時(shí)候才需要被喚醒。上面的這些可以用一張圖來說明：

由于我們之前說過，隊(duì)列中的head節(jié)點(diǎn)可以認(rèn)為是不存儲數(shù)據(jù)的標(biāo)志性節(jié)點(diǎn)，所以可以簡單的認(rèn)為出隊(duì)時(shí)直接取出第二個(gè)節(jié)點(diǎn)，當(dāng)然這個(gè)過程不是非常的嚴(yán)謹(jǐn)，我會在后面講解出隊(duì)的過程中再進(jìn)行補(bǔ)充說明。

面試官：那么阻塞方法put和它有什么區(qū)別?

Hydra：put和offer方法整體思路一致，不同的是加鎖是使用的是可被中斷的方式，并且當(dāng)隊(duì)列中元素已滿時(shí)，將線程加入notFull等待隊(duì)列中進(jìn)行等待，代碼中體現(xiàn)在：

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

這個(gè)過程體現(xiàn)在上面那張圖的notFull等待隊(duì)列中的元素上，就不重復(fù)說明了。另外，和put方法比較類似的，還有一個(gè)攜帶等待時(shí)間參數(shù)的offer方法，可以進(jìn)行有限時(shí)間內(nèi)的阻塞添加，當(dāng)超時(shí)后放棄插入元素，我們只看和offer方法不同部分的代碼：

 
 
 
 
    
  
  
  
  
  1. public boolean offer(E e, long timeout, TimeUnit unit){ 
    2.   
  
  
  
  2.     ... 
    3.   
  
  
  
  3.     long nanos = unit.toNanos(timeout);//轉(zhuǎn)換為納秒 
    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方法的基礎(chǔ)上，增加了超時(shí)跳出的機(jī)制，會在循環(huán)中計(jì)算是否到達(dá)預(yù)設(shè)的超時(shí)時(shí)間。如果在到達(dá)超時(shí)時(shí)間前被喚醒，那么會返回超時(shí)時(shí)間減去已經(jīng)消耗的時(shí)間。無論是被其他線程喚醒返回，還是到達(dá)指定的超時(shí)時(shí)間返回，只要方法返回值小于等于0，那么就認(rèn)為它已經(jīng)超時(shí)，最終直接返回false結(jié)束。

面試官：費(fèi)這么大頓功夫才把插入講明白，我先喝口水，你接著說獲取元素方法

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

 
 
 
 
    
  
  
  
  
  1. public E poll() { 
    2.   
  
  
  
  2.     final AtomicInteger count = this.count; 
    3.   
  
  
  
  3.     if (count.get() == 0)//隊(duì)列為空 
    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) {//隊(duì)列非空 
    11.   
  
  
  
  11.             x = dequeue(); 
    12.   
  
  
  
  12.             //出隊(duì)前隊(duì)列長隊(duì) 
    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.

出隊(duì)的邏輯和入隊(duì)的非常相似，當(dāng)隊(duì)列非空時(shí)就執(zhí)行dequeue進(jìn)行出隊(duì)操作，完成出隊(duì)后如果隊(duì)列仍然非空，那么喚醒等待隊(duì)列中掛起的獲取元素的線程。并且當(dāng)出隊(duì)前的元素?cái)?shù)量等于隊(duì)列長度時(shí)，在出隊(duì)后喚醒等待隊(duì)列上的添加線程。

出隊(duì)方法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.

之前提到過，頭節(jié)點(diǎn)head并不存儲數(shù)據(jù)，它的下一個(gè)節(jié)點(diǎn)才是真正意義上的第一個(gè)節(jié)點(diǎn)。在出隊(duì)操作中，先得到頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)first節(jié)點(diǎn)，將當(dāng)前頭結(jié)點(diǎn)的next指針指向自己，代碼中有一個(gè)簡單的注釋是help gc，個(gè)人理解這里是為了降低gc中的引用計(jì)數(shù)，方便它更早被回收。之后再將新的頭節(jié)點(diǎn)指向first，并返回清空為null前的內(nèi)容。使用圖來表示是這樣的：

面試官：(看看手表)take方法的整體邏輯也差不多，能簡單概括一下嗎

Hydra：阻塞方法take方法和poll的思路基本一致，是一個(gè)可以被中斷的阻塞獲取方法，在隊(duì)列為空時(shí)，會掛起當(dāng)前線程，將它添加到條件對象notEmpty的等待隊(duì)列中，等待其他線程喚醒。

面試官：再給你一句話的時(shí)間，總結(jié)一下它和ArrayBlockingQueue的異同，我要下班回家了

Hydra：好吧，我總結(jié)一下，有下面幾點(diǎn)：

1、隊(duì)列長度不同，ArrayBlockingQueue創(chuàng)建時(shí)需指定長度并且不可修改，而LinkedBlockingQueue可以指定也可以不指定長度

2、存儲方式不同，ArrayBlockingQueue使用數(shù)組，而LinkedBlockingQueue使用Node節(jié)點(diǎn)的鏈表

3、ArrayBlockingQueue使用一把鎖來控制元素的插入和移除，而LinkedBlockingQueue將入隊(duì)鎖和出隊(duì)鎖分離，提高了并發(fā)性能

4、ArrayBlockingQueue采用數(shù)組存儲元素，因此在插入和移除過程中不需要生成額外對象，LinkedBlockingQueue會生成新的Node節(jié)點(diǎn)，對gc會有影響


分享標(biāo)題：面試侃集合|LinkedBlockingQueue篇
地址分享：http://www.5511xx.com/article/djioich.html