Java Silver合格への道 ~拡張for文の中でArryaList.removeしても例外がスローされない謎に迫る~
スポンサーリンク
こんにちは。たろすです。
Java Silverの勉強をしている中で最も納得いかなかった問題を紹介します。
黒本にはあまり詳しく解説が書かれていなかったのでぜひ見ていただければと思います。
問題
以下のプログラムを実行したときの結果を答えよ。(黒本の問題を改題)
import java.util.ArrayList; public class For1 { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ ArrayList<String> array = new ArrayList<>(); array.add("A"); array.add("B"); array.add("C"); array.add("D"); for (String s : array) { if (s.equals("C")) { array.remove(s); } else { System.out.print(s); } } } }
A.「AB」と表示される
B.「ABCD」と表示される
C.「ABD」と表示される
D.例外がスローされる
E.コンパイルエラーが起こる
解答
答えはAです。
私は訳がわかりませんでした。
拡張for文の中でArrayListの要素を操作すると例外がスローされると思っていましたから。
黒本の解説を見ても、
「3番目の要素が削除されたときに4番目の要素が3番目に繰り上がり、次に削除する要素がなくなるため繰返し処理が終了します」
とだけ。
いやいや、そこじゃないんだよ。
なんで例外にならないの?
と非常にもやもやしました。
例外がスローされない理由
実は削除した要素が最後から2番目だから例外がスローされないんです。
ちなみに1番目、2番目、最後の要素を削除すると例外がスローされます。
このときスローされる例外は「ConcurrentModificationException」です。
公式ドキュメントを読んでみる
公式ドキュメントで「ConcurrentModificationException」について調べたところ
この例外は、オブジェクトの並行変更を検出したメソッドによって、そのような変更が許可されていない場合にスローされます。
たとえば、あるスレッドがCollectionで反復処理を行っている間に、別のスレッドがそのCollectionを変更することは一般に許可されません。通常、そのような環境では、反復処理の結果は保証されません。いくつかのイテレータ(Iterator)の実装(JREが提供するすべての一般的な目的のコレクションの実装の、イテレータの実装を含む)は、その動作が検出された場合にこの例外をスローすることを選択できます。この例外をスローするイテレータは、フェイルファストイテレータと呼ばれます。イテレータは、将来の予測できない時点において予測できない動作が発生する危険を回避するために、ただちにかつ手際よく例外をスローします。
とのことです。
どうやら拡張for文の中で要素を削除するとこの例外がスローされるのが正しい挙動のようです。
ArrayListのコードを読んでみる
前提として拡張for文は内部でイテレータを使っています。
ArrayListが継承しているAbstractList
private class Itr implements Iterator<E> { int cursor = 0; int lastRet = -1; int expectedModCount = modCount; public boolean hasNext() { return cursor != size(); } public E next() { checkForComodification(); try { int i = cursor; E next = get(i); lastRet = i; cursor = i + 1; return next; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
拡張for文ではまずhasNextメソッドを実行し、戻り値がtrueならnextメソッドでarray[i]の要素を取り出します。
nextメソッドの頭でcheckForComodificationメソッドを実行しています。
modCountとexpectedModCountが異なるとConcurrentModificationExceptionがスローされます。
次にremoveメソッドのコードを見てみます。
public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; }
今回の問題の場合、引数oはnullでないのでelseブロックに入ります。
そしてArryaListのサイズ分インクリメントし、oと等しい要素があればfastRemoveメソッドを実行します。
つまり今回の場合はarray[i]がCのときにfastRemoveが実行されます。
ではfastRemoveメソッドを見ていきます。
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 }
modCountはインクリメントされて、numMovedには4-2-1で1が入ります。
numMovedが0より大きいので、System.arraycopyが実行され、array[3]に入っていたDがarray[2]にコピーされます。
そしてarray[3]にnullを入れて戻ります。
このときiの位置はまだ動いていません。
このあと拡張for文の処理でhasNextメソッドを実行します。
すると
cursor != size()
がtrueになるのでnextメソッドを実行せずに終了します(cursor=i+1=3、size()の戻り値も3)。
逆に削除する要素が最後から2番目の要素でない場合、対象の要素を削除した後でこれがfalseになるのでnextメソッドが呼ばれcheckForComodificationが実行されます。
例えば一番最後の要素を削除した場合はこのようになります(cursor=i+1=4、size()の戻り値は3)。
modCountはfastRemoveメソッドの中でインクリメントされてexpectedModCountとは異なる値になっているので、ConcurrentModificationExceptionがスローされます。