Java源碼刨析之ArrayDeque
前言
在本篇文章當中主要跟大家介紹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，因此在邏輯上我們的隊列當中的數據布局如下圖所示：
根據前面一小節(jié)談到的輸入在入隊的時候數組當中數據的變化我們可以知道，數據在數組當中的布局為：
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的整數次冪的數進行上面移位操作的操作！
從上圖當中我們會發(fā)現，我們在一個數的二進制數的32位放一個1，經過移位之后最終32位的比特數字全部變成了1。根據上面數字變化的規(guī)律我們可以發(fā)現，任何一個比特經過上面移位的變化，這個比特后面的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 a a對 2 n 2^n 2n進行取余數操作和 a a a跟 2 n − 1 2^n - 1 2n−1進行&運算的結果相等，即：
從上面的代碼來看下標為tail的位置是沒有數據的，是一個空位置。
addFirst函數分析
// head 的初始值為 0
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
// 若此時數組長度elements.length = 16
// 那么下面代碼執(zhí)行過后 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();
}
上面代碼操作結果和上文當中我們提到的，在隊列當中從右向左加入數據一樣。從上面的代碼看，我們可以發(fā)現下標為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;
}上面的代碼還是比較簡單的，這里給大家一個圖示，大家就更加容易理解了：
擴容之后將原來數組的數據拷貝到了新數組當中，雖然數據在舊數組和新數組當中的順序發(fā)生變化了，但是他們的相對順序卻沒有發(fā)生變化，他們的邏輯順序也是一樣的，這里的邏輯可能有點繞，大家在這里可以好好思考一下。
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底層數組當中的數據順序和隊列的邏輯順序這部分可能比較抽象，大家可以根據圖示好好體會一下?。?！
到此這篇關于Java源碼刨析之ArrayDeque的文章就介紹到這了,更多相關Java ArrayDeque內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要給大家介紹了關于Java虛擬機處理異常的最佳方式，文中通過示例代碼介紹的非常詳細，對大家的學習或者使用Java具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-03-03
攔截器（Interceptor）是一種動態(tài)攔截方法調用的機制，在SpringMVC中動態(tài)攔截控制器方法的執(zhí)行。本文將詳細講講SpringMVC中攔截器的概念及入門案例，感興趣的可以嘗試一下2022-07-07
線程池的監(jiān)控很重要,本文就來介紹一下Springboot實現多線程及線程池監(jiān)控,文中通過示例代碼介紹的非常詳細,需要的朋友們下面隨著小編來一起學習學習吧2024-01-01
通過使用Spring Boot應用程序,我們可以創(chuàng)建一個war文件來部署到Web服務器中,這篇文章主要給大家介紹了關于SpringBoot項目部署到Tomcat的最新步驟,需要的朋友可以參考下2024-01-01
今天給大家?guī)淼氖顷P于Java的相關知識,文章圍繞著Java new String()展開,文中有非常詳細的介紹及代碼示例,需要的朋友可以參考下2021-06-06
這篇文章主要介紹了Spring循環(huán)依賴實現過程，Spring的解決循環(huán)依賴是有前置條件的，要解決循環(huán)依賴我們首先要了解Spring Bean對象的創(chuàng)建過程和依賴注入的方式2023-01-01
這篇文章主要介紹了java調用外部程序的方法及代碼演示的相關資料,需要的朋友可以參考下2023-03-03
springboot基于keytool實現https的雙向認證示例教程
這篇文章主要介紹了springboot基于keytool實現https的雙向認證,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-06-06
這篇文章主要介紹了配置Servlet兩種方法以及特點詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-03-03
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。本文將為大家詳細介紹雙向鏈表的特點與使用，需要的可以參考一下2021-12-12