面試侃集合 | ArrayBlockingQueue篇

面試官：平常在工作中你都用過(guò)什么什么集合？

Hydra：用過(guò) ArrayList树酪、HashMap浅碾，呃…沒(méi)有了

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

不知道大家在面試中是否也有過(guò)這樣的經(jīng)歷嗅回，工作中僅僅用過(guò)的那么幾種簡(jiǎn)單的集合及穗，被問(wèn)到時(shí)就會(huì)感覺(jué)捉襟見(jiàn)肘。在面試中绵载，如果能夠講清一些具有特殊的使用場(chǎng)景的集合工具類(lèi)，一定能秀的面試官頭皮發(fā)麻苛白。于是Hydra苦學(xué)半月娃豹，再次來(lái)和面試官對(duì)線

面試官：又來(lái)了老弟，讓我看看你這半個(gè)月學(xué)了些什么

Hydra：那就先從ArrayBlockingQueue 中開(kāi)始聊吧购裙，它是一個(gè)具有線程安全性和阻塞性的有界隊(duì)列

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

Hydra：ArrayBlockingQueue的線程安全是通過(guò)底層的ReentrantLock保證的，因此在元素出入隊(duì)列操作時(shí)躏率，無(wú)需額外加鎖躯畴。寫(xiě)一段簡(jiǎn)單的代碼舉個(gè)例子，從具體的使用來(lái)說(shuō)明它的線程安全吧

ArrayBlockingQueue<Integer> queue=new ArrayBlockingQueue(7,
        true, new ArrayList<>(Arrays.asList(new Integer[]{1,2,3,4,5,6,7})));

