技術者ブログ

はじめに

Scutumの開発ではJavaを使っていますが、以前HashMapの使い方を致命的に間違えてしまい、ひどいことになった経験が2度あります。今回はその内容について簡単に紹介します。

1. 消える要素

Mapに入れたはずの要素がその後忽然と姿を消した事象です。要点のみの再現コードは以下になります。

Map db = new HashMap();
Map key = new HashMap();

key.put( "aaa", "bbb" );
db.put( key, "ccc" );
System.out.println( db.get( key ) ); //ccc

key.put( "ddd", "eee" );
System.out.println( db.get( key ) ); //null

putした後、一度もremove()をコールしていないので、db.get(key)にはcccが返ってきてほしい心境だったのですが、最後の行ではnullが返ってきます(実行環境によっては、もしかしたらcccが返ってくるかもしれません)。

原因はputの後にkeyを変更してしまい、それによってkeyのハッシュ値が変わってしまっていることです。

キーとして使っているオブジェクトのハッシュ値が変わってしまうと、HashMap内部のテーブルにおいてハッシュ値の変更前とは別のbinに問い合わせを行う確率が高くなります。この場合には当然、要素が見つからないことになります。

ということで、「ハッシュ値が変わっていく可能性のあるオブジェクトはHashMapのキーに使ってはいけないし、同じくHashSetに入れてはいけない」ということです。コンピュータ・サイエンスでハッシュ検索を学んでいる人には「そりゃそうなるよね...」と思われる事例です。

状態が変化していくようなオブジェクトはハッシュ値が変わっていく可能性が高いので、そのようなオブジェクトは要注意です。

2. 重い検索

Mapに対する検索(get)が異常に重くなった事象です。デバッガ上で再現させMapの中身を見てみると、ハッシュの衝突が大量に発生していました。要点のみの再現コードは以下になります。

{
Map key = new HashMap();
key.put( "AAA", 0 );
key.put( "CCC", 1 );
System.out.println( key.hashCode() ); //131075
}
{
Map key = new HashMap();
key.put( "AAA", 1 );
key.put( "CCC", 0 );
System.out.println( key.hashCode() ); //131075
}

上と下で、keyはそれぞれ似ているけれども異なる状態になっています。しかしハッシュ値はどちらも同じく131075になっています。このようなハッシュ値の衝突が起こっているものを次々にHashMapのキーとしてputしていくと、非常に検索が遅くなります。

この例ではたった2つですが、実際に我々が体験した状況では、数千ほどの要素でこの現象(ハッシュ値の衝突)が発生し、観測できるレベルのパフォーマンスの劣化が発生しました。

上の1で見たようにそもそもHashMapのキーにHashMapを使うこと自体が良くないのですが、今回は1とは違い、putの後に内容を変えたりはしていません。Mapに格納されているデータは似てはいますが異なっており、この状態でハッシュ値が衝突すると予測することは難しいでしょう。何がまずいのでしょうか？

問題が起きた場面では殆どの要素が値として0か1を持っていたのですが、これがJavaのHashMapの実装のハッシュ値の実装と非常に相性が悪いことがわかりました。

return Objects.hashCode(key) ^ Objects.hashCode(value);

Mapのハッシュ値は、各エントリについて上記のようにkeyのハッシュ値とvalueのハッシュ値のxorを取ったものを、それぞれ足した値になります。そのため、例えばvalue側の値が0の場合、xor演算に対して何も変化を与えず、keyの値のハッシュ値がそのままそのエントリのハッシュ値になります。また、valueの値が1の場合は末尾の1ビットのみしか変化しません。つまり値が0や1だとハッシュ値に及ぼす影響が非常に小さくなるわけです。

そのため複数のMapインスタンスが「keyの組み合わせは全て同じで、valueはそれぞれ異なる。valueは、0か1が多い」のような場合、ハッシュ値の衝突が起こりやすくなります。(0と1以外でも、小さい数値はハッシュ値に及ぼす影響が少ないので、同じような問題が起こる可能性が高くなります。)

我々のケースでは特徴ベクトルの各データインスタンスをMapで表現していました。全データ、特徴の名前とその値をStringとIntegerで入れており、多くのベクトルはkeyがすべて同じであり、値は0や1が殆どだったためにハッシュ値の衝突が多く発生し、パフォーマンスの劣化が起こっていたのです。

対策は可能なのか

2のケースでは、(HashMapのキーにHashMapを使うことの是非はさておくと)事前にJavaのHashMapのハッシュ値がどのように計算されるのかまで熟知していないと、ハッシュ値の衝突を予測するのは難しいでしょう。そのため実際にランタイムにおいてハッシュの衝突が多く発生した際に発見する(もし発見されたら、理由を調べて対策する）という事後的なアプローチになりそうです。

あるHashMapインスタンスについて、ハッシュの衝突が起こっているのかどうかを調べる方法については、後日別エントリにまとめたいと思います。