[Java]HashSetの中身を直接書き換えると、containsが効かなくなる。

http://d.hatena.ne.jp/snuffkin/20080501/1209663468
これは仕様ですか?それとも使い方の問題ですか?

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2008/05/02 03:53:17
  • 終了:2008/05/09 03:55:04

回答(1件)

id:quintia No.1

quintia回答回数558ベストアンサー獲得回数672008/05/02 11:26:16

ポイント60pt

仕様でもあり、使い方の問題でもあります。

「連想配列」や「要素が重複しない集合」を実装するのに、なぜハッシュを使うといいのか? どのようにハッシュを使うのか? を理解するところから始めましょう。


1~10000 の範囲の乱数を順次発生させて重複しない集合を作りたい。重複は嫌だが乱数の発生は当然重複がありうる。

という問題を仮定します。

発生した数を単純に配列に格納すると、n番目の乱数を発生させた時に、重複チェックするのに n-1個の要素を比較する必要があります。

(1000個の数の集合が集まるまでに最低で499500回比較しないといけません)


そこでハッシュの登場です。

JavaではObject#hasCodeでハッシュ値を計算しますが、今は数そのものをハッシュ値と見なしましょう。

10個の配列を用意して、ハッシュ値の1桁目を見て、格納する配列を振り分けるという方法を採ります。

理想的には10個の配列に均等に数が入っていって、1000個の数の集合が集まる時にはそれぞれの配列に100個ぐらいの数が入っています(もちろんそう理想的にはいきませんが)。

n番目の乱数を発生させた時に、その数に対応する配列に入っている要素数は(理想的には)\frac{n-1}{10}です。

ハッシュ値の計算が十分に高速ならば、という仮定付きで重複のチェックにかかる比較を1/10にできます。それが利点です。


さて、いったん格納した数字を書き換えてしまったらどうなるでしょうか?

先の例えだと「1桁目が5である数を格納している配列」の中のある要素を書き換えて、1桁目を別のものにしてしまうことにあたります。

105→106 にしたとしましょう。

その後 106 が生成されたなら、当然「1桁目が6である数を格納している配列」を探索します。そして「その配列の中に 106 が無ければ集合全体に 106 はない」と判断してしまいます(ついでにいうと106が重複して入ってしまいます!)。

これが「HashSetの中身を直接書き換えると、containsが効かなくなる」理由です。


JavaDoc の java.util.Set にはこうあります(古いバージョンから引いているのはわざとです)。

注: 可変オブジェクトがセット要素として使用される場合は、細心の注意が必要です。オブジェクトがセット内の要素であるうちに equals 比較に影響する方式でその値が変更された場合、セットの動作は保証されません。この禁止事項の特例により、セットがそれ自体を要素として持つことは許可されません。

http://java.sun.com/j2se/1.3/ja/docs/ja/api/java/util/Set.html

また、Object#hashCode() にはこうあります。

equals(Object) メソッドで 2 つのオブジェクトが等価とされた場合、どちらのオブジェクトで hashCode メソッドを呼び出しても結果は同じ整数値にならなければならない

http://java.sun.com/j2se/1.3/ja/docs/ja/api/java/lang/Object.htm...()

この2つの制約から、HashSet, HashMap, Hashtable に格納したインスタンスの内容を変更していいのは、equals 比較や hashCode を変化させない範囲内でなければならない、ということになります。

  • id:afternoontea
    終了ボタンを押したらポイント配分の画面が出ないでいきなり終わってしまった… orz
    いるかを付けたかったのに…

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません