ArrayListのadd/get/growから見るジェネリクスと配列管理

下準備

JAVA標準のソースを取得

sudo apt install openjdk-17-source

ソースの場所を調べる

unzip -l /usr/lib/jvm/java-17-openjdk-amd64/lib/src.zip | grep List.java

見たいJAVAファイルを探す

unzip -p /usr/lib/jvm/java-17-openjdk-amd64/lib/src.zip java.base/java/util/List.java | less
unzip -l /usr/lib/jvm/java-17-openjdk-amd64/lib/src.zip | grep ArrayList.java

List.java

List.javaはただのインターフェースで、実体はArrayList等の中で実装されている。

public interface List<E> extends Collection<E> {

ArrayList.java

コンストラクタ

コンストラクタは複数あるが最も一般的なもの(new ArrayList<>()とした時に呼ばれるコンストラクタ)を読む。

初めに内部配列elementDataを{}で初期化している。
リストの要素は内部的にObject型の配列として保存されていることが分かる。

    /**
     * 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 = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    //...中略...

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

追加(add)

※indexつきの方は配列をずらす処理をしているが、今回はジェネリクスの扱いを理解することが主旨の為、簡単なadd(E e)のみ読む。

sizeはリストに入っている要素の数。
add()が呼ばれると、内部配列elementDataの最後尾にeを格納し、sizeを1増やす。
elementDataはObject型で、E型の要素をそのまま代入している。
ジェネリクス型は実質Object型と同じ扱いになる。

    /**
     * This helper method split out from add(E) to keep method
     * bytecode size under 35 (the -XX:MaxInlineSize default value),
     * which helps when add(E) is called in a C1-compiled loop.
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

取得(get)

index が 0 <= index < size の範囲にあるか確認
elementData[index]を返す。
return (E) elementData[index];`
型消去により実行時EはObjectへ変換されている。よってキャストして元の型情報を明記する必要がある。 一番したのコメントで訂正済み

    /**
     * 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) {
        Objects.checkIndex(index, size);
        return elementData(index);
    }

    // Positional Access Operations

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

配列拡張(grow)

配列がいっぱいの時に呼ばれる。
新しい配列の長さ(newCapacity)を計算し、その長さで新しい配列を生成したのち旧配列の中身を新しい配列へ複製する。
配列が空の場合は新しい配列を返す。

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

    private Object[] grow() {
        return grow(size + 1);
    }