1

簡単に言うと、(x, y) の形のポイントがたくさんあります。

ポイントをキーにして、これらのポイントをハッシュテーブルに入れたいと思います。

hashCode()classのメソッドをどのように実装すればよいPointですか? Javaを言語として採用

class Point {
   public double x;
   public double y;

   @Override
   public int hashCode() {
      // How do I implement here?
   }
}
4

3 に答える 3

2

数値は、ほとんどの座標平面でクラスター化する傾向があります。なぜなら、快適な範囲内の数字を使用する傾向があるからです。このため、単純な xor の組み合わせは望ましくありません。すべての数値 wherex == yが衝突し、すべての数値 where などが衝突するx + 1 == yからです。

これを回避するには、x 座標で xor する前に、y 座標のバイトを逆にすることをお勧めします。これにより、1 つの入力の変動性が最も高い領域 (下位バイト) と、他の入力の変動性が最も低い領域 (上位バイト) が結合されます。このようなアルゴリズムは、数のクラスター (1 から 1000 の間の x の値など) を考慮するときに、より均一な分布を提供します。

ハッシュ アルゴリズムは、ハッシュが重度のクラスタリングなしで数値フィールドを生成する場合に最適に機能するため、このようなソリューションは、ハッシュの衝突が頻繁に発生しないため、ハッシュ関連のデータ構造を実際に高速化します。

もちろん、以下は最適化されていません。ニーズに合わせてトリミングできる可能性がありますが、基本的な考え方は次のとおりです。

public int hashCode() {

    long bits = Double.doubleToLongBits(y);
    byte[] ybits = new byte[] {
        (byte)((y >> 56) & 0xff),
        (byte)((y >> 48) & 0xff),
        (byte)((y >> 40) & 0xff),
        (byte)((y >> 32) & 0xff),
        (byte)((y >> 24) & 0xff),
        (byte)((y >> 16) & 0xff),
        (byte)((y >> 8) & 0xff),
        (byte)((y >> 0) & 0xff),
    };
    byte[] xbits = new byte[] {
        (byte)((x >> 56) & 0xff),
        (byte)((x >> 48) & 0xff),
        (byte)((x >> 40) & 0xff),
        (byte)((x >> 32) & 0xff),
        (byte)((x >> 24) & 0xff),
        (byte)((x >> 16) & 0xff),
        (byte)((x >> 8) & 0xff),
        (byte)((x >> 0) & 0xff),
    };
    // this combines the bytes of X with the reversed order
    // bytes of Y, and then packs both of those into 4 bytes
    // because we need to return an int (4 bytes).
    byte[] xorbits = new byte[] {
         (xbits[0]^ybits[7])^(xbits[4]^ybits[3]),
         (xbits[1]^ybits[6])^(xbits[5]^ybits[2]),
         (xbits[2]^ybits[5])^(xbits[6]^ybits[1]),
         (xbits[3]^ybits[4])^(xbits[7]^ybits[0]),
    };

    int value = 0;
    for (int i = 0; i < 3; i++) {
       value = (value << 8) + (by[i] & 0xff);
    }
    return value;
}

私が提案する最初の最適化は、その後のルックアップのためにオブジェクトにハッシュコードをキャッシュすることです。プロファイリングでそれが問題であることが示唆された場合は、作成/破棄された配列をより効率的に管理することをお勧めします。

于 2012-06-07T16:38:56.660 に答える
0

必要な機能は何でも使用できます。それはすべて、座標がどのような典型的な値であるか、およびハッシュ関数がどれだけ優れているかによって異なります。

たとえば、すべてのポイントが 100 万から 100 万の範囲にある場合、次のようなものを使用できます (これは C++ コードです。使用している言語はわかりません)。

size_t hashCode = (size_t)x * (size_t)y;

または、値を追加したり、値を乗算したり、必要なことを行うことができます。

size_t hashCode = (size_t)(x+y);

また

size_t hashCode = (size_t)(x*y);

あるいは

size_t hashCode = (size_t)(x*y) + (size_t)(x+y);
于 2012-06-07T16:35:26.473 に答える
0

I'm not sure how good the double's hashing is, but you should be able to do:

public int hashCode() {
  return x.hashCode() ^ y.hashCode();
}

If this gives too many collisions in testing (you do that right?), you can vary it a bit with bit shifting, magic numbers, etc. All kinds of bitwise operations, really.

Is this Java? I'm basing my answer on my experience with C#.

于 2012-06-07T16:30:35.067 に答える