ArrayDeque

双端队列，在OkHttp#Dispatcher有用到

感谢xiaoshua ArrayDeque源码分析

一 构造

这个数据结构有两个构造，默认的容积(capacity)为8，而通过构造参数传入的并不是简单的按照传入值来确定容积(capacity)

最后的容积总是为2 的 n次方，8 <capacity < 2^31 ，这样做的好处可以方便elements - 1用作&运算符加快运算

二 添加元素

举例一个容积为8的ArrayDeque，添加元素时的位置

• addFirst()

  8 > 7 > 6 > 5 > 4 > ...

• addLast()

  0 > 1 > 2 > 3 > 4 > ...

同时，如果头(head)尾(tail)相等时，

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;
}

会创建一个双倍的数组，然后使用System.arraycopy 两次将旧的数组中的元素复制到新数组中，第一次拷贝右边的(head - elements.length],第二次拷贝左边的(0 - head],然后将head置为0,tail置为原数组的长度

addFirst(e)中的elements[head = (head - 1) & (elements.length - 1)] = e; 的作用

int a = -1;
int mod = 16;
if (a == -1){
  System.out.println("a == -1 ---------------");
  System.out.println(a & (mod - 1));
  System.out.println(mod - 1);
}

a = 14;
if (-1 < a  && a < mod){
  System.out.println("-1 < a  && a < mod ---------------");
  System.out.println(a & (mod - 1));
  System.out.println(a);
}

a = 16;
if (a == mod){
  System.out.println("a == mod ---------------");
  System.out.println(a & (mod - 1));
  System.out.println(0);
}

输出

a == -1 ---------------
15
15
-1 < a && a < mod ---------------
14
14
a == mod ---------------
0
0

也就是说，如果 head = 0 的时候，那么在存放新元素(指addFirst)的索引为elements.length -1 ,而其他时候存放新元素的索引为head - 1,

如果 head = elements.length - 1 的时，进行取值操作， 取值后 head 会成为0