日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

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

新聞中心

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

面試官：平常在工作中你都用過什么什么集合?

Hydra：用過 ArrayList、HashMap，呃…沒有了

創(chuàng)新互聯(lián)建站于2013年創(chuàng)立，是專業(yè)互聯(lián)網(wǎng)技術服務公司，擁有項目成都網(wǎng)站制作、做網(wǎng)站、外貿營銷網(wǎng)站建設網(wǎng)站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元樂都做網(wǎng)站,已為上家服務,為樂都各地企業(yè)和個人服務,聯(lián)系電話:028-86922220

面試官：好的，回家等通知吧…

不知道大家在面試中是否也有過這樣的經(jīng)歷，工作中僅僅用過的那么幾種簡單的集合，被問到時就會感覺捉襟見肘。在面試中，如果能夠講清一些具有特殊使用場景的集合工具類的原理，一定能秀的面試官頭皮發(fā)麻。于是Hydra苦學半月，再次來和面試官對線

面試官：又來了老弟，讓我看看你這半個月學了些什么

Hydra：那就先從ArrayBlockingQueue 中開始聊吧，它是一個具有線程安全性和阻塞性的有界隊列

面試官：好啊，那先給我解釋一下它的線程安全性

Hydra：ArrayBlockingQueue的線程安全是通過底層的ReentrantLock保證的，因此在元素出入隊列操作時，無需額外加鎖。寫一段簡單的代碼舉個例子，從具體的使用來說明它的線程安全吧

 
 
 
 
    
  
  
  
  
  1. ArrayBlockingQueue queue=new ArrayBlockingQueue(7,
    2. 
  
  
  
  
  2.         true, new ArrayList<>(Arrays.asList(new Integer[]{1,2,3,4,5,6,7})));
    3. 
  
  
  
  
  3. 
  
  
  
  
  4. @AllArgsConstructor
    5. 
  
  
  
  
  5. class Task implements Runnable{
    6. 
  
  
  
  
  6.     String threadName;
    7. 
  
  
  
  
  7.     @Override
    8. 
  
  
  
  
  8.     public void run() {
    9. 
  
  
  
  
  9.         while(true) {
    10. 
  
  
  
  
  10.             try {
    11. 
  
  
  
  
  11.                 System.out.println(threadName+" take: "+queue.take());
    12. 
  
  
  
  
  12.             } catch (InterruptedException e) {
    13. 
  
  
  
  
  13.                 e.printStackTrace();
    14. 
  
  
  
  
  14.             }
    15. 
  
  
  
  
  15.         }
    16. 
  
  
  
  
  16.     }
    17. 
  
  
  
  
  17. }
    18. 
  
  
  
  
  18. 
  
  
  
  
  19. private void queueTest(){
    20. 
  
  
  
  
  20.     new Thread(new Task("Thread 1")).start();
    21. 
  
  
  
  
  21.     new Thread(new Task("Thread 2")).start();
    22. 
  
  
  
  
  22. }
    23.

在代碼中創(chuàng)建隊列時就往里放入了7個元素，然后創(chuàng)建兩個線程各自從隊列中取出元素。對隊列的操作也非常簡單，只用到了操作隊列中出隊方法take，運行結果如下：

 
 
 
 
    
  
  
  
  
  1. Thread 1 take: 1
    2. 
  
  
  
  
  2. Thread 2 take: 2
    3. 
  
  
  
  
  3. Thread 1 take: 3
    4. 
  
  
  
  
  4. Thread 2 take: 4
    5. 
  
  
  
  
  5. Thread 1 take: 5
    6. 
  
  
  
  
  6. Thread 2 take: 6
    7. 
  
  
  
  
  7. Thread 1 take: 7
    8.

可以看到在公平模式下，兩個線程交替對隊列中的元素執(zhí)行出隊操作，并沒有出現(xiàn)重復取出的情況，即保證了多個線程對資源競爭的互斥訪問。它的過程如下：

