图文并茂分析ArrayDeque源码，达到知根知底，让你面试胖揍面试官

大家好，欢迎来到IT知识分享网。

源码分享说明

1. 本人非常热衷于源码研究，同时也非常愿意将自己在源码方面研究的心得进行分享，如果读者也想对源码进行研究，可以关注我的分享的文章。
2. 在进行源码解析的过程中，将会选择庖丁解牛式的剖析，将会解析清楚每一行核心代码，让读者能够真正透彻理解，这样无论是在以后的面试中还是独立开发中间件都会有很大好处。

序言

1. 本小节从上帝角度分析了整个Java容器类，让读者从宏观上把握，一目了然，对于本小节中涉及的位运算，如果觉得基础不够，可以查看笔者的位运算的那一篇
2. 具体分析了ArrayDeque容器类，从数据结构谈起，由假溢出–顺序队列存储结构的不足过渡到ArrayDeque选择的数据结构，循环队列。通过图文并茂的形式详细分析ArrayDeque中的核心代码，同时打开了容器类源码阅读技巧之门，让源码阅读从晦涩难懂到赏心悦目。
3. 研究Java容器类源码将会获得很多优势。1.Java容器类经常出现在面试中，这样让你在面试中脱颖而出，胖揍面试官。2.对于你学习数据结构和算法打下坚实基础。3.让你编写出高质量代码，具有高效性能和更好代码容错性，考虑问题更全面。

1.Java集合类综述

2.研究心得

整体说一下Java集合类源码研究心得，读者想要能够顺利阅读源码，就得具有两项技能。

1).位运算能力(位运算性能非常好，并且某些功能使用位运算才容易实现，比如hashmap求哈希表容量为2的整数次幂)

2).数据结构能力

Java集合类每一个实现类都是基于某一种特定数据结构，这也是笔者前面3节发大力气介绍位运算和树结构的初衷所在，就是希望读者能够对相应数据结构掌握得非常清楚，如果这两项能力不够扎实，关注笔者，去学习前面的内容，只要具备了这两项能力阅读源代码就是非常容易的事情。

对于任何一个容器类你只需要关注构造器,新增操作，删除操作，修改操作，在进行这些容器怎样调整就可以了

我会详细分析PriorityQueue，ArrayDeque，HashMap，TreeMap这四个核心容器类，通过图文并茂形式解释清楚每一行核心代码，因为在笔者看来这4个类是整个Java集合类中技术含量最高的，有必要讲解清楚，只要读者能够吃透这4个类的源码，再去研究其他的容器的源码将会是非常轻松。

3.涉及数据结构和算法

在容器类中，我们看到了如下数据结构的应用：

1. 动态数组：ArrayList内部就是动态数组，HashMap内部的链表数组也是动态扩展的，ArrayDeque和PriorityQueue内部也都是动态扩展的数组。
2. 链表：LinkedList是用双向链表实现的，HashMap中映射到同一个链表数组的键值对是通过单向链表链接起来的，LinkedHashMap中每个元素还加入到了一个双向链表中以维护插入或访问顺序。
3. 哈希表：HashMap是用哈希表实现的，HashSet, LinkedHashSet和LinkedHashMap基于HashMap，内部当然也是哈希表。
4. 排序二叉树：TreeMap是用红黑树(基于排序二叉树)实现的，TreeSet内部使用TreeMap，当然也是红黑树，红黑树能保持元素的顺序且综合性能很高。
5. 堆：PriorityQueue是用堆实现的，堆逻辑上是树，物理上是动态数组，堆可以高效地解决一些其他数据结构难以解决的问题。
6. 循环数组：ArrayDeque是用循环数组实现的，通过对头尾变量的维护，实现了高效的队列操作。
7. 位向量：EnumSet是用位向量实现的，对于只有两种状态，且需要进行集合运算的数据，使用位向量进行表示、位运算进行处理，精简且高效。

每种数据结构中往往包含一定的算法策略，这种策略往往是一种折中，比如：

1. 动态扩展算法：动态数组的扩展策略，一般是指数级扩展的，是在两方面进行平衡，一方面是希望减少内存消耗，另一方面希望减少内存分配、移动和拷贝的开销。
2. 哈希算法：哈希表中键映射到链表数组索引的算法，算法要快，同时要尽量随机和均匀。
3. 排序二叉树的平衡算法：排序二叉树的平衡非常重要，红黑树是一种平衡算法，AVL树是另一种，平衡算法一方面要保证尽量平衡，另一方面要尽量减少综合开销。

ArrayDeque

4.数据结构分析

1.假溢出–顺序队列存储结构的不足

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

假设是长度为5的数组，初始状态，空队列如所示，front与 rear指针均指向下标为0的位置。

