So-net無料ブログ作成

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

Effective Java 第2版 (The Java Series)

Effective Java 第2版 (The Java Series)

  • 作者: Joshua Bloch
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2008/11/27
  • メディア: 単行本(ソフトカバー)

項目9「equalsをオーバーライドする時は、常にhashCodeをオーバーライドする」では、ハッシュコードの計算方法がp.47に示されています。そして、計算の最初のステップとして、次のようにのべられています。
  1. 何らかのゼロではない定数、たとえば、17を、resultという名のint変数に保存します。
この17を使用することに関して、p.48には次のように述べられています。
ゼロでない初期値がステップ1で使用されていますので、ステップ2aで計算された結果ゼロとなるハッシュ値を持つ最初のフィールドから、ハッシュ値は影響を受けます。もし、ステップ1で初期値としてゼロが使用されたら、全般的なハッシュ値は、そのような最初のフィールドから影響を受けないことになり、衝突が増加することになります。値17は、任意の値です。
この衝突が増加するということに関しては、ハッシュコードの計算対象となるフィールドが固定数であれば、値が0であっても衝突は増加しません。たとえば、次のようなPointクラスにhashCodeメソッドを実装すると、計算対象のフィールドはxyの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});



スポンサーリンク





nice!(0)  コメント(0)  トラックバック(0) 

nice! 0

コメント 0

コメントを書く

お名前:[必須]
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

トラックバック 0

トラックバックの受付は締め切りました