问：谈谈你对 ArrayDeque 主要方法实现原理的认识？
答：即循环数组的实现原理。
从 ArrayDeque 命名就能看出他的实现基于数组（LinkedList 是基于链表实现的双端队列），但是 ArrayDeque 的数组是一个可扩容动态数组，每次队列满了就会进行扩容，除非扩容至 int 边界才会抛出异常，ArrayDeque 不允许元素为 null。ArrayDeque 的主要成员是一个 elements 数组和 int 的 head 与 tail 索引，head 是队列的头部元素索引，而 tail 是队列下一个要添加的元素的索引，elements 的默认容量是 16 且默认容量必须是 2 的幂次，不足 2 的幂次会自动向上调整为 2 的幂次。
- ArrayDeque 获取队列头部元素的 element()\getFirst()\peek()\peekFirst() 操作，其都是调用 getFirst() 实现的，访问队列头部元素但不删除，即如下：
public E getFirst() {
@SuppressWarnings("unchecked")
//获取head索引处的元素
E result = (E) elements[head];
if (result == null) throw new NoSuchElementException();
return result;
}
- ArrayDeque 删除队列头部元素的 remove()\removeFirst()\poll()\pollFirst() 操作，其都是调用 pollFirst() 实现的，移除队列头部元素且返回被移除的元素，即如下：
public E pollFirst() {
final Object[] elements = this.elements;
final int h = head;
@SuppressWarnings("unchecked")
//取出队列头部索引处的元素
E result = (E) elements[h];
// Element is null if deque empty
if (result != null) {
//将head头位置元素置空，即删除元素
elements[h] = null;//Must null out slot
// 删除后把head索引向前移动一个位置
// (h + 1)操作就是head索引移动，后面的按位&操作是为了防止索引越界和head循环
head = (h + 1) & (elements.length - 1);
}
return result;
}
- ArrayDeque 添加元素到队列尾部的操作可以发现 add(E e)\offer(E e)\offerLast(E e)\addLast(E e) 操作都是调用 addLast(E e) 实现的，即如下：
public void addLast(E e) {
//如果元素为空抛出异常
if (e == null) throw new NullPointerException();
// 将新添加到尾部的元素放在索引为tail的地方
elements[tail] = e;
// 判断tail和head是否相等，如果相等则对数组进行扩容
if ((tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity();
}
private void doubleCapacity() {
// 双倍扩容，然后head为0，tail为n，即tail为下一个要插入元素的索引
......
// int n = elements . length ;
......
// int newCapacity = n << 1 ;
......
elements = a;
head = 0;
tail = n;
}
addLast 的实现原理，也就是那句 if 操作与双倍扩容到底是做了什么，所以我们先看下不扩容情况下 ArrayDeque 相关操作的图解，如下：
正如上图中最后的多次操作结果所示，如果此时我们再 add 操作一个元素到 tail 索引处则 tail+1 会变成 8 导致数组越界，理论上来说这时候应该进行扩容操作了，但是由于下标为 0、1、2、3 处没有存储元素，直接扩容有些浪费（ArrayList 为了避免浪费是通过拷贝将删除之后的元素整体前挪一位），所以为了高效利用数组中现有的剩余空间就有了 addLast(E e) 中的代码 (tail = (tail + 1) & (elements.length - 1)); 实质类似上面 pollFirst() 里面 head 操作，即假设 elements 默认初始化长度是 8，则当前 tail + 1（8=1000）按位与上数组长度减一（7=0111）的结果为十进制的 0，所以下一个被 addLast(E e) 的元素实际会放在索引为 0 的位置，再下一个会放在索引为 1 的位置，如下图：
可以看到，随着出队入队不断操作，如果 tail 移动到 length-1 之后数组的第一个位置 0 处没有元素则需要将 tail 指向 0，依次循环，当 tail 如果等于 head 时说明数组要满了，接下来需要进行数组扩容，所以就有了上面 addLast(E e) 里面那个 if 判断的逻辑去触发 doubleCapacity()。因此这也就解释了为什么 ArrayDeque 的初始容量必须是 2 的幂次（扩容每次都是成倍的，所以自然也满足 2 的幂次），因为只有容量为 2 的幂次时 ((tail + 1) & (elements.length - 1)) 操作中的 (elements.length - 1) 二进制最高位永远为 0，当 (tail + 1) 与其按位与操作时才能保证循环归零置位。
ArrayDeque 的 doubleCapacity() 扩容操作的实现，如下：
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];
//扩容后分两次复制，head到当前数组末尾
System.arraycopy(elements, p, a, 0, r);
// 当前数组头到tail位置
System.arraycopy(elements, 0, a, r, p);
//相关索引置位
elements = a;
head = 0;
tail = n;
}
上面的扩容操作流程演示如下：
所以 ArrayDeque 是一个双向循环队列，其基于数组实现了双向循环操作（依赖按位与操作循环），初始容量必须是 2 的幂次，默认为 16，存储的元素不能为空，非线程并发安全。
网友评论