39

Javaには、int座標でポイントを表すクラスがあります

public class Point {
    int x = -1;
    int y = -1;

    public Point (int xNew, int yNew) {
        x = xNew; y = yNew;
    }

    public boolean equals (Object o) {
        // no need for (o instanceof Point) by design
        return x == ((Point)o).x && y == ((Point)o).y;
    }
}

クラスのオブジェクトをPointaのキーとして、HashMapおよびの要素として使用していますHashSet。

hashCode関数の最良の候補は何でしょうか？左の部分がx、右の部分がyになるように、それをdoubleにします。たとえば 、次のようx = 4, y = 12にすると、hashCodeが返されます4.12。しかし、実装によって、それは倍になることはできず、intだけです。

これはオプションではありません：

public int hashCode() {
    // no need to check for exception parseInt since x and y are valid by design
    return Integer.parseInt(Integer.toString(x) + Integer.toString(y));
}

値xとyが長すぎる可能性があるため、一緒に変換されません。

4

8 に答える 8

57

のタイプを変更することはできません。また、変更するhashCode必要もありません。

私はちょうど次のようなもので行きます：

public int hashCode() {
    return x * 31 + y;
}

これは、ほとんどの場合（たとえば、加算やXOR-ingとは異なり）、（a、b）が（b、a）とは異なることを意味することに注意してください。これは、実際に「切り替えられた」値のキーを頻繁に使用する場合に役立ちます。

一意ではありませんが、ハッシュコードは一意である必要はありません。それらは、（正確さのために）等しい値に対しては同じである必要があり、（効率のために）等しくない値に対しては「通常」異なり、妥当な分布である必要があります。

一般的に、私は通常、JoshBlochがEffectiveJavaで提案しているのと同じ種類のパターンに従います。

public int hashCode() {
    int hash = 17;
    hash = hash * 31 + field1Hash;
    hash = hash * 31 + field2Hash;
    hash = hash * 31 + field3Hash;
    hash = hash * 31 + field4Hash;
    ...
    return hash;
}

field1Hash参照型フィールドのハッシュコード（またはnull参照の場合は0）、int値の場合はintそれ自体、64ビットから32までのある種のハッシュなどはどこにありますかlong。

編集：31と17がうまく連携する理由の詳細を思い出せません。両方とも素数であるという事実は役立つかもしれませんが、私が覚えていることから、このようなハッシュが一般的に合理的である理由の背後にある数学（可能性のある値の分布が事前にわかっているハッシュほど良くはありませんが）は難しいか、よく理解されていません。31を掛けるのは安いことを知っています（左に5シフトして元の値を引きます）...

于 2012-07-31T14:39:49.003 に答える
12

等しくないオブジェクトが同じハッシュコードを持っていても問題ないことを私は知っています。ただし、衝突が多いほど、パフォーマンスは低下します（たとえば、ハッシュテーブル内）。

私の知る限り、Z² → Zからの最適なマッピングは、「エレガントな対関数」（google it）です。これが実装です

// x,y must be non-negative
int elegant(int x, int y) {
    return x < y ? y * y + x : x * x + x + y;
}


// returns a unique number for every x,y pair
int elegantSigned(int x, int y) {
    if (x < 0) {
        if (y < 0)
            return 3 + 4 * elegant(-x - 1, -y - 1);
        return 2 + 4 * elegant(-x - 1, y);
    }
    if (y < 0)
        return 1 + 4 * elegant(x, -y - 1);
    return 4 * elegant(x, y);
}

これは、乗算オーバーフローが発生するとすぐにオーバーラップし始めます。xとyの絶対値が約46000未満の場合、ハッシュの衝突はゼロになります。

于 2016-01-14T21:07:52.573 に答える
10

java.util.Objects.hash（Object ... values）を使用するだけです。

public int hashCode() {
    return Objects.hash(field1,field2);
}

Objects.hashは実際にArrays.hashCode（Object a []）を呼び出します

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}
于 2016-07-17T02:14:05.980 に答える
4

この質問はかなり古いものですが、Javaが存在する限り、まさにそのアイデアは現実のものになると思います。上記のアプローチを分析してみましょう。

  1. Objects.hash(...)流暢で何をする必要があるかが明確ですが、varargs（暗黙的に配列を作成する）を使用し、さらに、メソッドに渡されるすべてのプリミティブを暗黙的にボックス化します。
  2. x * 31 + yパフォーマンス効率が高い：ボクシングがなく、明示的または暗黙的な配列作成操作が使用されていません。しかし、何をする必要があるのか​​は不明です。なぜ31、42ではないのですか？ハッシュがどのように機能するかをよく知っている人にとっては、そのようなコードを理解するのは難しいことではありませんが、他の人にとってはどうでしょうか？2つ目の落とし穴は、拡張が難しいことです。たとえば、3Dに移行してz座標を追加したい場合は、ハッシュコードに新しい値を追加するのを忘れがちです。これは、ほぼ同じコードをコピーして貼り付ける必要があるためです。回数。

上記の回答では言及されていない、3番目のアプローチを紹介できます。

@Override
public final int hashCode()
{
    final int[] numbers = {x, y};
    return Arrays.hashCode(numbers);
}

一時的な配列を使用して、ハッシュされる整数を保持し、Java 1.5以降で使用可能なArrays.hashCode（）を呼び出します。他のプリミティブ型のバージョンもあります。

長所：それは乾燥していて、流暢で、何をする必要があるかを完全に明確にしています。暗黙のボクシングの影響を受けず、暗黙のvarargを使用しません。比較的高速で安価です。配列初期化子に数値を追加することで簡単に拡張できます。

短所：コピー＆ペースト方式ほど高速ではありません。ハッシュコードが頻繁に呼び出される場合は考慮してください。

よろしくお願いします。

于 2018-08-15T14:09:47.193 に答える
3

多くの場合、 ApacheCommonsHashCodeBuilderを検討する価値があります

このクラスを使用すると、任意のクラスに対して適切なhashCodeメソッドを構築できます。これは、JoshuaBloch著のEffectiveJavaに記載されている規則に従います。優れたhashCodeメソッドを作成することは、実際には非常に困難です。このクラスは、プロセスを簡素化することを目的としています

そして私は間違いなく参照された本EffectiveJavaを見ることをお勧めします。

于 2012-07-31T14:42:17.217 に答える
2

ハッシュコード操作を生成する一般的な戦略があります。あなたの場合、これは次のようになります：

public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + x;
    result = prime * result + y;
    return result;

}

于 2012-07-31T14:40:52.687 に答える
1

Google Guavaの Objects.hashCode（Object ...）メソッドを確認することをお勧めします。

public int hashCode() {
  return Objects.hashCode(x, y);
}
于 2012-07-31T14:47:12.813 に答える
-1

ハッシュコードを追加してみてください。？

new Integer（x）.hashCode（）+ new Integer（y）.hashCode（）;を返します。

于 2012-07-31T14:38:58.823 に答える