原創(chuàng)文章&經(jīng)驗總結(jié)&從校招到A廠一路陽光一路滄桑

詳情請戳www.codercc.com

image

1.ConcurrentLinkedQueue簡介

在單線程編程中我們會經(jīng)常用到一些集合類毕箍，比如ArrayList,HashMap等磨淌，但是這些類都不是線程安全的類宏蛉。在面試中也經(jīng)常會有一些考點奥吩，比如ArrayList不是線程安全的时捌，Vector是線程安全亏吝。而保障Vector線程安全的方式店诗，是非常粗暴的在方法上用synchronized獨占鎖裹刮，將多線程執(zhí)行變成串行化。要想將ArrayList變成線程安全的也可以使用Collections.synchronizedList(List<T> list)方法ArrayList轉(zhuǎn)換成線程安全的庞瘸，但這種轉(zhuǎn)換方式依然是通過synchronized修飾方法實現(xiàn)的捧弃，很顯然這不是一種高效的方式，同時擦囊，隊列也是我們常用的一種數(shù)據(jù)結(jié)構(gòu)违霞，為了解決線程安全的問題，Doug Lea大師為我們準(zhǔn)備了ConcurrentLinkedQueue這個線程安全的隊列瞬场。從類名就可以看的出來實現(xiàn)隊列的數(shù)據(jù)結(jié)構(gòu)是鏈?zhǔn)健?/p>

1.1 Node

要想先學(xué)習(xí)ConcurrentLinkedQueue自然而然得先從它的節(jié)點類看起买鸽，明白它的底層數(shù)據(jù)結(jié)構(gòu)。Node類的源碼為：

private static class Node<E> {
        volatile E item;
        volatile Node<E> next;
        .......
}

Node節(jié)點主要包含了兩個域：一個是數(shù)據(jù)域item贯被，另一個是next指針癞谒，用于指向下一個節(jié)點從而構(gòu)成鏈?zhǔn)疥犃小２⑶叶际怯胿olatile進(jìn)行修飾的刃榨，以保證內(nèi)存可見性（關(guān)于volatile可以看這篇文章）弹砚。另外ConcurrentLinkedQueue含有這樣兩個成員變量：

private transient volatile Node<E> head;
private transient volatile Node<E> tail;

說明ConcurrentLinkedQueue通過持有頭尾指針進(jìn)行管理隊列。當(dāng)我們調(diào)用無參構(gòu)造器時枢希，其源碼為：

public ConcurrentLinkedQueue() {
    head = tail = new Node<E>(null);
}

head和tail指針會指向一個item域為null的節(jié)點,此時ConcurrentLinkedQueue狀態(tài)如下圖所示：

如圖桌吃，head和tail指向同一個節(jié)點Node0，該節(jié)點item域為null,next域為null苞轿。

1.ConcurrentLinkedQueue初始化狀態(tài).png

1.2 操作Node的幾個CAS操作

在隊列進(jìn)行出隊入隊的時候免不了對節(jié)點需要進(jìn)行操作茅诱，在多線程就很容易出現(xiàn)線程安全的問題“嶙洌可以看出在處理器指令集能夠支持CMPXCHG指令后瑟俭，在java源碼中涉及到并發(fā)處理都會使用CAS操作(關(guān)于CAS操作可以看這篇文章的第3.1節(jié))，那么在ConcurrentLinkedQueue對Node的CAS操作有這樣幾個：

//更改Node中的數(shù)據(jù)域item   
boolean casItem(E cmp, E val) {
    return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
}
//更改Node中的指針域next
void lazySetNext(Node<E> val) {
    UNSAFE.putOrderedObject(this, nextOffset, val);
}
//更改Node中的指針域next
boolean casNext(Node<E> cmp, Node<E> val) {
    return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
}

可以看出這些方法實際上是通過調(diào)用UNSAFE實例的方法契邀，UNSAFE為sun.misc.Unsafe類摆寄，該類是hotspot底層方法，目前為止了解即可，知道CAS的操作歸根結(jié)底是由該類提供就好微饥。

