並列コレクションの問題を理解したい

Question

現在Java Goldの問題を解いています。
その中で並列コレクションの問題を解いているのですが、理解できない箇所があるためアドバイス頂けたらと思い質問しました。

問題は以下で、実行結果は「実行時エラー（java.util.ConcurrentModificationException）が発生する」というものです。

import java.util.*;

class Test {
  public static void main(String[] args) {
    Set<String> set = new TreeSet<String>();
    set.add("A"); set.add("B");
    Iterator<String> ite = set.iterator();
    set.add("C"); set.add("D");
    while(ite.hasNext()){
      System.out.print(ite.next() + " ");
    }
  }
}

しっくりこないところは
結論から言うと、
なぜ直接イテレータオブジェクトに詰めている訳ではないのに、
ite.next()の部分で実行時エラーが発生してしまうのかということです。

イテレータオブジェクト生成後、TreeSetオブジェクトに要素を追加し、要素の取り出しを行っているためエラーが発生する。ということはわかりました。

しかし、文字列C,Dは直接イテレータオブジェクトに詰め込んでいないし、
要素を取り出そうとしているのはsetとかでなく、イテレータオブジェクトに対してなのでなぜ影響が出るのかわかりません。そこがしっくりきていない箇所です。

ConcurrentModificationException例外は「あるスレッドがコレクションで繰り返し処理を行っている間に、別のスレッドがそのコレクションを変更する」といったときに起こるという認識ですが、
スレッドもコードに特に記述がないので、なぜ起きているのかわかっていません。

Set<String> set = new TreeSet<String>(); を
CopyOnWriteArraySet<String> set = new CopyOnWriteArraySet<String>(); に変えるとスレッドセーフとなるため例外が発生しないことも知っています。C,D追加の変更は反映されませんが。

言葉ではわかっているけどロジック的に理解できていないような感じです。
アドバイスいただけると幸いです。よろしくお願い致します。

Answer 1

イテレータオブジェクトは元になったオブジェクトのことを見ています。
具体的には「あのオブジェクトの、バージョン○○のときの○番目まで取り出した」という情報を格納しています。

元オブジェクトに改変が加わった時点で元オブジェクトは自身のバージョン番号を上げる（このバージョン番号という数値はパッケージローカールなので利用者からはアクセスできないものです）ので、イテレータは値を取り出そうとして「バージョン番号が違うじゃん!」と怒って例外を投げる、そんな仕組みです。

Comments

[k499778]

迅速な対応ありがとうございます。
ここでいう「元になったオブジェクト」とはTreeSetオブジェクトという認識で合っていますか？
イテレータオブジェクトはTreeSetオブジェクトを見ているから、直接TreeSetオブジェクトにアクセスしていないタイミングでも例外が発生するという訳ですか。でその原因は文字列C,Dを詰めたタイミングでバージョン番号が変わったから。それであると例外が発生するタイミングが要素を取り出す1回目（文字列Aを取り出す時）であることもうなづけます。

そのような理解でまちがいないでしょうか？

[yuba]

説明のご理解はその通りで間違いありません。
ただ、先ほど本文に追記したとおりでして、やはり「Gold」名乗る以上求められているのは「ソース読んでみたら確かにそうなっていた」もしくは「ソース読んでみたら回答の説明間違ってるじゃん!」です。
よろしくお願いします。

[k499778]

もちろんソースコードも実際に書きデバッグをして確かめました。
変数iteも解析しました。
しかし「set.add("C");」したタイミングの変数iteを見てもExpectedModCountは変わっておらず、
ぱっと見変わっていなかったので疑問が解決されませんでした。
yubaさんがおっしゃっているバージョン番号がどれにあたるかも現在確認してもどれに該当するかわかっていません。

[yuba]

ExpectedModCount は変わりません。これが、TreeSet本体のバージョン番号と食い違うから例外が飛ぶのです。
TreeSet本体のバージョン番号はどこにあるかというと、TreeSet.m.modCount です。

