【Effective Java】項目９：equals をオーバーライドする時は、常に hashCode をオーバーライドする

equals をオーバーライドする時は、hashCode メソッドを必ずオーバーライドしなければならない。

オーバーライドしない場合、Object.hashCode の一般契約を破ることになり、HashMap、HashSet、HashTable など、hashCode の一般契約に基づくコレクションが適切に機能しない。

Object.hashCode の一般契約

Object.hashCode の一般契約は以下の通り。

hashCode メソッドの値は、equals で利用する個々のプロパティが変更されない限り、同一アプリケーション実行で同じ値を返す必要がある。
- なお、この値は別のアプリケーション実行に対しては首尾一貫する必要はない
２つのオブジェクトに対する equals による比較が等しければ、２つのオブジェクトの hashCode 呼び出しは同じ整数結果を返さなければならない。
２つのオブジェクトに対する equals による比較が等しくなければ、２つのオブジェクトの hashCode 呼び出しの整数結果が異なる必要はない。
- しかし、equals で等しくないオブジェクトに同じ整数結果を返すことはハッシュテーブルのパフォーマンスを大幅に低下させることを覚えておく。

hashCode のオーバーライドを忘れた場合

hashCode のオーバーライドを忘れると２つめの「等しいオブジェクトは同じ hashCode 値を持たなければならない」という一般契約を破ることになってしまう。

たとえば次の PhoneNumber クラスは項目８のやり方に従って equals が書かれている。

public class PhoneNumber {
    private final short areaCode;
    private final short prefix;
    private final short lineNumber;

    public PhoneNumber(int areaCode, int prefix, int lineNumber) {
        rangeCheck(areaCode, 999, "areaCode");
        rangeCheck(prefix, 999, "prefix");
        rangeCheck(lineNumber, 9999, "line number");
        this.areaCode = (short) areaCode;
        this.prefix = (short) prefix;
        this.lineNumber = (short) lineNumber;
    }

    private static void rangeCheck(int arg, int max, String name) {
        if (arg < 0 || max < arg) {
            throw new IllegalArgumentException(name + ": " + arg);
        }
    }

    @Override
    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof PhoneNumber))
            return false;

        PhoneNumber phoneNumber = (PhoneNumber) o;
        return phoneNumber.lineNumber == this.lineNumber
                && phoneNumber.prefix == prefix
                && phoneNumber.areaCode == areaCode;
    }

    // hashCode がない！
}

このクラスを以下のように HashMap で利用すると意図しない事象が発生する。

Map<PhoneNumber, String> m = new HashMap<PhoneNumber, String>();
m.put(new PhoneNumber(707, 867, 5309), "Jenny");
m.get(new PhoneNumber(707, 867, 5309)); // => null

最後の行は、2行目に与えたオブジェクトが返されることを期待しているが、そうはならない。 hashCode がオーバーライドされていないため、３行目の put は２行目のオブジェクトが保存されたバケットとは異なるバケットを検索するためである。

もし、運良く同じバケットで検索を始めても、HashMap の実装はハッシュコードが一致しないオブジェクトは同一だと見なさず、equals 比較を行わないのでほとんどの場合 null が返ることになる。

hashCode をオーバーライドする

上記のコードの問題は hashCode をオーバーライドすると解決する。極端な話、以下の様な hashCode を実装すれば HashMap は理論上は機能するようになる。

@Override
public int hashCode() {
    return 42;
}

ただし、このハッシュコードでは、すべてのオブジェクトが HashMap 内の同一バケットに存在し、同一バケット内は LinkedList に対する検索になる。そのため、パフォーマンスが著しく悪化し、実質機能しないとの同様である。

そこで、等しくないオブジェクトに対して、適度に等しくない値を生成するハッシュ関数でオーバーライドするべきである。理想的には等しくないいかなるインスタンスに対しても、すべて異なるハッシュ値を生成する関数を用いるべきだが、これはかなりの困難なので、適度に近似する関数を用いる。

以下は Java でよく用いられるハッシュ関数の定義である。

何らかのゼロでない定数、例えば 17 を result という int 変数に保存する
オブジェクト内の equals で考慮されるフィールドに対して以下のことを行う
- そのフィールドに対する int c を計算する。
  - boolean ならば int c = field f? 0: 1 を計算する
  - byte, char, short, int ならば int c = (int) field を計算する
  - float ならば int c = (int) (field ^ (f >>> 32)) を計算する
  - double ならば int c = Double.doublToLongBits(field) を計算し、long を (int) にキャストする
  - オブジェクト参照で、equals 内でフィールドを equals によって比較しているならば再帰的に hashCode を呼び出す。フィールドが null なら 0 にする。
  - 配列ならば各要素を別々のフィールドとして取り扱い、再帰的にこれらの規則を適用して int c を計算する
- 上記で計算した c を result = 31 * result + c; として評価する
result を返す
等しいインスタンスが等しいハッシュコードを持つかどうかを自問し、単体テストを書く

実際に PhoneNumber に hashCode を実装すると以下の様になる。

@Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + areaCode;
        result = 31 * result + prefix;
        result = 31 * result + lineNumber;
        return result;
    }

ハッシュコード計算の詳細

ゼロでない初期値（この場合は１７）を利用する理由

初期値をゼロとすると、異なる数のフィールドを持つオブジェクトで、それらのフィールドがすべてがゼロの場合、同一の hashCode の値０を持つことになる。異なる数のフィールドを持つ場合、クラスが異なるためオブジェクトは異なるはずである。そのため、同じ値０となるのは都合が悪い。

結果の乗算を行う理由

ステップ 2b の乗算によってハッシュ値はフィールドの順序に依存するようになり、同じようなフィールド値を複数持つオブジェクトの衝突する可能性が減る。たとえば、String のハッシュコード計算でこの乗算が省略されていたら、アナグラムの String はすべて同じハッシュコードを持つことになる。

31の理由

乗数 31 は奇数の素数なので選ばれている。偶数を選んだ場合、乗算がオーバーフローすると情報が失われる。また、31 は 31 * i = (i << 5) - i と最適化できるためである。

hashCode の最適化

何度も hashCode が呼び出される場合で、クラスが不変であることが保証されている場合、ハッシュコードをキャッシュすることが可能である。最初に hashCode が呼び出された場合に遅延初期化（項目７１）することを選択してもよいが、ほとんど利点はない。

パフォーマンスを向上させるためにハッシュコードの計算から意味のある部分を排除してはならない。実際、リリース1.2 よりも前の String のハッシュ計算は最初の文字から始めて16文字だけを1文字おきに調べていた。この場合、URI のような階層化された文字列に対しては、上記で説明した異常なパフォーマンスの低下を起こしていた。

String, Integer, Date などの Java ライブラリは hashCode の返り値として厳密な値を定義している。この考えは一般的にはよい考えではない。さらによいハッシュ関数の実装があった場合に、置き換えることができなくなるからである。