然后入队a1、a2、a3、a4, front指针依然指向下标为0位置，而rear指针指向下标为4的位置

出队a1、a2，则front指针指向下标为2的位置，rear不变，如下图所示，再入队a5，此时front指针不变，rear指针移动到数组之外。

假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。把这种现象叫做假溢出

2.优化–循环队列

存在问题：当不断出队时，队头左边的空间得不到充分利用，导致队列容量越来越小。

问题解决：通过数组实现循环队列来充分利用空间(取模:%)，当记录队尾的变量到达数组长度时，查看记录队头的变量是不是在数组起始位置。若不是，则队尾从数组的起始位置开始存值，并且后移。

实现循环队列的方法：

1. 增加一个属性size用来记录目前的元素个数。目的是当head=rear的时候，通过size=0还是size=数组长度，来区分队列为空，或者队列已满。
2. 数组中只存储数组大小-1个元素，保证rear转一圈之后不会和head相等，也就是队列满的时候，rear+1=head，中间刚好空一个元素。

ArrayDeque采用方法：

ArrayDeque采用第二种方式，即牺牲一个元素空间来区分队空和队满的代码。

1.front变量的含义做一个调整：front直接指向数组队列的第一个元素 front = 0

2.rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置,因为希望空出一个空间做为约定rear = 0

3.当队列满时，条件是rear+1 % maxSize == front [满]

4.当队列为空的条件，rear == front [空]

5.当我们这样分析，队列中的有效数据个数 (rear+maxsize-front) % maxsize

注意：这5个性质一定要牢牢记住并且深厚理解，ArrayDeque中源码就是在这些结论的基础上实现的，从ArrayDeque源码分析中就会让你实际感受到位运算和数据结构的重要性

特殊说在明ArrayDeque源码中，初始时front = tail = 0，如果往队首添加元素front逆时针旋转，往队尾添加元素tail顺时针旋转，当front == tail 说明队列已满，需要进行扩容。

5.具体代码分析

5.1实例变量

/ * The array in which the elements of the deque are stored. * The capacity of the deque is the length of this array, which is * always a power of two. The array is never allowed to become * full, except transiently within an addX method where it is * resized (see doubleCapacity) immediately upon becoming full, * thus avoiding head and tail wrapping around to equal each * other. We also guarantee that all array cells not holding * deque elements are always null. */ transient Object[] elements; // non-private to simplify nested class access / * The index of the element at the head of the deque (which is the * element that would be removed by remove() or pop()); or an * arbitrary number equal to tail if the deque is empty. */ transient int head; / * The index at which the next element would be added to the tail * of the deque (via addLast(E), add(E), or push(E)). */ transient int tail;

5.2核心位运算分析