TreeSetのコンストラクタを見てください。いきなり自分自身にTreeMapを与えて初期化しています（そのTreeMapオブジェクトはmに保持されます）。TreeSetはTreeMapのラッパーでしかないのです。なのでTreeMapを見に行きます。
すると、putメソッドなんかでmodCount++しているのが見つかるはずです。

[k499778]

返答ありがとうございます。
解析してソース上でもだいたい理解することができました。

yubaさんのおっしゃる通り、TreeSetはTreeMapのラッパーとなっていますね。

public TreeSet() {
this(new TreeMap<E,Object>());
}

そしてTreeSetオブジェクトにaddしたタイミングで以下が呼ばれ、
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
TreeMapクラスのputメソッドを呼び出し、その中でmodCount++しています。
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check

root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}　…

そしてite.next()でTreeMapクラスのKeyIteratorクラスが呼ばれ、nextEntry()を呼び出し、
nextEntry()の中でmodCountとexpectedModCountが合致しない時はスローを投げています。
if (modCount != expectedModCount)
throw new ConcurrentModificationException();

そのため今回の場合、イテレータオブジェクトを生成した段階で決まる「expectedModCount」とTreeSetオブジェクトに値を詰めるたびに変更されるmodCountの値が合致せず、ConcurrentModificationException例外が発生する。

そういった流れを理解することができました。
ありがとうございました。

[k499778]

もうひとつだけ気になるのが
「ite.next()でTreeMapクラスのKeyIteratorクラスが呼ばれ」の部分です。
ここのつながりが正直理解しきれていないのですが、なぜite.next()を実行するとKeyIteratorクラスが呼ばれるのでしょうか。

もしお時間ございましたらお答えいただけると幸いです。

[swordone]

iteがそのKeyIteratorクラスのインスタンスだからでは？

[k499778]

お！

TreeMapクラスのKeyIteratorインナークラスがPrivateEntryIterator<K>抽象クラスを継承し、

final class KeyIterator extends PrivateEntryIterator<K> {
KeyIterator(Entry<K,V> first) {
super(first);
}
public K next() {
return nextEntry().key;
}
}

PrivateEntryIterator<K>抽象クラスがIterator<T>インターフェイスを実装していました。
abstract class PrivateEntryIterator<T> implements Iterator<T> {
Entry<K,V> next;
Entry<K,V> lastReturned;
int expectedModCount;
…

そのためオーバーライドしたKeyIteratorクラスのnext()の処理が走っていた訳ですね。
微々たる知識ながら流れを理解したつもりです。

swordoneさん、アドバイスいただきありがとうございます。

[yuba]

解決してよかったです。
あとソースを読んでいないのではと勝手に決めつけた非礼はお詫びさせてください。

[k499778]

yubaさん
ありがとうございました。yubaさんのおかげでスッキリ解決することができました。
いえ全く問題ないです????
ありがとうございました。

Answer 2

ConcurrentModificationException例外は「あるスレッドがコレクションで繰り返し処理を行っている間に、別のスレッドがそのコレクションを変更する」といったときに起こるという認識ですが、

この例外に関する質問はいくつかあり、よく誤解されていますが、この例外のドキュメントを見に行くと、

**たとえば、**あるスレッドがCollectionで反復処理を行っている間に、別のスレッドがそのCollectionを変更することは一般に許可されません。

とある通り、あくまで一例なのです。
例えるなら、エクセルで作った表をファックスで送るという場合(メールで送れよという突っ込みはなしで)、送るために読み込んでいる最中に「ちょっとここの行追加で」みたいなことやられると、ファックス側が「ちょ、ちょっと待って」となるわけです。

Comments

[k499778]

回答ありがとうございます。すごくわかりやすいです！笑
そういったときに起こる例外が「ConcurrentModificationException例外」なのですね！
大変参考になりました。ありがとうございます。