@AllArgsConstructor
class Task implements Runnable{
    String threadName;
    @Override
    public void run() {
        while(true) {
            try {
                System.out.println(threadName+" take: "+queue.take());
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

private void queueTest(){
    new Thread(new Task("Thread 1")).start();
    new Thread(new Task("Thread 2")).start();
}

在代碼中創(chuàng)建隊(duì)列時(shí)就往里放入了7個(gè)元素薇芝，然后創(chuàng)建兩個(gè)線程各自從隊(duì)列中取出元素蓬抄。對(duì)隊(duì)列的操作也非常簡(jiǎn)單，只用到了操作隊(duì)列中出隊(duì)方法take夯到，運(yùn)行結(jié)果如下：

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

可以看到在公平模式下嚷缭，兩個(gè)線程交替對(duì)隊(duì)列中的元素執(zhí)行出隊(duì)操作，并沒(méi)有出現(xiàn)重復(fù)取出的情況耍贾，即保證了多個(gè)線程對(duì)資源競(jìng)爭(zhēng)的互斥訪問(wèn)阅爽。它的過(guò)程如下：

image

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

Hydra：好的荐开，還是寫(xiě)段代碼通過(guò)例子來(lái)說(shuō)明

private static void queueTest() throws InterruptedException {
    ArrayBlockingQueue<Integer> queue=new ArrayBlockingQueue<>(3);
    int size=7;
    Thread putThread=new Thread(()->{
        for (int i = 0; i <size ; i++) {
            try {
                queue.put(i);
                System.out.println("PutThread put: "+i+" - Size:"+queue.size());
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    });
    Thread takeThread = new Thread(() -> {
        for (int i = 0; i < size+1 ; i++) {
            try {
                Thread.sleep(3000);
                System.out.println("TakeThread take: "+queue.take());
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    });

    putThread.start();
    Thread.sleep(1000);
    takeThread.start();
}

和第一個(gè)例子中的代碼不同付翁，這次我們創(chuàng)建隊(duì)列時(shí)只指定長(zhǎng)度，并不在初始化時(shí)就往隊(duì)列中放入元素晃听。接下來(lái)創(chuàng)建兩個(gè)線程百侧，一個(gè)線程充當(dāng)生產(chǎn)者着帽，生產(chǎn)產(chǎn)品放入到隊(duì)列中，另一個(gè)線程充當(dāng)消費(fèi)者移层，消費(fèi)隊(duì)列中的產(chǎn)品仍翰。需要注意生產(chǎn)和消費(fèi)的速度是不同的，生產(chǎn)者每一秒生產(chǎn)一個(gè)观话，而消費(fèi)者每三秒才消費(fèi)一個(gè)予借。執(zhí)行上面的代碼，運(yùn)行結(jié)果如下：

PutThread put: 0 - Size:1
PutThread put: 1 - Size:2
PutThread put: 2 - Size:3
TakeThread take: 0
PutThread put: 3 - Size:3
TakeThread take: 1
PutThread put: 4 - Size:3
TakeThread take: 2
PutThread put: 5 - Size:3
TakeThread take: 3
PutThread put: 6 - Size:3
TakeThread take: 4
TakeThread take: 5
TakeThread take: 6

來(lái)給你畫(huà)個(gè)比較直觀的圖吧：

image

分析運(yùn)行結(jié)果频蛔，能夠在兩個(gè)方面體現(xiàn)出隊(duì)列的阻塞性：

  • 入隊(duì)阻塞：當(dāng)隊(duì)列中的元素個(gè)數(shù)等于隊(duì)列長(zhǎng)度時(shí)灵迫，會(huì)阻塞向隊(duì)列中放入元素的操作，當(dāng)有出隊(duì)操作取走隊(duì)列中元素晦溪，隊(duì)列出現(xiàn)空缺位置后瀑粥，才會(huì)再進(jìn)行入隊(duì)
  • 出隊(duì)阻塞：當(dāng)隊(duì)列中的元素為空時(shí)，執(zhí)行出隊(duì)操作的線程將被阻塞三圆，直到隊(duì)列不為空時(shí)才會(huì)再次執(zhí)行出隊(duì)操作狞换。在上面的代碼的出隊(duì)線程中，我們故意將出隊(duì)的次數(shù)設(shè)為了隊(duì)列中元素?cái)?shù)量加一舟肉，因此這個(gè)線程最后會(huì)被一直阻塞修噪，程序?qū)⒁恢眻?zhí)行不會(huì)結(jié)束

面試官：你只會(huì)用put和take方法嗎，能不能講講其他的方法路媚？

Hydra：方法太多了黄琼，簡(jiǎn)單概括一下插入和移除相關(guān)的操作吧

image

面試官：方法記得還挺清楚，看樣子是個(gè)合格的 API caller整慎。下面說(shuō)說(shuō)原理吧脏款，先講一下ArrayBlockingQueue 的結(jié)構(gòu)

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

final Object[] items;
final ReentrantLock lock;
private final Condition notEmpty;
private final Condition notFull;

public ArrayBlockingQueue(int capacity, boolean fair) {
    if (capacity <= 0) throw new IllegalArgumentException();
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull =  lock.newCondition();
}

在構(gòu)造函數(shù)中對(duì)它們進(jìn)行了初始化：

  • Object[] items：隊(duì)列的底層由數(shù)組組成啡专，并且數(shù)組的長(zhǎng)度在初始化就已經(jīng)固定买猖，之后無(wú)法改變
  • ReentrantLock lock：用對(duì)控制隊(duì)列操作的獨(dú)占鎖，在操作隊(duì)列的元素前需要獲取鎖得问，保護(hù)競(jìng)爭(zhēng)資源
  • Condition notEmpty：條件對(duì)象比然，如果有線程從隊(duì)列中獲取元素時(shí)隊(duì)列為空丈氓，就會(huì)在此進(jìn)行等待，直到其他線程向隊(duì)列后插入元素才會(huì)被喚醒
  • Condition notFull：如果有線程試圖向隊(duì)列中插入元素强法，且此時(shí)隊(duì)列為滿(mǎn)時(shí)万俗，就會(huì)在這進(jìn)行等待，直到其他線程取出隊(duì)列中的元素才會(huì)被喚醒

Condition是一個(gè)接口饮怯，代碼中的notFull和notEmpty實(shí)例化的是AQS的內(nèi)部類(lèi)ConditionObject闰歪，它的內(nèi)部是由AQS中的Node組成的等待鏈，ConditionObject中有一個(gè)頭節(jié)點(diǎn)firstWaiter和尾節(jié)點(diǎn)lastWaiter蓖墅，并且每一個(gè)Node都有指向相鄰節(jié)點(diǎn)的指針库倘。簡(jiǎn)單的來(lái)說(shuō)临扮，它的結(jié)構(gòu)是下面這樣的：

image

至于它的作用先賣(mài)個(gè)關(guān)子，放在后面講教翩。除此之外杆勇，還有兩個(gè)int類(lèi)型的屬性takeIndex和putIndex，表示獲取元素的索引位置和插入元素的索引位置饱亿。假設(shè)一個(gè)長(zhǎng)度為5的隊(duì)列中已經(jīng)有了3個(gè)元素蚜退，那么它的結(jié)構(gòu)是這樣的：

image

面試官：說(shuō)一下隊(duì)列的插入操作吧

Hydra：好的，那我們先說(shuō)add和offer方法彪笼，在執(zhí)行add方法時(shí)钻注，調(diào)用了其父類(lèi)AbstractQueue中的add方法。add方法則調(diào)用了offer方法配猫，如果添加成功返回true幅恋，添加失敗時(shí)拋出異常，看一下源碼：

public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}

public boolean offer(E e) {
    checkNotNull(e);//檢查元素非空
    final ReentrantLock lock = this.lock; //獲取鎖并加鎖
    lock.lock();
    try {
        if (count == items.length)//隊(duì)列已滿(mǎn)
            return false;
        else {
            enqueue(e);//入隊(duì)
            return true;
        }
    } finally {
        lock.unlock();
    }
}

實(shí)際將元素加入隊(duì)列的核心方法enqueue：

private void enqueue(E x) {
    final Object[] items = this.items;
    items[putIndex] = x; 
    if (++putIndex == items.length)
        putIndex = 0;
    count++;
    notEmpty.signal();
}

在enqueue中泵肄，首先將元素放入數(shù)組中下標(biāo)為putIndex的位置捆交，然后對(duì)putIndex自增，并判斷是否已處于隊(duì)列中最后一個(gè)位置凡伊，如果putIndex索引位置等于數(shù)組的長(zhǎng)度時(shí)零渐，那么將putIndex置為0，即下一次在元素入隊(duì)時(shí)系忙，從隊(duì)列頭開(kāi)始放置。

舉個(gè)例子惠豺，假設(shè)有一個(gè)長(zhǎng)度為5的隊(duì)列银还，現(xiàn)在已經(jīng)有4個(gè)元素，我們進(jìn)行下面一系列的操作洁墙，來(lái)看一下索引下標(biāo)的變化：

image

上面這個(gè)例子提前用到了隊(duì)列中元素被移除時(shí)takeIndex會(huì)自增的知識(shí)點(diǎn)蛹疯，通過(guò)這個(gè)例子中索引的變化，可以看出ArrayBlockingQueue就是一個(gè)循環(huán)隊(duì)列热监，takeIndex就相當(dāng)于隊(duì)列的頭指針捺弦，而putIndex相當(dāng)于隊(duì)列的尾指針的下一個(gè)位置索引。并且這里不需要擔(dān)心在隊(duì)列已滿(mǎn)時(shí)還會(huì)繼續(xù)向隊(duì)列中添加元素孝扛，因?yàn)樵?code>offer方法中會(huì)首先判斷隊(duì)列是否已滿(mǎn)列吼，只有在隊(duì)列不滿(mǎn)時(shí)才會(huì)執(zhí)行enqueue方法。

面試官：這個(gè)過(guò)程我明白了苦始，那enqueue方法里最后的notEmpty.signal()是什么意思寞钥？

Hydra：這是一個(gè)喚醒操作，等后面講完它的掛起后再說(shuō)陌选。我還是先把插入操作中的put方講完吧理郑，看一下它的源碼：

public void put(E e) throws InterruptedException {
    checkNotNull(e);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == items.length)
            notFull.await();
        enqueue(e);
    } finally {
        lock.unlock();
    }
}

