JDK ArrayListソースコード解析

今日はArrayListのソースコードを見て、自分の心得を書いてみました
まずArrayListの継承体系であり、コードは以下の通りである.

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayListは、リストインタフェースの実装クラスである、リストインタフェースは、規則的に重複する要素を格納することができることを規定するので、ArrayListはこの原則に従う.次に、ArrayListの構成方法を見てみましょう.

 public ArrayList(int initialCapacity) {
	super();
        if (initialCapacity < 0) // 0， 
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
	this.elementData = new Object[initialCapacity];// ArrayList 
    }


    public ArrayList() {
	this(10);// 
    }

まず第2の構造方法を見てみると、構造方法にはパラメータはありませんが、実装では本クラスのパラメータ付き構造方法がデフォルトで呼び出され、10個の長さに初期化されます.最初の構成方法では、ArrayList容量を初期化するためのパラメータが入力される
 
次のセクションでは、一般的な方法を分析します.

 public boolean add(E e) {
	ensureCapacity(size + 1);  // e
	elementData[size++] = e; // size e, size+1
	return true;// , true
    }

 
この方法では、ensureCapacity(size+1)という方法に重点を置いています.次に、ソースコードを見てみましょう.

 public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;// 
	if (minCapacity > oldCapacity) {          // minCapacity
	    Object oldData[] = elementData;   
	    int newCapacity = (oldCapacity * 3)/2 + 1;// 
    	    if (newCapacity < minCapacity) // 
		newCapacity = minCapacity;// 
            elementData = Arrays.copyOf(elementData, newCapacity);// newCapacity  
	}
    }

配列長が定義されると変化しないため、JDKではensureCapacityメソッドを用いて配列長が動的に変化することを確保している.これもArrayListと配列の違いである
 
 

 public E get(int index) {
	RangeCheck(index); // index 

	return (E) elementData[index]; // index 
    }

 
getメソッドはindexの要素を取り出すために使用され、このメソッドではRangeCheckメソッドを使用してインデックスが境界を越えているかどうかを確認します.
 
 

 public boolean contains(Object o) {
	return indexOf(o) >= 0;
    }

containsメソッドは,ArrayList中のオブジェクトoが存在するか否かを判断するために用いられ,indexOfを呼び出して実現する.
 

public int indexOf(Object o) {
	if (o == null) {// o null
	    for (int i = 0; i < size; i++)// ArrayList 
		if (elementData[i]==null)// , 
		    return i;
	} else {         // o null
	    for (int i = 0; i < size; i++)// ArrayList 
		if (o.equals(elementData[i]))// o, 
		    return i;
	}
	return -1;// -1
    }

 
indexOf法は比較的簡単であるが,オブジェクトoをnullと非nullに分けて判断することに注意する.
 
 

 public E remove(int index) {
	RangeCheck(index);// 

	modCount++;
	E oldValue = (E) elementData[index];// index 

	int numMoved = size - index - 1;// , 1, 
	if (numMoved > 0)// 0, ArrayList 
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	elementData[--size] = null; //  null, 

	return oldValue;// 
    }

上のソースコードから分かるように、1つの要素を削除して最後の要素ではない場合、下位の配列を移動する必要があり、効率が低下するため、ArrayList
削除操作が多すぎるシーンには適していません
 
ArrayListにはremoveメソッドも再ロードされています.
 

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;
    }

その基本思想はremove(int)と大きく異なる
 
 
 

 public void add(int index, E element) {
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);

	ensureCapacity(size+1);  
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);  // , 
	elementData[index] = element;
	size++;
    }

上記のaddメソッドは、指定したインデックスに要素を挿入するために使用され、配列を移動する必要があり、効率が低下します.
 
今日はまずここまで議論して、ArrayListのその他の方法について、討論しないで、使う時自分でJDKソースコードを開けて見ることができます