Java 集合源碼解析系列：
- 拆行解碼 Java 集合源碼之總覽
- 拆行解碼 Java 集合源碼之 Collection 的三大體系
- 拆行解碼 Java 集合源碼之疊代器
- 拆行解碼 Java 集合源碼之 ArrayList
- 拆行解碼 Java 集合源碼之 LinkedList
- 拆行解碼 Java 集合源碼之 HashMap
- 拆行解碼 Java 集合源碼之 Hashtable
- 拆行解碼 Java 集合源碼之 LinkedHashMap
- 拆行解碼 Java 集合源碼之 PriorityQueue
- 拆行解碼 Java 集合源碼之 ArrayDeque
特性
- 環形隊列。
-
初始容量 16
指定容量時，因為是環形隊列，是以數組末尾必須有個空位，用作頭尾判空或滿的依據。
(numElements < 1) ? 1 : (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE : numElements + 1 - 儲存雙端索引：head 和 tail。
- 為空時：0 <= head = tail < elements.length
- 滿：length - head = tail
- elements[tail] 一直為 null
- 預設擴容容量：
(oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)
。
單個添加後，才去擴容。
- 最關鍵的點就是維護好 head 和 tail 關系。
構造函數
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable {
transient Object[] elements;
/**
* 空 :0 <= head = tail < elements.length
* 滿 : elements.length - head = tail
*/
transient int head;
/**
* elements[tail] 在任意操作後,對外展示時, 一定是 null
*/
transient int tail;
public ArrayDeque() {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
// 盡量會保留一個空槽
elements =
new Object[(numElements < 1) ? 1 :
(numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
numElements + 1];
}
public ArrayDeque(Collection<? extends E> c) {
this(c.size());
copyElements(c);
}
}
頭尾索引的維護
一般 modulus = elements.length。
/**
* Circularly increments i, mod modulus.
* Precondition and postcondition: 0 <= i < modulus.
*/
static final int inc(int i, int modulus) {
if (++i >= modulus) i = 0;
return i;
}
/**
* Circularly decrements i, mod modulus.
* Precondition and postcondition: 0 <= i < modulus.
*/
static final int dec(int i, int modulus) {
if (--i < 0) i = modulus - 1;
return i;
}
/**
* Circularly adds the given distance to index i, mod modulus.
* Precondition: 0 <= i < modulus, 0 <= distance <= modulus.
* @return index 0 <= i < modulus
*/
static final int inc(int i, int distance, int modulus) {
if ((i += distance) - modulus >= 0) i -= modulus;
return i;
}
/**
* Subtracts j from i, mod modulus.
* Index i must be logically ahead of index j.
* Precondition: 0 <= i < modulus, 0 <= j < modulus.
* @return the "circular distance" from j to i; corner case i == j
* is disambiguated to "empty", returning 0.
*/
static final int sub(int i, int j, int modulus) {
if ((i -= j) < 0) i += modulus;
return i;
}
/**
* Returns element at array index i.
* This is a slight abuse of generics, accepted by javac.
*/
@SuppressWarnings("unchecked")
static final <E> E elementAt(Object[] es, int i) {
return (E) es[i];
}
添加
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
es[head = dec(head, es.length)] = e;
if (head == tail)
// 添加後擴容
grow(1);
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
es[tail] = e;
if (head == (tail = inc(tail, es.length)))
// 添加後擴容
grow(1);
}
public boolean addAll(Collection<? extends E> c) {
final int s, needed;
if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0)
grow(needed);
copyElements(c);
return size() > s;
}
private void copyElements(Collection<? extends E> c) {
c.forEach(this::addLast);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
移除
public E removeFirst() {
E e = pollFirst();
if (e == null)
throw new NoSuchElementException();
return e;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E removeLast() {
E e = pollLast();
if (e == null)
throw new NoSuchElementException();
return e;
}
public E pollFirst() {
final Object[] es;
final int h;
E e = elementAt(es = elements, h = head);
if (e != null) {
es[h] = null;
head = inc(h, es.length);
}
return e;
}
public E pollLast() {
final Object[] es;
final int t;
E e = elementAt(es = elements, t = dec(tail, es.length));
if (e != null)
es[tail = t] = null;
return e;
}
擴容
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int needed) {
// overflow-conscious code
final int oldCapacity = elements.length;
int newCapacity;
// Double capacity if small; else grow by 50%
int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump);
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// Exceptionally, here tail == head needs to be disambiguated
if (tail < head
// 因為是添加後擴容, 是以需要判斷 tail == head 的歧義(可能是滿,違反了 tail 一定是 null 的規則)
|| (tail == head && es[head] != null)) {
// wrap around; slide first leg forward to end of array
// ++++++tail-------head++++++|------ 或 ++++++++++++head&tail++++++|------
int newSpace = newCapacity - oldCapacity;
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
for (int i = head, to = (head += newSpace); i < to; i++)
es[i] = null;
// 處理後:++++++tail-------------head++++++ 或 ++++++++++++tail------head++++++
}
}
/** Capacity calculation for edge conditions, especially overflow. */
private int newCapacity(int needed, int jump) {
final int oldCapacity = elements.length, minCapacity;
if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
if (minCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
return Integer.MAX_VALUE;
}
if (needed > jump)
return minCapacity;
return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
? oldCapacity + jump
: MAX_ARRAY_SIZE;
}
指定删除
涉及到元素向前向後挪移、頭尾索引的維護。
力求挪移最少的元素。
批量删除
利用位圖，批量查詢符合條件的，批量删除。
避免 頭尾索引的重複計算。
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)