面試官：那它的阻塞性呢?

Hydra：好的，還是寫段代碼通過例子來說明

 
 
 
 
    
  
  
  
  
  1. private static void queueTest() throws InterruptedException {
    2. 
  
  
  
  
  2.     ArrayBlockingQueue queue=new ArrayBlockingQueue<>(3);
    3. 
  
  
  
  
  3.     int size=7;
    4. 
  
  
  
  
  4.     Thread putThread=new Thread(()->{
    5. 
  
  
  
  
  5.         for (int i = 0; i 
  
  
  
  
  6.             try {
    7. 
  
  
  
  
  7.                 queue.put(i);
    8. 
  
  
  
  
  8.                 System.out.println("PutThread put: "+i+" - Size:"+queue.size());
    9. 
  
  
  
  
  9.                 Thread.sleep(1000);
    10. 
  
  
  
  
  10.             } catch (InterruptedException e) {
    11. 
  
  
  
  
  11.                 e.printStackTrace();
    12. 
  
  
  
  
  12.             }
    13. 
  
  
  
  
  13.         }
    14. 
  
  
  
  
  14.     });
    15. 
  
  
  
  
  15.     Thread takeThread = new Thread(() -> {
    16. 
  
  
  
  
  16.         for (int i = 0; i < size+1 ; i++) {
    17. 
  
  
  
  
  17.             try {
    18. 
  
  
  
  
  18.                 Thread.sleep(3000);
    19. 
  
  
  
  
  19.                 System.out.println("TakeThread take: "+queue.take());
    20. 
  
  
  
  
  20.             } catch (InterruptedException e) {
    21. 
  
  
  
  
  21.                 e.printStackTrace();
    22. 
  
  
  
  
  22.             }
    23. 
  
  
  
  
  23.         }
    24. 
  
  
  
  
  24.     });
    25. 
  
  
  
  
  25. 
  
  
  
  
  26.     putThread.start();
    27. 
  
  
  
  
  27.     Thread.sleep(1000);
    28. 
  
  
  
  
  28.     takeThread.start();
    29. 
  
  
  
  
  29. }
    30.

和第一個例子中的代碼不同，這次我們創(chuàng)建隊列時只指定長度，并不在初始化時就往隊列中放入元素。接下來創(chuàng)建兩個線程，一個線程充當生產(chǎn)者，生產(chǎn)產(chǎn)品放入到隊列中，另一個線程充當消費者，消費隊列中的產(chǎn)品。需要注意生產(chǎn)和消費的速度是不同的，生產(chǎn)者每一秒生產(chǎn)一個，而消費者每三秒才消費一個。執(zhí)行上面的代碼，運行結果如下：

 
 
 
 
    
  
  
  
  
  1. PutThread put: 0 - Size:1
    2. 
  
  
  
  
  2. PutThread put: 1 - Size:2
    3. 
  
  
  
  
  3. PutThread put: 2 - Size:3
    4. 
  
  
  
  
  4. TakeThread take: 0
    5. 
  
  
  
  
  5. PutThread put: 3 - Size:3
    6. 
  
  
  
  
  6. TakeThread take: 1
    7. 
  
  
  
  
  7. PutThread put: 4 - Size:3
    8. 
  
  
  
  
  8. TakeThread take: 2
    9. 
  
  
  
  
  9. PutThread put: 5 - Size:3
    10. 
  
  
  
  
  10. TakeThread take: 3
    11. 
  
  
  
  
  11. PutThread put: 6 - Size:3
    12. 
  
  
  
  
  12. TakeThread take: 4
    13. 
  
  
  
  
  13. TakeThread take: 5
    14. 
  
  
  
  
  14. TakeThread take: 6
    15.

來給你畫個比較直觀的圖來演示一下吧：

