HashMap/Setにまつわる2つの事
この記事はJava Advent Calendar(http://atnd.org/events/11000)の延長戦(28日)です。
prev: http://d.hatena.ne.jp/cactusman/20101227
※以下の2つの記事にはほとんど関連はありません。
ミュータブルな値を持ったHashデータ構造
Scalaスケーラブルプログラミング(コップ本)に書いてあって、名古屋Scala勉強会でも議論したことです。
常識だとぐるぐるの人*1には言われましたが、軽くEffective Javaを見直して見ても見あたらなかったので改めて書いてみます。
もし書いてあったらゴメンナサイ。
さて、以下のコードを見てみましょう。
import java.awt.Point;
import java.util.HashMap;
import java.util.Map;
// 途中略
public static void main(String[] args) {
Map<Point, String> map = new HashMap<Point, String>();
map.put(new Point(0, 0), "origin");
System.out.printf("(0, 0) is %s%n", map.get(new Point(0, 0)));
}
// 終端略このコードを実行すると、"(0, 0) is origin"という結果が得られます。
さて、このmap全体を並行移動したいと思いました。
そこで、全てのkeyの値を更新します。
public static void main(String[] args) {
Map<Point, String> map = new HashMap<Point, String>();
map.put(new Point(0, 0), "origin");
// key points translate
for(Point p : map.keySet()) {
p.translate(10, 10);
}
System.out.printf("(0, 0) is %s%n", map.get(new Point(0, 0)));
System.out.printf("(10, 10) is %s%n", map.get(new Point(10, 10)));
}methodで原点を(10, 10)ほど並行移動させて見ました。
さて、この結果を見てみましょう。
(0, 0) is null
(10, 10) is null
あれれ？
どういうことでしょうか？
よく考えれば分かるのですが、hash値は格納する時にそのオブジェクトの物を利用します。
ここでは、Point(0, 0)の時のhash値を元に格納先(=A)を決めているわけです。
しかし、このPoint(0, 0)の値が変更されてしまいました。
このときのhash値は、普通元のhash値とは異なる結果となります。
さて、実際の検索時にはまずはkeyのhash値を取り、そのhash値が格納されたグループのみを探索することで、効率の良い探索を実現しています。
ここではnew Point(10, 10)として格納先(=B)を見ます。
本来put(new Point(10, 10), "value")として格納された要素はBに入れられるのですが、keyの要素が書き換えられただけなので、そのPoint(10, 10)は元々の格納先Aに入ったままです。
その結果、Aに入っているPoint(10, 10)はnew Point(10, 10)で探索されずに、結果として発見が出来なくなるのです。
当然、Point(0, 0)でも発見できなくなるので、そのデータはまさに死に体としてMapの中に転がっている訳です。
(たまたまA = Bとなったときには動作するかもしれませんが……、その場合は手強いバグと成る事は想像に難くありません)
今回はかなり故意的に問題を起こしていますが、Javaの基本データ渡しは「参照の値渡し」なので、変数を使い回すなどを行うと、この様な問題が生じる可能性が高くなります。
注:可変オブジェクトをマップキーとして使用する場合は細心の注意が必要です。オブジェクトがマップ内のキーであるときに、equals の比較に影響を与える方法でオブジェクトの値が変更された場合、マップの動作は保証されません。この禁止事項の特殊な例として、マップがそれ自身をキーとして持つことができないことが挙げられます。マップがそれ自身を値として持つことは許可されますが、その場合は細心の注意が必要です。そのようなマップでは equals メソッドおよび hashCode メソッドの動作は保証されません。
http://java.sun.com/javase/ja/6/docs/ja/api/java/util/Map.html
この問題の回避策はKeyに不変(Immutable)オブジェクトを用いる事が最も簡単です。
そうで無い場合……ラッパーを書くのも大変です。
というのも、正しくhashCodeとequalsをオーバーライドする必要があるからです。
ああ、case classの素晴らしさが本当によく分かる……
競技プログラミングの選択肢としてのメリット
さてさて、昨今Javaを使わなくなってきている自分ですが、Javaと向き合う時があります。
それが競技プログラミング(ex, ACM-ICPC, TopCoder, Codeforces)です。
使用できる言語が限られている*2競技プログラミングでは、使える言語の中で自分が最も得意な物を用いて素早く、（答えを出すために）正確にプログラミングをする必要があります。
ちなみに、C, C++, Javaという選択肢がある場合、大半の人はC++を使います。
実行時間制限という壁、タイプ文字数の多さから、Javaは選択されづらいのです。
しかしながら、Javaが活かせる問題形式が１つあります。
それはデフォルトでHashMap/Setが用意されている事です。
C++/STLのmap/setは標準ではtree構造に成っており、数多くのランダム要素を追加する場合、Hash構造に分があることがあります。
後は、ACM-ICPCではJavaチャレンジという要素もあるので、大学プロコンの参加者はある程度Javaを身につけて置くといいんじゃないかな。かな。
