【Java】ArrayListのcapacityの増え方

# 結論

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

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

# 経緯

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

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

https://www.javadrive.jp/start/collection/index1.html

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

> 当然割り当てたい数を引数に渡せばその分確保してくれる。
![スクリーンショット 2023-02-04 14.48.45.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/777324/306221f8-c592-7b7b-25f2-8669972456a7.png)


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

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

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

https://docs.oracle.com/javase/jp/11/docs/api/java.base/java/util/ArrayList.html

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

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


> **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):


https://stackoverflow.com/questions/4450628/arraylist-how-does-the-size-increase

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

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

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

https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/ArrayList.java

## DEFAULT_CAPACITY

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

```java: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) | このリストの最後に、指定された要素を追加します。 |

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

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

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

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

> `E`は型パラメータ

https://programmer-life.work/java/generics-type

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

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

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

```java: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)

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


```java: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()`としたときに数が合わなくなっちゃうので
```java: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`。

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

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

```java: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`が発生する。

```java: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
ビットシフトをした値を加えることで設定している。

```java
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倍した値**が新しいキャパになるみたい。

```java: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**だから。
```java
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
```

```java: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)`の誤植なのかな？

```java: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`メソッドのときにエラーハンドリングしておけばいい気がするけども。。

```java: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`に合わせる。
って処理みたい。

理由は、謎です。

```java: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()`を使ってみる。

https://www.sejuku.net/blog/44904

## テストコード

```java: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

```text: 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

```text: 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

```text: 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


```text: 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（追記）

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

https://qiita.com/BumpeiShimada/items/522798a380dc26c50a50

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

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

```java:Main.java
...
...
long start = System.currentTimeMillis();
list.get(SIZE - 1000000);
long end = System.currentTimeMillis();
System.out.println(end - start);
```


```text: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`の方が早くなるのかも。

```java: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);
```

```text: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倍とかでも配列を作り直す手間が増えるからいい塩梅なのかも。

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

https://qiita.com/e_tyubo/items/48398391a8ef0f24c1be

# 余談

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

https://qiita.com/fukushiw/items/dade32371df476987bec