大家好,又见面了,我是你们的朋友全栈君。
ArrayDeque是一个实现了Deque接口,并且可调整大小的一个双向队列。ArrayDeque队列没有容量限制,它可以根据需要扩容。
ArrayDeque底层采用数组实现的。
我们在分析AsyncTask时,它的内部实现就用到了ArrayDeque作为一个先进先出的队列。
private static class SerialExecutor implements Executor {
final ArrayDeque<Runnable> mTasks = new ArrayDeque<Runnable>();
Runnable mActive;
public synchronized void execute(final Runnable r) {
mTasks.offer(new Runnable() {
……
});
……
}
protected synchronized void scheduleNext() {
if ((mActive = mTasks.poll()) != null) {
THREAD_POOL_EXECUTOR.execute(mActive);
}
}
}
这里使用了offer方法添加元素,使用poll方法获取元素。我们知道LinkedList也可以实现队列操作,那么为什么会使用ArrayDeque呢?它有哪些优势呢?
我们接下来分析它的实现原理。
首先我们来看ArrayDeque的构建。
ArrayDeque队列的容量必须满足2的n次幂,它是如何保证的呢?如果我们给它的构造函数传递一个非2次幂的值,它又是如何来调整大小的呢?
public ArrayDeque() {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
那么我们就来分析allocateElements的实现吧。
ArrayDeque的构造函数中会调用allocateElements方法,来实现队列的初始化。
allocateElements的源码:
private static final int MIN_INITIAL_CAPACITY = 8;
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// 如果队列容量size的大小,大于最小值时,需要通过位运算来设置成一个符合2的n次幂的值。例如,如果参数值是9~15之间的任意值,size(initialCapacity变量的值)的最终大小就是16,如果参数值是17~31之间的任意值,则size的最终大小是32。
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // 如果值太大溢出(即小于0),需要缩小2倍
initialCapacity >>>= 1; // 最大运行值是 2^30
}
elements = new Object[initialCapacity];
}
当两个双端指针相遇时,也就是head等于tail时,则表示数组需要扩容了。扩容是通过方法doubleCapacity来实现的。
private void doubleCapacity() {
assert head == tail; //断言
int p = head; //临时变量p,等于head
int n = elements.length;//扩容前的size
int r = n - p; // head右侧元素个数
int newCapacity = n << 1;//size扩大1倍
if (newCapacity < 0)//溢出了,抛出错误
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];//创建新的数组,容量为原来的2倍
System.arraycopy(elements, p, a, 0, r);//将head右侧数据从原来数组copy到新数组
System.arraycopy(elements, 0, a, r, p);//将head左侧的数据从原数组copy到新数组
// Android-added: Clear old array instance that's about to become eligible for GC.
// This ensures that array elements can be eligible for garbage collection even
// before the array itself is recognized as being eligible; the latter might
// take a while in some GC implementations, if the array instance is longer lived
// (its liveness rarely checked) than some of its contents.
Arrays.fill(elements, null);//将原数组清空
elements = a;//将扩容后的数组赋给elements
head = 0;//设置head为0
tail = n;//设置tail为扩容前的数组大小,作为指针起点
}
下面我们再来分析ArrayDeque的几个关键方法。
head代表了队列头当前插入点的指针,它的初始值是0。
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 的使head得指针向左移动一位。例如,当head初始值为0时,队列容量是8时,head – 1的值就是-1,用二进制表示是1111,(elements.length – 1)的二进制表示是0111,两者按位&操作,结果就是7。这种操作结果类似于取余操作,但使用起来非常方便。
也就是说addFirst的第一个元素,在数组中的位置是elements[elements.length – 1],之后每次插入操作,head指针都会向左移动。
当head指针和tail指针相等时,表示数组容器已经满了,需要进一步扩容了,扩容调用doubleCapacity方法即可。
head代表了队列尾当前插入点的指针,它的初始值是0。
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
public E pollFirst() {
final Object[] elements = this.elements;
final int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result != null) {
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
}
return result;
}
public E pollLast() {
final Object[] elements = this.elements;
final int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result != null) {
elements[t] = null;
tail = t;
}
return result;
}
前文原理解析中,介绍了ArrayDeque的主要方法,但并没有AsyncTask中使用的offer方法和poll方法。其实这两个方法都是基于之前方法实现的封装接口,我们来看。
public boolean offer(E e) {
return offerLast(e);
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
offer方法调用了offerLast方法,offerLast方法最终调用的是offerLast方法,offerLast方法之前已经做过分析了,它实现了在队尾添加元素。
public E poll() {
return pollFirst();
}
poll方法直接return了pollFirst方法,pollFirst方法实现了队列头部弹出。
我们在本文中分析了ArrayDeque的实现、使用、及原理,下面来简单总结一下:
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/191250.html原文链接:https://javaforall.cn