共计 3495 个字符，预计需要花费 9 分钟才能阅读完成。
download：深刻 Go 底层原理，重写 Redis 中间件实战（残缺无密）
ArrayDeque 深度解析
概述
ArrayDeque 这个容器不晓得大家在平时的工作中使用的多吗？它是一个十分弱小的容器，既能够作为队列实现 FIFO 先进先出的功能，也具备栈的功能实现 FILO 先进后出的功能，那么它到底是怎么样的呢？性能又如何？
ArrayDeque 介绍
ArrayDeque 次要是基于数组实现的 Deque(Double Ended Queue) 双端队列，即双端队列，它既能够当作栈使用，也能够当作队列使用。
ArrayDeque 是一个没有容量限度的双端队列，底层是基于数组实现，会主动扩容。
ArrayDeque 不是线程平安的。
ArrayDeque 不能够存取 null 元素。
当作为栈使用时，性能比 Stack 好；当作为队列使用时，性能比 LinkedList 好。
实现了 Queue 接口，它实践上是一个单端队列，只能操作队列的一端。
实现了 Deque 接口，Deque 集成了 Queue 接口，有 api 能够同时操作队列的双端。
实现了 Cloneable 接口，阐明该队列反对 clone。
实现了 Serializable 接口，标记该接口反对序列化操作。
构造方法
办法阐明 ArrayDeque()结构一个初始容量为 16 的数组双端队列 ArrayDeque(int numElements)结构一个初始容量为 numElements 的数组双端队列 ArrayDeque(Collection<? extends E> c)结构一个初始内容未 c 的数组双端队列
要害办法
增加相干办法
等价办法阐明 add(e)addLast(e)向队列尾部增加元素 offer(e)offerLast(e)向队列尾部增加元素 addFirst(e)offerFirst(e)向队列头部增加元素
add 前缀的办法，假如超过容量限度，增加失败，会抛出运行时异样
offer 前缀的办法，比拟非凡，假如超过容量限度，会返回指定值 true false
队列获取元素相干办法
等价办法阐明 remove()removeFirst()获取并且删除队列头部元素 poll()pollFirst()获取并且删除队列头部元素 removeLast()pollLast()获取并且删除队列尾部
remove 前缀的办法，假如容量为空，会抛出运行时异样
offer 前缀的办法，假如容量为空，会返回指定值 null
办法等价办法阐明 element()getFirst()查看队列头部元素 peek()peekFirst()查看队列头部元素 getLast()peekLast()查看队列尾部元素
peek 前缀的办法，假如容量为空，会返回指定 true，false，其余办法失败会抛出异样。
栈相干办法等价办法阐明 push(e)addFirst(e)向栈中增加元素 pop()removeFirst()获取栈顶元素 peek()peekFirst()查看栈顶元素
其余办法
阐明 removeFirstOccurrence(Object o)删除队列中第一次相等的元素 removeLastOccurrence(Object o)删除队列中最初一个相等的元素
tips：粗疏操作是返回指定值还是抛出异样，倡议看源码的 javadoc，写的十分分明了。
使用案例
测试队列功能
@Test
public void test1() {Deque<String> deque = new ArrayDeque<>();
deque.add("1");
deque.offer("2");
deque.offerLast("3");
System.out.println(deque);
String poll = deque.poll();
System.out.println(poll);
System.out.println(deque);
}
测试栈的功能
@Test
public void test2() {Deque<String> deque = new ArrayDeque<>();
deque.push("1");
deque.push("2");
deque.push("3");
String pop = deque.pop();
System.out.println(pop);
}
测试存储 null 数据
@Test
public void test3() {Deque<String> deque = new ArrayDeque<>();
boolean offerResult = deque.offer(null);
System.out.println(offerResult);
System.out.println(deque);
}
测试 poll 和 remove 的区别
@Test
public void test4() {Deque<String> deque = new ArrayDeque<>();
String poll = deque.poll();
// 取出为 null
System.out.println(poll);
// 因为容量为空了，会抛出异样
String remove = deque.remove();
System.out.println(remove);
System.out.println(deque);
}核心机制
实现机制
从名字能够看出 ArrayDeque 底层通过数组实现，为了满足能够同时在数组两端插入或删除元素的需要，该数组还必须是循环的，即循环数组，也就是说数组的任何一点都可能被看作终点或者起点。
总的来说，ArrayDeque 外部它是一个动静扩大的循环数组，通过 head 和 tail 变量保护数组的开始和结尾，数组长度为 2 的幂次方，使用高效的位操作停止各种判断，以及对 head 和 tail 的保护。
源码解析
结构放办法 ArrayDeque(int numElements)
public ArrayDeque(int numElements) {
// 初始化数组
allocateElements(numElements);
}
private void allocateElements(int numElements) {
// 初始化数组，通过 calculateSize 办法计算数组长度
elements = new Object[calculateSize(numElements)];
}复制代码
private static int calculateSize(int numElements) {
// 设置初始容量等于 8
int initialCapacity = MIN_INITIAL_CAPACITY;
// 假如 numElement 大于等于初始容量
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;
}
程序运行到第五行时，numElements >= initialCapacity 成立，10>=8，则会进入到 if 语句外部。
程序运行到第六行时，initialCapacity = numElements，initialCapacity 设置为 10，10 的二进制示意形式是 1010。
程序运行到第七行时，initialCapacity 无符号向右挪动一位，1010 无符号向右挪动一位是 0101，1010|0101=1111，十进制示意形式是 15。
程序运行到第八行时，initialCapacity 无符号向右挪动 2 位，1111 无符号向右挪动一位是 0011，1111|0011=1111，十进制示意形式是 15，不断继续上来都是 15，当程序运行到第 12 行时，15 停止加 1 操作，则变成 16。这个时候 16 就是 2 的幂次方返回。
整体思路是每次挪动将位数最高的值变成 1，从而将二进制所有位数都变成 1，变成 1 之后失去的十进制加上 1 之后失去值就是 2 的幂次方的值。最终，数组长度永远都是是 2 的幂次方。
