Logic Dice このページをアンテナに追加

2010-12-27

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の基本データ渡しは「参照の値渡し」なので、変数を使い回すなどを行うと、この様な問題が生じる可能性が高くなります。


これはJava APIにも記述があります。

注:可変オブジェクトをマップキーとして使用する場合は細心の注意が必要です。オブジェクトがマップ内のキーであるときに、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が活かせる問題形式が1つあります。

それはデフォルトでHashMap/Setが用意されている事です。

C++/STLのmap/setは標準ではtree構造に成っており、数多くのランダム要素を追加する場合、Hash構造に分があることがあります。


後は、ACM-ICPCではJavaチャレンジという要素もあるので、大学プロコンの参加者はある程度Javaを身につけて置くといいんじゃないかな。かな。


終わりに

どう見ても初心者のチラシの裏ですね。

お目汚し申し訳ない。

同日に書くと思われる宮川 拓さんに期待します。


次の延長戦@yoshioriさんの模様です。

*1:ぶれなんとかさん

*2:多くはC, C++, JavaC#Pythonも使えたり、場所によっては使用できる言語は増加傾向にある

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/a-hisame/20101227/1293467830
Connection: close