役員：あなたはソースコードに精通していると言ったが、ArrayListのソースコードの設計思想を知っている？

Arraylistソースコード解析

I：全体的なアーキテクチャ

ArrayListの構造

ArrayList全体的なアーキテクチャは、比較的単純な配列構造であり、比較的単純な、次の図：

図は長さnの配列で、indexは0から数えて配列の添え字を表し、elementDataは配列そのものを表します。ソースコードにはこの2つの概念に加えて、以下の3つの基本概念があります：

1. DEFAULT_CAPACITY ： 配列の初期サイズ；
2. volatileによって変更されない、スレッドセーフでない、現在の配列のサイズ ；
3. modCount, 現在の配列が変更された回数を数えます；

ArrayListクラスのノート

クラスの注釈では、主に以下の4点について話しています。

1. null 値を指定すると、自動的に展開さ れます；
2. size、isEmpty、get、set、add の各メソッドは、いずれも計算量が O です；
3. はスレッドセーフではないので、マルチスレッド環境では、スレッドセーフなクラスである Collections#synchronizedList を使うことをお勧めします；
4. forループを強化するか、高速に失敗し、反復中に配列サイズが変更された場合に例外をスローするイテレータを使用します。

第二：ソースコード解析

初期化

ArrayListには3つの初期化メソッドがあります。パラメータなしの直接初期化、サイズを指定した初期化、初期データを指定した初期化です：

// パラメータなしで直接初期化すると、配列のサイズが空になる。
public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 初期化のサイズを指定する
public ArrayList(int initialCapacity) {
 if (initialCapacity > 0) {
 this.elementData = new Object[initialCapacity];
 } else if (initialCapacity == 0) {
 this.elementData = EMPTY_ELEMENTDATA;
 } else {
 throw new IllegalArgumentException("Illegal Capacity: "+
 initialCapacity);
 }
}
// 初期データの初期化を指定する
public ArrayList(Collection<? extends E> c) {
	elementData = c.toArray();
 if ((size = elementData.length) != 0) {
 	// c.toArray might (incorrectly) not return Object[] (see )
 if (elementData.getClass() != Object[].class) {
 elementData = Arrays.copyOf(elementData, size, Object[].class);
 } else {
 // replace with empty array.
 this.elementData = EMPTY_ELEMENTDATA;
 }
}

注意: ArrayList のデフォルトのサイズは、パラメータなしのコンストラクタで初期化されたときの空の配列です。

新規および拡張キャパシティの実現

新しいメソッドは、主に2つのステップに分かれています：最初に配列を拡張する必要があるかどうかを判断し、必要な場合は、操作を展開し、そうでない場合は、直接割り当て。新しいメソッドのソースコードは次のとおりです、その中でsecureCapacityInternal（）メソッドは、拡張操作です。

public boolean add(E e) {
 //配列のサイズが十分であることを確認し、拡張を実行するのに十分ではない、サイズは配列の現在のサイズである。
 ensureCapacityInternal(size + 1); // Increments modCount!!
 //直接代入、スレッドアンセーフ
 elementData[size++] = e;
 return true;
}

拡張のソースコード：

private void ensureCapacityInternal(int minCapacity) {
 // 配列のサイズの初期化は、指定された初期値がある場合は、指定されたサイズが優先するものとし、ロジックの場合は行かない。
 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 }
 // ボリュームが十分であることを確認する
 ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
 // レコード配列が変更される
 modCount++;
 // 希望する最小容量が配列の現在の長さよりも大きい場合は、容量を拡張する。
 if (minCapacity - elementData.length > 0)
 grow(minCapacity);
}
// 展開し、既存のデータを新しい配列にコピーする
private void grow(int minCapacity) {
 int oldCapacity = elementData.length;
 // oldCapacity >> 1 はoldCapacityを2で割った意味である。
 int newCapacity = oldCapacity + (oldCapacity >> 1);
 // もし展開された値< 期待値、展開された値は期待値と等しくなる
 if (newCapacity - minCapacity < 0)
 newCapacity = minCapacity;
 // もし展開された値> jvm 割り当てることができる配列の最大値は、整数の最大値を使用する
 if (newCapacity - MAX_ARRAY_SIZE > 0)
 newCapacity = hugeCapacity(minCapacity);
 // 複製による拡張
 elementData = Arrays.copyOf(elementData, newCapacity);
}

エクスパンションのソースコードからわかるように：

1. 倍ではなく、1．
2. ArrayListの配列容量の最大値はInteger.MAX_VALUEで、これを超えるとJVMは配列にメモリ領域を割り当てません；

削除

ArrayListは、さまざまな方法で要素を削除するなど、配列のインデックス削除に応じて、削除またはバッチ削除の値に応じてなど、原理とアイデアが似ている、ソースコードを説明する方法の削除の値に応じて選択します：

public boolean remove(Object o) {
 // 削除する値がnullの場合、nullの最初の値を探して削除する。
 if (o == null) {
 for (int index = 0; index < size; index++)
 if (elementData[index] == null) {
 fastRemove(index);
 return true;
 }
 } else {
 // 削除する値がNULLでなければ、削除する値と等しい最初の値を探して削除する。
 for (int index = 0; index < size; index++)
 // ここでは、値が等しい、等しいし、削除のインデックスの位置に応じて決定するために等しいに基づいている。
 if (o.equals(elementData[index])) {
 fastRemove(index);
 return true;
 }
 }
 return false;
}

上のソースコードからわかるように：

1. ヌル値が追加された時点ではヌル値の判定は行われていないので、ヌル値を削除することは可能です ;)
2. 配列内の値のインデックス位置の検索はequalsによって決定されますが、配列要素が基本型でない場合は、equalsの特定の実装に注目する必要があります；

具体的な削除ロジックはfastRemove()に実装されており、そのソースコードを以下に示します。

private void fastRemove(int index) {
 // レコード配列の構造が変更される
 modCount++;
 // numMoved インデックス位置の要素を削除した後、インデックスから前面に移動する必要がある要素の数は？
 // マイナス1の理由は、サイズが1からカウントされ、インデックスが0からカウントされるからである。
 int numMoved = size - index - 1;
 if (numMoved > 0)
 // インデックスから+1 コピーの開始位置はindexで、長さはnumMovedである。
 System.arraycopy(elementData, index+1, elementData, index, numMoved);
 //GCを助けるために配列の最後の位置にnullを代入する。
 elementData[--size] = null;
}

複雑さの分析

スレッドセーフ

ArrayListがメソッド内のローカル変数である場合、スレッドセーフの問題はありません。

ArrayListのスレッドセーフの問題の本質は、ArrayList自身のelementData、size、modConutがさまざまな操作のためにロック解除され、これらの変数の型が見えないため、複数のスレッドがこれらの変数に対して操作を行うと、値が上書きされる可能性があることです。

第三：まとめ

上記のArrayListの部分のソースコードの分析から、あなたはArrayListの底部は、実際には配列構造の周りにあることがわかります、各APIは、配列の操作にカプセル化されているので、ユーザーは、基本的な実装を知覚する必要はありません、唯一の使用方法に焦点を当てる必要があることができます。