详解九章算法的作者是谁_arrayset
大家好，又见面了，我是你们的朋友全栈君。
ArrayDeque方法很多，而他们按过程划分分为三种，初始化，扩容，CRUD操作。
下面依次来说
初始化过程中依赖一个核心的函数calculateSize，
它的源码如下
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;
}首先它的作用是处理输入的容量，使之为2的倍数，如果处理后发生溢出，则向右算术右移一位。
具体实现过程是在if代码块中，整体的目标是使得输入数字的二进制最高位及以后全为一，之后加1。结果必然只有最高位为1，其余全为0.
那么为什么恰好5次移位即可完成的，我用递归来辅助大家理解。
public static int get(int n) {
if(n == 0) {
return 1;
}
return 2 * get(n - 1);
}首先，每次移位之后，新生成的1和之前所有的1必然不碰撞，即他们之间相互独立。因此，可以用递归来表达整个的移位过程，默认不考虑0，输入n为移动次数，结果是不考虑位宽限制下的最高位移动n次后的1的总数量。
当输入n为0时，不移动，最高位1不动，总共1个1。
当输入n大于1时，最高位移动移位，生成的1和本身的1开始新的移动过程即get(n – 1) + get(n – 1) = 2 * get(n- 1)。通过式子可以发现，当n = 5时，可以使得从最高位1开始的32位全为1.而int只有32位，也就是说可以使得从最高位开始所有的位都为1.
最后做一个边界情况的处理,如果进来的数字小于MIN_INITIAL_CAPACITY（8），直接返回
initialCapacity。下面开始讲CRUD。
这里面有许多方法，他们底层调用了四个方法addFirst，addLast，pollFirst，pollLast。
一个个来说
addFirstpublic void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}它的主体逻辑是，取模获取index，之后赋值。而取模的过程它利用数组的长度是2的倍数这一特性用位运算取代了模运算，提高了效率。这同样也意味着，扩容之后长度也必须是2的倍数，这决定了长度最大为2^30。
另外的点是为什么使用head，而不是tail，用head-1这个操作。
这需要讲到ArrayDeque的架构。它有两个描述数组的变量，head和tail。head表示队列的头，tail表示尾可插入的位置，一个elements描述存储变量的数组结构。均不可序列化。
插入遵循着一个约定，先插入，再处理扩容问题。
addLast
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}在index上是有区别的，head是先移位，再赋值（插入）。而tail是先赋值再移位。
当输入为null时都抛异常。
二者讲完要讲doubleCapacity这个重要的扩容函数了。
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];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}首先扩容，容量为原来的两倍，如果溢出，抛出异常（这是运行时异常）。之后，分两段复制，一段为[head, elements.length)，一段为[0, head)。之所以要这样复制，也是因为System.arraycopy的缘故。因为如果写
for (int i = 0; i < n; i++) {
a[i] = elements[head & (elements.length - 1)];
head = (head + 1) & elements.length;
}从实现上来讲是没有问题的，但是其没有调用系统提供的调用，从效率上来讲会差一点（经过试验，使用系统调用会是下面的实现性能的2倍)，而且不够优雅，扩展性不足。
下面开始讲
pollFirst
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;
}首先会用
@SuppressWarnings忽略unchecked警告。之后如果没有，返回null。否则将此位置设为null，并将head向前移动移位。设为null，这个操作是必须的，因为这表示数据被弹出。而ArrayDeque又不允许输入为null，这样数组内为null的槽为空槽，不为null的槽即为在使用的槽
pollLast
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}整体流程和pollFirst无区别，只是要注意tail – 1.为什么减一参照之前的说明。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/191637.html原文链接：https://javaforall.cn
腾讯云开发者
