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

49次阅读

共计 3821 个字符,预计需要花费 10 分钟才能阅读完成。

最近盯上了 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,’ 或 ’ 操作后 11000
2.initialCapacity |= (initialCapacity >>> 2) 接上一步,右移 2 位作 | 操作,11000->00110,’ 或 ’ 操作后 11110
3.initialCapacity |= (initialCapacity >>> 4) 接上一步,右移 4 位作 | 操作,11110->00001,’ 或 ’ 操作后 11111
……
后面就两步都是 11111 | 00000,结果就是 11111
4.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 方法入手。
插入
addFirst
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 – 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 指针从后向前移动。
addLast
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 指针,从前向后移动!
上图中再做一次 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

正文完
 0