put方法是一個(gè)阻塞方法蹄溉，當(dāng)隊(duì)列中元素未滿(mǎn)時(shí)，會(huì)直接調(diào)用enqueue方法將元素加入隊(duì)列中您炉。如果隊(duì)列已滿(mǎn)柒爵，就會(huì)調(diào)用notFull.await()方法將掛起當(dāng)前線程，直到隊(duì)列不滿(mǎn)時(shí)才會(huì)被喚醒赚爵，繼續(xù)執(zhí)行插入操作棉胀。

當(dāng)隊(duì)列已滿(mǎn)，再執(zhí)行put操作時(shí)囱晴，就會(huì)執(zhí)行下面的流程：

image

這里提前劇透一下膏蚓，當(dāng)隊(duì)列中有元素被移除，在調(diào)用dequeue方法中的notFull.signal()時(shí)畸写，會(huì)喚醒等待隊(duì)列中的線程驮瞧，并把對(duì)應(yīng)的元素添加到隊(duì)列中，流程如下：

image

做一個(gè)總結(jié)枯芬，在插入元素的幾個(gè)方法中论笔，add、offer以及帶有超時(shí)的offer方法都是非阻塞的千所，會(huì)立即返回或超時(shí)后立即返回狂魔，而put方法是阻塞的，只有當(dāng)隊(duì)列不滿(mǎn)添加成功后才會(huì)被返回淫痰。

面試官：講的不錯(cuò)最楷，講完插入操作了再講講移除操作吧

Hydra：還是老規(guī)矩，先說(shuō)非阻塞的方法remove和poll待错，父類(lèi)的remove方法還是會(huì)調(diào)用子類(lèi)的poll方法籽孙，不同的是remove方法在隊(duì)列為空時(shí)拋出異常，而poll會(huì)直接返回null火俄。這兩個(gè)方法的核心還是調(diào)用的dequeue方法犯建，它的源碼如下：

