9.3 剖析ArrayDeque

发表于 更新于 分类于 ， ， Waline： 本文字数： 5.9k 阅读时长 ≈ 5 分钟

9.3 剖析ArrayDeque

LinkedList实现了队列接口Queue和双端队列接口Deque, Java容器类中还有一个双端队列的实现类ArrayDeque，它是基于数组实现的。我们知道，一般而言，由于需要移动元素，数组的插入和删除效率比较低，但ArrayDeque的效率却非常高，它是怎么实现的呢？本节就来详细探讨。

ArrayDeque有如下构造方法：

1
2
3
public ArrayDeque()
public ArrayDeque(int numElements)
public ArrayDeque(Collection<? extends E> c)

numElements表示元素个数，初始分配的空间会至少容纳这么多元素，但空间不是正好numElements这么大，待会我们会介绍其实现细节。

ArrayDeque实现了Deque接口，同LinkedList一样，它的队列长度也是没有限制的， Deque扩展了Queue，有队列的所有方法，还可以看作栈，有栈的基本方法push/pop/peek，还有明确的操作两端的方法如addFirst/removeLast等，具体用法与LinkedList一节介绍的类似，就不赘述了，下面看其实现原理（基于Java
7）。

9.3.1 实现原理

ArrayDeque内部主要有如下实例变量：

1
2
3
private transient E[] elements;
private transient int head;
private transient int tail;

elements就是存储元素的数组。ArrayDeque的高效来源于head和tail这两个变量，它们使得物理上简单的从头到尾的数组变为了一个逻辑上循环的数组，避免了在头尾操作时的移动。我们来解释下循环数组的概念。

1．循环数组

对于一般数组，比如arr，第一个元素为arr[0]，最后一个为arr[arr.length-1]。但对于ArrayDeque中的数组，它是一个逻辑上的循环数组，所谓循环是指元素到数组尾之后可以接着从数组头开始，数组的长度、第一个和最后一个元素都与head和tail这两个变量有关，具体来说：
1）如果head和tail相同，则数组为空，长度为0。
2）如果tail大于head，则第一个元素为elements[head]，最后一个为elements[tail-1]，长度为tail-head，元素索引从head到tail-1。
3）如果tail小于head，且为0，则第一个元素为elements[head]，最后一个为elements [elements.length-1]，元素索引从head到elements.length-1。
4）如果tail小于head，且大于0，则会形成循环，第一个元素为elements[head]，最后一个是elements[tail-1]，元素索引从head到elements.length-1，然后再从0到tail-1。

我们来看一些图示。第一种情况，数组为空，head和tail相同，如图9-6所示。

epub_923038_63

图9-6 循环数组：head和tail相同

第二种情况，tail大于head，如图9-7所示，都包含三个元素。

epub_923038_64

图9-7 循环数组：tail大于head

第三种情况，tail为0，如图9-8所示。

epub_923038_65

图9-8 循环数组：tail为0

第四种情况，tail不为0，且小于head，如图9-9所示。

epub_923038_66

图9-9 循环数组：tail不为0且小于head

2．构造方法

默认构造方法的代码为：

1
2
3
public ArrayDeque() {
    elements = (E[]) new Object[16];
}

分配了一个长度为16的数组。如果有参数numElements，代码为：

1
2
3
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

不是简单地分配给定的长度，而是调用了allocateElements。这个方法的代码看上去比较复杂，我们就不列举了，它主要就是在计算应该分配的数组的长度，计算逻辑如下：
1）如果numElements小于8，就是8。
2）在numElements大于等于8的情况下，分配的实际长度是严格大于numElements并且为2的整数次幂的最小数。比如，如果numElements为10，则实际分配16，如果num-Elements为32，则为64。

为什么要为2的幂次数呢？我们待会会看到，这样会使得很多操作的效率很高。为什么要严格大于numElements呢？因为循环数组必须时刻至少留一个空位，tail变量指向下一个空位，为了容纳numElements个元素，至少需要numElements+1个位置。

看最后一个构造方法：

1
2
3
4
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

同样调用allocateElements分配数组，随后调用了addAll，而addAll只是循环调用了add方法。下面我们来看add的实现。

3．从尾部添加

add方法的代码为：

1
2
3
4
public boolean add(E e) {
    addLast(e);
    return true;
}

