集合源码解析之ArrayDeque

     今天我们来说说ArrayDeque.很多人可能没用过甚至都没有听过这个类.当需要使用栈时,官
 方已不推荐Stack,而是推荐使用效率更高的ArrayDeque(次选LinkedList).

概述

双端队列是一种两端皆可实现进出的特殊队列,而ArrayDeque便是Java中一个双端队列的实现.它内部基于数组存储数据,维护两个指针分别指向首尾,可以更高效的进行元素的插入和查找.其作为栈使用比Stack效率高,作为队列使用比LinkedList快,可以说ArrayDeque是用作队列,栈的不二选择.

源码分析

结构图

ArrayDeque结构图

继承关系

    public class ArrayDeque<E> extends AbstractCollection<E>
                               implements Deque<E>, Cloneable, Serializable{

AbstractCollection是Collection接口唯一子类且是个抽象类,提供了对集合操作的基本实现.ArrayDeque实现了Deque接口,说明它是一个双端队列,支持首尾进出操作.

类中属性

    /** 版本号 */
    private static final long serialVersionUID = 2340985798034038923L;
    
    /** 核心数组 (基于head&tail逻辑实现循环数组) **/
    transient Object[] elements;
    
    /** 头指针 **/
    transient int head;
    
    /** 尾指针(指向最后一个节点的下一个位置) **/
    transient int tail;
    
    /** 最小容量 (长度需保持2的幂,便于把求余操作转为移位操作) **/
    private static final int MIN_INITIAL_CAPACITY = 8;

上述属性中elements就是存数据的核心数组,其大小始终为2的幂次方.这个数组每次都会在add方法中进行动态扩容,使head和tail不会交叉.
head标识双端队列中头元素的位置.tail为双端队列的末端,始终是空的,每次尾部添加数据,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,我们来看看它的实现:

    /** 数组分配及大小调整 */
    private void allocateElements(int numElements) {
        // 最小容量
        int initialCapacity = MIN_INITIAL_CAPACITY;
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0) 
                initialCapacity >>>= 1;
        }
        elements = new Object[initialCapacity];
    }

allocateElements函数主要用于给内部数组分配合适的大小使数组容量始终保持2^n .如果指定大小numElements小于MIN_INITIAL_CAPACITY,那么容量将设置成8,否则通过多次右移和位或运算分配容量为大于numElements且最小的2次幂.
>>>为无符号右位移操作符,如上经过五次位移和位或操作可以保证得到2^k-1,再加1即可.
最后一小节:

if (initialCapacity < 0) 
    initialCapacity >>>= 1;

这是防止给定的numElements过大,导致位操作得到int最大值,再加1,则溢出变成负数,所以需要检测临界点回退一位.
即指定容量为111111111111111111111111111111031位1(十进制为2147483646)经过各位操作后得111111111111111111111111111111132位1(十进制为2147483647)为int最大值.

常用函数

操作	队首	失败抛异常	失败返回特殊值	队尾	失败抛异常	失败返回特殊值
插入		addFirst(E)	offerFirst(E)		addLast(E)	offerLast(E)
移除		removeFirst()	pollFirst()		removeLast()	pollLast()
获取		getFirst()	peekFirst()		getLast()	peekLast()

添加函数

void addFirst(E e)

    /** 队首插入元素,为null抛异常 **/
    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        // 核心代码
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }

addFirst函数核心代码elements[head = (head - 1) & (elements.length - 1)] = e,同样也是为什么数组容量为2的次幂原因:当length为2的次幂时,某整数n & (length - 1) 等价于 n % length ,且对二进制而言& 操作要比 % 效率更好.
如下图:

添加过程

当head为0的时候就会head指针移动到数组末尾.如若head == tail则触发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; // 左位移,等同于乘2,保持2的次幂
        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;
    }

doubleCapacity通过数组拷贝和重新调整指针来完成扩容,每次扩容为原大小的2倍,保持2^n . 如下图:

扩容

void addLast(E e)

    /** 队尾插入元素,为null抛异常 **/
    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
            
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

addLast和addFirst类似,只不过addLast是控制tail指针,从前往后移动.

删除函数

E pollFirst()

/** 取出并删除队首 为空返回null **/
    public E pollFirst() {
        int h = head;
        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;
    }

取出头元素,如果头元素为空,返回null.否则将头元素置为null,再把head向后移动一位,即加1再和(length-1)按位&计算出新的head.

E pollLast()

/** 取出并删除队尾元素 为空返回null **/
    public E pollLast() {
        int t = (tail - 1) & (elements.length - 1);
        E result = (E) elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;
        return result;
    }

pollLast和pollFirst差不多,先定位尾元素下标取出尾元素,为空返回null,不为空置为null,并把tail指针指向当前下标.

获取函数

    /** 取出队首元素 为空抛异常 **/
    public E getFirst() {
        E result = (E) elements[head];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }

    /** 取出队尾元素 为空返回抛异常 **/
    public E getLast() {
        E result = (E) elements[(tail - 1) & (elements.length - 1)];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }

getFirst和getLast函数较为简单,一个直接获取head元素,一个通过&运算定位下标获取,代码分析到这里就结束了,其他部分也应该能看懂了。

总结

ArrayDeque是Deque的一种具体实现,是基于头尾指针循环利用数组实现的.
每当ArrayDeque容量不足时都会动态扩容,每次扩容容量增加一倍.
ArrayDeque提供了对栈的实现,也可直接作为栈来使用.