2.offer方法

對一個隊列來說逗扒，插入滿足FIFO特性，插入元素總是在隊列最末尾的地方進(jìn)行插入欠橘，而染丶纭（移除）元素總是從隊列的隊頭。所有要想能夠徹底弄懂ConcurrentLinkedQueue自然而然是從offer方法和poll方法開始肃续。那么為了能夠理解offer方法黍檩，采用debug的方式來一行一行的看代碼走。另外始锚，在看多線程的代碼時刽酱，可采用這樣的思維方式：

單個線程offer
多個線程offer
部分線程offer，部分線程poll
----offer的速度快于poll
--------隊列長度會越來越長疼蛾，由于offer節(jié)點總是在對隊列隊尾肛跌，而poll節(jié)點總是在隊列對頭，也就是說offer線程和poll線程兩者并無“交集”察郁，也就是說兩類線程間并不會相互影響衍慎，這種情況站在相對速率的角度來看，也就是一個"單線程offer"
----offer的速度慢于poll
--------poll的相對速率快于offer皮钠，也就是隊頭刪的速度要快于隊尾添加節(jié)點的速度稳捆，導(dǎo)致的結(jié)果就是隊列長度會越來越短，而offer線程和poll線程就會出現(xiàn)“交集”麦轰，即那一時刻就可以稱之為offer線程和poll線程同時操作的節(jié)點為 臨界點 乔夯，且在該節(jié)點offer線程和poll線程必定相互影響。根據(jù)在臨界點時offer和poll發(fā)生的相對順序又可從兩個角度去思考：1. 執(zhí)行順序為offer-->poll-->offer款侵，即表現(xiàn)為當(dāng)offer線程在Node1后插入Node2時末荐，此時poll線程已經(jīng)將Node1刪除，這種情況很顯然需要在offer方法中考慮新锈； 2.執(zhí)行順序可能為：poll-->offer-->poll甲脏，即表現(xiàn)為當(dāng)poll線程準(zhǔn)備刪除的節(jié)點為null時（隊列為空隊列），此時offer線程插入一個節(jié)點使得隊列變?yōu)榉强贞犃?/p>

先看這么一段代碼：

1. ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();
2. queue.offer(1);
3. queue.offer(2);

創(chuàng)建一個ConcurrentLinkedQueue實例妹笆，先offer 1块请，然后再offer 2。offer的源碼為：

public boolean offer(E e) {
1.    checkNotNull(e);
2.    final Node<E> newNode = new Node<E>(e);

3.    for (Node<E> t = tail, p = t;;) {
4.        Node<E> q = p.next;
5.        if (q == null) {
6.            // p is last node
7.            if (p.casNext(null, newNode)) {
                // Successful CAS is the linearization point
                // for e to become an element of this queue,
               // and for newNode to become "live".
8.                if (p != t) // hop two nodes at a time
9.                    casTail(t, newNode);  // Failure is OK.
10.                return true;
            }
            // Lost CAS race to another thread; re-read next
        }
11.        else if (p == q)
            // We have fallen off list.  If tail is unchanged, it
            // will also be off-list, in which case we need to
            // jump to head, from which all live nodes are always
            // reachable.  Else the new tail is a better bet.
12.            p = (t != (t = tail)) ? t : head;
           else
            // Check for tail updates after two hops.
13.            p = (p != t && t != (t = tail)) ? t : q;
    }
}

單線程執(zhí)行角度分析：

