Java源碼刨析之ArrayDeque

更新時間：2022年07月22日 10:58:26 作者：一無是處的研究僧

ArrayDeque是Deque接口的一個實現(xiàn)，使用了可變數(shù)組，所以沒有容量上的限制。同時,?ArrayDeque是線程不安全的，在沒有外部同步的情況下，不能再多線程環(huán)境下使用<BR>

前言

在本篇文章當(dāng)中主要跟大家介紹JDK給我們提供的一種用數(shù)組實現(xiàn)的雙端隊列，在之前的文章LinkedList源碼剖析當(dāng)中我們已經(jīng)介紹了一種雙端隊列，不過與ArrayDeque不同的是，LinkedList的雙端隊列使用雙向鏈表實現(xiàn)的。

雙端隊列整體分析

我們通常所談?wù)摰降年犃卸际且欢诉M(jìn)一端出，而雙端隊列的兩端則都是可進(jìn)可出。下面是雙端隊列的幾個操作：

數(shù)據(jù)從雙端隊列左側(cè)進(jìn)入。

數(shù)據(jù)從雙端隊列右側(cè)進(jìn)入。

數(shù)據(jù)從雙端隊列左側(cè)彈出。

數(shù)據(jù)從雙端隊列右側(cè)彈出。

而在ArrayDeque當(dāng)中也給我們提供了對應(yīng)的方法去實現(xiàn)，比如下面這個例子就是上圖對應(yīng)的代碼操作：

public void test() {
    ArrayDeque<Integer> deque = new ArrayDeque<>();
    deque.addLast(100);
    System.out.println(deque);
    deque.addFirst(55);
    System.out.println(deque);
    deque.addLast(-55);
    System.out.println(deque);
    deque.removeFirst();
    System.out.println(deque);
    deque.removeLast();
    System.out.println(deque);
}

// 輸出結(jié)果
[100]
[55, 100]
[55, 100, -55]
[100, -55]
[100]

數(shù)組實現(xiàn)ArrayDeque(雙端隊列)的原理

ArrayDeque底層是使用數(shù)組實現(xiàn)的，而且數(shù)組的長度必須是2的整數(shù)次冪，這么操作的原因是為了后面位運算好操作。在ArrayDeque當(dāng)中有兩個整形變量head和tail，分別指向右側(cè)的第一個進(jìn)入隊列的數(shù)據(jù)和左側(cè)第一個進(jìn)行隊列的數(shù)據(jù)，整個內(nèi)存布局如下圖所示：

其中tail指的位置沒有數(shù)據(jù)，head指的位置存在數(shù)據(jù)。

當(dāng)我們需要從左往右增加數(shù)據(jù)時（入隊），內(nèi)存當(dāng)中數(shù)據(jù)變化情況如下：

當(dāng)我們需要從右往做左增加數(shù)據(jù)時（入隊），內(nèi)存當(dāng)中數(shù)據(jù)變化情況如下：

當(dāng)我們需要從右往左刪除數(shù)據(jù)時（出隊），內(nèi)存當(dāng)中數(shù)據(jù)變化情況如下：

當(dāng)我們需要從左往右刪除數(shù)據(jù)時（出隊），內(nèi)存當(dāng)中數(shù)據(jù)變化情況如下：

底層數(shù)據(jù)遍歷順序和邏輯順序

上面主要談?wù)摰降臄?shù)組在內(nèi)存當(dāng)中的布局，但是他是具體的物理存儲數(shù)據(jù)的順序，這個順序和我們的邏輯上的順序是不一樣的，根據(jù)上面的插入順序，我們可以畫出下面的圖，大家可以仔細(xì)分析一下這個圖的順序問題。

上圖當(dāng)中隊列左側(cè)的如隊順序是0, 1, 2, 3，右側(cè)入隊的順序為15, 14, 13, 12, 11, 10, 9, 8，因此在邏輯上我們的隊列當(dāng)中的數(shù)據(jù)布局如下圖所示：

根據(jù)前面一小節(jié)談到的輸入在入隊的時候數(shù)組當(dāng)中數(shù)據(jù)的變化我們可以知道，數(shù)據(jù)在數(shù)組當(dāng)中的布局為：

ArrayDeque類關(guān)鍵字段分析

// 底層用于存儲具體數(shù)據(jù)的數(shù)組
transient Object[] elements;
// 這就是前面談到的 head
transient int head;
// 與上文談到的 tail 含義一樣
transient int tail;
// MIN_INITIAL_CAPACITY 表示數(shù)組 elements 的最短長度
private static final int MIN_INITIAL_CAPACITY = 8;

以上就是ArrayDeque當(dāng)中的最主要的字段，其含義還是比較容易理解的！

ArrayDeque構(gòu)造函數(shù)分析