分析運行結果，能夠在兩個方面體現(xiàn)出隊列的阻塞性：

  • 入隊阻塞：當隊列中的元素個數(shù)等于隊列長度時，會阻塞向隊列中放入元素的操作，當有出隊操作取走隊列中元素，隊列出現(xiàn)空缺位置后，才會再進行入隊
  • 出隊阻塞：當隊列中的元素為空時，執(zhí)行出隊操作的線程將被阻塞，直到隊列不為空時才會再次執(zhí)行出隊操作。在上面的代碼的出隊線程中，我們故意將出隊的次數(shù)設為了隊列中元素數(shù)量加一，因此這個線程最后會被一直阻塞，程序將一直執(zhí)行不會結束

面試官：你只會用put和take方法嗎，能不能講講其他的方法?

Hydra：方法太多了，簡單概括一下插入和移除相關的操作吧

面試官：方法記得還挺清楚，看樣子是個合格的 API caller。下面說說原理吧，先講一下ArrayBlockingQueue 的結構

Hydra：在ArrayBlockingQueue 中有下面四個比較重要的屬性

 
 
 
 
    
  
  
  
  
  1. final Object[] items;
    2. 
  
  
  
  
  2. final ReentrantLock lock;
    3. 
  
  
  
  
  3. private final Condition notEmpty;
    4. 
  
  
  
  
  4. private final Condition notFull;
    5. 
  
  
  
  
  5. 
  
  
  
  
  6. public ArrayBlockingQueue(int capacity, boolean fair) {
    7. 
  
  
  
  
  7.     if (capacity <= 0) throw new IllegalArgumentException();
    8. 
  
  
  
  
  8.     this.items = new Object[capacity];
    9. 
  
  
  
  
  9.     lock = new ReentrantLock(fair);
    10. 
  
  
  
  
  10.     notEmpty = lock.newCondition();
    11. 
  
  
  
  
  11.     notFull =  lock.newCondition();
    12. 
  
  
  
  
  12. }
    13.

在構造函數(shù)中對它們進行了初始化：

  • Object[] items：隊列的底層由數(shù)組組成，并且數(shù)組的長度在初始化就已經(jīng)固定，之后無法改變
  • ReentrantLock lock：控制隊列操作的獨占鎖，在操作隊列的元素前需要獲取鎖，保護競爭資源
  • Condition notEmpty：條件對象，如果有線程從隊列中獲取元素時隊列為空，就會在此進行等待，直到其他線程向隊列后插入元素才會被喚醒
  • Condition notFull：如果有線程試圖向隊列中插入元素，且此時隊列為滿時，就會在這進行等待，直到其他線程取出隊列中的元素才會被喚醒

Condition是一個接口，代碼中的notFull和notEmpty實例化的是AQS的內部類ConditionObject，它的內部是由AQS中的Node組成的等待鏈，ConditionObject中有一個頭節(jié)點firstWaiter和尾節(jié)點lastWaiter，并且每一個Node都有指向相鄰節(jié)點的指針。簡單的來說，它的結構是下面這樣的：

至于它的作用先賣個關子，放在后面講。除此之外，還有兩個int類型的屬性takeIndex和putIndex，表示獲取元素的索引位置和插入元素的索引位置。假設一個長度為5的隊列中已經(jīng)有了3個元素，那么它的結構是這樣的：

面試官：說一下隊列的插入操作吧