先從單線程執(zhí)行的角度看起拳缠，分析offer 1的過程墩新。第1行代碼會對是否為null進(jìn)行判斷，為null的話就直接拋出空指針異常窟坐，第2行代碼將e包裝成一個Node類海渊，第3行為for循環(huán)绵疲，只有初始化條件沒有循環(huán)結(jié)束條件，這很符合CAS的“套路”切省，在循環(huán)體CAS操作成功會直接return返回最岗，如果CAS操作失敗的話就在for循環(huán)中不斷重試直至成功帕胆。這里實例變量t被初始化為tail朝捆，p被初始化為t即tail。為了方便下面的理解懒豹，p被認(rèn)為隊列真正的尾節(jié)點芙盘，tail不一定指向?qū)ο笳嬲奈补?jié)點，因為在ConcurrentLinkedQueue中tail是被延遲更新的脸秽，具體原因我們慢慢來看儒老。代碼走到第3行的時候，t和p都分別指向初始化時創(chuàng)建的item域為null记餐，next域為null的Node0驮樊。第4行變量q被賦值為null，第5行if判斷為true片酝，在第7行使用casNext將插入的Node設(shè)置成當(dāng)前隊列尾節(jié)點p的next節(jié)點囚衔，如果CAS操作失敗，此次循環(huán)結(jié)束在下次循環(huán)中進(jìn)行重試雕沿。CAS操作成功走到第8行练湿，此時p==t，if判斷為false,直接return true返回审轮。如果成功插入1的話肥哎，此時ConcurrentLinkedQueue的狀態(tài)如下圖所示：

2.offer 1后隊列的狀態(tài).png

如圖，此時隊列的尾節(jié)點應(yīng)該為Node1,而tail指向的節(jié)點依然還是Node0,因此可以說明tail是延遲更新的疾渣。那么我們繼續(xù)來看offer 2的時候的情況篡诽，很顯然此時第4行q指向的節(jié)點不為null了，而是指向Node1,第5行if判斷為false,第11行if判斷為false,代碼會走到第13行榴捡。好了杈女，再插入節(jié)點的時候我們會問自己這樣一個問題？上面已經(jīng)解釋了tail并不是指向隊列真正的尾節(jié)點薄疚，那么在插入節(jié)點的時候碧信，我們是不是應(yīng)該最開始做的就是找到隊列當(dāng)前的尾節(jié)點在哪里才能插入？那么第13行代碼就是找出隊列真正的尾節(jié)點街夭。

定位隊列真正的對尾節(jié)點

p = (p != t && t != (t = tail)) ? t : q;

我們來分析一下這行代碼砰碴，如果這段代碼在單線程環(huán)境執(zhí)行時，很顯然由于p==t,此時p會被賦值為q,而q等于Node<E> q = p.next板丽，即Node1呈枉。在第一次循環(huán)中指針p指向了隊列真正的隊尾節(jié)點Node1趁尼，那么在下一次循環(huán)中第4行q指向的節(jié)點為null，那么在第5行中if判斷為true,那么在第7行依然通過casNext方法設(shè)置p節(jié)點的next為當(dāng)前新增的Node,接下來走到第8行猖辫，這個時候p!=t酥泞，第8行if判斷為true,會通過casTail(t, newNode)將當(dāng)前節(jié)點Node設(shè)置為隊列的隊尾節(jié)點,此時的隊列狀態(tài)示意圖如下圖所示：

3.隊列offer 2后的狀態(tài).png

tail指向的節(jié)點由Node0改變?yōu)镹ode2,這里的casTail失敗不需要重試的原因是，offer代碼中主要是通過p的next節(jié)點q(Node<E> q = p.next)決定后面的邏輯走向的啃憎，當(dāng)casTail失敗時狀態(tài)示意圖如下：

4.隊列進(jìn)行入隊操作后casTail失敗后的狀態(tài)圖.png

如圖芝囤，如果這里casTail設(shè)置tail失敗即tail還是指向Node0節(jié)點的話，無非就是多循環(huán)幾次通過13行代碼定位到隊尾節(jié)點辛萍。

通過對單線程執(zhí)行角度進(jìn)行分析悯姊，我們可以了解到poll的執(zhí)行邏輯為：

