ハッシュコードの衝突の増加

（こちらのブログの記事からの転記です）

EFFECTIVE JAVA 第2版 (The Java Series)

• 作者: Joshua Bloch
• 出版社/メーカー: 丸善出版
• 発売日: 2014/03/11
• メディア: 単行本（ソフトカバー）

項目9「equalsをオーバーライドする時は、常にhashCodeをオーバーライドする」では、ハッシュコードの計算方法がp.47に示されています。そして、計算の最初のステップとして、次のようにのべられています。

1. 何らかのゼロではない定数、たとえば、17を、resultという名のint変数に保存します。

この17を使用することに関して、p.48には次のように述べられています。

ゼロでない初期値がステップ1で使用されていますので、ステップ2aで計算された結果ゼロとなるハッシュ値を持つ最初のフィールドから、ハッシュ値は影響を受けます。もし、ステップ1で初期値としてゼロが使用されたら、全般的なハッシュ値は、そのような最初のフィールドから影響を受けないことになり、衝突が増加することになります。値17は、任意の値です。

この衝突が増加するということに関しては、ハッシュコードの計算対象となるフィールドが固定数であれば、値が0であっても衝突は増加しません。たとえば、次のようなPointクラスにhashCodeメソッドを実装すると、計算対象のフィールドはxとyの2つです。

public class Point {
    public final int x;
    public final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

この場合、初期値がゼロでもハッシュコード値の衝突が増えることはありません。では、次のようなクラスではどうでしょうか。

public class IntArray {
    private int[] data;

    public IntArray(int[] data) {
        this.data = data.clone();
    }
    ....
}

このIntArrayクラスは、intの配列を保持することになります。したがって、ハッシュコードの計算対象は、配列の個々の要素となります。そして、その要素の個数はインスタンスごとに異なります。もし、ハッシュコードの初期値としてゼロを使用すると、簡単にハッシコードが衝突します。次の二つのインスタンス生成で作成されたインスタンスは、ハッシュコードの初期値としてゼロが使用されると、どちらもハッシュコード値がゼロとなり、衝突することになります。

new IntArray(new int[] {0});
new IntArray(new int[] {0, 0});