Hydra：好的，那我們先說add和offer方法，在執(zhí)行add方法時，調用了其父類AbstractQueue中的add方法。add方法則調用了offer方法，如果添加成功返回true，添加失敗時拋出異常，看一下源碼：

 
 
 
 
    
  
  
  
  
  1. public boolean add(E e) {
    2. 
  
  
  
  
  2.     if (offer(e))
    3. 
  
  
  
  
  3.         return true;
    4. 
  
  
  
  
  4.     else
    5. 
  
  
  
  
  5.         throw new IllegalStateException("Queue full");
    6. 
  
  
  
  
  6. }
    7. 
  
  
  
  
  7. 
  
  
  
  
  8. public boolean offer(E e) {
    9. 
  
  
  
  
  9.     checkNotNull(e);//檢查元素非空
    10. 
  
  
  
  
  10.     final ReentrantLock lock = this.lock; //獲取鎖并加鎖
    11. 
  
  
  
  
  11.     lock.lock();
    12. 
  
  
  
  
  12.     try {
    13. 
  
  
  
  
  13.         if (count == items.length)//隊列已滿
    14. 
  
  
  
  
  14.             return false;
    15. 
  
  
  
  
  15.         else {
    16. 
  
  
  
  
  16.             enqueue(e);//入隊
    17. 
  
  
  
  
  17.             return true;
    18. 
  
  
  
  
  18.         }
    19. 
  
  
  
  
  19.     } finally {
    20. 
  
  
  
  
  20.         lock.unlock();
    21. 
  
  
  
  
  21.     }
    22. 
  
  
  
  
  22. }
    23.

實際將元素加入隊列的核心方法enqueue：

 
 
 
 
    
  
  
  
  
  1. private void enqueue(E x) {
    2. 
  
  
  
  
  2.     final Object[] items = this.items;
    3. 
  
  
  
  
  3.     items[putIndex] = x; 
    4. 
  
  
  
  
  4.     if (++putIndex == items.length)
    5. 
  
  
  
  
  5.         putIndex = 0;
    6. 
  
  
  
  
  6.     count++;
    7. 
  
  
  
  
  7.     notEmpty.signal();
    8. 
  
  
  
  
  8. }
    9.

在enqueue中，首先將元素放入數(shù)組中下標為putIndex的位置，然后對putIndex自增，并判斷是否已處于隊列中最后一個位置，如果putIndex索引位置等于數(shù)組的長度時，那么將putIndex置為0，即下一次在元素入隊時，從隊列頭開始放置。

舉個例子，假設有一個長度為5的隊列，現(xiàn)在已經(jīng)有4個元素，我們進行下面一系列的操作，來看一下索引下標的變化：

上面這個例子提前用到了隊列中元素被移除時takeIndex會自增的知識點，通過這個例子中索引的變化，可以看出ArrayBlockingQueue就是一個循環(huán)隊列，takeIndex就相當于隊列的頭指針，而putIndex相當于隊列的尾指針的下一個位置索引。并且這里不需要擔心在隊列已滿時還會繼續(xù)向隊列中添加元素，因為在offer方法中會首先判斷隊列是否已滿，只有在隊列不滿時才會執(zhí)行enqueue方法。

面試官：這個過程我明白了，那enqueue方法里最后的notEmpty.signal()是什么意思?

Hydra：這是一個喚醒操作，等后面講完它的掛起后再說。我還是先把插入操作中的put方講完吧，看一下它的源碼：

 
 
 
 
    
  
  
  
  
  1. public void put(E e) throws InterruptedException {
    2. 
  
  
  
  
  2.     checkNotNull(e);
    3. 
  
  
  
  
  3.     final ReentrantLock lock = this.lock;
    4. 
  
  
  
  
  4.     lock.lockInterruptibly();
    5. 
  
  
  
  
  5.     try {
    6. 
  
  
  
  
  6.         while (count == items.length)
    7. 
  
  
  
  
  7.             notFull.await();
    8. 
  
  
  
  
  8.         enqueue(e);
    9. 
  
  
  
  
  9.     } finally {
    10. 
  
  
  
  
  10.         lock.unlock();
    11. 
  
  
  
  
  11.     }
    12. 
  
  
  
  
  12. }
    13.

put方法是一個阻塞方法，當隊列中元素未滿時，會直接調用enqueue方法將元素加入隊列中。如果隊列已滿，就會調用notFull.await()方法將掛起當前線程，直到隊列不滿時才會被喚醒，繼續(xù)執(zhí)行插入操作。

當隊列已滿，再執(zhí)行put操作時，就會執(zhí)行下面的流程：

