ArrayDeque源码解析

来源：

Java编程的逻辑

基于动态扩展的循环数组实现的双端队列

一般而言，由于需要移动元素，数组的插入和删除效率比较低，但ArrayDeque的效率却非常高，因为内部是循环数组

2 实现原理

2.1 Deque接口

此接口扩展了Queue接口，可以看做一个先进先出的队列，还可以看做栈

2.2 内部组成

主要有如下实例变量：

transient Object[] elements;
transient int head;
transient int tail;

ArrayDeque的高效来源于head和tail这两个变量，它们使得物理上简单的从头到尾的数组变为了一个逻辑上循环的数组，避免了在头尾操作时的移动（循环数组）

2.2.1 循环数组

所谓循环是指元素到数组尾之后可以接着从数组头开始，数组的长度、第一个和最后一个元素都与head和tail这两个变量有关，具体来说分为四种情况：

如果head和tail相同，则数组为空，长度为0。

[外链图片转存失败(img-zKbKZcCf-1564757029381)(…/…/markdownPicture/assets/1564753602782.png)]
如果tail大于head，则第一个元素为elements[head]，最后一个为elements[tail-1]，长度为tail-head，元素索引从head到tail-1。

[外链图片转存失败(img-bd3FDKMP-1564757029388)(…/…/markdownPicture/assets/1564753609600.png)]
如果tail小于head，且为0，则第一个元素为elements[head]，最后一个为elements[elements.length-1]，元素索引从head到elements.length-1。

[外链图片转存失败(img-km4SP5WD-1564757029390)(…/…/markdownPicture/assets/1564753616431.png)]
如果tail小于head，且大于0，则会形成循环，第一个元素为elements[head]，最后一个是elements[tail-1]，元素索引从head到elements.length-1，然后再从0到tail-1。

[外链图片转存失败(img-Vl3ka89Y-1564757029392)(…/…/markdownPicture/assets/1564753622616.png)]

2.3 构造方法

默认构造方法的代码为：

//分配了一个长度为16的数组
public ArrayDeque() {
    elements = new Object[16];
}

如果有参数numElements，代码为：

public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

private void allocateElements(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        //将initialCapacity左边最高位的1复制到右边的每一位
        //这种复制类似于病毒复制，是1传2、2传4、4传8式的指数级复制
        //最后再执行initialCapacity++就可以得到比initialCapacity大且为2的幂次方的最小的数。
        //Integer的一些二进制操作中就有非常类似的代码，如highestOneBit
        //假设numElements为32，即0010 0000 则逐步变为：
        initialCapacity |= (initialCapacity >>>  1);//0011 0000
        initialCapacity |= (initialCapacity >>>  2);//0011 1100
        initialCapacity |= (initialCapacity >>>  4);//0011 1111
        initialCapacity |= (initialCapacity >>>  8);//0011 1111
        initialCapacity |= (initialCapacity >>> 16);//0011 1111
        initialCapacity++;//0100 0000
		//溢出处理
        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    elements = new Object[initialCapacity];
}

计算应该分配的数组长度initialCapacity，计算逻辑：

如果numElements小于MIN_INITIAL_CAPACITY，则分配的数组长度就是MIN_INITIAL_CAPACITY，它是一个静态常量，值为8。
在numElements大于等于8的情况下，分配的实际长度是严格大于numElements并且为2的整数次幂的最小数。比如，如果numElements为10，则实际分配16，如果numElements为32，则为64。

要为2的幂次数的原因：这样会使得很多操作的效率很高，后续会讲到(如addLast方法)

要严格大于numElements的原因：因为循环数组必须时刻至少留一个空位，tail变量指向下一个空位，为了容纳numElements个元素，至少需要numElements+1个位置。

最后一个构造方法：

//同样调用allocateElements分配数组，随后调用了addAll
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

2.4 从尾部添加元素

public boolean add(E e) {
    addLast(e);
    return true;
}

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    //如果队列满了，则调用doubleCapacity扩展数组
    //tail的下一个位置是：(tail + 1) & (elements.length - 1)
    //如果与head相同，则队列就满了。
    //需要进行与操作是要保证索引在正确范围；
    //与(elements.length - 1)相与就可以得到下一个正确位置，是因为elements.length是2的幂次方，(elements.length - 1)的后几位全是1，无论是正数还是负数，与(elements.length - 1)相与都能得到期望的下一个正确位置。
	//比如说，如果elements.length为8，则(elements.length - 1)为7，二进制为0111；
    //对于tail为6，加1为7，与7相与，结果为7；对于tail为7，加1为8，与7相与，结果为0（-1&7也为7）
    //都能达到循环数组中找下一个正确位置的目的。
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

