Java ArrayDeque 原理之循环数组

2018-01-22 本文已影响0人 Little丶Jerry

问：谈谈你对 ArrayDeque 主要方法实现原理的认识？

答：即循环数组的实现原理。

从 ArrayDeque 命名就能看出他的实现基于数组（LinkedList 是基于链表实现的双端队列），但是 ArrayDeque 的数组是一个可扩容动态数组，每次队列满了就会进行扩容，除非扩容至 int 边界才会抛出异常，ArrayDeque 不允许元素为 null。ArrayDeque 的主要成员是一个 elements 数组和 int 的 head 与 tail 索引，head 是队列的头部元素索引，而 tail 是队列下一个要添加的元素的索引，elements 的默认容量是 16 且默认容量必须是 2 的幂次，不足 2 的幂次会自动向上调整为 2 的幂次。

ArrayDeque 获取队列头部元素的 element()\getFirst()\peek()\peekFirst() 操作，其都是调用 getFirst() 实现的，访问队列头部元素但不删除，即如下：

    public E getFirst() {
        @SuppressWarnings("unchecked")
        //获取head索引处的元素
                E result = (E) elements[head];
        if (result == null) throw new NoSuchElementException();
        return result;
    }

ArrayDeque 删除队列头部元素的 remove()\removeFirst()\poll()\pollFirst() 操作，其都是调用 pollFirst() 实现的，移除队列头部元素且返回被移除的元素，即如下：

    public E pollFirst() {
        final Object[] elements = this.elements;
        final int h = head;
        @SuppressWarnings("unchecked")
        //取出队列头部索引处的元素
                E result = (E) elements[h];
        // Element is null if deque empty
        if (result != null) {
            //将head头位置元素置空，即删除元素
            elements[h] = null;//Must null out slot 
            // 删除后把head索引向前移动一个位置 
            // (h + 1)操作就是head索引移动，后面的按位&操作是为了防止索引越界和head循环 
            head = (h + 1) & (elements.length - 1);
        }
        return result;
    }

ArrayDeque 添加元素到队列尾部的操作可以发现 add(E e)\offer(E e)\offerLast(E e)\addLast(E e) 操作都是调用 addLast(E e) 实现的，即如下：

    public void addLast(E e) {
        //如果元素为空抛出异常 
        if (e == null) throw new NullPointerException();
        // 将新添加到尾部的元素放在索引为tail的地方 
        elements[tail] = e;
        // 判断tail和head是否相等，如果相等则对数组进行扩容 
        if ((tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity();
    }

    private void doubleCapacity() {
        // 双倍扩容，然后head为0，tail为n，即tail为下一个要插入元素的索引
         ......
        // int n = elements . length ;
         ......
        // int newCapacity = n << 1 ; 
        ......
        elements = a;
        head = 0;
        tail = n;
    }

addLast 的实现原理，也就是那句 if 操作与双倍扩容到底是做了什么，所以我们先看下不扩容情况下 ArrayDeque 相关操作的图解，如下：

正如上图中最后的多次操作结果所示，如果此时我们再 add 操作一个元素到 tail 索引处则 tail+1 会变成 8 导致数组越界，理论上来说这时候应该进行扩容操作了，但是由于下标为 0、1、2、3 处没有存储元素，直接扩容有些浪费（ArrayList 为了避免浪费是通过拷贝将删除之后的元素整体前挪一位），所以为了高效利用数组中现有的剩余空间就有了 addLast(E e) 中的代码 (tail = (tail + 1) & (elements.length - 1)); 实质类似上面 pollFirst() 里面 head 操作，即假设 elements 默认初始化长度是 8，则当前 tail + 1（8=1000）按位与上数组长度减一（7=0111）的结果为十进制的 0，所以下一个被 addLast(E e) 的元素实际会放在索引为 0 的位置，再下一个会放在索引为 1 的位置，如下图：

可以看到，随着出队入队不断操作，如果 tail 移动到 length-1 之后数组的第一个位置 0 处没有元素则需要将 tail 指向 0，依次循环，当 tail 如果等于 head 时说明数组要满了，接下来需要进行数组扩容，所以就有了上面 addLast(E e) 里面那个 if 判断的逻辑去触发 doubleCapacity()。因此这也就解释了为什么 ArrayDeque 的初始容量必须是 2 的幂次（扩容每次都是成倍的，所以自然也满足 2 的幂次），因为只有容量为 2 的幂次时 ((tail + 1) & (elements.length - 1)) 操作中的 (elements.length - 1) 二进制最高位永远为 0，当 (tail + 1) 与其按位与操作时才能保证循环归零置位。

ArrayDeque 的 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;
        if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        //扩容后分两次复制，head到当前数组末尾
        System.arraycopy(elements, p, a, 0, r);
        // 当前数组头到tail位置 
        System.arraycopy(elements, 0, a, r, p);
        //相关索引置位
        elements = a;
        head = 0;
        tail = n;
    }

上面的扩容操作流程演示如下：

所以 ArrayDeque 是一个双向循环队列，其基于数组实现了双向循环操作（依赖按位与操作循环），初始容量必须是 2 的幂次，默认为 16，存储的元素不能为空，非线程并发安全。

Java ArrayDeque 原理之循环数组

猜你喜欢

热点阅读