ArrayDeque源码分析

ArrayDeque源码大致了解

ArrayDeque是一个数组实现的链表。话不多说我们来看代码，首先是三个最重要的结构：

// 数据存储的数组，这个数组的长度总是2的倍数，当head指针跟tail指针重合的时候会扩容
  transient Object[] elements; // non-private to simplify nested class access
//head指针
    transient int head;
//尾指针
    transient int tail;

然后看初始化，三种方式初始化。

//默认方式，直接申请一个长度为16的数组来存储对象
 public ArrayDeque() {
        elements = new Object[16];
    }

 //指定长度的数组申请
    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }

//给定一个集合来生成
    public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

可以看到其中两种用到了allocateElements，这个方法的简介可以参考我的另外一篇文章ArrayDeque中allocateElements的分析，有详细介绍。
看了allocateElements 我们会发现还有一个最重要的扩容的方法doubleCapacity()，这个方法很重要，一会儿我们着重看这个方法。
我们看到有一段注释The main insertion and extraction methods are addFirst, addLast, pollFirst, pollLast. The other methods are defined in terms of these. 我们看到源码有介绍，告诉我们其实主要方法是addFirst, addLast, pollFirst, pollLast。其他的add get offer poll peek remove element都是基于这四个方法做的，我们去看这四个方法。

//这几个方法其实看名字就知道是什么功能了。
public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
//查找head并给head赋值
        elements[head = (head - 1) & (elements.length - 1)] = e;
//是否扩容判断
        if (head == tail)
            doubleCapacity();
    }

    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
//给tail赋值
        elements[tail] = e;
//tail重新赋值并做head==tail判断
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

//取head并移除
  public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h]; //取当前head的element
        // Element is null if deque empty
        if (result == null)
            return null;
//置null
        elements[h] = null;     // Must null out slot
//head重新赋值 head+1
        head = (h + 1) & (elements.length - 1);
        return result;
    }

//取tail的element
    public E pollLast() {
//得到tail-1的element，为什么是-1下面介绍
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
        E result = (E) elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;
        return result;
    }

 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];
// 拷贝原来数组的右半段到新数组的0坐标位置，也就是[0,r]
        System.arraycopy(elements, p, a, 0, r); 
// 拷贝原来数组的左边段到新数组的[r , n]，也就是上面那句话拷贝的数据后面
        System.arraycopy(elements, 0, a, r, p); 
        elements = a;//新数组赋值
        head = 0;//head到0的位置
        tail = n;//tail到n的位置
    }

看完这段代码之后我们肯定是疑惑重重，我们先抛砖引玉，介绍一下ArrayDeque的逻辑结构，再通过代码来印证。
ArrayDeque存储是用一个一位数组，但是通过head和tail两个指针来实现一个逻辑上的环状结构。
往下讲之前，关于(tail + 1) & (elements.length - 1)，我们能在代码里看到一堆这种代码，其实这是一种取模的操作，HashMap中也有这种操作，不是很理解的可以看length = 2n 且X>0，X % length = X & (length - 1)

ArrayDeque环状结构的基础

其实我们没有看到head和tail有初始化成某个int值的地方，说明初始值都是0。我们看addFirst和addLast里面分别取head跟tail的位置并做了赋值操作。

//addFirst
elements[head = (head - 1) & (elements.length - 1)] = e;

//addLast
elements[tail] = e;
if ((tail = (tail + 1) & (elements.length - 1)) == head)
     doubleCapacity();

我们看到不管怎么样，head永远-1的，tail永远是+1的，所以可能会有下面两种情况：

Picture A

我然后用两幅图来讲解上面的几个方法：
Picture A 图一：在初始化结束后数组有16位的时候。
这时候调用addFirst会调用 elements[head = (head - 1) & (elements.length - 1)] = e;此时head为0；element.length-1=15;
-> head=(0-1)&15;
-> 11111111111111111111111111111111&1111 = 1111
所以head=15。
调用addTail会先调用elements[tail] = e;这个时候tail=0，所以会先赋值给第0个元素然后调用(tail = (tail + 1) & (elements.length - 1)把tail加一。
所以我们看到addFirst和addTail的区别，除了是head是-1，tail是+1之外，head是先-1就赋值，tail是先+1再赋值。这是因为head跟tail指向的坐标中是否含有元素有关，一张图说明：

Picture B
很明显tail指向的是有效cell的index+1，所以当head==tail的时候，正好是整个elements满了的时候，这个时候就需要调用doubleCapacity()扩容了。还是一幅图来解释:
Picture C

（其实真实情况下不可能出现8个扩容，因为最小容量是16个，但是太多了不好画，我就拿8个画了，原理是一样的。）扩容之后head=0，tail=8。
这个时候如果addTail，tail就变成了tail = (tail + 1) & (elements.length - 1)=9，就会变成上图中Picture A 图二的情况。
这个时候如果继续addFirst()，head就变成了(head-1)&(elements.length-1)=15，又会变成Picture A 图一的情况。
这样一来，ArrayDeque就用两个指针完成了一个环状结构。那怎么判断含有多少元素了呢？

    public int size() {
        return (tail - head) & (elements.length - 1);
    }

tail-head这个值有可能是负的也有可能是正的，看上面Picture A，图一图三都是负数，图二就是正数。正数比较好理解，与上length-1就是自己，负数就不好理解了。
我们再看Picture B，length是16，tail=3，head=13，所以length=(3-13)&(16-1); -> (-10)&15
-10 -> 11111111111111111111111111110110
15 -> 1111
0110 & 1111 -> 0110 也就是6。很巧妙。

为什么求容量是tail-head呢？
如果是PictureA图一的情况：
∵ tail = 数据A => 数据A = tail
∵ head = length - 数据B -> 数据B = length + 1 - head
∴ 数据A + 数据B = tail + (length - head) = tail - head + length
如果是PictureA图二的情况：
数据就直接是：
数据 = tail - head
所以数据 = tail - head + length * n (n∈[0,1])。
那看起来这个数据是可能大于length，其实不然，这种情况是建立在head比较大的情况下的，实际的值还是小于length的。
然后作取模运算就是 (tail - head + length * n) & (length -1) => (tail - head) & (elements.length - 1)
结果就这样得出来了。
其实刚开始我很疑惑，因为tail-head有可能是负的，负数跟length-1做与运算是个什么情况，应该怎么算呢？比如上面的例子length=(3-13)&(16-1) 结果是6。
-10&15应该怎么理解呢，你看根据我们上面的结论：
数据 = tail - head + length * n (n∈[0,1])。
So：-10&(16-1) = -10+16&(16-1) = 6&(16-1) = 6。这样来理解就好了。

总结：
1、ArrayDeque是逻辑上的环状结构，实际存储使用了一维数组，用两个指针tail，head实现逻辑上的环形。
2、如果给定一个自定义的长度，allocateElements使用一直右移的方法找到离此长度最近的10...000
3、ArrayDeque的长度必须为2ⁿ，利于定位元素存储的位置。
4、doubleCapacity扩容时从index 0开始先放head的元素再放tail的元素。
5、使用(tail - head) & (elements.length - 1)计算数据长度