天天看点
返回

ArrayDeque原理详解

介绍

ArrayDeque是双向队列，线程不安全的双向队列，长度可以自己扩容的双向队列，并且长度需要是2的幂次方，双端主要是头部和尾部两端都可以进行插入删除和获取操作，该实现类实现了Deque接口，Deque接口提供了双向队列需要实现的方法，接口提供了从头部插入、尾部插入，从头部获取、尾部获取以及删除等操作。ArrayDeque从名称来看能看出ArrayDeque内部使用的是数组来进行存储元素。

类图

ArrayDeque原理详解

通过类图也可以清晰的看到ArrayDeque继承自Deque接口，并且继承自Queue接口。同时也继承自Collection接口说明可以使用迭代器进行遍历集合。

源码分析

在分析源码之前，我们可以试想一些问题，前文已经介绍过ArrayDeque内部使用的数组元素来进行存储，数组中是如何控制从头部进行插入的呢？当数组为空时，从头部插入元素是如何实现的？以及数组元素中有值时，比如数组a=[1,2,3]，这时候数组元素0的位置是有元素的，那又是如何将元素插入到数组下标0的元素之前的呢？前文讲述过数组的长度是2的幂次方？为什么数组的长度要是2的幂次方呢？带着这个问题来看源码的分析。

字段信息

由于Deque接口是双向队列，所以再进行添加元素的时候会指定head指针和tail尾指针，head指针指向数据元素的头部，tail指针指向数据元素的尾部，通过head指针和tail指针控制是从头部进行操作还是尾部进行操作，以下是ArrayDeque中的字段信息：

/**
 * 数组存储的元素。
 */
transient Object[] elements; // non-private to simplify nested class access

/**
 * 头指针。
 */
transient int head;

/**
 * 尾指针。
 */
transient int tail;

/**
 * 数组的默认最小大小。长度必须是2的幂次方。
 */
private static final int MIN_INITIAL_CAPACITY = 8;

calculateSize方法

首先我们来解决第一个问题，就是数组的长度的问题，数组长度前面说必须是2的幂次方，但是看到构造函数中可以指定数组的长度，既然可以指定数组的长度，那这里指定数组长度为10，这个数字也不是2的幂次方啊，其实我们指定的虽然不是2的幂次方，但是ArrayDeque内部会帮我进行调整，调整数组长度为2的幂次方，先看一下ArrarDeque的构造函数：

// 默认长度为16的数组。
public ArrayDeque() {
    elements = new Object[16];
}

/**
 * 指定数组长度，发现指定数组长度时，调用了allocateElements方法。
 */
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

/**
 * 指定集合并且初始化大小。
 */
public ArrayDeque(Collection<!--? extends E--> c) {
    allocateElements(c.size());
    addAll(c);
}

构造函数中除了第一个默认构造函数之外，其他两个构造函数都调用了

allocateElements

方法来进行初始化数组的动作以及容量调整的动作，接下来我们来分析下是如何做到容量是2的幂次方？

/**
 * 初始化数组大小，调用calculateSize方法来调整容量大小。
 */
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}

上面的方法对数组元素进行初始化，在初始化前需要进行容量的调整，实际调整容量大小的方法是calculateSize方法。

private static int calculateSize(int numElements) {
  	// 获取最小的初始化容量大小。
    int initialCapacity = MIN_INITIAL_CAPACITY;
		// 如果容量大于最小的容量，则寻找一个2的幂次方的值。
    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
    }
  	// 返回2的幂次方值。
    return initialCapacity;
}

以开始时的例子为主，比如我们在初始化ArrayDeque指定了数组长度为10，它在进行初始化数组大小时会调用calculateSize来计算一个2的幂次方的值。

public static void main(String[] args) {
    ArrayDeque<integer> arrayDeque = new ArrayDeque<>(10);
}
  1. 程序运行到第五行时，numElements >= initialCapacity成立，10>=8，则会进入到if语句内部。
  2. 程序运行到第六行时， initialCapacity = numElements，initialCapacity 设置为10，10的二进制表示方式是1010。
  3. 程序运行到第七行时， initialCapacity无符号向右移动一位，1010无符号向右移动一位是0101，1010|0101=1111，十进制表示方式是15。
  4. 程序运行到第七行时， initialCapacity无符号向右移动一位，1111无符号向右移动一位是0011，1111|0011=1111，十进制表示方式是15，一直持续下去都是15，当程序运行到第12行时，15进行加1操作，则变成16。这个时候16就是2的幂次方返回。

整体思路是每次移动将位数最高的值变成1，从而将二进制所有位数都变成1，变成1之后得到的十进制加上1之后得到值就是2的幂次方的值，这里的操作在JDK1.7版本中的HashMap扩容操作代码是类似的。

AddFirst方法

以上就是如何保证了数组的大小是2的幂次方的代码逻辑，代码设计很巧妙，2的幂次方数组大小有什么好处呢？其实这里我可以简单描述下好处在于可以控制指针的在数组中的位置，也就是可以解决第一个问题，接下来再往下继续进行分析数组进行头部插入时的内容，先上源码先上源码：

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

在头部进行插入元素，比如我们看一下如下代码的运行结果，先进行头部进行插入，然后再尾部插入，看一下整体的插入过程，通过这个简单的实例能够了解为什么数组长度设置为2的幂次方。

public static void main(String[] args) {
    ArrayDeque<integer> arrayDeque = new ArrayDeque<>(10);
    arrayDeque.addFirst(5);
    arrayDeque.addLast(1);
    arrayDeque.forEach(System.out::println);
}

