ソース分析(二)――ArrayList(JDK 1.6ベース)
15980 ワード
一、ArrayListの定義:
public class ArrayList
extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable
上記の定義から、
1.ArrayListはAbstractListから継承され、Listが実現されているため、関連する追加、削除、修正、遍歴などの機能をサポートするキューである.
2.ArrayListはRandomAccessインタフェースを実現し、ランダムアクセス機能を提供する.RandmoAccessはjavaでListによって実装され、Listに高速アクセス機能を提供するために使用される.
3.ArrayListはCloneableインタフェース、すなわちclone()関数を実現する.クローン化できます.
4.ArrayListはjavaを実現する.io.Serializableインタフェース、シーケンス化をサポートします.
5.ArrayListは汎用型をサポートしています.
二、ArrayListの基本属性:
ArrayListでは、要素を格納する配列と配列サイズの2つの基本プロパティのみが定義されています.
三、ArrayListの構造方法:
1.最初の構築方法(パラメータなし):
2.第2の構成方法(パラメータ付き:初期容量):
3.第3の構成方法(1つの集合に入力)
四、ArrayList追加要素方法:
1.add(E e):配列の末尾に要素を追加します.
ensureCapacity():
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
//minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
modCountを追加した後、minCapacity(すなわちsize+1)がoldCapacity(すなわちelementData.length)より大きいかどうかを判断し、それより大きい場合はmax((oldCapacity*3)/2+1、minCapacity)に調整し、elementData容量を新しい容量に調整し、コンテンツが元の配列要素であり、サイズが新しい容量の配列がelementDataに割り当てられる.そうでなければ操作しません.
したがって、次のことがわかります.
ArrayList容量の拡張は配列要素の複製をもたらし,多重拡張容量は配列内容全体の複製を複数回実行する.リストの長さを大まかに判断し、ensureCapacityを呼び出して容量を調整すれば、運転速度を効果的に向上させることができます.
また,ArrayListは容量拡張ごとに約1.5倍,2分の1増加した.
2.add(int index,E element):指定したインデックスに要素を追加します.
まず指定位置indexがelementDataの限界を超えるか否かを判断し、その後ensureCapacity調整容量(容量が十分であれば拡張しない)を呼び出し、Systemを呼び出す.arraycopyは、elementDataのindexから始まるsize-index個の要素をindex+1からsize+1までの位置(すなわち、indexから始まる要素はいずれも1つ後ろに移動)にコピーし、index位置の値をelementに向けます.
3.addAll(Collectionc):arrayListを別のarrayListに追加します.
まず集合cを配列に変換する、変換後の配列の程度とArrayListのsizeに応じて容量を広げてからSystemを呼び出す.arraycopyメソッドは要素をelementDataの末尾にコピーし、sizeを調整します.返されるコンテンツ解析によれば,集合cのサイズが空でない,すなわち変換後の配列長が0でない限りtrueが返される.
4.addAll(int index,Collectionc):1つのarrayListを別のarrayListの指定したインデックスに追加します.
まずindexが境界を越えているかどうかを判断します.その他のコンテンツはaddAll(Collectionc)とほぼ一致していますが、レプリケーション時にindexから始まる要素をX(cが配列に変わった後の長さ)個の位置(レプリケーションのプロセスでもあります)、その後、配列コンテンツをelementDataのindex位置からindex+Xにレプリケーションします.
五、ArrayListの要素削除方法:
1.remove(int index)メソッド:指定した位置の要素を除去します.
まず範囲をチェックし、modCountを修正し、除去する要素を保持し、除去位置の後の要素を前に移動し、list末尾要素を空にし、除去された要素を返します.
2.remove(Object o)メソッド:指定した要素の要素を除去します.
まず、コードから、削除に成功した後にtrueを返し、そうでなければfalseを返すことがわかります.remove(Object o)ではelementを巡回して受信オブジェクトが存在するかどうかを探し,見つかったらfastRemoveを呼び出してオブジェクトを除去する.なぜエレメントを見つけたらindexがわかり、remove(index)でエレメントを除去しないのですか?fastRemoveは境界を判断する処理をスキップしたため、要素を見つけることはindexが境界を超えないことを決定することに相当し、fastRemoveは除去された要素を返さない.次はfastRemoveのコードで、基本的にremove(index)と一致しています.
fastRemove():
3.removeRange(int fromIndex,int toIndex):指定した範囲の要素を除去します.
実行プロセスは、elementDataをtoIndex位置から始まる要素をfromIndexに移動し、toIndex位置以降の要素をすべて空にしてsizeを変更します.
4.clear():ArrayListメソッドをクリアします.
clearの場合、elementDataの長さは変更されていません(せっかく申請したり、広げたりしたのに、どうして解放したのか、残しておいても無駄です.リストの内容を変更しないと判断したらtrimToSizeを呼び出してスペースを解放したほうがいいです)、すべての要素をnull、sizeを0に設定します.つまりclearメソッドは配列内の要素をnullに、ArrayListのサイズを0に、メモリを解放しません.
六、ArrayListの要素修正方法:
1.set(int index,E element):指定したインデックス位置の要素の値を変更します.
まず範囲をチェックし、古い要素を新しい要素で置き換え、古い要素を返します.
七、ArrayListの要素取得方法:
1.get(int index):指定したインデックスの要素を取得します.
まずRangeCheckメソッドを呼び出してインデックスが境界を越えているかどうかを検出し,配列の下付きスケールに基づいて配列要素を直接取得することで,ArrayListは要素の挿入が遅いが,クエリが速い(配列のクエリ速度が速い)ことがわかる.
八、ArrayListのインデックス関連方法:
1.indexOf(Object):ArrayList内の要素のインデックスを取得します.
オブジェクトがlistにあるかどうかはelementData配列を巡回して判断し,存在する場合は要素のindex([0,size-1]),存在しない場合は−1を返す.
2.lastIndexOf():指定した要素の最後に表示されるインデックス値を取得します.
後ろから前へelement配列を巡回し,Objectに遭遇するとindex値を返し,遭遇しなければ−1を返す.
九、ArrayListの他の方法:
1.isEmpty():ArrayListが空かどうかを判断します.
public boolean isEmpty() {
return size == 0;
}
sizeが0に等しいかどうかを直接返します.
2.size():ArrayListのサイズを取得します.
public int size() {
return size;
}
3.contains(Object):要素がArrayListにあるかどうかを判断します.
4.toArray():ArrayListを配列に変換します.
Arraysを呼び出します.copyOfは、size個のelementDataの要素である配列を返します.すなわち、elementDataが0からsize-1の位置にある要素をコピーして新しい配列に返します.
以下は一般的な書き方です.
受信配列の長さがsizeより小さい場合、新しい配列が返されます.サイズはsizeで、タイプは受信配列と同じです.受信配列の長さがsizeと等しい場合、elementDataを受信配列にコピーし、受信配列を返します.受信配列の長さがsizeより大きい場合、elementDataのコピーに加えて、返される配列のsize番目の要素が空になります.
5.trimToSize():格納要素配列の空間サイズを圧縮します.
elementDataの長さが広がるため、sizeはその中に含まれる要素の数をマークします.だからsizeは小さいがelementDataが現れる.lengthが大きい場合、空間の浪費が発生します.trimToSizeはelementDataに新しい配列を返し、要素の内容は変わらず、lengthはsizeと同じで、スペースを節約します.
十、ArrayListとLinkListの比較:
1.実装方式:ArrayListは動的配列に基づくデータ構造を実現し、LinkedListはチェーンテーブルに基づくデータ構造を実現する.
2.ランダムアクセス速度:ArrayListの下位層は配列によって実現され、LinkedListは双方向チェーンテーブルであるため、ArrayListのランダムアクセス速度はLinkedListより速い.
3.挿入削除速度:ArrayList下位層は配列によって実現されるため、0番位置に挿入するとlistのすべての要素が移動し、最後に要素を挿入する際に移動する必要がない.LinkedListは双方向チェーンテーブルで、任意の場所に要素を挿入するのに要する時間は同じです.従ってLinkedList挿入削除速度はArrayListよりも速い.
以上のように、リストに多くの挿入と削除操作がある場合はLinkedListを使用して効率を上げ、インデックスクエリが多い場合はArrayListを使用する(拡張型のforループやIteratorを使用してLinkedListを巡る効率が大幅に向上する).
public class ArrayList
extends AbstractList
implements List
上記の定義から、
1.ArrayListはAbstractListから継承され、Listが実現されているため、関連する追加、削除、修正、遍歴などの機能をサポートするキューである.
2.ArrayListはRandomAccessインタフェースを実現し、ランダムアクセス機能を提供する.RandmoAccessはjavaでListによって実装され、Listに高速アクセス機能を提供するために使用される.
3.ArrayListはCloneableインタフェース、すなわちclone()関数を実現する.クローン化できます.
4.ArrayListはjavaを実現する.io.Serializableインタフェース、シーケンス化をサポートします.
5.ArrayListは汎用型をサポートしています.
二、ArrayListの基本属性:
ArrayListでは、要素を格納する配列と配列サイズの2つの基本プロパティのみが定義されています.
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer.
*/
private transient Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;三、ArrayListの構造方法:
1.最初の構築方法(パラメータなし):
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}2.第2の構成方法(パラメータ付き:初期容量):
/**
* Constructs an empty list with the specified initial capacity.
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}3.第3の構成方法(1つの集合に入力)
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}四、ArrayList追加要素方法:
1.add(E e):配列の末尾に要素を追加します.
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}ensureCapacity():
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
//minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
modCountを追加した後、minCapacity(すなわちsize+1)がoldCapacity(すなわちelementData.length)より大きいかどうかを判断し、それより大きい場合はmax((oldCapacity*3)/2+1、minCapacity)に調整し、elementData容量を新しい容量に調整し、コンテンツが元の配列要素であり、サイズが新しい容量の配列がelementDataに割り当てられる.そうでなければ操作しません.
したがって、次のことがわかります.
ArrayList容量の拡張は配列要素の複製をもたらし,多重拡張容量は配列内容全体の複製を複数回実行する.リストの長さを大まかに判断し、ensureCapacityを呼び出して容量を調整すれば、運転速度を効果的に向上させることができます.
また,ArrayListは容量拡張ごとに約1.5倍,2分の1増加した.
2.add(int index,E element):指定したインデックスに要素を追加します.
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}まず指定位置indexがelementDataの限界を超えるか否かを判断し、その後ensureCapacity調整容量(容量が十分であれば拡張しない)を呼び出し、Systemを呼び出す.arraycopyは、elementDataのindexから始まるsize-index個の要素をindex+1からsize+1までの位置(すなわち、indexから始まる要素はいずれも1つ後ろに移動)にコピーし、index位置の値をelementに向けます.
3.addAll(Collectionc):arrayListを別のarrayListに追加します.
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}まず集合cを配列に変換する、変換後の配列の程度とArrayListのsizeに応じて容量を広げてからSystemを呼び出す.arraycopyメソッドは要素をelementDataの末尾にコピーし、sizeを調整します.返されるコンテンツ解析によれば,集合cのサイズが空でない,すなわち変換後の配列長が0でない限りtrueが返される.
4.addAll(int index,Collectionc):1つのarrayListを別のarrayListの指定したインデックスに追加します.
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + size);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}まずindexが境界を越えているかどうかを判断します.その他のコンテンツはaddAll(Collectionc)とほぼ一致していますが、レプリケーション時にindexから始まる要素をX(cが配列に変わった後の長さ)個の位置(レプリケーションのプロセスでもあります)、その後、配列コンテンツをelementDataのindex位置からindex+Xにレプリケーションします.
五、ArrayListの要素削除方法:
1.remove(int index)メソッド:指定した位置の要素を除去します.
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}まず範囲をチェックし、modCountを修正し、除去する要素を保持し、除去位置の後の要素を前に移動し、list末尾要素を空にし、除去された要素を返します.
2.remove(Object o)メソッド:指定した要素の要素を除去します.
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}まず、コードから、削除に成功した後にtrueを返し、そうでなければfalseを返すことがわかります.remove(Object o)ではelementを巡回して受信オブジェクトが存在するかどうかを探し,見つかったらfastRemoveを呼び出してオブジェクトを除去する.なぜエレメントを見つけたらindexがわかり、remove(index)でエレメントを除去しないのですか?fastRemoveは境界を判断する処理をスキップしたため、要素を見つけることはindexが境界を超えないことを決定することに相当し、fastRemoveは除去された要素を返さない.次はfastRemoveのコードで、基本的にremove(index)と一致しています.
fastRemove():
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
}3.removeRange(int fromIndex,int toIndex):指定した範囲の要素を除去します.
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// Let gc do its work
int newSize = size - (toIndex-fromIndex);
while (size != newSize)
elementData[--size] = null;
}実行プロセスは、elementDataをtoIndex位置から始まる要素をfromIndexに移動し、toIndex位置以降の要素をすべて空にしてsizeを変更します.
4.clear():ArrayListメソッドをクリアします.
public void clear() {
modCount++;
// Let gc do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}clearの場合、elementDataの長さは変更されていません(せっかく申請したり、広げたりしたのに、どうして解放したのか、残しておいても無駄です.リストの内容を変更しないと判断したらtrimToSizeを呼び出してスペースを解放したほうがいいです)、すべての要素をnull、sizeを0に設定します.つまりclearメソッドは配列内の要素をnullに、ArrayListのサイズを0に、メモリを解放しません.
六、ArrayListの要素修正方法:
1.set(int index,E element):指定したインデックス位置の要素の値を変更します.
public E set(int index, E element) {
RangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}まず範囲をチェックし、古い要素を新しい要素で置き換え、古い要素を返します.
七、ArrayListの要素取得方法:
1.get(int index):指定したインデックスの要素を取得します.
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}まずRangeCheckメソッドを呼び出してインデックスが境界を越えているかどうかを検出し,配列の下付きスケールに基づいて配列要素を直接取得することで,ArrayListは要素の挿入が遅いが,クエリが速い(配列のクエリ速度が速い)ことがわかる.
八、ArrayListのインデックス関連方法:
1.indexOf(Object):ArrayList内の要素のインデックスを取得します.
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}オブジェクトがlistにあるかどうかはelementData配列を巡回して判断し,存在する場合は要素のindex([0,size-1]),存在しない場合は−1を返す.
2.lastIndexOf():指定した要素の最後に表示されるインデックス値を取得します.
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}後ろから前へelement配列を巡回し,Objectに遭遇するとindex値を返し,遭遇しなければ−1を返す.
九、ArrayListの他の方法:
1.isEmpty():ArrayListが空かどうかを判断します.
public boolean isEmpty() {
return size == 0;
}
sizeが0に等しいかどうかを直接返します.
2.size():ArrayListのサイズを取得します.
public int size() {
return size;
}
3.contains(Object):要素がArrayListにあるかどうかを判断します.
public boolean contains(Object o) {
return indexOf(o) >= 0;
}4.toArray():ArrayListを配列に変換します.
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}Arraysを呼び出します.copyOfは、size個のelementDataの要素である配列を返します.すなわち、elementDataが0からsize-1の位置にある要素をコピーして新しい配列に返します.
以下は一般的な書き方です.
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}受信配列の長さがsizeより小さい場合、新しい配列が返されます.サイズはsizeで、タイプは受信配列と同じです.受信配列の長さがsizeと等しい場合、elementDataを受信配列にコピーし、受信配列を返します.受信配列の長さがsizeより大きい場合、elementDataのコピーに加えて、返される配列のsize番目の要素が空になります.
5.trimToSize():格納要素配列の空間サイズを圧縮します.
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}elementDataの長さが広がるため、sizeはその中に含まれる要素の数をマークします.だからsizeは小さいがelementDataが現れる.lengthが大きい場合、空間の浪費が発生します.trimToSizeはelementDataに新しい配列を返し、要素の内容は変わらず、lengthはsizeと同じで、スペースを節約します.
十、ArrayListとLinkListの比較:
1.実装方式:ArrayListは動的配列に基づくデータ構造を実現し、LinkedListはチェーンテーブルに基づくデータ構造を実現する.
2.ランダムアクセス速度:ArrayListの下位層は配列によって実現され、LinkedListは双方向チェーンテーブルであるため、ArrayListのランダムアクセス速度はLinkedListより速い.
3.挿入削除速度:ArrayList下位層は配列によって実現されるため、0番位置に挿入するとlistのすべての要素が移動し、最後に要素を挿入する際に移動する必要がない.LinkedListは双方向チェーンテーブルで、任意の場所に要素を挿入するのに要する時間は同じです.従ってLinkedList挿入削除速度はArrayListよりも速い.
以上のように、リストに多くの挿入と削除操作がある場合はLinkedListを使用して効率を上げ、インデックスクエリが多い場合はArrayListを使用する(拡張型のforループやIteratorを使用してLinkedListを巡る効率が大幅に向上する).