JavaにおけるequalsとhashCode - hashCodeメソッドを理解する

hashCodeとは

equalsメソッドを実装した場合は、hashCodeメソッドも実装する必要があります。 なお、hashCodeメソッドは以下のルールに従って実装します。

  • equalsメソッドの結果がtrueとなるオブジェクトは、hashCodeメソッド呼び出しの結果同じ値を返す必要がある。 (equalsがfalseとなるオブジェクトが同じhashCodeの結果を返すことは、かまわない)

Userクラスにおいて、IDの値で同値性を判定するequalsメソッドを実装した場合、hashCode メソッドは、一つの例としては、下記のように実装します。

例1

	/**
	 * ハッシュコードを返します。
	 *
	 * @return このクラスのインスタンスのハッシュ値
	 */
	public int hashCode() {

		return this.id;
	}
						

equalsメソッドでは、IDの値を元に同値性を判定しているので、IDの値が等しい、つまり、 equalsメソッドがtrueを返すオブジェクトのhashCodeメソッドは、上記の実装により同じ値を返すことになり、 上記hashCodeメソッドの処理は上記のルールに対して妥当であると言えます。

例2

	/**
	 * ハッシュコードを返します。
	 * 
	 * @return このクラスのインスタンスのハッシュ値
	 */
	public int hashCode() {

		return 0;
	}
						

上記hashCodeメソッドの処理も、実は妥当であるといえます。 全てのオブジェクトのhashCodeは0を返す。つまり、equalsメソッドがtrueになるオブジェクトは 全てhashCodeの戻り値として、同じ値(0)を返します。 equalsメソッドがtrueにならない(equalsメソッドの呼び出しの結果がfalseとなる)オブジェクトが 同じhashCodeメソッドを返すことは問題ないので、 上記実装もまた、hashCode実装のルールに照らした場合問題ないとみなされます。

ただし、例2の実装は、推奨できるものではありません。 hashCodeを実装する場合は、少なくとも例1のように実装して下さい。

hashCodeを正しく実装しなかった場合

ハッシュアルゴリズムを使用するクラス(HashMap、HashSet等)のインスタンスに、hashCodeを正しく実装しないオブジェクト追加した場合、期待した動作を得られません。

ハッシュアルゴリズムとは

オブジェクトの格納、検索を行う際に、あらかじめハッシュ値を計算し、得られたハッシュ値に 基づいてオブジェクトの格納、検索を行うことで、処理を効率化するアルゴリズムです。

ハッシュアルゴリズムを理解するには、ArrayListとHashSetの動作の違いを比較するとよいでしょう。

ArrayListとHashSetはともにCollectionインターフェースを実装するクラスですが、以下の ような動作の違いがあります。
(HashSetはハッシュアルゴリズムを実装している。)

ArrayListの場合

ArrayListのイメージ

ArrayListは追加された要素を1列のリストに格納して保持します。 格納されている要素を取り出すときは、リストの先頭から順番にオブジェクトのequalsメソッド を呼び出して、equalsメソッド呼び出しの結果がtrueとなる要素を戻り値として返します。

⇒ リストの要素の数が膨大で、かつ取り出したい要素がリストの後方に存在した場合、 検索効率が極端に悪化する可能性がある。

HashSetの場合

HashSetは追加された要素を以下の手順に従って格納、検索します。

HashSetのイメージ
  1. 追加対象のオブジェクトのhashCodeメソッドを呼び出します。
  2. hashCodeメソッドの戻り値ごとにオブジェクトを「部屋」(HashSetクラスの実装上の 用語はBucket)に分類し、hashCodeの部屋番号が付けられた「部屋」に 対象オブジェクトを格納します。
  3. 要素を取り出す場合は、hashCodeの値を元に、そのhashCodeの値を 部屋番号としてもつ「部屋」にまず対象となるオブジェクトを探しにいきます。
  4. 手順3で探し当てた「部屋」に格納されているオブジェクトに対して順番にequalsメソッドを 呼び出し、equalsメソッド呼び出しの結果がtrueとなる要素を戻り値として返す。

あらかじめ要素をhashCodeに基づく「部屋」に分類して保持しているため、 オブジェクト同士を比較する際、限られた数のオブジェクトを比較すればよく、検索 効率が向上します。

hashCodeが正しく実装されていない場合、同値のオブジェクトであるにもかかわらず 異なる部屋に対象となるオブジェクトを探しに行ってしまうため、対象となるオブジェクト が見つからないという事態が発生する可能性があります。

hashCodeが0を返すように実装されている場合、実質部屋番号0の「部屋」に全ての オブジェクトが格納されることになり、アルゴリズムとしてはArrayListに要素を追加する 同じとなり、ハッシュアルゴリズムの利点が得られません。