private E dequeue() {
    final Object[] items = this.items;
    E x = (E) items[takeIndex];
    items[takeIndex] = null;
    if (++takeIndex == items.length)
        takeIndex = 0;
    count--;
    if (itrs != null)
        //更新迭代器中的元素
        itrs.elementDequeued();
    notFull.signal();
    return x;
}

在dequeue中，在獲取到數(shù)組下標(biāo)為takeIndex的元素瓜客，并將該位置置為null适瓦。將takeIndex自增后判斷是否與數(shù)組長(zhǎng)度相等，如果相等還是按之前循環(huán)隊(duì)列的理論谱仪，將它的索引置為0玻熙，并將隊(duì)列的中的計(jì)數(shù)減1。

有一個(gè)隊(duì)列初始化時(shí)有5個(gè)元素芽卿，我們對(duì)齊分別進(jìn)行5次的出隊(duì)操作揭芍，查看索引下標(biāo)的變化情況：

image

然后我們還是結(jié)合take方法來(lái)說(shuō)明線程的掛起和喚醒的操作，與put方法相對(duì)卸例，take用于阻塞獲取元素称杨，來(lái)看一下它的源碼：

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == 0)
            notEmpty.await();
        return dequeue();
    } finally {
        lock.unlock();
    }
}

take是一個(gè)可以被中斷的阻塞獲取元素的方法肌毅，首先判斷隊(duì)列是否為空，如果隊(duì)列不為空那么就調(diào)用dequeue方法移除元素姑原，如果隊(duì)列為空時(shí)就調(diào)用notEmpty.await()就將當(dāng)前線程掛起悬而，直到有其他的線程調(diào)用了enqueue方法，才會(huì)喚醒等待隊(duì)列中被掛起的線程锭汛”康欤可以參考下面的圖來(lái)理解：

image

當(dāng)有其他線程向隊(duì)列中插入元素后：

image

入隊(duì)的enqueue方法會(huì)調(diào)用notEmpty.signal()，喚醒等待隊(duì)列中firstWaiter指向的節(jié)中的線程唤殴，并且該線程會(huì)調(diào)用dequeue完成元素的出隊(duì)操作般婆。到這移除的操作就也分析完了，至于開(kāi)頭為什么說(shuō)ArrayBlockingQueue是線程安全的朵逝，看到每個(gè)方法前都通過(guò)全局單例的lock加鎖蔚袍，相信你也應(yīng)該明白了

面試官：好了，ArrayBlockingQueue我懂了配名，我先去吃個(gè)飯啤咽，回來(lái)咱們?cè)倭牧膭e的集合

Hydra：……

image

如果文章對(duì)您有所幫助，歡迎關(guān)注公眾號(hào) 碼農(nóng)參上

<img src="https://gitee.com/trunks2008/picture/raw/master/2021-3-29/1616991591638-qrcode_for_gh_96a0cbd3c729_344.jpg" style="zoom:70%;" />

面試官：平常在工作中你都用過(guò)什么什么集合渠脉？

Hydra：用過(guò) ArrayList宇整、HashMap，呃…沒(méi)有了

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

不知道大家在面試中是否也有過(guò)這樣的經(jīng)歷鳞青，工作中僅僅用過(guò)的那么幾種簡(jiǎn)單的集合，被問(wèn)到時(shí)就會(huì)感覺(jué)捉襟見(jiàn)肘为朋。在面試中盼玄，如果能夠講清一些具有特殊的使用場(chǎng)景的集合工具類(lèi)，一定能秀的面試官頭皮發(fā)麻潜腻。于是Hydra苦學(xué)半月，再次來(lái)和面試官對(duì)線

面試官：又來(lái)了老弟器仗，讓我看看你這半個(gè)月學(xué)了些什么

Hydra：那就先從ArrayBlockingQueue 中開(kāi)始聊吧融涣，它是一個(gè)具有線程安全性和阻塞性的有界隊(duì)列

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

Hydra：ArrayBlockingQueue的線程安全是通過(guò)底層的ReentrantLock保證的精钮，因此在元素出入隊(duì)列操作時(shí)威鹿，無(wú)需額外加鎖。寫(xiě)一段簡(jiǎn)單的代碼舉個(gè)例子轨香，從具體的使用來(lái)說(shuō)明它的線程安全吧

ArrayBlockingQueue<Integer> queue=new ArrayBlockingQueue(7,
        true, new ArrayList<>(Arrays.asList(new Integer[]{1,2,3,4,5,6,7})));