addLast的代码为：

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

将元素添加到tail处，然后tail指向下一个位置，如果队列满了，则调用doubleCapa-city扩展数组。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，对于负数-1，与7相与，结果为7，对于正数8，与7相与，结果为0，都能达到循环数组中找下一个正确位置的目的。这种位操作是循环数组中一种常见的操作，效率也很高，后续代码中还会看到。

doubleCapacity将数组扩大为两倍，代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 = (E[])a;
    head = 0;
    tail = n;
}

分配一个长度翻倍的新数组a，将head右边的元素复制到新数组开头处，再复制左边的元素到新数组中，最后重新设置head和tail, head设为0, tail设为n。

我们来看一个例子，假设原长度为8, head和tail为4，现在开始扩大数组，扩大前后的结构如图9-10所示。

epub_923038_67

图9-10 循环数组：扩容前后对比

add是在末尾添加，我们再看在头部添加的代码。

4．从头部添加

addFirst()方法的代码为：

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

在头部添加，要先让head指向前一个位置，然后再赋值给head所在位置。head的前一个位置是(head-1) & (elements.length-1)。刚开始head为0，如果elements.length为8，则(head-1) & (elements.length-1)的结果为7。比如，执行如下代码：

1
2
3
Deque<String> queue = new ArrayDeque<>(7);
queue.addFirst("a");
queue.addFirst("b");

执行完后，内部结构如图9-11所示。

epub_923038_68

图9-11 循环数组：从头部添加后

介绍完了添加，下面来看删除。

5．从头部删除

removeFirst方法的代码为：

1
2
3
4
5
6
public E removeFirst() {
    E x = pollFirst();
    if(x == null)
        throw new NoSuchElementException();
    return x;
}

主要调用了pollFirst方法，pollFirst方法的代码为：

1
2
3
4
5
6
7
8
9
public E pollFirst() {
    int h = head;
    E result = 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，然后head置为下一个位置，下一个位置为(h+1) & (elements.length-1)。从尾部删除的代码是类似的，就不赘述了。

6．查看长度

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

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

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

7．检查给定元素是否存在

contains方法的代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean contains(Object o) {
    if(o == null)
        return false;
    int mask = elements.length - 1;
    int i = head;
    E x;
    while( (x = elements[i]) ! = null) {
        if(o.equals(x))
            return true;
        i = (i + 1) & mask;
    }
    return false;
}

就是从head开始遍历并进行对比，循环过程中没有使用tail，而是到元素为null就结束了，这是因为在ArrayDeque中，有效元素不允许为null。

8. toArray方法

toArray方法的代码为：

1
2
3
public Object[] toArray() {
    return copyElements(new Object[size()]);
}

copyElements的代码为：

1
2
3
4
5
6
7
8
9
10
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;
}

如果head小于tail，就是从head开始复制size个，否则，复制逻辑与doubleCapacity方法中的类似，先复制从head到末尾的部分，然后复制从0到tail的部分。

9．原理小结

以上就是ArrayDeque的基本原理，内部它是一个动态扩展的循环数组，通过head和tail变量维护数组的开始和结尾，数组长度为2的幂次方，使用高效的位操作进行各种判断，以及对head和tail进行维护。

9.3.2 ArrayDeque特点分析

ArrayDeque实现了双端队列，内部使用循环数组实现，这决定了它有如下特点。
1）在两端添加、删除元素的效率很高，动态扩展需要的内存分配以及数组复制开销可以被平摊，具体来说，添加N个元素的效率为O(N)。
2）根据元素内容查找和删除的效率比较低，为O(N)。
3）与ArrayList和LinkedList不同，没有索引位置的概念，不能根据索引位置进行操作。

ArrayDeque和LinkedList都实现了Deque接口，应该用哪一个呢？如果只需要Deque接口，从两端进行操作，一般而言，ArrayDeque效率更高一些，应该被优先使用；如果同时需要根据索引位置进行操作，或者经常需要在中间进行插入和删除，则应该选LinkedList。

至此，关于列表和队列的内容就介绍完了，无论是ArrayList、LinkedList还是Array-Deque，按内容查找元素的效率都很低，都需要逐个进行比较，有没有更有效的方式呢？让我们下一章来看各种Map和Set。