Effective Javaを読むチャレンジ-項目9-

項目9 equalsをオーバーライドする時は、常にhashCodeをオーバーライドする

なぜこうしなければならないかというと、HashMap、HashSet、HashTableなど、ハッシュに基づくコレクションが適切に機能しないからです。

ハッシュとは

ハッシュは、キー値にハッシュコードという正の整数を割り当てて、キー探索の際の高速化を図るための仕組みです。Javaでいうとjava.util.HashTableが一番仕組みが単純なので、HashTableを例にハッシュの使い方を見てみます。

hashtable

かなり大雑把にいうと、データをハッシュ表という1次元配列に格納しているだけです。

配列の添え字となる数値は、ハッシュ関数というもので計算しています。ハッシュ関数についてはアルゴリズムの知識がいるので割愛します。大事なところは、データが何かのルールでハッシュ表に分配されるという点と、データ探索時にはキーのハッシュ値をデータ格納時と同じハッシュ関数で割り出して高速にデータの取りだしが行えるという点です。

注意して欲しいのは、ハッシュ関数によっては同じハッシュ値のエントリリストに複数のデータが格納されてしまうことです。これでは結局たくさんのデータを検索する必要があるので、効率がよくありません。なるべくエントリリストに偏りが起きないよう均等に分配できるハッシュ関数が理想かと思います。

ではhashCodeメソッドは何をするメソッドなのかというと、HashTableなどで使うハッシュ関数の計算に使うためのオブジェクトごとのハッシュ値を生成するために使われています。

ハッシュとhashCodeの理解がこの項目を読む前提です。

hashCodeの一般契約

java.lang.ObjectのhashCodeメソッドのマニュアルに一般契約が書かれています。簡単にすると以下のようになります。

  • 1回のアプリケーション実行の間はhashCodeは一貫して同じ整数を返さなければならない。2回目の実行で違う整数となってもよい。
  • equalsで等しくなる2つのオブジェクトはhashCodeの結果は同じ整数にならなければならない。
  • equalsで等しくならない2つのオブジェクトのhashCodeの結果は同じでも違っててもよい。ただし、違う整数を返す方がパフォーマンスによい。

2番目は当然そうならないといけませんね。上のHashTableの説明でいうと、ハッシュ値が違えばエントリリストの中に同じキーを持つオブジェクトはありませんから、HashTableは検索結果を返せません。

3番目も上の説明のとおり、同じハッシュ値に属するエントリリストが大量になるということはそれだけ検索に時間がかかるということです。

equalsとhashCodeをセットでオーバーライドする理由

ここまでの説明でもうお分かりかと思いますが、この項目で言いたいのは、hashCodeの一般契約の2番目のことです。

equalsだけオーバーライドしてhashCodeがオーバーライドされない場合、値クラスのオブジェクトはjava.lang.ObjectのhashCodeメソッドを使用することになります。

ObjectのhashCodeはオブジェクトの参照が異なると違うハッシュ値を生成します。これが何を意味しているかというと、格納したデータのキーオブジェクト自身をキーとて検索しない限り、HashTableからデータは取得できなくなるということです。そんな検索APIがあったら使い物にならないのはすぐ分かりますね。

本書では、なるべくエントリが均等となるようなhashCode生成の処方箋を考えてくれています。書いていることはそれほど難しくないですが、本当に最適かどうかは分かりません。どうやって検証すればよいのか・・・

あと、コストのかかるハッシュ値生成には遅延初期化を使ってもよいのでは、と提案していますが、これは後の項目に出るのでそのときということで。

広告
  • LINEで送る