Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@syoshika_(sho yoshikawa)

【Java】ArrayListのcapacityの増え方

Last updated at Posted at 2023-02-04

結論

  • デフォルトで10個確保する。
  • 足りなくなったら1.5倍して確保する
  • その際、拡張ではなく新しい配列を作り直してる。

詳細はまとめにあります。

経緯

以下のサイトでArrayListとListの違いなどを勉強してたらこんな文章があった。

ArryaList クラスのリストでは、デフォルトで 10 個の要素を格納できる領域が用意されています。その領域の中で先頭から順番に要素が追加されていきます。もし領域が足りなくなった場合には自動的に領域が追加されるため、要素の数があらかじめ決まっている配列とは異なり追加できる要素の数に制限はありません。

この自動的に増えてく仕組みが気になったので調べてみた。

当然割り当てたい数を引数に渡せばその分確保してくれる。
スクリーンショット 2023-02-04 14.48.45.png

容量の拡張ではなく、新しく配列？

ドキュメントにはこう書いてある。

ArrayListに要素を追加すると、その容量は自動的に拡大します。拡大のポリシーについては、要素を追加すると 「一定の償却時間コスト」 が伴うこと以外は、詳しくは指定されていません。

ユーザー目線では詳しく書く必要ないってことなんだろう。
また容量の拡張により処理時間が多くかかることがあるみたいなので、尚更知っておきたい。

同じように気になってる人もいて、回答にはこんなことが書いてあった。

A new array is created and the contents of the old one are copied over. That's all you know at the API level. Quoting from the docs (my emphasis):

どちらかというと拡張ではなく、新しく配列を作り直してるっぽい。

ソースコードを軽く読んでみる

諸事情によりjdk11で読んでます。
1759行もあるのか。

DEFAULT_CAPACITY

冒頭でも触れた通り、最初はサイズ10で確保されるみたい。

openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

add

ArrayListのaddはオーバーロードされてるので、indexを指定して追加もできる。この2つのどちらか。

型　メソッド 説明
void add​(int index, E element) このリスト内の指定された位置に指定された要素を挿入します。
boolean add​(E e) このリストの最後に、指定された要素を追加します。

今回は以下のようなオブジェクト（文字列）のみを追加した時で考える。

sample
ArrayList<String> sample = new ArrayList<>();
sample.add("test");
sample.add("sample");

ソースコードで言うとここに投げられる。

openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

Eは型パラメータ

modCount++

この変数はArrayListに追加や削除などの変更があった際にインクリメントされ、配列が正しく操作されたか整合性を取るためにあるっぽい。

checkForComodificationが至る関数に設置されていて、随時チェックしながら、一致しなければ例外を出す。

ちなみにこいつは減ったりすることはなく、単調に増加するのみ。
誤り訂正ビットとかに近い存在なのかな？

openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
private void checkForComodification(final int expectedModCount) {
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

add(e, elementData, size)

引数を整理すると、

型　変数 説明
E e 追加するデータ
object[] elementData 配列自身
int size 配列自身のサイズ

こいつらを持ってaddに移る。

return true

正しく追加できましたよーの返り値true。

add(E e, Object[] elementData, int s)

処理はとってもシンプル。

openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

  • 容量が10個中10個maxで使われていたら、容量を追加(grow)する処理を入れる

  • 例えば要素が10個くらいしかないのに、new ArrayList<>(123)のように余分に確保してインスタンス化した場合は、新たに領域を追加する必要がないのでif処理はスキップする。

  • 最後尾に要素を追加したいのでelementData[s]に入れる

  • sizeをインクリメントしてあげる。

配列のサイズを返す???.size()としたときに数が合わなくなっちゃうので

openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
/**
 * Returns the number of elements in this list.
 *
 * @return the number of elements in this list
 */
public int size() {
    return size;
}

grow()

サイズを1つ増やしてprivate Object[] grow(int minCapacity)に移る。
このminCapacityがこの後の処理でずっと使われるので覚えておくといいかも。中身はsize + 1。

openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
private Object[] grow() {
    return grow(size + 1);
}

grow(int minCapacity)

新しく配列を作り替えてるのはここだった。
Arrays.copyOfで複製する際にnewCapacityでサイズを決めてるみたいだ。

openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
return elementData =
Arrays.copyOf(elementData, newCapacity(minCapacity));

【本題】newCapacity(int minCapacity)

出てきている定数についておさらい。

型　変数 説明
DEFAULT_CAPACITY 10
MAX_ARRAY_SIZE Integer.MAX_VALUE - 8 = 2147483639
DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}（Object[]）

