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=)