在介紹了Queue與Deque概念之后潮瓶，這是要進(jìn)行分析的第一個實現(xiàn)類。ArrayDeque可能大家用的都比較少钙姊，但其實現(xiàn)里有許多亮點還是值得我們關(guān)注的毯辅。
Deque的定義為double ended queue煞额，也就是允許在兩側(cè)進(jìn)行插入和刪除等操作的隊列思恐。這個定義看起來很簡單，那么我們怎么實現(xiàn)它呢立镶？我們最容易想到的就是使用雙向鏈表壁袄。我們在前文介紹過單鏈表，其每個數(shù)據(jù)單元都包含一個數(shù)據(jù)元素和一個指向下一個元素位置的指針next媚媒，這樣的鏈表只能從前向后遍歷嗜逻。如果我們要把它變成雙向的，只需要添加一個可以指向上一個元素位置的指針previous缭召，同時記錄下其尾節(jié)點即可栈顷。LinkedList的實現(xiàn)就是采用了這一實現(xiàn)方案。
那ArrayDeque又是什么嵌巷，它的結(jié)構(gòu)又是怎樣的呢萄凤？我們先看下其文檔吧：
Resizable-array implementation of the Deque interface. Array deques have no capacity restrictions; they grow as necessary to support usage. They are not thread-safe; in the absence of external synchronization, they do not support concurrent access by multiple threads. Null elements are prohibited. This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
文檔中并沒有過多的介紹實現(xiàn)細(xì)節(jié)，但說它是Resizable-array implementation of the Deque interface搪哪，也就是用可動態(tài)調(diào)整大小的數(shù)組來實現(xiàn)了Deque靡努，聽起來是不是像ArrayList？但ArrayDeque對數(shù)組的操作方式和ArrayList有較大的差別晓折。下面我們就深入其源碼看看它是如何巧妙的使用數(shù)組的惑朦，以及為何說
faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
構(gòu)造函數(shù)與重要成員變量
ArrayDeque共有四個成員變量，其中兩個我們在分析ArrayList時已經(jīng)見過了漓概，還有兩個我們需要認(rèn)真研究一下：
//存放元素漾月，長度和capacity一致，并且總是2的次冪
//這一點胃珍，我們放在后面解釋
transient Object[] elements;
//capacity最小值梁肿，也是2的次冪
private static final int MIN_INITIAL_CAPACITY = 8;
//標(biāo)記隊首元素所在的位置
transient int head;
//標(biāo)記隊尾元素所在的位置
transient int tail;
其構(gòu)造函數(shù)共有三個：
//默認(rèn)構(gòu)造函數(shù)，將elements長度設(shè)為16觅彰，相當(dāng)于最小capacity的兩倍
public ArrayDeque() {
elements = new Object[16];
}
//帶初始大小的構(gòu)造
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
//從其他集合類導(dǎo)入初始數(shù)據(jù)
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
這里看到有兩個構(gòu)造函數(shù)都用到了allocateElements方法吩蔑，這是一個非常經(jīng)典的方法，我們接下來就先重點研究它填抬。
尋找最近的2次冪
在定義elements變量時說哥纫，其長度總是2的次冪，但用戶傳入的參數(shù)并不一定符合規(guī)則，所以就需要根據(jù)用戶的輸入蛀骇，找到比它大的最近的2次冪厌秒。比如用戶輸入13，就把它調(diào)整為16擅憔，輸入31鸵闪，就調(diào)整為32，等等暑诸“鏊希考慮下，我們有什么方法可以實現(xiàn)呢个榕？
來看下ArrayDeque是怎么做的吧：
private void allocateElements(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
}
elements = new Object[initialCapacity];
}
看到這段迷之代碼了嗎篡石？在HashMap中也有一段類似的實現(xiàn)。但要讀懂它西采，我們需要先掌握以下幾個概念：
在java中凰萨，int的長度是32位，有符號int可以表示的值范圍是 (-2)31 到 231-1械馆，其中最高位是符號位胖眷，0表示正數(shù)，1表示負(fù)數(shù)霹崎。
>>>：無符號右移珊搀，忽略符號位，空位都以0補(bǔ)齊尾菇。|：位或運算境析，按位進(jìn)行或操作，逢1為1派诬。
我們知道劳淆，計算機(jī)存儲任何數(shù)據(jù)都是采用二進(jìn)制形式，所以一個int值為80的數(shù)在內(nèi)存中可能是這樣的：
0000 0000 0000 0000 0000 0000 0101 0000
比80大的最近的2次冪是128千埃，其值是這樣的：
0000 0000 0000 0000 0000 0000 1000 0000
我們多找?guī)捉M數(shù)據(jù)就可以發(fā)現(xiàn)規(guī)律：
每個2的次冪用二進(jìn)制表示時憔儿，只有一位為 1忆植，其余位均為 0（不包含符合位）
要找到比一個數(shù)大的2的次冪（在正數(shù)范圍內(nèi)）放可，只需要將其最高位左移一位（從左往右第一個 1 出現(xiàn)的位置），其余位置 0 即可朝刊。
但從實踐上講耀里，沒有可行的方法能夠進(jìn)行以上操作，即使通過&操作符可以將某一位置 0 或置 1拾氓，也無法確認(rèn)最高位出現(xiàn)的位置冯挎，也就是基于最高位進(jìn)行操作不可行。
但還有一個很整齊的數(shù)字可以被我們利用咙鞍，那就是 2n-1房官，我們看下128-1=127的表示形式：
0000 0000 0000 0000 0000 0000 0111 1111
把它和80對比一下：
0000 0000 0000 0000 0000 0000 0101 0000 //80
0000 0000 0000 0000 0000 0000 0111 1111 //127
可以發(fā)現(xiàn)趾徽，我們只要把80從最高位起每一位全置為1，就可以得到離它最近且比它大的 2n-1翰守，最后再執(zhí)行一次+1操作即可孵奶。具體操作步驟為（為了演示，這里使用了很大的數(shù)字）：
原值：
0011 0000 0000 0000 0000 0000 0000 0010
- 無符號右移1位
0001 1000 0000 0000 0000 0000 0000 0001
- 與原值
|操作：
0011 1000 0000 0000 0000 0000 0000 0011
可以看到最高2位都是1了蜡峰，也僅能保證前兩位為1了袁，這時就可以直接移動兩位
- 無符號右移2位
0000 1110 0000 0000 0000 0000 0000 0000
- 與原值
|操作：
0011 1110 0000 0000 0000 0000 0000 0011
此時就可以保證前4位為1了，下一步移動4位
- 無符號右移4位
0000 0011 1110 0000 0000 0000 0000 0000
- 與原值
|操作：
0011 1111 1110 0000 0000 0000 0000 0011
此時就可以保證前8位為1了湿颅，下一步移動8位
- 無符號右移8位
0000 0000 0011 1111 1110 0000 0000 0000
- 與原值
|操作：
0011 1111 1111 1111 1110 0000 0000 0011
此時前16位都是1载绿，只需要再移位操作一次，即可把32位都置為1了油航。
- 無符號右移16位
0000 0000 0000 0000 0011 1111 1111 1111
- 與原值
|操作：
0011 1111 1111 1111 1111 1111 1111 1111
- 進(jìn)行+1操作：
0100 0000 0000 0000 0000 0000 0000 0000
如此經(jīng)過11步操作后崭庸，我們終于找到了合適的2次冪。寫成代碼就是：
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
不過為了防止溢出劝堪，導(dǎo)致出現(xiàn)負(fù)值（如果把符號位置為1冀自，就為負(fù)值了）還需要一次校驗：
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
至此，初始化的過程就完畢了秒啦。
重要操作方法
add分析
Deque主要定義了一些關(guān)于First和Last的操作熬粗，如add、remove余境、get等驻呐。我們看看它是如何實現(xiàn)的吧。
//在隊首添加一個元素芳来，非空
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
//在隊尾添加一個元素含末，非空
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
這里，又有一段迷之代碼需要我們認(rèn)真研究了即舌，這也是ArrayDeque值得我們研究的地方之一佣盒，通過位運算提升效率。
elements[head = (head - 1) & (elements.length - 1)] = e;
很明顯這是一個賦值操作顽聂，而且應(yīng)該是給head之前的位置賦值肥惭，所以head = (head - 1)是合理的操作，那這個& (elements.length - 1)又表示什么呢紊搪？
在之前的定義與初始化中蜜葱，elements.length要求為2的次冪，也就是 2n 形式耀石，那這個& (elements.length - 1)也就是 2n-1 了牵囤，在內(nèi)存中用二進(jìn)制表示就是從最高位起每一位都是1。我們還以之前的127為例：
0000 0000 0000 0000 0000 0000 0111 1111
&就是按位與，全1才為1揭鳞。那么任意一個正數(shù)和127進(jìn)行按位與操作后炕贵，都只有最右側(cè)7位被保留了下來，其他位全部置0（除符號位）野崇，而對一個負(fù)數(shù)而言鲁驶，則會把它的符號位置為0，&操作后會變成正數(shù)舞骆。比如-1的值是1111 ... 1111（32個1）钥弯，和127按位操作后結(jié)果就變成了127 。所以督禽，對于正數(shù)它就是取模脆霎，對于負(fù)數(shù)，它就是把元素插入了數(shù)組的結(jié)尾狈惫。所以睛蛛，這個數(shù)組并不是向前添加元素就向前擴(kuò)展，向后添加就向后擴(kuò)展胧谈，它是循環(huán)的忆肾，類似這樣：
初始時，head與tail都指向a[0]菱肖，這時候數(shù)組是空的客冈。當(dāng)執(zhí)行addFirst()方法時，head指針移動一位稳强，指向a[elements.length-1]场仲，并賦值，也就是給a[elements.length-1]賦值退疫。當(dāng)執(zhí)行addLast()操作時渠缕，先給a[0]賦值，再將tail指針移動一位褒繁，指向a[1]亦鳞。所以執(zhí)行完之后head指針位置是有值的，而tail位置是沒有值的棒坏。
隨著添加操作執(zhí)行燕差，數(shù)組總會占滿，那么怎么判斷它滿了然后擴(kuò)容呢俊抵？首先谁不，如果head==tail坐梯，則說明數(shù)組是空的徽诲，所以在添加元素時必須保證head與tail不相等。假如現(xiàn)在只有一個位置可以添加元素了，類似下圖：
此時，tail指向了a[8]，head已經(jīng)填充到a[9]了娄柳，只有a[8]是空閑的消略。很顯然，不管是addFirst還是addLast弛秋，再添加一個元素后都會導(dǎo)致head==tail。這時候就不得不擴(kuò)容了，因為head==tail是判斷是否為空的條件尉共。擴(kuò)容就比較簡單了，直接翻倍弃锐，我們看代碼：
private void doubleCapacity() {
//只有head==tail時才可以擴(kuò)容
assert head == tail;
int p = head;
int n = elements.length;
//在head之后袄友，還有多少元素
int r = n - p; // number of elements to the right of p
//直接翻倍，因為capacity初始化時就已經(jīng)是2的倍數(shù)了霹菊，這里無需再考慮
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
//左側(cè)數(shù)據(jù)拷貝
System.arraycopy(elements, p, a, 0, r);
//右側(cè)數(shù)據(jù)拷貝
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
分析完add剧蚣，那么get以及remove等都大同小異，感興趣可以查看源碼旋廷。我們還要看看在Deque中定義的removeFirstOccurrence和removeLastOccurrence方法的具體實現(xiàn)鸠按。
Occurrence相關(guān)
removeFirstOccurrence和removeLastOccurrence分別用于找到元素在隊首或隊尾第一次出現(xiàn)的位置并刪除。其實現(xiàn)原理是一致的饶碘，我們分析一個即可：
public boolean removeFirstOccurrence(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
return true;
}
i = (i + 1) & mask;
}
return false;
}
這里就是遍歷所有元素目尖，然后通過delete方法刪除，我們看看delete實現(xiàn)：
private boolean delete(int i) {
//檢查
checkInvariants();
final Object[] elements = this.elements;
final int mask = elements.length - 1;
final int h = head;
final int t = tail;
//待刪除元素前面的元素個數(shù)
final int front = (i - h) & mask;
//待刪除元素后面的元素個數(shù)
final int back = (t - i) & mask;
// Invariant: head <= i < tail mod circularity
//確認(rèn) i 在head和tail之間
if (front >= ((t - h) & mask))
throw new ConcurrentModificationException();
// Optimize for least element motion
//盡量最少操作數(shù)據(jù)
//前面數(shù)據(jù)比較少
if (front < back) {
if (h <= i) {
//這時 h 和 i 之間最近距離沒有跨過位置0
System.arraycopy(elements, h, elements, h + 1, front);
} else { // Wrap around
System.arraycopy(elements, 0, elements, 1, i);
elements[0] = elements[mask];
System.arraycopy(elements, h, elements, h + 1, mask - h);
}
elements[h] = null;
head = (h + 1) & mask;
return false;
} else {
if (i < t) { // Copy the null tail as well
//這時 t 和 i 之間最近距離沒有跨過位置0
System.arraycopy(elements, i + 1, elements, i, back);
tail = t - 1;
} else { // Wrap around
System.arraycopy(elements, i + 1, elements, i, mask - i);
elements[mask] = elements[0];
System.arraycopy(elements, 1, elements, 0, t);
tail = (t - 1) & mask;
}
return true;
}
}
總結(jié)
ArrayDeque通過循環(huán)數(shù)組的方式實現(xiàn)的循環(huán)隊列扎运，并通過位運算來提高效率卑雁，容量大小始終是2的次冪。當(dāng)數(shù)據(jù)充滿數(shù)組時绪囱，它的容量將翻倍测蹲。作為Stack，因為其非線程安全所以效率高于java.util.Stack鬼吵，而作為隊列扣甲，因為其不需要結(jié)點支持所以更快（LinkedList使用Node存儲數(shù)據(jù)，這個對象頻繁的new與clean齿椅，使得其效率略低于ArrayDeque）琉挖。但隊列更多的用來處理多線程問題，所以我們更多的使用BlockingQueue涣脚，關(guān)于多線程的問題示辈，以后再認(rèn)真研究。
上一篇：Java集合源碼分析之Queue（二）：接口Deque
我是飛機(jī)醬遣蚀，如果您喜歡我的文章矾麻，可以關(guān)注我~
編程之路纱耻，道阻且長。唯险耀，路漫漫其修遠(yuǎn)兮弄喘，吾將上下而求索。
