深度剖析 ArrayDeque源码

ArrayDequeJDK双端队列源码深度剖析前言在本篇文章当中主要跟大家介绍JDK给我们提供的一种用数组实现的双端队列在之前的文章LinkedList源码剖析当中我们已经介绍了一种双端队列不过与ArrayDeque不同的是LinkedList的双端队列使用双向链表实现的。双端队列整体分析我们通常所谈论到的队列都是一端进一端出而双端队列的两端则都是可进可出。下面是双端队列的几个操作数据从双端队列左侧进入。数据从双端队列右侧进入。数据从双端队列左侧弹出。数据从双端队列右侧弹出。而在ArrayDeque当中也给我们提供了对应的方法去实现比如下面这个例子就是上图对应的代码操作public void test() { ArrayDequeInteger deque new ArrayDeque(); deque.addLast(100); System.out.println(deque); deque.addFirst(55); System.out.println(deque); deque.addLast(-55); System.out.println(deque); deque.removeFirst(); System.out.println(deque); deque.removeLast(); System.out.println(deque);}// 输出结果[100][55, 100][55, 100, -55][100, -55][100]数组实现ArrayDeque(双端队列)的原理ArrayDeque底层是使用数组实现的而且数组的长度必须是2的整数次幂这么操作的原因是为了后面位运算好操作。在ArrayDeque当中有两个整形变量head和tail分别指向右侧的第一个进入队列的数据和左侧第一个进行队列的数据整个内存布局如下图所示其中tail指的位置没有数据head指的位置存在数据。当我们需要从左往右增加数据时入队内存当中数据变化情况如下当我们需要从右往做左增加数据时入队内存当中数据变化情况如下当我们需要从右往左删除数据时出队内存当中数据变化情况如下当我们需要从左往右删除数据时出队内存当中数据变化情况如下底层数据遍历顺序和逻辑顺序上面主要谈论到的数组在内存当中的布局但是他是具体的物理存储数据的顺序这个顺序和我们的逻辑上的顺序是不一样的根据上面的插入顺序我们可以画出下面的图大家可以仔细分析一下这个图的顺序问题。上图当中队列左侧的如队顺序是0, 1, 2, 3右侧入队的顺序为15, 14, 13, 12, 11, 10, 9, 8因此在逻辑上我们的队列当中的数据布局如下图所示根据前面一小节谈到的输入在入队的时候数组当中数据的变化我们可以知道数据在数组当中的布局为ArrayDeque类关键字段分析// 底层用于存储具体数据的数组transient Object[] elements;// 这就是前面谈到的 headtransient int head;// 与上文谈到的 tail 含义一样transient int tail;// MIN_INITIAL_CAPACITY 表示数组 elements 的最短长度private static final int MIN_INITIAL_CAPACITY 8;以上就是ArrayDeque当中的最主要的字段其含义还是比较容易理解的ArrayDeque构造函数分析默认构造函数数组默认申请的长度为16。public ArrayDeque() { elements new Object[16];}指定数组长度的初始化长度下面列出了改构造函数涉及的所有函数。public ArrayDeque(int numElements) { allocateElements(numElements);} private void allocateElements(int numElements) { elements new Object[calculateSize(numElements)];}private static int calculateSize(int numElements) { int initialCapacity MIN_INITIAL_CAPACITY; // Find the best power of two to hold elements. // Tests because arrays arent 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;}上面的最难理解的就是函数calculateSize了他的主要作用是如果用户输入的长度小于MIN_INITIAL_CAPACITY时返回MIN_INITIAL_CAPACITY。否则返回比initialCapacity大的第一个是2的整数幂的整数比如说如果输入的是9返回的16输入4返回8。calculateSize的代码还是很难理解的让我们一点一点的来分析。首先我们使用一个2的整数次幂的数进行上面移位操作的操作从上图当中我们会发现我们在一个数的二进制数的32位放一个1经过移位之后最终32位的比特数字全部变成了1。根据上面数字变化的规律我们可以发现任何一个比特经过上面移位的变化这个比特后面的31个比特位都会变成1像下图那样因此上述的移位操作的结果只取决于最高一位的比特值为1移位操作后它后面的所有比特位的值全为1而在上面函数的最后我们返回的结果就是上面移位之后的结果 1。又因为移位之后最高位的1到最低位的1之间的比特值全为1当我们1之后他会不断的进位最终只有一个比特位置是1因此它是2的整数倍。经过上述过程分析我们就可以立即函数calculateSize了。ArrayDeque关键函数分析addLast函数分析// tail 的初始值为 0 public void addLast(E e) { if (e null) throw new NullPointerException(); elements[tail] e; // 这里进行的 位运算 相当于取余数操作 // (tail 1) (elements.length - 1) (tail 1) % elements.length // 这个操作主要是用于判断数组是否满了如果满了则需要扩容 // 同时这个操作将 tail 1即 tail tail 1 if ( (tail (tail 1) (elements.length - 1)) head) doubleCapacity();}代码(tail 1) (elements.length - 1) (tail 1) % elements.length成立的原因是任意一个数a对2n进行取余数操作和a跟2n−1进行运算的结果相等即a%2na(2n−1)从上面的代码来看下标为tail的位置是没有数据的是一个空位置。addFirst函数分析// head 的初始值为 0 public void addFirst(E e) { if (e null) throw new NullPointerException(); // 若此时数组长度elements.length 16 // 那么下面代码执行过后 head 15 // 下面代码的操作结果和下面两行代码含义一致 // elements[(head - 1 elements.length) % elements.length] e // head (head - 1 elements.length) % elements.length elements[head (head - 1) (elements.length - 1)] e; if (head tail) doubleCapacity();}上面代码操作结果和上文当中我们提到的在队列当中从右向左加入数据一样。从上面的代码看我们可以发现下标为head的位置是存在数据的。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]; // arraycopy(Object src, int srcPos, Object dest, int destPos, int length) // 上面是函数 System.arraycopy 的函数参数列表 // 大家可以参考上面理解下面的拷贝代码 System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p); elements a; head 0; tail n;}上面的代码还是比较简单的这里给大家一个图示大家就更加容易理解了扩容之后将原来数组的数据拷贝到了新数组当中虽然数据在旧数组和新数组当中的顺序发生变化了但是他们的相对顺序却没有发生变化他们的逻辑顺序也是一样的这里的逻辑可能有点绕大家在这里可以好好思考一下。pollLast和pollFirst函数分析这两个函数的代码就比较简单了大家可以根据前文所谈到的内容和图示去理解下面的代码。public E pollLast() { // 计算出待删除的数据的下标 int t (tail - 1) (elements.length - 1); SuppressWarnings(unchecked) E result (E) elements[t]; if (result null) return null; // 将需要删除的数据的下标值设置为 null 这样这块内存就 // 可以被回收了 elements[t] null; tail t; return result;} 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;}总结在本篇文章当中主要跟大家分享了ArrayDeque的设计原理和他的底层实现过程。ArrayDeque底层数组当中的数据顺序和队列的逻辑顺序这部分可能比较抽象大家可以根据图示好好体会一下