何がアラリストですか

13608 ワード
概要
ArayListはjava集合の枠組みの中で比較的によく使われるデータ構造である.AbstractListから引き継ぎ、Listインターフェースを実現しました.下部は配列に基づいて容量サイズの動的変化を実現した.nullの存在を許可します.また、RandomAccess、Cloeable、Serializableインターフェースを実現したので、ArayListはクイックアクセス、コピー、プログレッシブをサポートしています.
メンバー変数
ArayList下層は配列に基づいて容量サイズの動的変化を実現した.
/**
* The size of the ArrayList (the number of elements it contains).
*/
private int size;  //       
transient Object[] elementData;
注意:上のsizeはelementaの中に実際にどれぐらいの要素があるかを意味します.element Data.lengthは集合容量で、最大でどれぐらいの要素が収容できるかを表しています.
デフォルトの初期容量は10です.
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
この変数はAbstractListに定義されている.Listの操作回数を記録します.主に使用するのはIteratorで、反復の過程で集合が修正されることを防止するためです.
protected transient int modCount = 0;
次の二つの変数はコンストラクションの中で使われます.
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
二つの空の配列は何の違いがありますか?We distinguish this from EMPTY_ELIENTDATA to know how much to inflate when first element is added.簡単に言うと、最初に元素を添加した時に、このelement Dataが空からの構造関数か、それとも構造関数が初期化されているかを知っています.どのように拡大するかを確認します.
構造関数
  • 無惨構造関数
    • /**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
    注:コメントは、容量が10の空のリストセットを構成するということですが、構造関数は、elementaに空の配列を割り当てただけで、実は最初に要素を追加した時に容量が10に拡大しました.
  • は、初期容量の大きさがinitial CapacityであるArayList
    • を構成する.
    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);
	}
}
    上記のソースから分かります.無参画構造関数を使う時はDEFAULtCAPACITY_です.EMPTY_EEMENTDATAはelementaに値を与えます.initial Capacityがゼロの時はEMPTY_です.EEMENTDATAはelementaに値を与えます.initial Capacityが0より大きいとき、initial Capacityサイズのobject配列を初期化して、element Dataに値を与えます.
  • は、指定Collectionを使用してArayListの構造関数
    • を構築する.
    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;
	}
}
    Collectionを配列に変換し、element Dataに値を与え、elementaの要素の個数をsizeに与えます.sizeがゼロでなければ、elementaのクラスタイプはObject[]であるかどうかを判断し、そうでなければ一回の変換を行います.sizeがゼロなら、EMPTY_を.EEMENTDATAは、new ArayList(0)に相当するelementaに割り当てられている.
    主な操作方法の解析
  • add操作
    • 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++;
	// overflow-conscious code
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}
    したがって、要素を集合に追加するたびに、集合容量の大きさを確認する.そしてsizeを1から増やします.ensureCapacity Internal関数では、elementa=DEFAULTCCAPACITY_EMPTY_EEMENTDATAはDEFAULT_を取ります.CAPACITYとminCapacityの最大値はつまり10です.これがEMPTY_ですELLENTDATAとDEFAULTACACITY_EMPTY_EEMENTDATAの違いはどこですか?また、上記の説明も検証した.無惨な構造関数を使用する場合、初めて元素を添加する時に初期化容量は10である.ensureExplicit CapacityではmodCountに対して1を自己増加し、操作回数を記録し、その後、minCapacityがelementaの長さより大きい場合、集合を拡張する.初めて要素を追加した時のelementaの長さは明らかにゼロです.じゃ、grow関数を見てみます.
    private void grow(int minCapacity) {
	// overflow-conscious code
	int oldCapacity = elementData.length;
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	if (newCapacity - minCapacity < 0)
	    newCapacity = minCapacity;
	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);
}
    簡単明瞭な関数で、デフォルトでは1.5倍の容量に拡張されます.しかし、拡張後は必ずしも適用されません.小さすぎるかもしれません.大きすぎるかもしれません.だから次の二つのif判断があります.もし1.5倍が小さすぎると、私たちが必要とする容量の大きさをnewCapacityに割り当てます.1.5倍が大きすぎたり、必要な容量が大きすぎたりしたら、直接newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZEを持って拡大します.そして、元の配列のデータをnewCapacityサイズの新しい配列にコピーし、新しい配列をelementaに割り当てます.
    public void add(int index, E element) {
	rangeCheckForAdd(index);
	ensureCapacityInternal(size + 1);  // Increments modCount!!
	System.arraycopy(elementData, index, elementData, index + 1, size - index);
	elementData[index] = element;
	size++;
}

public boolean addAll(Collection extends E> c) {
	Object[] a = c.toArray();
	int numNew = a.length;
	ensureCapacityInternal(size + numNew);  // Increments modCount
	System.arraycopy(a, 0, elementData, size, numNew);
	size += numNew;
	return numNew != 0;
}

public boolean addAll(int index, Collection extends E> c) {
	rangeCheckForAdd(index);

	Object[] a = c.toArray();
	int numNew = a.length;
	ensureCapacityInternal(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;
}
    以上のソースコードから分かるように、add(int index、E element)、addAll(Collection extens E>c)、addAll(int index、Collection extens E>c)操作は、集合容量の検査を先に行い、配列が逸脱しないことを確認します.そして、古い配列要素をSystem.arraycopy()法で新しい配列にコピーします.
  • Remove操作
    • public E remove(int index) {
	rangeCheck(index);
	modCount++;
	E oldValue = elementData(index);
	int numMoved = size - index - 1;
	if (numMoved > 0)
		System.arraycopy(elementData, index+1, elementData, index, numMoved);
	elementData[--size] = null; // clear to let GC do its work
	return oldValue;
}
	
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;
}

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; // clear to let GC do its work
}
    remove(int index)を呼び出すと、まずindexが適法かどうかを確認し、削除する要素が配列の最後の位置にあるかを判断します.indexが最後でないなら、再度System.arraycopy()メソッドコピー配列を呼び出します.つまり、index+1からすべての要素を前に一つの位置に移動します.配列の最後の位置を空白にします.size-1.indexが最後の要素であれば、配列の最後の位置をそのまま空にします.size-1でいいです.remove(Object o)を呼び出すと、oを空に分けて処理します.その後、配列を巡回して、最初のoに対応する下付きindexを見つけて、fastRemove方法を呼び出して、indexとしてマークされた要素を削除します.実際にはfastRemove(int index)方法とremove(int index)方法は基本的に全部同じです.
  • get操作
    • public E get(int index) {
	rangeCheck(index);
	return elementData(index);
}
    ArayList下層は配列に基づいて実現されるので、要素を取得するのはかなり簡単であり、配列ランダムアクセスを直接呼び出すだけでよい.
    ディエ代機iterator
    集合を使用したことがある人は知っています.forで集合を巡回する時は集合をremove操作してはいけません.remove操作で集合の大きさが変わります.結果が不正確であり、配列の下の標的がオフラインになりやすいため、より深刻なものはConcerentModificationExceptionを投げます.
    foreach巡回はiteratorと同じです.異常原因を明らかにするためには、ソースコードをもう一度通過しなければなりません.
    public Iterator iterator() {
	return new Itr();
}
    元は直接にItrオブジェクトを返します.
    private class Itr implements Iterator {
	int cursor;       // index of next element to return
	int lastRet = -1; // index of last element returned; -1 if no such
	int expectedModCount = modCount;

	public boolean hasNext() {
		return cursor != size;
	}

	@SuppressWarnings("unchecked")
	public E next() {
		checkForComodification();
		int i = cursor;
		if (i >= size)
			throw new NoSuchElementException();
		Object[] elementData = ArrayList.this.elementData;
		if (i >= elementData.length)
			throw new ConcurrentModificationException();
		cursor = i + 1;
		return (E) elementData[lastRet = i];
	}

	public void remove() {
		if (lastRet < 0)
			throw new IllegalStateException();
		checkForComodification();

		try {
			ArrayList.this.remove(lastRet);
			cursor = lastRet;
			lastRet = -1;
			expectedModCount = modCount;
		} catch (IndexOutOfBoundsException ex) {
			throw new ConcurrentModificationException();
		}
	}

	final void checkForComodification() {
		if (modCount != expectedModCount)
			throw new ConcurrentModificationException();
	}
}
    ソースからは、ArayListはItrインターフェースを実現する内部カテゴリを定義することができます.Itr内部には3つのメンバー変数があります.cursor:次の訪問する要素を表します.lastRet:前に訪問する要素の下付きを表します.expectedModCount:ArayList修正回数に対する期待値を表し、初期値はmodCountである.
    Itrの3つの主要関数を見てみます.
    hasNextは比較的に簡単に実現して、もし次の元素の下付きが集合の大きさに等しいならば、最後まで証明しました.
    nextの方法も複雑ではないですが、肝心です.まず、expectedModCountとmodCountが同じかどうかを判断します.その後、cursorを判断して、セットサイズと配列長を超えているかどうかを確認します.その後、cursorはlastRetに値を割り当て、lastRetとラベル付けされた要素を返します.最後にcursorを1から増やします.開始時、cursor=0、lastRet=-1;nextメソッドを呼び出すたびに、cursorとlastRetは1つずつ増加します.
    remove方法はまず、lastRetの値が0より小さいかどうかを判断し、expectedCountとmodCountが等しいかを確認します.次にキーとして、直接ArayListを呼び出すremove方法は、lastRetと名付けられた要素を削除する.その後、lastRetをcursorに割り当て、lastRetを−1に再割り当てし、expectedModCountに値を再割り当てする.
    次にItrの動作を分析します.図のように、開始時には0とラベルされた要素を指し、lastRetは−1とラベルされた要素、つまりnullを指します.nextを呼び出すたびに、cursorとlastRetはそれぞれ1つずつ増加します.nextが“C”に戻ると、cursorとlastRetはそれぞれ3と2[図2]である.
    このときremoveを呼び出します.Itrのremoveではなく、ArayListのremoveです.D Eの二つの要素を直接前に移動します.最後の位置が空いています.そしてmodCountは1を増やします.remove方法から分かります.[図三]
    このときcursor=3,size=4は、配列の最後まで来ていないので、ループは継続します.nextメソッドに来て、前のステップのremove方法がmodCountに対して修正をしたため、expected ModCountとmodCountが等しくなくなりました.これがConccurrent Modification Exception異常の原因です.例.pngからもArayListの内部カテゴリItrにおけるcheckForCompodification方法による異常が見られます.
    異常な解決:
    iterator.removeを直接呼び出してもいいです.この方法ではexpected ModCount＝modCount動作が追加されているからです.しかし、このremove方法にも弊害があります.
  • はremove操作しかできません.add、clearなどItrにはありません.
  • Removeを呼び出す前にnextを呼び出す必要があります.removeが始まったので、lastRetをチェックしました.また、lastRetは-1に初期化されます.
  • next以降は一回だけremoveを呼び出すことができます.RemoveはlastRetを-1
    • に再初期化するためです.
    要約:ArayList下層は、配列に基づいて容量の大きさとダイナミック可変性を実現する.拡大機構は、最初の拡大容量が原容量の1.5倍である.もし1.5倍が小さすぎると、私たちが必要とする容量の大きさをnewCapacityに割り当てます.1.5倍が大きすぎたり、必要な容量が大きすぎたりしたら、直接newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZEを持って拡大します.拡張後は配列のコピーにより元素の正確性を確保しますので、拡大操作をできるだけ減らすようにします.ArayListの最大記憶能力:Integer.MAX_VALEsizeはセットに格納されている要素の個数です.elementeData.lengthは配列長であり、最大でいくつの要素が記憶されてもよいかを示しています.周りを見ながらremoveが必要なら、iteratorを使用しなければなりません.またremoveの前にnextをしなければなりません.nextの後は一回だけremoveを使います.
    いくつかのC言語で実施される順序付けアルゴリズム