1. 如果tail指向的節(jié)點的下一個節(jié)點（next域）為null的話，說明tail指向的節(jié)點即為隊列真正的隊尾節(jié)點贩毕，因此可以通過casNext插入當(dāng)前待插入的節(jié)點,但此時tail并未變化悯许，如圖2;

2. 如果tail指向的節(jié)點的下一個節(jié)點（next域）不為null的話，說明tail指向的節(jié)點不是隊列的真正隊尾節(jié)點辉阶。通過q（Node<E> q = p.next）指針往前遞進(jìn)去找到隊尾節(jié)點先壕，然后通過casNext插入當(dāng)前待插入的節(jié)點，并通過casTail方式更改tail谆甜，如圖3垃僚。

我們回過頭再來看p = (p != t && t != (t = tail)) ? t : q;這行代碼在單線程中，這段代碼永遠(yuǎn)不會將p賦值為t,那么這么寫就不會有任何作用店印，那我們試著在多線程的情況下進(jìn)行分析冈在。

多線程執(zhí)行角度分析

多個線程offer

很顯然這么寫另有深意，其實在多線程環(huán)境下這行代碼很有意思的按摘。 t != (t = tail)這個操作并非一個原子操作包券，有這樣一種情況：

5.線程A和線程B有可能的執(zhí)行時序.png

如圖，假設(shè)線程A此時讀取了變量t炫贤，線程B剛好在這個時候offer一個Node后溅固，此時會修改tail指針,那么這個時候線程A再次執(zhí)行t=tail時t會指向另外一個節(jié)點，很顯然線程A前后兩次讀取的變量t指向的節(jié)點不相同兰珍，即t != (t = tail)為true,并且由于t指向節(jié)點的變化p != t也為true侍郭，此時該行代碼的執(zhí)行結(jié)果為p和t最新的t指針指向了同一個節(jié)點，并且此時t也是隊列真正的對尾節(jié)點掠河。那么亮元，現(xiàn)在已經(jīng)定位到隊列真正的隊尾節(jié)點，就可以執(zhí)行offer操作了唠摹。

offer->poll->offer

那么還剩下第11行的代碼我們沒有分析爆捞，大致可以猜想到應(yīng)該就是回答一部分線程offer，一部分poll的這種情況勾拉。當(dāng)if (p == q)為true時煮甥，說明p指向的節(jié)點的next也指向它自己盗温，這種節(jié)點稱之為哨兵節(jié)點成肘，這種節(jié)點在隊列中存在的價值不大，一般表示為要刪除的節(jié)點或者是空節(jié)點双霍。為了能夠很好的理解這種情況，我們先看看poll方法的執(zhí)行過程后蟹演，再回過頭來看风钻，總之這是一個很有意思的事情 :)。

3.poll方法

poll方法源碼如下：

public E poll() {
    restartFromHead:
    1. for (;;) {
    2.    for (Node<E> h = head, p = h, q;;) {
    3.        E item = p.item;

    4.        if (item != null && p.casItem(item, null)) {
                // Successful CAS is the linearization point
                // for item to be removed from this queue.
    5.            if (p != h) // hop two nodes at a time
    6.                updateHead(h, ((q = p.next) != null) ? q : p);
    7.            return item;
            }
    8.        else if ((q = p.next) == null) {
    9.            updateHead(h, p);
    10.            return null;
            }
    11.        else if (p == q)
    12.            continue restartFromHead;
            else
    13.            p = q;
        }
    }
}

我們還是先站在單線程的角度去理清該方法的基本邏輯鸣个。假設(shè)ConcurrentLinkedQueue初始狀態(tài)如下圖所示：

6.隊列初始狀態(tài).png

