ArrayDeque
一、类图关系
二、要点分析
1. ArrayDeque 不允许空元素 null
2. 当用作栈时,比 Stack 快,当用作队列时,比 LinkedList 快
一是因为它基于循环数组(只需操作索引),二是没有使用 Synchronized 修饰方法(非线程安全)
This class is likely to be faster than
Stack
when used as a stack, and faster thanLinkedList
when used as a queue.
3. 迭代器 fail-fast
4. 容量是 2 的整数次幂,最小(初始)容量是 8,构造函数可以指定容量,自动修正为 2 的整数次幂大小
默认容量是16
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];
}// 解释说明
简单分析一下代码的运算过程,注:">>>"代表按位右移 (空位 0 补齐):
假设a=1xxxxxxxxxxxx...(base 2, x代表该位任意为0或1)
首先a |= (a >>> 1)之后,a => 11xxxxxxxx...(最高两位是1)
然后a |= (a>>> 2): a => 1111xxxxxxxxx...(最高四位是1)
再a |= (a>>> 4): a => 11111111xxxxxxx...(最高八位是1)
........
最终,a的所有低位也都变成了1,即11111111...111(全是1)
再a++ 就变成了10000000000...000(加一之后进位,比原来的二进制串多了一位,且第一位是1,其它位都是0),这个算法不仅时间效率高,而且只用到了一个变量,真可谓是短小精悍,在HashMap里也可以看到这个算法的身影。
5. 容量占满时,使用翻倍策略扩容,内部是个数组(循环数组)
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];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p); // 理解这两句,请看下图
elements = a;
head = 0;
tail = n;
}
注意: head 指向实际存有数据的头节点,tail 指向下一个应该放数据的尾节点
6. 取下标操作使用位运算,例如
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;
}
7. 含逆向迭代方法 descendingIterator