ArrayListの詳細解析

ArrayList は本質的にクラスで、内部に配列を持って要素を保存し、size という変数で「実際に何個の要素が入っているか」を管理します。

抽象化すると次のようになります。

Java

        public class ArrayList<E> {
    transient Object[] elementData;
    private int size;
}

ここで重要なのは次の 2 つです。

elementData：実データを保持する内部配列
size：現在有効な要素数

elementData.length と size は同じではありません。

例えば：

elementData.length = 10 は容量が 10
size = 3 は実際には 3 つだけ使用中

つまり、先頭 3 つにデータがあり、残り 7 つは空の可能性があります。

なぜ内部実装は Object なのか

ソースでは E[] ではなく、通常 Object[] が使われます。

理由は、Java ジェネリクスの型消去です。実行時には E の具体型が分からないため、多くのジェネリックコレクションは Object[] に格納し、取り出すときにキャストします。

つまり：

保存時：Object[] に入る
取得時：E にキャストする

このため ArrayList はさまざまな型を扱えますが、型安全のためにジェネリクスは必ず使うべきです。

初期化はどう行われるか

ArrayList の代表的なコンストラクタは次のとおりです。

Java

        new ArrayList<>();
new ArrayList<>(20);
new ArrayList<>(collection);

ソースを理解するうえでは前 2 つが重要です。

引数なしコンストラクタ
いきなり長さ 10 の配列を作るのではなく、まず空配列を参照します。
例えば：
Java
```
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

    
```
これは次を意味します。
- new ArrayList<>() 直後にはデフォルト容量は未確保
- 最初の add で初めてデフォルト容量へ拡張
使われないリストに無駄なメモリを使わないための設計です。

初期容量指定コンストラクタ
new ArrayList<>(20); と書くと、長さ 20 の配列を即座に作ります。
例えば：

Java

        public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
       this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
       this.elementData = EMPTY_ELEMENTDATA;
    } else {
       throw new IllegalArgumentException(...);
    }
}

要素数の見込みがある場合、再拡張回数を減らせるため有効です。

add は実際に何をしているか

もっともよく使うのは list.add(e); です。

処理イメージは次のとおりです。

Java

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

2 ステップで理解できます。

容量確認 ensureCapacityInternal(size + 1) は、追加後に size + 1 個入るかを確認し、不足なら拡張します。
末尾へ追加

Java

        elementData[size] = e;
size++;

または：

Java

        elementData[size++] = e;

末尾追加が速い理由：

位置探索が不要
既存要素の移動が不要
多くの場合は配列末尾への 1 回代入だけ

そのため、末尾追加は償却 O(1) です。

最初の add でなぜ容量 10 になるのか

ここは誤解されやすいポイントです。

引数なしコンストラクタでは最初から長さ 10 の配列は作られません。最初の add で初期容量確保が走ります。

概略は次のとおりです。

Java

        private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

デフォルト容量は通常 private static final int DEFAULT_CAPACITY = 10; です。

つまり：

new ArrayList<>() 直後は空配列参照
最初の add で容量 10 へ

これは遅延確保戦略です。

拡張（grow）メカニズム

容量不足時は grow() が呼ばれます。典型的には次のようなロジックです。

Java

        // JDK 8
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// JDK 17
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(
                oldCapacity,
                minCapacity - oldCapacity, // 最小増分
                oldCapacity >> 1             // 希望増分：1.5倍
        );
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // 初回拡張は 10
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

重要なのは次の行です。 int newCapacity = oldCapacity + (oldCapacity >> 1);

oldCapacity >> 1 は 2 で割ることなので、新容量はおおむね 1.5 倍です。

例：

10 -> 15
15 -> 22
22 -> 33

なぜ 2 倍でも +1 でもなく 1.5 倍なのか。これはメモリと性能のバランスです。

毎回 +1 だと：

拡張回数が多すぎる
毎回コピーが発生する
性能が悪化する

毎回 2 倍だと：

拡張回数は減る
ただしメモリ浪費が増えやすい

1.5 倍はその中間の現実的な選択です。

本当に重い処理は Arrays.copyOf(elementData, newCapacity); です。

より大きい新配列を作成
旧配列の要素をコピー
参照を新配列へ付け替え

