人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

[Java]HashSetの中身を直接書き換えると、containsが効かなくなる。
http://d.hatena.ne.jp/snuffkin/20080501/1209663468
これは仕様ですか?それとも使い方の問題ですか?

●質問者: afternoontea
●カテゴリ:コンピュータ
✍キーワード:Java 仕様です
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● quintia
●60ポイント

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

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


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 を変化させない範囲内でなければならない、ということになります。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