ArrayList
ArrayListは、動的な配列は、実際には、要素の追加と削除の動的なメソッドを提供する配列の複雑なバージョンです。
ソースコードを分析すると、ArrayListには3つのコンストラクタ・メソッドがあることがわかります。
空のコンストラクタ
渡された値のサイズに基づいて、指定された長さの配列を作成します。
Collection要素のリストを渡して生成します。
// デフォルトの容量サイズ
private static final int DEFAULT_CAPACITY = 10;
// 空の配列が定義される
private static final Object[] EMPTY_ELEMENTDATA = {};
// 直列化できない配列は、要素が格納されるバッファと等価である。
transient Object[] elementData;
// リストの長さ
private int size;
/**
* 空のコンストラクタ
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* ユーザーから渡された容量に基づいてリストを構築する。長さは0以上でもいいが、負の場合は例外が投げられる。
*/
public ArrayList(int initialCapacity) {
// 初期容量が0より大きい場合
if (initialCapacity > 0) {
// initialCapacityサイズの配列を作成する。
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 空の配列を作成する
this.elementData = EMPTY_ELEMENTDATA;
} else {
// もし負の数であれば例外が投げられる
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 指定されたコレクションの要素を含むリストを構築し、コレクションのイテレータを使って順番に返す。
* 指定されたコレクションがNULLの場合、NullPointerExceptionをスローする。
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
ArrayList関連する問題
ArrayList
利点
ArrayListはランダムアクセスパターンである配列を一番下に実装しており、さらにRandomAccessインターフェイスを実装しているため、getメソッドの実行が非常に高速です。
ArrayListは非常にシーンで要素を追加するために、単に配列に要素を追加し、要素の添え字のトラバーサルによると、高効率。自動的に拡張することができ、デフォルトでは、各拡張のための元の容量の1.5倍です。
欠点
配列内の要素の挿入や削除は、移動する要素の数が多いため非効率的です。
ArrayListは、拡張容量未満の場合、実際には、増加操作の効率は非常に高く、拡張容量を含む場合には、追加操作の効率は本当に低く、削除操作は、コピーをシフトする必要があります。
同時に、ArrayListは、System.arrayCopy（）処理のこの非効率的なメソッドを呼び出すために要素を追加または削除するため、少し大きめのデータ量または操作の頻繁な挿入と削除の必要性に遭遇し、低の効率は、上記のシナリオに遭遇した場合は、その後、LinkedListの代わりに使用する必要があるためです。ArrayListの利点は、良い配列を構築した後、要素への頻繁なアクセスの効率は非常に高いです。
ArrayListベクターとの違い
まず、Listインターフェースには、ArrayList、Vector、LinkedListの3つの実装クラスがあります。
VectorとArrayListは、配列を介して実装され、違いは、Vectorは、スレッドの同期をサポートしていることです、つまり、特定の瞬間に、唯一のスレッドは、複数のスレッドが同時に書き込むことによって引き起こされる不整合を回避し、Vectorを書き込むことができますが、同期を達成するために非常に高い世代が必要です。はArrayListよりも遅い
同時に、VectorとArrayListの拡張メカニズムには違いがあり、Vectorは毎回配列の長さを2倍にしますが、ArrayListは元の配列の長さの1.5倍です。
拡張メカニズム
add
まず、ArrayListのaddメソッドがどのように要素を追加するのかを見てみましょう。
// 指定された要素をリストの最後に追加する。
public boolean add(E e) {
// 要素を追加するには、まずsecureCapacityInternalメソッドを呼び出す。
ensureCapacityInternal(size + 1); // Increments modCount!!
// このようにArrayListに要素を追加する本質は、配列に値を代入することと同じである。
elementData[size++] = e;
return true;
}
ensureCapacityInternal
要素に追加する場合、minCapacityが1であれば、2つの要素の最大値を取ります。
// 最小拡張容量を得る
private void ensureCapacityInternal(int minCapacity) {
// デフォルトでリストが空の場合
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 渡されたパラメータのデフォルト容量と最大値を取得する。
// DEFAULT_CAPACITY: 10 , minCapacity: 1
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
ensureExplicitCapacity
上記の操作は、実行後にsecureExplicitCapacityメソッドを呼び出します。
// 成長させる必要があるかどうかを判断する
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
// growメソッドを呼び出して展開する
grow(minCapacity);
}
grow
配列の現在の長さよりも大きな要素が追加されると、grow操作がトリガーされ、配列が拡張されます。
int newCapacity = oldCapacity + (oldCapacity >> 1)
コアコードは、上記の文は、元の配列の長さ、1.5倍に拡大し、コピーコマンドの実装では、古い配列の内容は、新しい配列にコピーし、操作の要素の拡張を実現するためです。
elementData = Arrays.copyOf(elementData, newCapacity);
完全なコードは以下の通りです
// 確保される配列のサイズ
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// セットの容量
int oldCapacity = elementData.length;
// 集合の新しい容量（ここでは、コンピュータで最も高速なビット演算を使用し、1ビットを右にシフトする ）.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 新しい容量が追加されたコレクションの容量より小さい場合、コレクションの容量で置き換える
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
/** 新しい容量がMAX_ARRAY_SIZE,入る`hugeCapacity()` とminCapacityを比較する* MAX_ARRAY_SIZE，もしminCapacityが最大容量より大きければ、新しい容量は次のようになる。`Integer.MAX_VALUE`， ， * 新しい容量サイズはMAXとなる_ARRAY_SIZE `Integer.MAX_VALUE - 8`。
*/
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 元の配列を新しい配列にコピーする。
elementData = Arrays.copyOf(elementData, newCapacity);
}
/** 新しい容量がMAX_ARRAY_SIZE,入る`hugeCapacity()` とminCapacityを比較する* MAX_ARRAY_SIZE，もしminCapacityが最大容量より大きければ、新しい容量は次のようになる。`Integer.MAX_VALUE`， ， * 新しい容量サイズはMAXとなる_ARRAY_SIZE `Integer.MAX_VALUE - 8`。
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
まとめ
以上の方法を組み合わせると、以下のようになります。
2つ目の要素を追加するとminCapacityが2になり、この時elementData.length()は1つ目の要素を追加した後、展開が10になり、この時minCapacity - elementData.length > 0が保持されないので、grow(minCapacity)メソッドに入りません。.
同時に、要素3,4.... 11番目の要素で、minCapacity(11)が10より大きい場合、growオペレーションがトリガされます。
