ArrayDeque（JDK雙端佇列）原始碼深度剖析
前言
在本篇文章當中主要跟大家介紹JDK給我們提供的一種用陣列實作的雙端佇列，在之前的文章LinkedList原始碼剖析當中我們已經介紹了一種雙端佇列，不過與ArrayDeque不同的是，LinkedList的雙端佇列使用雙向鏈表實作的，
雙端佇列整體分析
我們通常所談論到的佇列都是一端進一端出，而雙端佇列的兩端則都是可進可出，下面是雙端佇列的幾個操作：
-
資料從雙端佇列左側進入，
-
資料從雙端佇列右側進入，
- 資料從雙端佇列左側彈出，
- 資料從雙端佇列右側彈出，
而在ArrayDeque當中也給我們提供了對應的方法去實作，比如下面這個例子就是上圖對應的代碼操作：
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);
}
// 輸出結果
[100]
[55, 100]
[55, 100, -55]
[100, -55]
[100]
陣列實作ArrayDeque(雙端佇列)的原理
ArrayDeque底層是使用陣列實作的，而且陣列的長度必須是2的整數次冪，這么操作的原因是為了后面位運算好操作，在ArrayDeque當中有兩個整形變數head和tail，分別指向右側的第一個進入佇列的資料和左側第一個進行佇列的資料，整個記憶體布局如下圖所示：
其中tail指的位置沒有資料，head指的位置存在資料，
- 當我們需要從左往右增加資料時（入隊），記憶體當中資料變化情況如下：
- 當我們需要從右往做左增加資料時（入隊），記憶體當中資料變化情況如下：
- 當我們需要從右往左洗掉資料時（出隊），記憶體當中資料變化情況如下：
- 當我們需要從左往右洗掉資料時（出隊），記憶體當中資料變化情況如下：
底層資料遍歷順序和邏輯順序
上面主要談論到的陣列在記憶體當中的布局，但是他是具體的物理存盤資料的順序，這個順序和我們的邏輯上的順序是不一樣的，根據上面的插入順序，我們可以畫出下面的圖，大家可以仔細分析一下這個圖的順序問題，
上圖當中佇列左側的如隊順序是0, 1, 2, 3，右側入隊的順序為15, 14, 13, 12, 11, 10, 9, 8，因此在邏輯上我們的佇列當中的資料布局如下圖所示：
根據前面一小節談到的輸入在入隊的時候陣列當中資料的變化我們可以知道，資料在陣列當中的布局為：
ArrayDeque類關鍵欄位分析
// 底層用于存盤具體資料的陣列
transient Object[] elements;
// 這就是前面談到的 head
transient int head;
// 與上文談到的 tail 含義一樣
transient int tail;
// MIN_INITIAL_CAPACITY 表示陣列 elements 的最短長度
private static final int MIN_INITIAL_CAPACITY = 8;
以上就是ArrayDeque當中的最主要的欄位，其含義還是比較容易理解的！
ArrayDeque建構式分析
- 默認建構式，陣列默認申請的長度為
16，
public ArrayDeque() {
elements = new Object[16];
}
- 指定陣列長度的初始化長度，下面列出了改建構式涉及的所有函式，
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;
}
上面的最難理解的就是函式calculateSize了，他的主要作用是如果用戶輸入的長度小于MIN_INITIAL_CAPACITY時，回傳MIN_INITIAL_CAPACITY，否則回傳比initialCapacity大的第一個是2的整數冪的整數，比如說如果輸入的是9回傳的16，輸入4回傳8，
calculateSize的代碼還是很難理解的，讓我們一點一點的來分析，首先我們使用一個2的整數次冪的數進行上面移位操作的操作！
從上圖當中我們會發現，我們在一個數的二進制數的32位放一個1，經過移位之后最終32位的位元數字全部變成了1，根據上面數字變化的規律我們可以發現，任何一個位元經過上面移位的變化，這個位元后面的31個位元位都會變成1，像下圖那樣：
因此上述的移位操作的結果只取決于最高一位的位元值為1，移位操作后它后面的所有位元位的值全為1，而在上面函式的最后，我們回傳的結果就是上面移位之后的結果 +1，又因為移位之后最高位的1到最低位的1之間的位元值全為1，當我們+1之后他會不斷的進位，最終只有一個位元位置是1，因此它是2的整數倍，
經過上述程序分析，我們就可以立即函式calculateSize了，
ArrayDeque關鍵函式分析
addLast函式分析
// tail 的初始值為 0
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
// 這里進行的 & 位運算 相當于取余數操作
// (tail + 1) & (elements.length - 1) == (tail + 1) % elements.length
// 這個操作主要是用于判斷陣列是否滿了，如果滿了則需要擴容
// 同時這個操作將 tail + 1，即 tail = tail + 1
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
代碼(tail + 1) & (elements.length - 1) == (tail + 1) % elements.length成立的原因是任意一個數\(a\)對\(2^n\)進行取余數操作和\(a\)跟\(2^n - 1\)進行&運算的結果相等，即：
從上面的代碼來看下標為tail的位置是沒有資料的，是一個空位置，
addFirst函式分析
// head 的初始值為 0
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
// 若此時陣列長度elements.length = 16
// 那么下面代碼執行過后 head = 15
// 下面代碼的操作結果和下面兩行代碼含義一致
// 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();
}
上面代碼操作結果和上文當中我們提到的，在佇列當中從右向左加入資料一樣，從上面的代碼看，我們可以發現下標為head的位置是存在資料的，
doubleCapacity函式分析
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)
// 上面是函式 System.arraycopy 的函式引數串列
// 大家可以參考上面理解下面的拷貝代碼
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
上面的代碼還是比較簡單的，這里給大家一個圖示，大家就更加容易理解了：
擴容之后將原來陣列的資料拷貝到了新陣列當中，雖然資料在舊陣列和新陣列當中的順序發生變化了，但是他們的相對順序卻沒有發生變化，他們的邏輯順序也是一樣的，這里的邏輯可能有點繞，大家在這里可以好好思考一下，
pollLast和pollFirst函式分析
這兩個函式的代碼就比較簡單了，大家可以根據前文所談到的內容和圖示去理解下面的代碼，
public E pollLast() {
// 計算出待洗掉的資料的下標
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
// 將需要洗掉的資料的下標值設定為 null 這樣這塊記憶體就
// 可以被回收了
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;
}
總結
在本篇文章當中，主要跟大家分享了ArrayDeque的設計原理，和他的底層實作程序，ArrayDeque底層陣列當中的資料順序和佇列的邏輯順序這部分可能比較抽象，大家可以根據圖示好好體會一下！！！
以上就是本篇文章的所有內容了，希望大家有所識訓，我是LeHung，我們下期再見！！！都看到這里了，給孩子一個贊（start）吧，
免費的哦!!!
更多精彩內容合集可訪問專案：https://github.com/Chang-LeHung/CSCore
關注公眾號：一無是處的研究僧，了解更多計算機（Java、Python、計算機系統基礎、演算法與資料結構）知識，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499348.html
標籤：其他