MAX_ARRAY_SIZEの決め方にも疑問が残るがとりあえずあれ以上確保するとOutOfMemoryErrorが発生する。

openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

int newCapacity

ビットシフトをした値を加えることで設定している。

int newCapacity = oldCapacity + (oldCapacity >> 1);

今、oldCapacity = 100として考えると

  • 2進数変換
    oldCapacity = 100 = 1100 1000(2)
  • 右へ1ビットシフト
    (oldCapacity >> 1) = 0110 0100(2) = 50
  • newCapacity = 100 + 50 = 150

要するに、1.5倍した値が新しいキャパになるみたい。

openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    return Math.max(DEFAULT_CAPACITY, minCapacity);

ArrayListをインスタンス化ばかりで、配列に何もない状態なのであれば、デフォルトのサイズ10と比較して、大きい方で確保する。
なぜなら宣言時（何も要素を追加してない状態）ではサイズ0だから。

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
return minCapacity;

コメントでオーバーフローって書いてあるので、その通りです。

ビットシフトした値を加算した結果Integer.MAX_VALUE = 2147483647を超えた場合、負になってしまうので例外が発生します。

ここに関しては、この後説明するhugeCapacityで同じ処理が書かれているため、if (newCapacity < 0)の誤植なのかな？

openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
return (newCapacity - MAX_ARRAY_SIZE <= 0)
    ? newCapacity
    : hugeCapacity(minCapacity);
}

三項演算子を使って、newCapacity <= MAX_ARRAY_SIZEになってないかチェック。
それを超えるほどどでかい場合は男すぎるのでhugeCapacityへ投げる。

int hugeCapacity(int minCapacity)

grow(size + 1)の段階でオーバーフローしていないかチェック。
newCapacityメソッドのときにエラーハンドリングしておけばいい気がするけども。。

openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

returnに関しては
2147483640 ~ 2147483647の範囲であれば、
一律2147483647に合わせる。

~ 2147483639以下の範囲であれは、
一律2147483639に合わせる。
って処理みたい。

理由は、謎です。

openjdk-jdk11/src/java.base/share/classes/java/util/ArrayList.java
return (minCapacity > MAX_ARRAY_SIZE)
    ? Integer.MAX_VALUE
    : MAX_ARRAY_SIZE;

まとめ

まとめると、

タイミング 確保される数
引数なし宣言時 DEFAULTCAPACITY_EMPTY_ELEMENTDATAにより0
引数に0で宣言時 EMPTY_ELEMENTDATAにより0
add（初回） 10
add（2回目） 10
add（3回目） 10
... ...
... ...
add（10回目） 10
add(11回目) 15
add(12回目) 15
add(13回目) 15
add(14回目) 15
add(15回目) 15
add(16回目) 22
add(17回目) 22
... ...
... ...
add(2147483637回目) 2147483639
add(2147483638回目) 2147483639
add(2147483639回目) 2147483639
add(2147483640回目) 2147483647
add(2147483641回目) 2147483647
add(2147483642回目) 2147483647
... ...
... ...
add(2147483647回目) 2147483647
add(2147483648回目) OutOfMemoryError

かな？
数の大きいあたりはあまり理解しきれてないかもしれない。

2147483648以上も確保するプログラムがあるならば、設計を見直すべきかもなので、例外を投げるのは妥当かもしれない。

