[学習ノート-Java集合-1]List-ArayListソースコード分析
概要
ArayListは配列で実現されるListであり、配列と比較して動的に拡張された能力を有しており、したがって動的配列とも呼ばれる。
継承システム ArayListはList、RandomAccess、Cloeable、java.io.Serialzableなどのインターフェースを実現しました。 ArayListはListを実現し、ベースの追加、削除、エルゴードなどの動作を提供している。 ArayListはRandomAccessを実現し、ランダムアクセスの能力を提供する。 ArayListはCloneeableを実現し、クローン化できる。 ArayListはSerializableを実現し、順序付けされてもよい。 ソース分析
元素を末尾に追加します。平均時間の複雑度はO（1）です。拡張が必要かどうかを検査する。 もしelement DataがDEFAULTCCAPACITY_EMPTY_ELEEMENTDATAは初期化容量がDEFAULT_である。CAPACITY; 新容量は古い容量の1.5倍（oldCapacity+（oldCapacity>>1）であり、これだけ多くの容量を加えると、必要な容量よりも小さいことが分かります。 は、新しい容量の配列を作成し、古い配列を新しい配列にコピーする。 add(int index，E element)方法
元素を指定の位置に追加します。平均時間の複雑度はO（n）です。インデックスが境界を越えるかどうかをチェックする。 拡張が必要かどうかを検査する。 インデックス位置に挿入された要素を一つ後ろに移動します。 インデックスを挿入する位置に挿入された要素を配置する。 サイズに1を追加します。 addAll方法
二つの集合の集合を求める。
インデックスの位置を指定する要素を取得します。時間の複雑さはO（1）です。インデックスが境界を越えているかどうかをチェックします。ここでは上位の境界を越えてIndexOutOfBounds Exceptionを投げた場合、下位の境界を越えて投げ出されたのはArayIndexOutOnds Exception異常です。 はインデックス位置の要素を返します。 remove(int index)方法
インデックス位置を指定する要素を削除します。時間の複雑さはO（n）です。インデックスが境界を越えるかどうかをチェックする。 は、インデックス位置を指定する要素を取得する。 削除が最後のビットではない場合、他の要素は前のビットに移動します。 は最後の位置をnullとし、GCの回収に便利です。 は、削除された要素を返す。 ArayListが元素を削除した時は縮みませんでした。
remove(Object o)メソッド
指定した要素の値を削除します。時間の複雑さはO（n）です。は、最初の要素の値を指定することに等しい要素を見つける。 急速に削除されます。 fastRemove(int index)はremove(int index)に対してインデックスの境界をチェックする動作が少なくなりました。jdkは性能を極限まで最適化することが分かります。
retainAllメソッド
二つの集合の交差点を求めます。エルゴートData配列を巡回します。 要素がcにある場合、この要素をelementa配列のw位置に追加し、w位置を1つ後ろに移動する。 が遍歴した後、w以前の元素は両方共有されています。w以降の要素は両方共有されていません。 はwの後（含む）の元素をnullに置いて、GCの回収に便利です。 removeAll
二つのセットの単一方向の差セットを求めて、現在のセットの中でcにない要素だけを保留して、cの中で現在のグループの中の要素を保留しません。 ArayList内部は配列記憶要素を使用し、配列長が足りない場合は拡大容量を行い、毎回半分の空間を追加すると、ArayListは縮小されない。 ArayListはランダムアクセスをサポートしています。インデックスを介して要素にアクセスするのは極めて速く、時間の複雑さはO（1）です。 ArayList添加元素は、末尾まで非常に速く、平均時間の複雑さはO（1）である。 ArayList添加元素は、中央に移動するのが遅いため、平均時間の複雑度はO（n）である。 ArayListは、尻尾から要素を削除するのがとても速い。時間の複雑さはO（1）である。 ArayListは、中央から要素を削除するのが遅いので、平均時間の複雑度はO（n）である。 ArayListは合計をサポートし、addAll（Collection extends E）方法を起動すれば良い。 ArayListは、クロスを求めることをサポートし、retainAll(Collection extends E>cを呼び出すことができます。 ArayListは、一方向差セットを求めることをサポートし、removeAll(Collection extends E>cを呼び出すことができます。
ArayListは配列で実現されるListであり、配列と比較して動的に拡張された能力を有しており、したがって動的配列とも呼ばれる。
継承システム
/**
* , 10， new ArrayList() 。
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* ， 0 , new ArrayList(0) 。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* ， ，
* new ArrayList() ，
* EMPTY_ELEMENTDATA DEFAULT_CAPACITY（10） 。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
*
* ， transient 。
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
*
* ， elementData 。
*/
private int size;
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 0，
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 0， EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 0，
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
public ArrayList() {
// ， DEFAULTCAPACITY_EMPTY_ELEMENTDATA
// 10
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* ArrayList
*/
public ArrayList(Collection extends E> c) {
//
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray() Object[] ， ， Object[].class
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// c ， EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
}
}class MyList extends ArrayList {
/**
* ，
* ， Object
* java bug
*/
@Override
public String[] toArray() {
//
return new String[]{"1", "2", "3"};
}
}
元素を末尾に追加します。平均時間の複雑度はO（1）です。
public boolean add(E e) {
//
ensureCapacityInternal(size + 1);
//
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// DEFAULTCAPACITY_EMPTY_ELEMENTDATA， 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
//
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 1.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
// ，
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// ，
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//
elementData = Arrays.copyOf(elementData, newCapacity);
}
元素を指定の位置に追加します。平均時間の複雑度はO（n）です。
public void add(int index, E element) {
//
rangeCheckForAdd(index);
//
ensureCapacityInternal(size + 1);
// inex ， index
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// index
elementData[index] = element;
// 1
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}二つの集合の集合を求める。
/**
* c ArrayList
*/
public boolean addAll(Collection extends E> c) {
// c
Object[] a = c.toArray();
int numNew = a.length;
//
ensureCapacityInternal(size + numNew);
// c
System.arraycopy(a, 0, elementData, size, numNew);
// c
size += numNew;
// c true， false
return numNew != 0;
}インデックスの位置を指定する要素を取得します。時間の複雑さはO（1）です。
public E get(int index) {
//
rangeCheck(index);
// index
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
インデックス位置を指定する要素を削除します。時間の複雑さはO（n）です。
public E remove(int index) {
//
rangeCheck(index);
modCount++;
// index
E oldValue = elementData(index);
// index ， index
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// ， GC
elementData[--size] = null; // clear to let GC do its work
//
return oldValue;
}
remove(Object o)メソッド
指定した要素の値を削除します。時間の複雑さはO（n）です。
public boolean remove(Object o) {
if (o == null) {
// ， ，
for (int index = 0; index < size; index++)
// null， null ， ==
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// ， ，
for (int index = 0; index < size; index++)
// null， ， equals()
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
//
modCount++;
// index ， index
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// ， GC
elementData[--size] = null; // clear to let GC do its work
}
retainAllメソッド
二つの集合の交差点を求めます。
public boolean retainAll(Collection> c) {
// c null
Objects.requireNonNull(c);
// ， complement true， c
return batchRemove(c, true);
}
/**
*
* complement true c
* complement false c
*/
private boolean batchRemove(Collection> c, boolean complement) {
final Object[] elementData = this.elementData;
//
// 1， 1
// ，
int r = 0, w = 0;
boolean modified = false;
try {
// ， c ， （ complement ）
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// r size ， c.contains()
if (r != size) {
// c.contains() ，
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// ， GC
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
// （ 1， ）
size = w;
modified = true;
}
}
// true
return modified;
}
二つのセットの単一方向の差セットを求めて、現在のセットの中でcにない要素だけを保留して、cの中で現在のグループの中の要素を保留しません。
public boolean removeAll(Collection> c) {
// c
Objects.requireNonNull(c);
// ， complement false， c
return batchRemove(c, false);
}