參數(shù)offer時的定義布朦，我們還是先將變量p作為隊列要刪除真正的隊頭節(jié)點，h（head）指向的節(jié)點并不一定是隊列的隊頭節(jié)點涛舍。先來看poll出Node1時的情況，由于p=h=head唆途，參照上圖富雅，很顯然此時p指向的Node1的數(shù)據(jù)域不為null,在第4行代碼中item!=null判斷為true后接下來通過casItem將Node1的數(shù)據(jù)域設(shè)置為null。如果CAS設(shè)置失敗則此次循環(huán)結(jié)束等待下一次循環(huán)進(jìn)行重試肛搬。若第4行執(zhí)行成功進(jìn)入到第5行代碼没佑，此時p和h都指向Node1,第5行if判斷為false,然后直接到第7行return回Node1的數(shù)據(jù)域1，方法運行結(jié)束温赔，此時的隊列狀態(tài)如下圖蛤奢。

7.隊列出隊操作后的狀態(tài).png

下面繼續(xù)從隊列中poll，很顯然當(dāng)前h和p指向的Node1的數(shù)據(jù)域為null陶贼，那么第一件事就是要定位準(zhǔn)備刪除的隊頭節(jié)點(找到數(shù)據(jù)域不為null的節(jié)點)啤贩。

定位刪除的隊頭節(jié)點

繼續(xù)看，第三行代碼item為null,第4行代碼if判斷為false,走到第8行代碼（q = p.next）if也為false拜秧，由于q指向了Node2,在第11行的if判斷也為false痹屹，因此代碼走到了第13行，這個時候p和q共同指向了Node2,也就找到了要刪除的真正的隊頭節(jié)點腹纳×÷樱可以總結(jié)出驱犹，定位待刪除的隊頭節(jié)點的過程為：如果當(dāng)前節(jié)點的數(shù)據(jù)域為null，很顯然該節(jié)點不是待刪除的節(jié)點足画，就用當(dāng)前節(jié)點的下一個節(jié)點去試探雄驹。在經(jīng)過第一次循環(huán)后，此時狀態(tài)圖為下圖：

8.經(jīng)過一次循環(huán)后的狀態(tài).png

進(jìn)行下一次循環(huán)淹辞，第4行的操作同上述医舆，當(dāng)前假設(shè)第4行中casItem設(shè)置成功，由于p已經(jīng)指向了Node2,而h還依舊指向Node1,此時第5行的if判斷為true象缀，然后執(zhí)行updateHead(h, ((q = p.next) != null) ? q : p)蔬将，此時q指向的Node3，所有傳入updateHead方法的分別是指向Node1的h引用和指向Node3的q引用央星。updateHead方法的源碼為：

final void updateHead(Node<E> h, Node<E> p) {
    if (h != p && casHead(h, p))
        h.lazySetNext(h);
}

該方法主要是通過casHead將隊列的head指向Node3,并且通過 h.lazySetNext將Node1的next域指向它自己霞怀。最后在第7行代碼中返回Node2的值毙石。此時隊列的狀態(tài)如下圖所示：

9.Node2從隊列中出隊后的狀態(tài).png

Node1的next域指向它自己徐矩，head指向了Node3滤灯。如果隊列為空隊列的話鳞骤，就會執(zhí)行到代碼的第8行(q = p.next) == null弟孟，if判斷為true,因此在第10行中直接返回null拂募。以上的分析是從單線程執(zhí)行的角度去看陈症，也可以讓我們了解poll的整體思路录肯，現(xiàn)在來做一個總結(jié)：

1. 如果當(dāng)前head,h和p指向的節(jié)點的Item不為null的話论咏，說明該節(jié)點即為真正的隊頭節(jié)點（待刪除節(jié)點）厅贪，只需要通過casItem方法將item域設(shè)置為null,然后將原來的item直接返回即可养涮。

2. 如果當(dāng)前head,h和p指向的節(jié)點的item為null的話贯吓，則說明該節(jié)點不是真正的待刪除節(jié)點悄谐，那么應(yīng)該做的就是尋找item不為null的節(jié)點尊沸。通過讓q指向p的下一個節(jié)點（q = p.next）進(jìn)行試探洼专，若找到則通過updateHead方法更新head指向的節(jié)點以及構(gòu)造哨兵節(jié)點（通過updateHead方法的h.lazySetNext(h)）屁商。

