ArrayDeque 的工作原理(Android 7.1源码)
简介
ArrayDeque 是以循环数组形式实现的双向队列
运行原理
- ArrayDeque内部是使用的数组实现,并通过head以及tail两个索引来进行操作。
...
transient Object[] elements;
// non-private to simplify nested class access
...
transient int head;
...
transient int tail;
...
public ArrayDeque() {
//默认2的倍数
elements = new Object[16];
}
//另一个指定大小的构造函数也是将elements的大小设置成2的倍数
//由于函数太长就不再解释.
- offer函数的分析
...
public boolean offer(E e) {
return offerLast(e);
}
...
public boolean offerLast(E e) {
addLast(e);
return true
}
...
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
在tail位置插入数据
(tail + 1) 与 (elements.length - 1)相与,这一步是整个ArrayDeque设计本人认为最巧妙之处,大家可以借鉴到自己的项目中. (tail + 1) & (length - 1) 的作用就是获得tail的索引值,这一步就省去了判断是否索引越界的问题,首先ArrayDeque的大小是2的倍数,一般的Java数据结构都是这样设计的,方便计算与扩展。
-
如何当前是数组的大小16,那么最大的索引值就是(length - 1)就是15, 如果此时(tail + 1) 正好超出索引值也就是最后位置增1 = 16,正常的结果应该是在数组的顶部也就是为0。
tail = (1000 & 0111)
-
如果tail值与head相等则翻倍扩展, 此处的位操作可以收入自己的项目中,n << 1 其实就是 n * 2。
private void doubleCapacity() { assert head == tail; int p = head; int n = elements.length; // number of elements to the right of p int r = n - 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; }
- addFirst函数分析
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
与上面的addLast的同理,只不过head是减1,tail是加1。
- pollFirst与pollLast函数分析
//从队列的顶部获取数据
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;
}
其实原理依旧和offer相似只是获取数据而已,pollFirst直接把head的数据返回并置为空(GC可以清理),然后将head下移。pollLast由于当前的tail是指向的尾部的下一位,所以尾部的数据是tail的上一位,返回上一位数据并置空,然后将tail上移。