【源】ArrayDeque，Collection框架中不起眼的一个类

最近盯上了java collection框架中一个类——ArrayDeque。很多人可能没用过甚至没听说过这个类（i’m sorry,what’s fu*k this?），毕竟你坐在面试官面前的时候，关于数组链表的掌握情况，99%的可能性听到问题会是：说说ArrayList和LinkedList的区别？今天从ArrayDeque入手，换一个角度来检验下我们是否真正掌握了数组、链表。父类和接口不着急分析这个类的核心方法，先看下它的父类和接口，以便在Java Collection宇宙中找准它的定位，顺带从宏观角度窥探下Java Collection框架设计。父类父类是AbstractCollection，看下它的方法add、addAll、remove、clear、iterator、size……是不是都很常见？在你常用的xxList中经常会使用这些方法吧？可以说，AbstractCollection这个抽象类，是这种结构（数组、链表等等）的骨架！接口首先是Queue接口，定义出了最基本的队列功能：那么Deque接口呢？入眼各种xxFirst、xxLast，这种定义决定了它是双端队列的代表！框架设计相继看了接口和父类，楼主你到底想表达啥？嘿嘿，别急，我再反问一个经典问题——抽象类和接口有什么区别？你可能会有各种回答，比如抽象类能自己有自己的实现之类的。不能说不对，但这种答案相当于迷惑于奇技淫巧当中，未得正统。以设计角度来看，其实是is-a（抽象类）和has-a（接口）的区别！抽象类相当于某一个种族的基石比如定义汽车AbstractCar，会规定有轮子有发动机能跑的就是汽车；各家厂商生产的汽车都逃不出这个范畴，甭管你是大众宝马玛莎拉蒂。接口则关注各种功能有些汽车多了座椅加热；有些增设了天窗打开功能。但这些功能都是增强型的，并不是每种汽车都会有！抽象类和接口合理的组合，就产生了奇妙的效果：技能保证种族（类）的结构，又能对其进行扩展（接口）。给出大家熟悉的ArrayList和LinkedList，仔细感受下：这种设计不仅仅限于Java Collection，开源框架中也是如此，比如Spring IOC中的Context、Factory那部分……分析回归到本文的主角 ArrayDeque，既然它实现了Deque，自然具备双端队列的特性。类名中的 Array姓氏，无时无刻不在提醒我们，它是基于数组实现的。类注释中，有句话引起了我的注意：/** * This class is likely to be faster than * {@link Stack} when used as a stack, and faster than {@link LinkedList} * when used as a queue. */（Stack先不管）后半句说，ArrayDeque作为队列时比LinkedList快，看看它是怎么办到的！三大属性：transient Object[] elements; //基于数组实现transient int head; //头指针transient int tail; //尾巴指针技术敏感的同学已经能猜到它是怎么实现的了:数组作为基底，两个指分指头尾，插入删除操作时移动指针；如果头尾指针重合，则需要扩容……下面看看源码实现，是否和我们猜测的一致。构造器private static final int MIN_INITIAL_CAPACITY = 8;// ****** Array allocation and resizing utilities ******private static int calculateSize(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 } return initialCapacity;}规定最小值MIN_INITIAL_CAPACITY = 8，如果入参小于8，数组大小就定义成8；如果大于等于8，这一通右移是啥操作？假如我们传入了16，二进制10000，逐步分析下：1.initialCapacity |= (initialCapacity >>> 1)右移1位作|操作，10000->01000，‘或’ 操作后110002.initialCapacity |= (initialCapacity >>> 2)接上一步，右移2位作|操作，11000->00110，‘或’ 操作后111103.initialCapacity |= (initialCapacity >>> 4)接上一步，右移4位作|操作，11110->00001，‘或’ 操作后 11111……后面就两步都是11111 | 00000，结果就是 111114.initialCapacity++二进制数11111，+1之后100000，转换成十进制32最终的负值判断（用于处理超int正向范围情况），先不考虑。结论：这些’或’ 操作，最终得到了大于入参的2的次幂中最小的一个。底层数组始终是2的次幂，为什么如此？带着这个问题继续往下分析// The main insertion and extraction methods are addFirst,// addLast, pollFirst, pollLast. The other methods are defined in// terms of these.以上注释有云，核心方法就4个，我们从add方法入手。插入addFirstpublic void addFirst(E e) { if (e == null) throw new NullPointerException(); elements[head = (head - 1) & (elements.length - 1)] = e; //关键 if (head == tail) doubleCapacity();}head = (head - 1) & (elements.length - 1)，玄机就在这里。如果你对1.8的HashMap足够了解，就会知道hashmap的数组大小同样始终是2的次幂。其中很重要的一个原因就是：当lengh是2的次幂的时候，某数字 x 的操作 x & (length - 1) 等价于 x % length，而对二进制的计算机来说 & 操作要比 % 操作效率更好！而且head = (head - 1) & (elements.length - 1)，（head初始值0）第一次就将head指针定位到数组末尾了。画图分析下：可见，head指针从后向前移动。addLastpublic 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指针，从前向后移动！上图中再做一次add操作，指针将会重合。比如，再一次addFirst之后：if (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;}通过数组拷贝和重新调整指针，完成了扩容。至于pollFirst、pollLast是addFirst、addLast的相反操作，原理相似，不多做分析……参考这次，彻底弄懂接口及抽象类Jdk1.6 Collections Framework源码解析(3)-ArrayDeque