@AllArgsConstructor
class Task implements Runnable{
    String threadName;
    @Override
    public void run() {
        while(true) {
            try {
                System.out.println(threadName+" take: "+queue.take());
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

private void queueTest(){
    new Thread(new Task("Thread 1")).start();
    new Thread(new Task("Thread 2")).start();
}

在代碼中創(chuàng)建隊(duì)列時(shí)就往里放入了7個(gè)元素忽你，然后創(chuàng)建兩個(gè)線程各自從隊(duì)列中取出元素。對(duì)隊(duì)列的操作也非常簡(jiǎn)單臂容，只用到了操作隊(duì)列中出隊(duì)方法take科雳，運(yùn)行結(jié)果如下：

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

可以看到在公平模式下根蟹，兩個(gè)線程交替對(duì)隊(duì)列中的元素執(zhí)行出隊(duì)操作，并沒(méi)有出現(xiàn)重復(fù)取出的情況糟秘，即保證了多個(gè)線程對(duì)資源競(jìng)爭(zhēng)的互斥訪問(wèn)简逮。它的過(guò)程如下：

image

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

Hydra：好的尿赚，還是寫(xiě)段代碼通過(guò)例子來(lái)說(shuō)明

private static void queueTest() throws InterruptedException {
    ArrayBlockingQueue<Integer> queue=new ArrayBlockingQueue<>(3);
    int size=7;
    Thread putThread=new Thread(()->{
        for (int i = 0; i <size ; i++) {
            try {
                queue.put(i);
                System.out.println("PutThread put: "+i+" - Size:"+queue.size());
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    });
    Thread takeThread = new Thread(() -> {
        for (int i = 0; i < size+1 ; i++) {
            try {
                Thread.sleep(3000);
                System.out.println("TakeThread take: "+queue.take());
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    });

    putThread.start();
    Thread.sleep(1000);
    takeThread.start();
}

和第一個(gè)例子中的代碼不同散庶，這次我們創(chuàng)建隊(duì)列時(shí)只指定長(zhǎng)度，并不在初始化時(shí)就往隊(duì)列中放入元素凌净。接下來(lái)創(chuàng)建兩個(gè)線程悲龟，一個(gè)線程充當(dāng)生產(chǎn)者，生產(chǎn)產(chǎn)品放入到隊(duì)列中冰寻，另一個(gè)線程充當(dāng)消費(fèi)者须教，消費(fèi)隊(duì)列中的產(chǎn)品。需要注意生產(chǎn)和消費(fèi)的速度是不同的性雄，生產(chǎn)者每一秒生產(chǎn)一個(gè)没卸，而消費(fèi)者每三秒才消費(fèi)一個(gè)。執(zhí)行上面的代碼秒旋，運(yùn)行結(jié)果如下：

PutThread put: 0 - Size:1
PutThread put: 1 - Size:2
PutThread put: 2 - Size:3
TakeThread take: 0
PutThread put: 3 - Size:3
TakeThread take: 1
PutThread put: 4 - Size:3
TakeThread take: 2
PutThread put: 5 - Size:3
TakeThread take: 3
PutThread put: 6 - Size:3
TakeThread take: 4
TakeThread take: 5
TakeThread take: 6

來(lái)給你畫(huà)個(gè)比較直觀的圖吧：

image

分析運(yùn)行結(jié)果约计，能夠在兩個(gè)方面體現(xiàn)出隊(duì)列的阻塞性：

  • 入隊(duì)阻塞：當(dāng)隊(duì)列中的元素個(gè)數(shù)等于隊(duì)列長(zhǎng)度時(shí)，會(huì)阻塞向隊(duì)列中放入元素的操作迁筛，當(dāng)有出隊(duì)操作取走隊(duì)列中元素煤蚌，隊(duì)列出現(xiàn)空缺位置后，才會(huì)再進(jìn)行入隊(duì)
  • 出隊(duì)阻塞：當(dāng)隊(duì)列中的元素為空時(shí)细卧，執(zhí)行出隊(duì)操作的線程將被阻塞尉桩，直到隊(duì)列不為空時(shí)才會(huì)再次執(zhí)行出隊(duì)操作。在上面的代碼的出隊(duì)線程中贪庙，我們故意將出隊(duì)的次數(shù)設(shè)為了隊(duì)列中元素?cái)?shù)量加一蜘犁，因此這個(gè)線程最后會(huì)被一直阻塞，程序?qū)⒁恢眻?zhí)行不會(huì)結(jié)束

面試官：你只會(huì)用put和take方法嗎止邮，能不能講講其他的方法这橙？

Hydra：方法太多了，簡(jiǎn)單概括一下插入和移除相關(guān)的操作吧

image

面試官：方法記得還挺清楚导披，看樣子是個(gè)合格的 API caller屈扎。下面說(shuō)說(shuō)原理吧，先講一下ArrayBlockingQueue 的結(jié)構(gòu)

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

final Object[] items;
final ReentrantLock lock;
private final Condition notEmpty;
private final Condition notFull;

public ArrayBlockingQueue(int capacity, boolean fair) {
    if (capacity <= 0) throw new IllegalArgumentException();
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull =  lock.newCondition();
}

在構(gòu)造函數(shù)中對(duì)它們進(jìn)行了初始化：

  • Object[] items：隊(duì)列的底層由數(shù)組組成撩匕，并且數(shù)組的長(zhǎng)度在初始化就已經(jīng)固定鹰晨，之后無(wú)法改變
  • ReentrantLock lock：用對(duì)控制隊(duì)列操作的獨(dú)占鎖，在操作隊(duì)列的元素前需要獲取鎖，保護(hù)競(jìng)爭(zhēng)資源
  • Condition notEmpty：條件對(duì)象模蜡，如果有線程從隊(duì)列中獲取元素時(shí)隊(duì)列為空漠趁，就會(huì)在此進(jìn)行等待，直到其他線程向隊(duì)列后插入元素才會(huì)被喚醒
  • Condition notFull：如果有線程試圖向隊(duì)列中插入元素哩牍，且此時(shí)隊(duì)列為滿(mǎn)時(shí)棚潦，就會(huì)在這進(jìn)行等待，直到其他線程取出隊(duì)列中的元素才會(huì)被喚醒

Condition是一個(gè)接口膝昆，代碼中的notFull和notEmpty實(shí)例化的是AQS的內(nèi)部類(lèi)ConditionObject丸边，它的內(nèi)部是由AQS中的Node組成的等待鏈，ConditionObject中有一個(gè)頭節(jié)點(diǎn)firstWaiter和尾節(jié)點(diǎn)lastWaiter荚孵，并且每一個(gè)Node都有指向相鄰節(jié)點(diǎn)的指針妹窖。簡(jiǎn)單的來(lái)說(shuō)，它的結(jié)構(gòu)是下面這樣的：

image

至于它的作用先賣(mài)個(gè)關(guān)子收叶，放在后面講骄呼。除此之外，還有兩個(gè)int類(lèi)型的屬性takeIndex和putIndex判没，表示獲取元素的索引位置和插入元素的索引位置蜓萄。假設(shè)一個(gè)長(zhǎng)度為5的隊(duì)列中已經(jīng)有了3個(gè)元素，那么它的結(jié)構(gòu)是這樣的：

image

面試官：說(shuō)一下隊(duì)列的插入操作吧

Hydra：好的澄峰，那我們先說(shuō)add和offer方法嫉沽，在執(zhí)行add方法時(shí)，調(diào)用了其父類(lèi)AbstractQueue中的add方法俏竞。add方法則調(diào)用了offer方法绸硕，如果添加成功返回true，添加失敗時(shí)拋出異常魂毁，看一下源碼：

public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}

public boolean offer(E e) {
    checkNotNull(e);//檢查元素非空
    final ReentrantLock lock = this.lock; //獲取鎖并加鎖
    lock.lock();
    try {
        if (count == items.length)//隊(duì)列已滿(mǎn)
            return false;
        else {
            enqueue(e);//入隊(duì)
            return true;
        }
    } finally {
        lock.unlock();
    }
}

實(shí)際將元素加入隊(duì)列的核心方法enqueue：

private void enqueue(E x) {
    final Object[] items = this.items;
    items[putIndex] = x; 
    if (++putIndex == items.length)
        putIndex = 0;
    count++;
    notEmpty.signal();
}

在enqueue中玻佩，首先將元素放入數(shù)組中下標(biāo)為putIndex的位置，然后對(duì)putIndex自增席楚，并判斷是否已處于隊(duì)列中最后一個(gè)位置咬崔，如果putIndex索引位置等于數(shù)組的長(zhǎng)度時(shí)，那么將putIndex置為0烦秩，即下一次在元素入隊(duì)時(shí)刁赦，從隊(duì)列頭開(kāi)始放置。

舉個(gè)例子闻镶，假設(shè)有一個(gè)長(zhǎng)度為5的隊(duì)列，現(xiàn)在已經(jīng)有4個(gè)元素丸升，我們進(jìn)行下面一系列的操作铆农，來(lái)看一下索引下標(biāo)的變化：

image

上面這個(gè)例子提前用到了隊(duì)列中元素被移除時(shí)takeIndex會(huì)自增的知識(shí)點(diǎn)，通過(guò)這個(gè)例子中索引的變化，可以看出ArrayBlockingQueue就是一個(gè)循環(huán)隊(duì)列墩剖，takeIndex就相當(dāng)于隊(duì)列的頭指針猴凹，而putIndex相當(dāng)于隊(duì)列的尾指針的下一個(gè)位置索引。并且這里不需要擔(dān)心在隊(duì)列已滿(mǎn)時(shí)還會(huì)繼續(xù)向隊(duì)列中添加元素岭皂，因?yàn)樵?code>offer方法中會(huì)首先判斷隊(duì)列是否已滿(mǎn)郊霎，只有在隊(duì)列不滿(mǎn)時(shí)才會(huì)執(zhí)行enqueue方法。

面試官：這個(gè)過(guò)程我明白了爷绘，那enqueue方法里最后的notEmpty.signal()是什么意思书劝？

Hydra：這是一個(gè)喚醒操作，等后面講完它的掛起后再說(shuō)土至。我還是先把插入操作中的put方講完吧购对，看一下它的源碼：

public void put(E e) throws InterruptedException {
    checkNotNull(e);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == items.length)
            notFull.await();
        enqueue(e);
    } finally {
        lock.unlock();
    }
}