默認(rèn)構(gòu)造函數(shù)，數(shù)組默認(rèn)申請的長度為16。

public ArrayDeque() {
    elements = new Object[16];
}

指定數(shù)組長度的初始化長度，下面列出了改構(gòu)造函數(shù)涉及的所有函數(shù)。

public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}
private static int calculateSize(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // Find the best power of two to hold elements.
    // Tests "<=" because arrays aren't kept full.
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;
        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    return initialCapacity;
}

上面的最難理解的就是函數(shù)calculateSize了，他的主要作用是如果用戶輸入的長度小于MIN_INITIAL_CAPACITY時，返回MIN_INITIAL_CAPACITY。否則返回比initialCapacity大的第一個是2的整數(shù)冪的整數(shù)，比如說如果輸入的是9返回的16，輸入4返回8。

calculateSize的代碼還是很難理解的，讓我們一點一點的來分析。首先我們使用一個2的整數(shù)次冪的數(shù)進(jìn)行上面移位操作的操作！

從上圖當(dāng)中我們會發(fā)現(xiàn)，我們在一個數(shù)的二進(jìn)制數(shù)的32位放一個1，經(jīng)過移位之后最終32位的比特數(shù)字全部變成了1。根據(jù)上面數(shù)字變化的規(guī)律我們可以發(fā)現(xiàn)，任何一個比特經(jīng)過上面移位的變化，這個比特后面的31個比特位都會變成1，像下圖那樣：

因此上述的移位操作的結(jié)果只取決于最高一位的比特值為1，移位操作后它后面的所有比特位的值全為1，而在上面函數(shù)的最后，我們返回的結(jié)果就是上面移位之后的結(jié)果 +1。又因為移位之后最高位的1到最低位的1之間的比特值全為1，當(dāng)我們+1之后他會不斷的進(jìn)位，最終只有一個比特位置是1，因此它是2的整數(shù)倍。

經(jīng)過上述過程分析，我們就可以立即函數(shù)calculateSize了。

ArrayDeque關(guān)鍵函數(shù)分析

addLast函數(shù)分析

// tail 的初始值為 0 
public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    // 這里進(jìn)行的 & 位運算 相當(dāng)于取余數(shù)操作
    // (tail + 1) & (elements.length - 1) == (tail + 1) % elements.length
    // 這個操作主要是用于判斷數(shù)組是否滿了，如果滿了則需要擴(kuò)容
    // 同時這個操作將 tail + 1，即 tail = tail + 1
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

代碼(tail + 1) & (elements.length - 1) == (tail + 1) % elements.length成立的原因是任意一個數(shù) a a a對 2 n 2^n 2n進(jìn)行取余數(shù)操作和 a a a跟 2 n − 1 2^n - 1 2n−1進(jìn)行&運算的結(jié)果相等，即：

從上面的代碼來看下標(biāo)為tail的位置是沒有數(shù)據(jù)的，是一個空位置。

addFirst函數(shù)分析

// head 的初始值為 0 
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    // 若此時數(shù)組長度elements.length = 16
    // 那么下面代碼執(zhí)行過后 head = 15
    // 下面代碼的操作結(jié)果和下面兩行代碼含義一致
    // elements[(head - 1 + elements.length) % elements.length] = e
    // head = (head - 1 + elements.length) % elements.length
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

上面代碼操作結(jié)果和上文當(dāng)中我們提到的，在隊列當(dāng)中從右向左加入數(shù)據(jù)一樣。從上面的代碼看，我們可以發(fā)現(xiàn)下標(biāo)為head的位置是存在數(shù)據(jù)的。

doubleCapacity函數(shù)分析

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    // arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length)
    // 上面是函數(shù) System.arraycopy 的函數(shù)參數(shù)列表
    // 大家可以參考上面理解下面的拷貝代碼
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

上面的代碼還是比較簡單的，這里給大家一個圖示，大家就更加容易理解了：

擴(kuò)容之后將原來數(shù)組的數(shù)據(jù)拷貝到了新數(shù)組當(dāng)中，雖然數(shù)據(jù)在舊數(shù)組和新數(shù)組當(dāng)中的順序發(fā)生變化了，但是他們的相對順序卻沒有發(fā)生變化，他們的邏輯順序也是一樣的，這里的邏輯可能有點繞，大家在這里可以好好思考一下。

pollLast和pollFirst函數(shù)分析

這兩個函數(shù)的代碼就比較簡單了，大家可以根據(jù)前文所談到的內(nèi)容和圖示去理解下面的代碼。

public E pollLast() {
    // 計算出待刪除的數(shù)據(jù)的下標(biāo)
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    // 將需要刪除的數(shù)據(jù)的下標(biāo)值設(shè)置為 null 這樣這塊內(nèi)存就
    // 可以被回收了
    elements[t] = null;
    tail = t;
    return result;
}
public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}