接下來蜡镶，按照上面分析offer的思維方式官还，下面來分析一下多線程的情況望伦，第一種情況是屯伞；

多線程執(zhí)行情況分析：

多個線程poll

現(xiàn)在回過頭來看poll方法的源碼劣摇，有這樣一部分：

else if (p == q)
    continue restartFromHead;

這一部分就是處理多個線程poll的情況钧惧，q = p.next也就是說q永遠(yuǎn)指向的是p的下一個節(jié)點垢乙，那么什么情況下會使得p,q指向同一個節(jié)點呢追逮？根據(jù)上面我們的分析钮孵，只有p指向的節(jié)點在poll的時候轉(zhuǎn)變成了哨兵節(jié)點（通過updateHead方法中的h.lazySetNext）巴席。當(dāng)線程A在判斷p==q時漾唉，線程B已經(jīng)將執(zhí)行完poll方法將p指向的節(jié)點轉(zhuǎn)換為哨兵節(jié)點并且head指向的節(jié)點已經(jīng)發(fā)生了改變赵刑，所以就需要從restartFromHead處執(zhí)行般此，保證用到的是最新的head铐懊。

poll->offer->poll

試想科乎，還有這樣一種情況茅茂，如果當(dāng)前隊列為空隊列玉吁，線程A進(jìn)行poll操作进副，同時線程B執(zhí)行offer影斑，然后線程A在執(zhí)行poll矫户，那么此時線程A返回的是null還是線程B剛插入的最新的那個節(jié)點呢皆辽？我們來寫一代demo：

public static void main(String[] args) {
    Thread thread1 = new Thread(() -> {
        Integer value = queue.poll();
        System.out.println(Thread.currentThread().getName() + " poll 的值為：" + value);
        System.out.println("queue當(dāng)前是否為空隊列：" + queue.isEmpty());
    });
    thread1.start();
    Thread thread2 = new Thread(() -> {
        queue.offer(1);
    });
    thread2.start();
}

輸出結(jié)果為：

Thread-0 poll 的值為：null
queue當(dāng)前是否為空隊列：false

通過debug控制線程thread1和線程thread2的執(zhí)行順序耻台，thread1先執(zhí)行到第8行代碼if ((q = p.next) == null)盆耽，由于此時隊列為空隊列if判斷為true摄杂，進(jìn)入if塊析恢，此時先讓thread1暫停氮昧，然后thread2進(jìn)行offer插入值為1的節(jié)點后，thread2執(zhí)行結(jié)束咪辱。再讓thread1執(zhí)行油狂，這時thread1并沒有進(jìn)行重試专筷，而是代碼繼續(xù)往下走磷蛹，返回null味咳，盡管此時隊列由于thread2已經(jīng)插入了值為1的新的節(jié)點檬嘀。所以輸出結(jié)果為thread0 poll的為null,然隊列不為空隊列鸳兽。因此揍异，在判斷隊列是否為空隊列的時候是不能通過線程在poll的時候返回為null進(jìn)行判斷的衷掷，可以通過isEmpty方法進(jìn)行判斷棍鳖。

4. offer方法中部分線程offer部分線程poll

在分析offer方法的時候我們還留下了一個問題渡处，即對offer方法中第11行代碼的理解医瘫。

offer->poll->offer

在offer方法的第11行代碼if (p == q)醇份，能夠讓if判斷為true的情況為p指向的節(jié)點為哨兵節(jié)點僚纷，而什么時候會構(gòu)造哨兵節(jié)點呢怖竭？在對poll方法的討論中痊臭，我們已經(jīng)找到了答案广匙，即當(dāng)head指向的節(jié)點的item域為null時會尋找真正的隊頭節(jié)點鸦致，等到待插入的節(jié)點插入之后鲁纠，會更新head改含，并且將原來head指向的節(jié)點設(shè)置為哨兵節(jié)點迄汛。假設(shè)隊列初始狀態(tài)如下圖所示：