put方法是一個(gè)阻塞方法，當(dāng)隊(duì)列中元素未滿(mǎn)時(shí)陶因，會(huì)直接調(diào)用enqueue方法將元素加入隊(duì)列中骡苞。如果隊(duì)列已滿(mǎn)，就會(huì)調(diào)用notFull.await()方法將掛起當(dāng)前線程楷扬，直到隊(duì)列不滿(mǎn)時(shí)才會(huì)被喚醒解幽，繼續(xù)執(zhí)行插入操作。

當(dāng)隊(duì)列已滿(mǎn)烘苹，再執(zhí)行put操作時(shí)躲株，就會(huì)執(zhí)行下面的流程：

image

這里提前劇透一下，當(dāng)隊(duì)列中有元素被移除螟加，在調(diào)用dequeue方法中的notFull.signal()時(shí)徘溢，會(huì)喚醒等待隊(duì)列中的線程，并把對(duì)應(yīng)的元素添加到隊(duì)列中捆探，流程如下：

image

做一個(gè)總結(jié)然爆，在插入元素的幾個(gè)方法中，add黍图、offer以及帶有超時(shí)的offer方法都是非阻塞的曾雕，會(huì)立即返回或超時(shí)后立即返回，而put方法是阻塞的助被，只有當(dāng)隊(duì)列不滿(mǎn)添加成功后才會(huì)被返回剖张。