private void allocateElements(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY; // Find the best power of two to hold elements. // Tests "<=" because arrays aren't kept full. 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 } elements = new Object[initialCapacity]; }

1.结论：上面这个函数的左右找出比numElements大的第一个2的整数次幂的数

如果 numElements = 6；initialCapacity最终为8。

numElements = 10；initialCapacity最终为16。

注意numElements = 8；initialCapacity最终也是为16。

我们这样定义bit位索引顺序，0-15位

假如 n = 0000 0100 1110 0011 从左到右第一个出现1的索引位是11，对应0-10位上面的bit上的0和1不论怎样排列，经过如下运算之后，

总会将n 变为 0000 0111 1111 1111

n |= (n >>> 1); n |= (n >>> 2); n |= (n >>> 4); n |= (n >>> 8); n |= (n >>> 16);

着重分析 n |= (n >>> 1); n |= (n >>> 1) ==>> n = (n >>> 1) | n；

n >>> 1 就是将n原本11号索引位的1置为0,10号索引位置为1，在经过跟n进行|运算的结果赋值给了n，这样n的11-10号索引位都是1，即n = 0000 0110 1110 0011

同理n |= (n >>> 2);这样11-8号索引位都是1，即n = 0000 0111 1110 0011

同理n |= (n >>> 4);这样11-4号索引位都是1，即n = 0000 0111 1111 1011

同理n |= (n >>> 8);这样11-0号索引位都是1，即n = 0000 0111 1111 1111

同理n |= (n >>> 16);这样11-0号索引位都是1，即n = 0000 0111 1111 1111

n + 1 结果就是0000 1000 0000 0000 变成了2的整数次幂

2.当elements.length为2的整数次幂时:

(tail-head)&(elements.length-1)等于 (tail – head)%(elements.length-1)

如果不是2的整数次幂时结论不成立。

如果m = 8;n = 7， n % m = 7; n = 15， n % m = 7;n = 23， n % m = 7;

根据定义%的值我们只要关注m从最高位的1开始到后面为止就可以

对于8 ==>> 0000 0000 0000 1000 即只需要关注 1000 这4位上值就可以。

下面严格证明一下：

假如 n = 0001 0011 1001 1101; mask = 0000 1111 1111 1111

证明 n % mask = n & mask

根据%的定义 我们只需要关注右端12的值就可以，由于mask 右端有12个1，根据&的定义，1跟任何数(0或者1)进行运算，都能够保持原来的值不变。所以 n & mask运算之后，还是可以正确保持右端12位相应的值，所以

n % mask = n & mask

下面证明如果mask 不是 0000 1111 1111 1111 这样的形式，比如 0000 1111 1101 1111。右端第5号索引上的值为0，这一个索引位进行&运算，即使那一位的值为1，最终运算之后也会为0，改变了原有的值，所以只mask不是2的整数次幂 – 1，n % mask = n & mask才会成立，不然就不会成立，为什么Hashmap,ArrayDeque要将数组大小弄成2的整数次幂，就是为了利用这个性质，你们知道，位运算效率非常高。

上面这两个性质在hashmap中也使用到了，读者请牢牢记住。

5.3构造函数

/ * Constructs an empty array deque with an initial capacity * sufficient to hold 16 elements. */ public ArrayDeque() { elements = new Object[16]; } / * Constructs an empty array deque with an initial capacity * sufficient to hold the specified number of elements. * * @param numElements lower bound on initial capacity of the deque */ public ArrayDeque(int numElements) { allocateElements(numElements); } / * Constructs a deque containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. (The first element returned by the collection's * iterator becomes the first element, or <i>front</i> of the * deque.) * * @param c the collection whose elements are to be placed into the deque * @throws NullPointerException if the specified collection is null */ public ArrayDeque(Collection<? extends E> c) { allocateElements(c.size()); addAll(c); }

上面已经对allocateElements这个函数的作用进行了详细分析，这样的话整个构造函数应该还是很容易懂了。

5.4尾部添加

/ * Inserts the specified element at the end of this deque. * * <p>This method is equivalent to {@link #addLast}. * * @param e the element to add * @return {@code true} (as specified by {@link Collection#add}) * @throws NullPointerException if the specified element is null */ public boolean add(E e) { addLast(e); return true; } / * Inserts the specified element at the end of this deque. * * <p>This method is equivalent to {@link #add}. * * @param e the element to add * @throws NullPointerException if the specified element is null */ public void addLast(E e) { if (e == null) throw new NullPointerException(); elements[tail] = e; if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity(); } / * Doubles the capacity of this deque. Call only when full, i.e., * when head and tail have wrapped around to become equal. */ 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; }

elements[tail] = e;

就是将当前元素添加到队尾位置，当然还需要让tail指向下一个位置

分析一下这一段 (tail = (tail + 1) & (elements.length – 1)) == head

tail = (tail + 1) & (elements.length – 1)就是让tail指向循环队列下一个位置

(tail + 1) & (elements.length – 1) == head 说明队列已满，需要进行扩容。

下面着重分析一下扩容的过程，下面这张图形象表达这4行代码想要表达的意图

int r = n - p; // number of elements to the right of p Object[] a = new Object[newCapacity]; System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p);

让我们来看一个例子吧，假如原长度为8，head和tail为4，现在开始扩大数组，扩大后的长度为16，具体结构如下图所示：

5.5头部添加

/ * Inserts the specified element at the front of this deque. * * @param e the element to add * @throws NullPointerException if the specified element is null */ 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。

比如执行如下代码

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

执行后结果如下图所示

5.6头部删除

/ * @throws NoSuchElementException {@inheritDoc} */ 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; }

比较简单，就是让原head置为null，让head指向下一个位置，下一个位置为

(h + 1) & (elements.length – 1);

就是让head顺时针旋转，为了怕读者混淆，特地贴出此图

5.7查看长度

/ * Returns the number of elements in this deque. * * @return the number of elements in this deque */ public int size() { return (tail - head) & (elements.length - 1); }

经过前面的分析，这个是显然的

5.8检查给定元素是否存在

/ * Returns {@code true} if this deque contains the specified element. * More formally, returns {@code true} if and only if this deque contains * at least one element {@code e} such that {@code o.equals(e)}. * * @param o object to be checked for containment in this deque * @return {@code true} if this deque contains the specified element */ 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; }

 int mask = elements.length - 1; int i = head; i = (i + 1) & mask;

上面这3行代码就是从对头开始想后遍历并进行对比，当遇到元素为null则遍历结束，因为在ArrayDeque中元素不可以为null。i = (i + 1) & mask;就是让i指向下一个位置。