ソースの魅力-ArrayDequeの仕組み
3206 ワード
ArrayDequeの動作原理(Android 7.1ソースコード)
概要
ArrayDequeは循環配列で実現される双方向キューである
運転原理 ArrayDeque内部は使用する配列実装であり、headとtailの2つのインデックスによって動作する. offer関数の解析 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値がheadと等しい場合、2倍に拡張され、ここでのビット操作は自分のプロジェクトに格納され、n<<1は実際にはn*2である. addFirst関数解析
上のaddLastと同じ理屈ですが、headはマイナス1、tailはプラス1です. pollFirstとpollLast関数解析
実はofferと似ているのはデータを取得するだけで、pollFirstは直接headのデータを返して空にし(GCはクリーンアップ可能)、それからheadを下に移動します.pollLastは現在のtailが指している末尾の次のビットなので、末尾のデータはtailの前のビットで、前のデータを返して空にして、それからtailを上に移動します.
概要
ArrayDequeは循環配列で実現される双方向キューである
運転原理
...
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
// .
...
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 = (1000 & 0111)
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;
}
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です.
//
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を上に移動します.