面試官：講的不錯(cuò)，講完插入操作了再講講移除操作吧

Hydra：還是老規(guī)矩揩环，先說(shuō)非阻塞的方法remove和poll搔弄，父類(lèi)的remove方法還是會(huì)調(diào)用子類(lèi)的poll方法，不同的是remove方法在隊(duì)列為空時(shí)拋出異常丰滑，而poll會(huì)直接返回null顾犹。這兩個(gè)方法的核心還是調(diào)用的dequeue方法，它的源碼如下：

private E dequeue() {
    final Object[] items = this.items;
    E x = (E) items[takeIndex];
    items[takeIndex] = null;
    if (++takeIndex == items.length)
        takeIndex = 0;
    count--;
    if (itrs != null)
        //更新迭代器中的元素
        itrs.elementDequeued();
    notFull.signal();
    return x;
}

在dequeue中，在獲取到數(shù)組下標(biāo)為takeIndex的元素炫刷，并將該位置置為null擎宝。將takeIndex自增后判斷是否與數(shù)組長(zhǎng)度相等，如果相等還是按之前循環(huán)隊(duì)列的理論浑玛，將它的索引置為0绍申，并將隊(duì)列的中的計(jì)數(shù)減1。

有一個(gè)隊(duì)列初始化時(shí)有5個(gè)元素顾彰，我們對(duì)齊分別進(jìn)行5次的出隊(duì)操作极阅，查看索引下標(biāo)的變化情況：

image

然后我們還是結(jié)合take方法來(lái)說(shuō)明線程的掛起和喚醒的操作，與put方法相對(duì)拘央，take用于阻塞獲取元素涂屁，來(lái)看一下它的源碼：

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == 0)
            notEmpty.await();
        return dequeue();
    } finally {
        lock.unlock();
    }
}

take是一個(gè)可以被中斷的阻塞獲取元素的方法，首先判斷隊(duì)列是否為空灰伟，如果隊(duì)列不為空那么就調(diào)用dequeue方法移除元素拆又，如果隊(duì)列為空時(shí)就調(diào)用notEmpty.await()就將當(dāng)前線程掛起，直到有其他的線程調(diào)用了enqueue方法栏账，才會(huì)喚醒等待隊(duì)列中被掛起的線程帖族。可以參考下面的圖來(lái)理解：

