JDKを読む 〜 ArrayList 〜

うちのスタッフの連中と昼間話題になったのでJDKのソースを少し読んでみることに。非常に基本的なことなんで諸先輩方には退屈なエントリですが、、、ここは初心に戻ってまずArrayListから。

ArrayListクラスの中

• Arrayだけに内部は固定長の配列です。

余談ですが、ArrayListのE型ではなくObjectで管理されるんですね。

/**
     * 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;

• デフォルトコンストラクタを呼ぶと10要素分の配列が作られる

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
	this(10);
    }

• addメソッドではensureCapacityした後に配列の最後に要素が追加される

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
    }

• ensureCapacityは新しいサイズでArrays.copyOfしている。Arrays.copyOfは新しい配列をnewしてcopyします。当然、メモリのブロック転送が発生する。

    /**
     * Increases the capacity of this <tt>ArrayList</tt> instance, if
     * necessary, to ensure that it can hold at least the number of elements
     * specified by the minimum capacity argument.
     *
     * @param   minCapacity   the desired minimum capacity
     */
    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);
	}
    }

• getメソッドではレンジのチェック後、要素を返す。E型でキャストして返す。

    /**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
	RangeCheck(index);

	return (E) elementData[index];
    }

ArrayListは、要素の追加・削除が少ない用途では向いているが、それ以外の用途ではLinkedListですね〜。
こんな感じでJavaの中を読むと面白いよ〜。