10.offer和poll相互影響分析時隊列初始狀態(tài).png

11.線程A和線程B可能存在的執(zhí)行時序.png

如圖盗扇，線程A的tail節(jié)點存在next節(jié)點Node1,因此會通過引用q往前尋找隊列真正的隊尾節(jié)點疗隶，當(dāng)執(zhí)行到判斷if (p == q)時翼闹，此時線程B執(zhí)行poll操作坚弱，在對線程B來說关摇，head和p指向Node0,由于Node0的item域為null,同樣會往前遞進(jìn)找到隊列真正的隊頭節(jié)點Node1,在線程B執(zhí)行完poll之后停撞，Node0就會轉(zhuǎn)換為哨兵節(jié)點悼瓮，也就意味著隊列的head發(fā)生了改變，此時隊列狀態(tài)為下圖命贴。

12.線程B進(jìn)行poll后隊列的狀態(tài)圖.png

此時線程A在執(zhí)行判斷if (p == q)時就為true,會繼續(xù)執(zhí)行p = (t != (t = tail)) ? t : head;胸蛛，由于tail指針沒有發(fā)生改變所以p被賦值為head,重新從head開始完成插入操作泞当。

5. HOPS的設(shè)計

通過上面對offer和poll方法的分析襟士，我們發(fā)現(xiàn)tail和head是延遲更新的陋桂，兩者更新觸發(fā)時機(jī)為：

tail更新觸發(fā)時機(jī)：當(dāng)tail指向的節(jié)點的下一個節(jié)點不為null的時候嗜历，會執(zhí)行定位隊列真正的隊尾節(jié)點的操作梨州，找到隊尾節(jié)點后完成插入之后才會通過casTail進(jìn)行tail更新摊唇；當(dāng)tail指向的節(jié)點的下一個節(jié)點為null的時候巷查，只插入節(jié)點不更新tail岛请。

head更新觸發(fā)時機(jī)：當(dāng)head指向的節(jié)點的item域為null的時候警绩，會執(zhí)行定位隊列真正的隊頭節(jié)點的操作肩祥，找到隊頭節(jié)點后完成刪除之后才會通過updateHead進(jìn)行head更新混狠；當(dāng)head指向的節(jié)點的item域不為null的時候贡避，只刪除節(jié)點不更新head刮吧。

并且在更新操作時，源碼中會有注釋為：hop two nodes at a time。所以這種延遲更新的策略就被叫做HOPS的大概原因是這個（猜的 :)）旗笔，從上面更新時的狀態(tài)圖可以看出拄踪，head和tail的更新是“跳著的”即中間總是間隔了一個撮弧。那么這樣設(shè)計的意圖是什么呢贿衍？

如果讓tail永遠(yuǎn)作為隊列的隊尾節(jié)點救恨，實現(xiàn)的代碼量會更少贸辈，而且邏輯更易懂。但是肠槽，這樣做有一個缺點擎淤，如果大量的入隊操作，每次都要執(zhí)行CAS進(jìn)行tail的更新秸仙，匯總起來對性能也會是大大的損耗嘴拢。如果能減少CAS更新的操作，無疑可以大大提升入隊的操作效率寂纪，所以doug lea大師每間隔1次（tail和隊尾節(jié)點的距離為1）進(jìn)行才利用CAS更新tail席吴。對head的更新也是同樣的道理孝冒，雖然捣域，這樣設(shè)計會多出在循環(huán)中定位隊尾節(jié)點，但總體來說讀的操作效率要遠(yuǎn)遠(yuǎn)高于寫的性能该窗，因此，多出來的在循環(huán)中定位尾節(jié)點的操作的性能損耗相對而言是很小的。

參考資料

《java并發(fā)編程的藝術(shù)》
《Java高并發(fā)程序設(shè)計》
ConcurrentLinkedQueue博文：https://www.cnblogs.com/sunshine-2015/p/6067709.html