此时初始化时数组长度为16，头指针head和尾指针head默认是0，此时数组的内容如下所示：

ArrayDeque原理详解

当执行addFirst方法插入数组元素5时，通过源码可以看到需要执行

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

这一行代码，至于后面那个headtail是为了扩容使用，也就是只有在队列满时才会对数组进行扩容操作，队列满的标识是headtail代表队列已经满了，这里先进行分析

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

，我们将其拆分成如下内容

  • head=head-1，此时的head=0，那么head-1得到值15（二进制减法操作），15使用二进制表示为：1111
  • elements.length - 1，这里开始是初始化大小为10，通过calculateSize方法计算的到数组长度为16，16-1=15，二进制表示方式也是1111。
  • 1111&1111依然是1111，此时数组的下标为15。

咦？通过这个算出来的下标竟然是15，而不是0？可能大家猜想的是在头部插入时会当数组为空时，它会插入到数组的元素下标0的位置，其实并不是，而是插入到下标为15的位置处，通过图示法来看一下：

ArrayDeque原理详解

插入到下标为15的位置是因为，假如我们在0，1，2下标位置插入值后，在通过头插法插入值时，发现数组的头部已经没有位置了，它会利用数组的尾部进行插入，head会指向尾部的位置，这也是为什么数组要设置为2的幂次方的原因，是为了能够定位数组的中头指针的位置，大家看到头指针前一个指针是

head = (head - 1) & (elements.length - 1)

，那大胆猜测一下头指针的下一个指针指向的

head = (head + 1) & (elements.length - 1)

，这个我们后面来验证。

AddLast方法

还是回到上面的例子中，这里只是运行到了addFirst，继续运行addLast内容，首先先上源码，然后在针对源码进行分析：

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

这里从尾指针进行插入看着还是比较简单的，直接使用

elements[tail] = e;

即可，此时数组中元素存储情况以及tail指针移动位置。

ArrayDeque原理详解

此时tail指针是进行增加1，也就是会运行到

tail = (tail + 1) & (elements.length - 1)

这里，这里判断tail的下一个节点如果和head节点重合说明数组已经满了，需要进行扩容操作，相当于如下所示：

ArrayDeque原理详解

当有线程再对ArrayDeque队列进行插入值时，这是tail值插入值后，tail会指向head节点，此时head和tail进行重合，重合后进行扩容操作，如下图所示：

ArrayDeque原理详解

ArrayDeque双向队列巧妙的运用了数组的头部和尾部，简单点说头指针在获取数据时，需要将头指针进行增加1操作，当头指针达到数组尾部时，将头指针指向数组的头部，从数组的头部进行获取数据。如果从尾指针获取数据时，其实就是从尾指针数据进行减少1操作，向前进行获取数据，如果达到了数组头部，则将尾指针指向数组的数组的尾部，从尾部往前在进行寻找，如果找到值为空说明数组为空了。

pollFirst方法

当然ArrayDeque对获取数据还有peekFirst和peekLast，这两个方法比较简单，就是获取对应指针值，这里就不再赘述了，这里重点讲一下pollFirst和pollLast方法。

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

演示下刚才插入的两个元素情况进行pollFirst是一种什么样的操作，插入之后数组元素是这样的。

ArrayDeque原理详解

当pollFirst时，此时head=15，h=15，result=elements[15]=5，并且将 elements[15]设置为null，此时数组为：

ArrayDeque原理详解

设置为空后会执行如下语句，head = (h + 1) & (elements.length - 1)，啊哈，这里和上文中猜测的内容是一样的，h+1=15+1=16，用二进制表示1 0000，数组长度为16，16-1=15，用二进制表示1111，相当于1111&0000=0，此时数组head节点被调整到数组的头部，head=0。此时数组为：

ArrayDeque原理详解

pollLast方法

这里还是回归到插入两个元素的情况，即如下状态：

ArrayDeque原理详解

先看一下源码信息，如下所示：

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

当调用pollLast时，首先运行的是 int t = (tail - 1) & (elements.length - 1)，此时tail=1，tail-1=0，二进制表示为0000，elements.length - 1=16-1=15，用二进制表示为1111，0000&1111=0，则代表尾指针的最后一个元素存储的内容在尾指针的前一个坐标，此时获取数组下标为0的值，result=1，将 elements[t]设置为null，此时数组为：

ArrayDeque原理详解

接着将tail=t，t=0，将尾指针调整到0的位置，此时数组内容：

ArrayDeque原理详解

其他用法

在源码中还看到了removeFirst和removeLast其实内部调用的就是pollFist和pollLast方法，以及存在栈功能的pop方法和push方法，其实内部调用的就是addFist和pollFist的操作，这里就不在进行一一讲解了，主要方法都在上面讲述了。

总结

  1. ArrayDeque是一个双向队列，线程非安全。
  2. ArrayDeque是基于数组来进行实现的。
  3. ArrayDeque的数组长度是2的幂次方。
  4. 指针下一个和上一个表示方式：
    • 头指针的前一个节点定位坐标：(head-1)&(elements.length - 1)，下一个节点位置：(head+1)&(elements.length - 1)
    • 尾指针的前一个节点定位坐标：(tail-1)&(elements.length - 1)，下一个节点位置：(tail+1)&(elements.length - 1)
    • 总结起来就是前一个节点位置：(i-1)&(elements.length - 1)，下一个位置：(i+1)&(elements.length - 1)

喜欢的朋友可以关注我的微信公众号BattleHeart，不定时推送文章

上一篇: JVM性能优化
下一篇: IE 凉了？怎么可能！