[Java]新人向けにjava.util.ArrayListで発生するConcurrentModificationExceptionについて解説


# はじめに
* [Stylez Advent Calendar 2016](http://qiita.com/advent-calendar/2016/stylez)の15日目です。
* 弊社では、新人向け（新人というよりはJava初心者向け）に読書会形式で勉強会を行っています。細かい内容は以下を参考にしてください。
	* [javaプログラマー向け学習のための本（新人から５年めくらいまで）を考えてみた](http://qiita.com/bonybeat/items/a7ed6cc96d256570ac74)
	* [新人向けにJava関連の読書会をはじめた話](http://qiita.com/ukitiyan/items/d5bac86dc641a8795259)
	* [[Java]新人向けにJavaBeansの直列化やフィールド・プロパティの謎をPOJOとの違いを交えて解説](http://qiita.com/ukitiyan/items/3b7f1ea7eb3d208ed5fe)
* 自分は上記取り組みの講師をしてる訳ですが、世に出した方が良さそうな質問をよく受けるのでそんな質問の回答を記事にしてます。
* 今回は同取り組みで行った[Java Programmer, Silver SE 8](http://www.oracle.com/jp/education/certification/jse8-2489021-ja.html)の資格講座中で受けた`ConcurrentModificationException`に関連する質問についてです。

# シングルスレッドでも発生するConcurrentModificationException
* アンスレッドセーフな`java.util.ArrayList`インスタンスが、別スレッドから変更されると`java.util.ConcurrentModificationException`が発生するのは割りと知られた話ですがシングルスレッドな処理でも発生します。
* その手の問題が模擬試験に諸に出題されるということで質問を受けました。
* ということで、シングルスレッドでも発生する`ConcurrentModificationException`についてです。
* 内容としては、以下の場合はExceptionスローされないけど。

```java:DenaiConcurrentModificationException.java
public static void main(String[] args) {
	List<String> list = new ArrayList<String>();
	
	list.add("A");
	list.add("B");
	list.add("C");
	list.add("D");
	
	for (String str : list) {
		if ("C".equals(str)) {
			list.remove(str);
		} else {
			System.out.println(str);
		}
	}
}

```

* この場合は`ConcurrentModificationException`がスローされるという内容。


```java:DeruConcurrentModificationException.java
public static void main(String[] args) {
	List<String> list = new ArrayList<String>();
	
	list.add("A");
	list.add("B");
	list.add("C");
	list.add("D");
	list.add("E");
	
	for (String str : list) {
		if ("C".equals(str)) {
			list.remove(str);
		} else {
			System.out.println(str);
		}
	}
}
```

## どういう時にConcurrentModificationExceptionが発生しますか？
* 出題のされ方としては、上記どちらかのコードが記載され、その結果はどうなるか？といった内容になるとのこと。
* 観点は`ConcurrentModificationException`がスローされるか、されないか。になって、ざっくりとした試験対策的にはlistの最後から2番目 or 最後の要素をremoveする場合はスロー「されない」し、それ以外は「される」となります。
* 上記だけだとあれなので、一応docとコードを見ておきましょう。

## Java 8 SE ConcurrentModificationExceptionドキュメント
* [クラスConcurrentModificationException](https://docs.oracle.com/javase/jp/8/docs/api/java/util/ConcurrentModificationException.html)

```
この例外は、オブジェクトの並行変更を検出したメソッドによって、そのような変更が許可されていない場合にスローされます。
たとえば、あるスレッドがCollectionで反復処理を行っている間に、別のスレッドがそのCollectionを変更することは一般に許可されません。
通常、そのような環境では、反復処理の結果は保証されません。
いくつかのイテレータ(Iterator)の実装(JREが提供するすべての一般的な目的のコレクションの実装の、イテレータの実装を含む)は、
その動作が検出された場合にこの例外をスローすることを選択できます。
この例外をスローするイテレータは、フェイルファスト・イテレータと呼ばれます。
イテレータは、将来の予測できない時点において予測できない動作が発生する危険を回避するために、ただちにかつ手際よく例外をスローします。
```

* 要するに反復処理中に別のスレッドからの変更を検知したらスローするといった内容です。
* 文中にある「フェイルファスト・イテレータ」は、早く失敗しろという経営学的？な意味ではなくて、想定外の変更の可能性があるならば即座に例外を発生して処理を中断するイテレータといった意味です。
* シングルスレッド時のExceptionについては、ここでは触れてないのでもう少し読み進めます。

```
この例外は、オブジェクトが別のスレッドによって並行して更新されていないことを必ずしも示しているわけではありません。
単一のスレッドが、オブジェクトの規約に違反する一連のメソッドを発行した場合、オブジェクトはこの例外をスローします。
たとえば、フェイルファスト・イテレータを持つコレクションの反復処理を行いながら、スレッドがコレクションを直接修正する場合、
イテレータはこの例外をスローします。
```

* まず、[java.util.ArrayList](https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayList.html)はフェイルファスト・イテレータです。
* で、反復処理を行いながら、スレッドがコレクションを直接修正する場合、必ず`ConcurrentModificationException`がスローされるされるらしいです。
* でも、発生しない場合もある...みたいなので、実装も見てみましょう。

# java.util.ArrayListの実装を見てみる
* まず、拡張forループは内部でイテレータを使っているのが分かります。

```java:java
/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {}
```

* で、カーソルが移動する度にexpectedModCountとmodCountに差異があればConcurrentModificationExceptionをスローしてます。 プロパティの役割は名前から察してください。

```java:java
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}
```

* 更に読み進めると、`remove`でmodCountをインクリメントしていて、お陰で`ConcurrentModificationException`が発生していることが分かります。

```java:java
/*
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 */
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}
```

* `System.arraycopy(elementData, index+1, elementData, index, numMoved);`に着目すると、C要素を消す場合以下のように後ろの要素を繰り上げてることが分かります。

![skitch.3.png](https://qiita-image-store.s3.amazonaws.com/0/39596/5930fc1a-5795-b0da-8360-f5fd57daab12.png "skitch.3.png")
![skitch.4.png](https://qiita-image-store.s3.amazonaws.com/0/39596/8c5ea410-a68a-bfef-033a-9dc8adbb5d5f.png "skitch.4.png")

* 上記の図の通り、要素が繰り上がってカーソルは変わらないので、`list.remove("C")`の次は要素3が処理されます。前段は3が存在しないので、処理はそのまま終わって、後段は処理が継続され`checkForComodification`が実行され、ConcurrentModificationExceptionがスローされるわけです。

# まとめ
* コピペでつらつら書きましたが、実装見てデバッグすれば分かるのです。
* 資格講座中も実際にデバッグして、回答を導き出したのでした。。