image

當(dāng)有其他線程向隊(duì)列中插入元素后：

image

入隊(duì)的enqueue方法會(huì)調(diào)用notEmpty.signal()挡爵，喚醒等待隊(duì)列中firstWaiter指向的節(jié)中的線程竖般，并且該線程會(huì)調(diào)用dequeue完成元素的出隊(duì)操作。到這移除的操作就也分析完了茶鹃，至于開(kāi)頭為什么說(shuō)ArrayBlockingQueue是線程安全的涣雕，看到每個(gè)方法前都通過(guò)全局單例的lock加鎖，相信你也應(yīng)該明白了

面試官：好了闭翩，ArrayBlockingQueue我懂了挣郭，我先去吃個(gè)飯，回來(lái)咱們?cè)倭牧膭e的集合

Hydra：……

image

如果文章對(duì)您有所幫助疗韵，歡迎關(guān)注公眾號(hào) 碼農(nóng)參上兑障，第一時(shí)間推送面試文章

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市蕉汪，隨后出現(xiàn)的幾起案子流译，更是在濱河造成了極大的恐慌，老刑警劉巖者疤，帶你破解...
    沈念sama閱讀 218,546評(píng)論 6贊 507
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件福澡，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡驹马，警方通過(guò)查閱死者的電腦和手機(jī)竞漾，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,224評(píng)論 3贊 395
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門(mén)眯搭，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人业岁，你說(shuō)我怎么就攤上這事】芪茫” “怎么了笔时？”我有些...
    開(kāi)封第一講書(shū)人閱讀 164,911評(píng)論 0贊 354
  • 道士緝兇錄：失蹤的賣(mài)姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長(zhǎng)仗岸。 經(jīng)常有香客問(wèn)我允耿，道長(zhǎng)，這世上最難降的妖魔是什么扒怖？ 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,737評(píng)論 1贊 294
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任盗痒，我火速辦了婚禮鸟整，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘朦蕴。我一直安慰自己篮条，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,753評(píng)論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開(kāi)白布吩抓。 她就那樣靜靜地躺著涉茧，像睡著了一般。 火紅的嫁衣襯著肌膚如雪琴拧。 梳的紋絲不亂的頭發(fā)上降瞳，一...
    開(kāi)封第一講書(shū)人閱讀 51,598評(píng)論 1贊 305
  • 城市分裂傳說(shuō)
    那天，我揣著相機(jī)與錄音蚓胸，去河邊找鬼挣饥。 笑死，一個(gè)胖子當(dāng)著我的面吹牛沛膳，可吹牛的內(nèi)容都是我干的扔枫。 我是一名探鬼主播，決...
    沈念sama閱讀 40,338評(píng)論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開(kāi)眼锹安，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼短荐！你這毒婦竟也來(lái)了倚舀？” 一聲冷哼從身側(cè)響起，我...
    開(kāi)封第一講書(shū)人閱讀 39,249評(píng)論 0贊 276
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤忍宋，失蹤者是張志新（化名）和其女友劉穎痕貌，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體糠排，經(jīng)...
    沈念sama閱讀 45,696評(píng)論 1贊 314
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡舵稠，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,888評(píng)論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了入宦。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片哺徊。...
    茶點(diǎn)故事閱讀 40,013評(píng)論 1贊 348
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖乾闰，靈堂內(nèi)的尸體忽然破棺而出落追，到底是詐尸還是另有隱情，我是刑警寧澤涯肩，帶...
    沈念sama閱讀 35,731評(píng)論 5贊 346
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布轿钠，位于F島的核電站，受9級(jí)特大地震影響宽菜，放射性物質(zhì)發(fā)生泄漏谣膳。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,348評(píng)論 3贊 330
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一铅乡、第九天 我趴在偏房一處隱蔽的房頂上張望继谚。 院中可真熱鬧，春花似錦阵幸、人聲如沸花履。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,929評(píng)論 0贊 22
  • 一樁弒父案挚赊，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)诡壁。三九已至，卻和暖如春荠割，著一層夾襖步出監(jiān)牢的瞬間妹卿，已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,048評(píng)論 1贊 270
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工蔑鹦， 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留夺克，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,203評(píng)論 3贊 370
  • 代替公主和親
    正文 我出身青樓嚎朽，卻偏偏與公主長(zhǎng)得像铺纽，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子哟忍，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,960評(píng)論 2贊 355

推薦閱讀更多精彩內(nèi)容