ベンチマーク

ArrayListは容量を1.5倍ずつ増やしていくことで性能が良くなると言うのなら、実際にその恩恵があるのかを試してみる。

ArrayList()<>とArrayList(N)<>とで比較して、
測定はSystem.currentTimeMillis()を使ってみる。

テストコード

Main.java
import java.util.ArrayList;

public class Main {
    static final int SIZE = 10000;
    public static void test(ArrayList list, int times) {
        System.out.print(times + "回目: ");
        long start = System.currentTimeMillis();
        for (int i = 0; i < SIZE; i++) {
            list.add("hello");
        }
        long end = System.currentTimeMillis();
        System.out.println((end - start));
    }
    public static void main(String[] args) {
        System.out.println("ArrayList<>()");
        for (int i = 1; i <= 10; i++) {
            ArrayList list = new ArrayList<>();
            test(list, i);
        }

        System.out.println();

        System.out.println("ArrayList<>(SIZE)");
        for (int i = 1; i <= 10; i++) {
            ArrayList initList = new ArrayList<>(SIZE);
            test(initList, i);
        }
    }
}

SIZEを変えていきながら、それぞれ10回測定します。

SIZE = 10 0000

result
/Library/Java/JavaVirtualMachines/temurin-11.jdk/Contents/Home/bin/java -javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=52745:/Applications/IntelliJ IDEA CE.app/Contents/bin -Dfile.encoding=UTF-8 -classpath /Users/sho/Test/Test/out/test/Test Test.Main
ArrayList<>()
1回目: 10
2回目: 3
3回目: 2
4回目: 1
5回目: 6
6回目: 2
7回目: 1
8回目: 2
9回目: 1
10回目: 1

ArrayList<>(SIZE)
1回目: 0
2回目: 0
3回目: 1
4回目: 0
5回目: 1
6回目: 0
7回目: 1
8回目: 0
9回目: 1
10回目: 0

Process finished with exit code 0

SIZE = 100 0000

result
/Library/Java/JavaVirtualMachines/temurin-11.jdk/Contents/Home/bin/java -javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=52756:/Applications/IntelliJ IDEA CE.app/Contents/bin -Dfile.encoding=UTF-8 -classpath /Users/sho/Test/Test/out/test/Test Test.Main
ArrayList<>()
1回目: 37
2回目: 29
3回目: 22
4回目: 21
5回目: 24
6回目: 23
7回目: 27
8回目: 376
9回目: 14
10回目: 14

ArrayList<>(SIZE)
1回目: 11
2回目: 10
3回目: 10
4回目: 10
5回目: 9
6回目: 9
7回目: 9
8回目: 10
9回目: 10
10回目: 9

Process finished with exit code 0

SIZE = 1000 0000

result
/Library/Java/JavaVirtualMachines/temurin-11.jdk/Contents/Home/bin/java -javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=52762:/Applications/IntelliJ IDEA CE.app/Contents/bin -Dfile.encoding=UTF-8 -classpath /Users/sho/Test/Test/out/test/Test Test.Main
ArrayList<>()
1回目: 640
2回目: 780
3回目: 271
4回目: 942
5回目: 248
6回目: 160
7回目: 149
8回目: 243
9回目: 153
10回目: 143

ArrayList<>(SIZE)
1回目: 122
2回目: 115
3回目: 87
4回目: 86
5回目: 86
6回目: 86
7回目: 89
8回目: 87
9回目: 100
10回目: 93

Process finished with exit code 0

ArrayList<>()は最長実行時間942ms、
ArrayList<>(SIZE)は最短実行時間86msであることを考えると、ある程度要素数に目星がついてたらititialCapacityを与えてあげるほうがいいのかも。

SIZE = 1 0000 0000

