一、前言
1、源码位置在这里。
- ArrayDeque的三个基本成员变量
transient Object[] elements; // non-private to simplify nested class access
/**
* The index of the element at the head of the deque (which is the
* element that would be removed by remove() or pop()); or an
* arbitrary number equal to tail if the deque is empty.
*/
transient int head;
/**
* The index at which the next element would be added to the tail
* of the deque (via addLast(E), add(E), or push(E)).
*/
transient int tail;
实际上这就是一个数组+头尾下标。本文只简单介绍ArrayDeque作为Queue使用的情况。
二、ArrayDeque作为Queue使用
- Queue遵循先进先出的原则。
- 我们先看下进Queue的代码
public boolean offer(E e) {
return offerLast(e);
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
最终调用了addLast这个方法。tail初始为0，我们看到进队列，直接把元素加载了数组的尾部，并且tail = tail+1。这里比较难理解的就是这段代码
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
假设，数组的初始容量为8，tail=head=0。我们一直调用offer方法，直到tail=7，此时head=0，我们计算下8&7的值
0000 0000 0000 0000 0000 0000 0000 1000
&
0000 0000 0000 0000 0000 0000 0000 0111
=0
此时，数组满了，需要扩容。
我们先不说扩容的机制，我们思考另外一个问题，当队列使用的使用，有的任务想插队，对于ArrayDeque来说，也是也是允许的。
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
我们看下头元素下标位置的计算方式
elements[head = (head - 1) & (elements.length - 1)] = e;
最开始head=0，根据这个计算方式head=-1&7，我们知道，在计算机中，为了让符号位参与计算，采用了补码，所以
1111 1111 1111 1111 1111 1111 1111 1111
&
0000 0000 0000 0000 0000 0000 0000 0111
=7
所以，第一个元素的位置在7，如果再插入一个元素到头部，那么位置在6。所以& (elements.length - 1)就是一个低位掩码，相当于对数组长度取模操作，这得益于elements以2^n方式扩容。
经过一系列的offer和offerFirst操作，head和tail最终会相遇，此时就要扩容
这张图是从网上盗的，图式是没有调用offer的情况下扩容。
我们前面讲了插队，在实际应用中还有取消排队的情景。对于ArrayDeque来说就是删除指定位置的元素。
public boolean remove(Object o) {
return removeFirstOccurrence(o);
}
public boolean removeFirstOccurrence(Object o) {
if (o != null) {
int mask = elements.length - 1;
int i = head;
for (Object x; (x = elements[i]) != null; i = (i + 1) & mask) {
if (o.equals(x)) {
delete(i);
return true;
}
}
}
return false;
}
boolean delete(int i) {
checkInvariants();
final Object[] elements = this.elements;
final int mask = elements.length - 1;
final int h = head;
final int t = tail;
final int front = (i - h) & mask;
final int back = (t - i) & mask;
// Invariant: head <= i < tail mod circularity
if (front >= ((t - h) & mask))
throw new ConcurrentModificationException();
// Optimize for least element motion
if (front < back) {//如果要删除的元素距离头部比较近，那么移动head到删除元素之间的元素比较划算，反之移动要删元素和尾部之间的元素比较划算
if (h <= i) {
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
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;
}
}
我们知道ArrayList在删除某个元素的时候，这个元素后面的所有的元素都要向前位移1位，这种操作开销是比较大的。ArrayDeque也需要做类似的操作，只不过ArrayDeque采用了不同的位移策略，尽量减小位移带来的开销。这里面计算被删除元素离头部和尾部的距离比较难理解
final int mask = elements.length - 1;
final int front = (i - h) & mask;
final int back = (t - i) & mask;
ArrayDeque是采用数组+head和tail实现的一种可以从双端访问的数据结构，这些元素的的下标物理上是不连续的，所以我们不能通过i-h或者t-i来获取i前或者i后有多少个元素。原作者采用了取模操作，如果让我实现的话，我可能会采取几个分支来算这个数字，毫无疑问，原作者的算法更高效，只是我不太理解，从网上盗了几张张图帮大家理解这个事情。
非常感谢这篇文章。