//将数组扩大为两倍，此时head == tail
//分配一个长度翻倍的新数组a，将head(tail)右边的元素拷贝到新数组开头处，再拷贝左边的元素到新数组中
//最后重新设置head和tail，head设为0，tail设为n
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;
}

2.5 从头部添加元素

//在头部添加，要先让head指向前一个位置，然后再赋值给head所在位置。
//head的前一个位置是：(head - 1) & (elements.length - 1)。
//刚开始head为0，如果elements.length为8，则(head - 1) & (elements.length - 1)的结果为7。
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

2.6 从头部删除元素

//将原头部位置置为null，然后head置为下一个位置，下一个位置为：(h + 1) & (elements.length - 1)。 
public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

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

2.7 从尾部删除元素

public E removeLast() {
    E x = pollLast();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}
//t为新的最后一个位置，result为最后一个元素，将该位置置为null，然后修改tail指向前一个位置，最后返回原最后一个元素。
public E pollLast() {
    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;
}

2.8 查看长度

ArrayDeque没有单独的字段维护长度，其size方法的代码为：

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

通过该方法即可计算出size。

2.9 检查给定元素是否存在

//从head开始遍历并进行对比，循环过程中没有使用tail，而是到元素为null就结束了；
//因为在ArrayDeque中，有效元素不允许为null
public boolean contains(Object o) {
    if (o == null)
        return false;
    int mask = elements.length - 1;
    int i = head;
    Object x;
    while ( (x = elements[i]) != null) {
        if (o.equals(x))
            return true;
        i = (i + 1) & mask;
    }
    return false;
}

2.10 toArray方法

public Object[] toArray() {
    return copyElements(new Object[size()]);
}
//如果head小于tail，就是从head开始拷贝size()个；
//否则，拷贝逻辑与doubleCapacity方法中的类似，先拷贝从head到末尾的部分，然后拷贝从0到tail的部分
private <T> T[] copyElements(T[] a) {
    if (head < tail) {
        System.arraycopy(elements, head, a, 0, size());
    } else if (head > tail) {
        int headPortionLen = elements.length - head;
        System.arraycopy(elements, head, a, 0, headPortionLen);
        System.arraycopy(elements, 0, a, headPortionLen, tail);
    }
    return a;
}

3 特点分析

ArrayDeque实现了双端队列，内部使用循环数组实现，这决定了它有如下特点：

在两端添加、删除元素的效率很高，动态扩展需要的内存分配以及数组拷贝开销可以被平摊，具体来说，添加N个元素的效率为O(N)。
根据元素内容查找和删除的效率比较低，为O(N)。
与ArrayList和LinkedList不同，没有索引位置的概念，不能根据索引位置进行操作。

ArrayDeque和LinkedList都实现了Deque接口，应该用哪一个呢？

如果只需要Deque接口，从两端进行操作，一般而言，ArrayDeque效率更高一些，应该被优先使用；

不过，如果同时需要根据索引位置进行操作，或者经常需要在中间进行插入和删除，则应该选LinkedList。

ArrayDeque源码解析

2 实现原理

2.1 Deque接口

2.2 内部组成

2.2.1 循环数组

2.3 构造方法

2.4 从尾部添加元素

2.5 从头部添加元素

2.6 从头部删除元素

2.7 从尾部删除元素

2.8 查看长度

2.9 检查给定元素是否存在

2.10 toArray方法

3 特点分析

继续阅读

java编程思想_006短路现象

九、设计模式以及查找、排序算法

这是我见过最简单理解NIO的文章了

Map集合中get不存在的key值，返回值问题

每日一学（14）——（面向对象）抽象类作为方法参数与返回值

effective java-tagged class to hierarchy class

单点登录-CAS

集合练习题1

java 编程思想第四版学习随记

java之单用户登录

Java反射是什么，为什么要用反射

Double类parseDouble和valueOf方法的区别

java调用Windows命令行

如何提高个人开源网站源码开发利用率

java打印任意边长的菱形

java 8 Lamda 求 List 中 Bigdecimal类型的各种值求最大值求最小值求和求平均值