result
/Library/Java/JavaVirtualMachines/temurin-11.jdk/Contents/Home/bin/java -javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=52767:/Applications/IntelliJ IDEA CE.app/Contents/bin -Dfile.encoding=UTF-8 -classpath /Users/sho/Test/Test/out/test/Test Test.Main
ArrayList<>()
1回目: 5198
2回目: 5622
3回目: 5156
4回目: 6611
5回目: 3197
6回目: 6528
7回目: 5580
8回目: 5701
9回目: 5808
10回目: 5563

ArrayList<>(SIZE)
1回目: 1193
2回目: 1036
3回目: 1370
4回目: 1127
5回目: 1139
6回目: 1027
7回目: 1372
8回目: 1142
9回目: 1160
10回目: 1522

Process finished with exit code 0

ここら辺から顕著に違いが出てきてる。

LinkedList（追記）

そもそもこんなに配列を編集するなら連結リストの方が早いだろうってことでついでにテストしてみる。

ランダムアクセス(SIZE=1000 0000)

配列のindexを指定したときの速さを調べる。
1000万で用意して、900万番目にアクセスする速度を比較してみる。

Main.java
...
...
long start = System.currentTimeMillis();
list.get(SIZE - 1000000);
long end = System.currentTimeMillis();
System.out.println(end - start);
result
/Library/Java/JavaVirtualMachines/temurin-11.jdk/Contents/Home/bin/java -javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=52846:/Applications/IntelliJ IDEA CE.app/Contents/bin -Dfile.encoding=UTF-8 -classpath /Users/sho/Test/Test/out/test/Test Test.Main
ArrayList<>()
1回目: 0
2回目: 0
3回目: 0
4回目: 0
5回目: 0
6回目: 2
7回目: 0
8回目: 0
9回目: 0
10回目: 0

linkedList<>()
1回目: 6
2回目: 16
3回目: 5
4回目: 10
5回目: 4
6回目: 4
7回目: 4
8回目: 6
9回目: 6
10回目: 7

Process finished with exit code 0

これは確かにArrayListの方が早く出てますね。

remove(SIZE=1000 0000)

追加・削除操作ではLinkedListの方が早くなるのかも。

Main.java
...
...
long start = System.currentTimeMillis();
list.remove(SIZE - 1);
list.remove(SIZE - 100);
list.remove(SIZE - 10000);
list.remove(SIZE - 1000000);
long end = System.currentTimeMillis();
System.out.println(end - start);
result
/Library/Java/JavaVirtualMachines/temurin-11.jdk/Contents/Home/bin/java -javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=52889:/Applications/IntelliJ IDEA CE.app/Contents/bin -Dfile.encoding=UTF-8 -classpath /Users/sho/Test/Test/out/test/Test Test.Main
ArrayList<>()
1回目: 1
2回目: 17
3回目: 1
4回目: 13
5回目: 1
6回目: 0
7回目: 1
8回目: 0
9回目: 0
10回目: 14

linkedList<>()
1回目: 6
2回目: 4
3回目: 3
4回目: 4
5回目: 4
6回目: 4
7回目: 5
8回目: 6
9回目: 9
10回目: 4

Process finished with exit code 0

あれ、思ってたのと違う。
まあ、安定しているといえば安定しているのか。

感想

  • 一介の貧弱プログラマーから言わせてもらうと、ifの分岐とかみる限りテストケースのエラーハンドリングに対して最適化してしまったコード感がある（ちょっと読みづらかった）

  • sizeメンバに対して、こういうのってgetter, setter使わなくて大丈夫なの？

  • 増加率が1.5倍なのは、おそらく2倍3倍のようにあまりに大きい数を入れちゃうとオーバーフローがぐるぐるして結果が正の数になる可能性がありif文じゃ検知できなくなるし、1.25倍とかでも配列を作り直す手間が増えるからいい塩梅なのかも。

  • いらなくなった配列はガベージコレクションによって回収されるので、そこらへんの仕組みも勉強したい。

余談

ArrayListについて調べていたら同じようにソースコード見てる人がいたので、全文読み切りたい方はいいかもしれないです。

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?