つまり拡張は「既存配列を伸ばす」のではなく「新規作成 + コピー」です。

インデックス指定挿入が遅い理由

list.add(index, element); は単純な末尾追加ではありません。

Java

        public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

重要なのは System.arraycopy(...) です。

index 以降の要素を丸ごと 1 つ右へずらします。

例：[A, B, C, D] の位置 1 に X を挿入すると、B/C/D が後ろへ移動して [A, X, B, C, D] になります。

遅い理由は探索ではなく移動コストです。計算量は O(n)。

remove も遅い理由

削除は挿入の逆です。

list.remove(index); のイメージ：

Java

        public E remove(int index) {
    rangeCheck(index);
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null;
    return oldValue;
}

流れは 3 ステップです。

削除対象の古い値を取得
後続要素を前へ詰める
末尾スロットを null にする

elementData[--size] = null; は見た目のためではなく、不要参照を切って GC 回収しやすくするためです。

get が速い理由

get(index) は実質、配列インデックス参照です。

Java

        public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

連続配列なので直接アクセスでき、探索が不要で O(1) になります。

set も速い理由

set(index, element) は指定位置の上書きだけです。

Java

        public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

要素移動がないため、通常 O(1) です。

null と重複を許可する理由

ArrayList は重複排除もしませんし、null も禁止しません。

順序付きコンテナであり、一意性を保証する集合ではないためです。

Java

        list.add(null);
list.add("A");
list.add("A");

上記はすべて有効です。

走査中に ConcurrentModificationException が出る理由

これは modCount に関係します。

ArrayList の継承体系には protected transient int modCount = 0; があります。

add/remove/clear などの構造変更が起きると、通常 modCount が増えます。イテレータ生成時には int expectedModCount = modCount; を記録します。

反復ごとに現在の modCount と expectedModCount を比較し、ズレたら ConcurrentModificationException を投げます。

これが fail-fast です。スレッドセーフ性の提供ではなく、誤用の早期検出が目的です。

Java

        for (String s : list) {
    if (s.equals("A")) {
        list.remove(s);
    }
}

拡張 for は内部でイテレータを使うため、走査中に本体を直接変更するとすぐ例外になります。

Iterator.remove が許されるのは、イテレータ側で状態と expectedModCount を同期更新するためです。

なぜ ArrayList はスレッドセーフではないか

ほとんどの操作でロックを使っていません。

2 つのスレッドが同時に次を実行するとします。

Java

        list.add("A");
list.add("B");

add には次の処理が含まれます。

size 読み取り
容量確認
配列書き込み
size++

これらは原子的ではないため、競合すると上書き・サイズ不整合・範囲外アクセス・データ欠落が起こり得ます。

toArray に意味がある理由

内部は配列でも、そのまま内部配列を公開しないのは次のためです。

容量は有効要素数より大きい場合がある
直接公開するとカプセル化が壊れる

そのため toArray() は：

有効要素だけを含む新しい配列コピーを返す
外部から内部ストレージを直接壊せないようにする

という役割を持ちます。

理解用の簡易 ArrayList

Java

        class MyArrayList<E> {
    private Object[] data = new Object[10];
    private int size = 0;

    public void add(E e) {
        if (size == data.length) {
            grow();
        }
        data[size++] = e;
    }

    public E get(int index) {
        checkIndex(index);
        return (E) data[index];
    }

    public E remove(int index) {
        checkIndex(index);
        E oldValue = (E) data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        data[--size] = null;
        return oldValue;
    }

    private void grow() {
        int newCapacity = data.length + (data.length >> 1);
        Object[] newData = new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }
}

折りたたむ

時間計算量

インデックスアクセス：O(1) 配列なので直接到達できる。
末尾追加：償却 O(1) 通常は末尾代入のみ。拡張が発生した回はコピーで O(n)。
途中挿入：O(n) 後続要素の右シフトが必要。
途中削除：O(n) 後続要素の左シフトが必要。
値検索：O(n) 一般に線形走査が必要。

まとめると ArrayList は：

利点：ランダムアクセスが速く、末尾追加も効率的。

欠点：中間の挿入・削除が遅い。

Fonnpo

Spring フレームワーク完全ガイド

HashMapの詳細解析

LinkedListの詳細解析