Effective Java 第 2 版:第 3 章 項目 9

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

今回は、Object.hashCode の一般契約についての話。

hashCode は、あるオブジェクトのハッシュ値を返すメソッドである。

java.util.HashMap のようなコレクションは、hashCode によって得られるハッシュ値をキーとして、オブジェクトを格納している。

hashCode が従うべき一般契約

hashCode は以下の契約を守らなければならない。

  • あるアプリケーション実行中において、同じオブジェクトに対する hashCode の呼び出しは、常に同じ整数を返す
  • あるオブジェクト a, b に対して、a.equals(b) == true であれば、a.hashCode() == b.hashCode() である

2 番目の項目について、もし a.equals(b) == false であるとき、必ずしも a.hashCode() != b.hashCode() でなくてもよい。 つまり、論理的に等価でない 2 個のオブジェクトが偶然同じハッシュ値を返すことは許されている。 しかし、コレクションに対する操作のパフォーマンスを考慮すると、等価でないオブジェクト同士のハッシュ値は衝突させないことが望ましい。

hashCode の契約では equals が用いられている。 そのため、前項で触れた equals をオーバーライドしたとき、hashCode も必ずオーバーライドしなければならない。 例えば、equals がオーバーライドされているにも関わらず、hashCode がオーバーライドされていないときを考える。 このとき、equals によって論理的に等価と見なされる 2 個のオブジェクトは異なるハッシュ値を返しうる。 よって、HashMap などを用いる際に、実際は論理的に等価な 2 個のオブジェクトが、別のものとしてコレクションに格納されてしまう。

hashCode の望ましい処理

異なるオブジェクトからは異なるハッシュ値を生成するのが、望ましい hashCode である。 契約を守り、できるだけ偏りのないハッシュ値を生成する hashCode は、以下のような処理にするとよい。

  1. int result に何らかの定数を代入
  2. オブジェクトが持つ、意味のある各フィールド f に対して、以下 1 から 7 の方法でハッシュ値 int c を計算
    1. boolean なら f ? 0 : 1
    2. byte, char, short, int なら (int)f
    3. long なら (int)(f ^ (f >>> 32))
    4. float なら Float.floatToIntBits(f)
    5. double なら Double.doubleToLongBits(f) のあと long と同様の処理
    6. オブジェクト参照なら、そのオブジェクトに対して hashCode 呼び出し。null なら 0
    7. 配列なら、各要素に対して、対応する上記の処理のいずれか
    8. result = 31 * result + c を計算
  3. result をハッシュ値として返却

2-3 は、実際には Long.valueOf(f).hashCode() のように書くことで、ハッシュ値を得られる。

2-8 で 31 を乗じているのは、JVM によってシフト演算と減算に最適化されることを狙っている。

ハッシュ値の衝突を極力避けるため、ハッシュ値の計算は意味のあるフィールド全てについておこなうこと。

その他

  • ハッシュ値のキャッシュ
    • 必ずハッシュに基づいたコレクションのキーとして使われるオブジェクトでは有効

参考文献

EFFECTIVE JAVA 第2版 (The Java Series)

EFFECTIVE JAVA 第2版 (The Java Series)