這里提前劇透一下，當隊列中有元素被移除，在調用dequeue方法中的notFull.signal()時，會喚醒等待隊列中的線程，并把對應的元素添加到隊列中，流程如下：

做一個總結，在插入元素的幾個方法中，add、offer以及帶有超時的offer方法都是非阻塞的，會立即返回或超時后立即返回，而put方法是阻塞的，只有當隊列不滿添加成功后才會被返回。

面試官：講的不錯，講完插入操作了再講講移除操作怎么樣?

Hydra：還是老規(guī)矩，先說非阻塞的方法remove和poll，父類的remove方法還是會調用子類的poll方法，不同的是remove方法在隊列為空時拋出異常，而poll會直接返回null。這兩個方法的核心還是調用的dequeue方法，它的源碼如下：

 
 
 
 
    
  
  
  
  
  1. private E dequeue() {
    2. 
  
  
  
  
  2.     final Object[] items = this.items;
    3. 
  
  
  
  
  3.     E x = (E) items[takeIndex];
    4. 
  
  
  
  
  4.     items[takeIndex] = null;
    5. 
  
  
  
  
  5.     if (++takeIndex == items.length)
    6. 
  
  
  
  
  6.         takeIndex = 0;
    7. 
  
  
  
  
  7.     count--;
    8. 
  
  
  
  
  8.     if (itrs != null)
    9. 
  
  
  
  
  9.         //更新迭代器中的元素
    10. 
  
  
  
  
  10.         itrs.elementDequeued();
    11. 
  
  
  
  
  11.     notFull.signal();
    12. 
  
  
  
  
  12.     return x;
    13. 
  
  
  
  
  13. }
    14.

在dequeue中，在獲取到數(shù)組下標為takeIndex的元素，并將該位置置為null。將takeIndex自增后判斷是否與數(shù)組長度相等，如果相等還是按之前循環(huán)隊列的理論，將它的索引置為0，并將隊列的中的計數(shù)減1。

有一個隊列初始化時有5個元素，我們對齊分別進行5次的出隊操作，查看索引下標的變化情況：

然后我們還是結合take方法來說明線程的掛起和喚醒的操作，與put方法相對，take用于阻塞獲取元素，來看一下它的源碼：

 
 
 
 
    
  
  
  
  
  1. public E take() throws InterruptedException {
    2. 
  
  
  
  
  2.     final ReentrantLock lock = this.lock;
    3. 
  
  
  
  
  3.     lock.lockInterruptibly();
    4. 
  
  
  
  
  4.     try {
    5. 
  
  
  
  
  5.         while (count == 0)
    6. 
  
  
  
  
  6.             notEmpty.await();
    7. 
  
  
  
  
  7.         return dequeue();
    8. 
  
  
  
  
  8.     } finally {
    9. 
  
  
  
  
  9.         lock.unlock();
    10. 
  
  
  
  
  10.     }
    11. 
  
  
  
  
  11. }
    12.

take是一個可以被中斷的阻塞獲取元素的方法，首先判斷隊列是否為空，如果隊列不為空那么就調用dequeue方法移除元素，如果隊列為空時就調用notEmpty.await()就將當前線程掛起，直到有其他的線程調用了enqueue方法，才會喚醒等待隊列中被掛起的線程?？梢詤⒖枷旅娴膱D來理解：

當有其他線程向隊列中插入元素后：

入隊的enqueue方法會調用notEmpty.signal()，喚醒等待隊列中firstWaiter指向的節(jié)中的線程，并且該線程會調用dequeue完成元素的出隊操作。到這移除的操作就也分析完了，至于開頭為什么說ArrayBlockingQueue是線程安全的，看到每個方法前都通過全局單例的lock加鎖，相信你也應該明白了


網(wǎng)頁標題：面試侃集合|ArrayBlockingQueue篇
當前URL：http://www.dlmjj.cn/article/djgpgoj.html