10

2 つの int の単純なコンテナー オブジェクトの equals メソッドと hashcode メソッドをオーバーライドしています。各 int は、別のオブジェクトのインデックスを反映します (そのオブジェクトが何であるかは関係ありません)。クラスのポイントは、2 つのオブジェクト間の接続を表すことです。

接続の方向は重要ではないため、equals メソッドは、2 つの int がオブジェクト Eg 内のどの方向にあるかに関係なく、true を返す必要があります。

connectionA = new Connection(1,2);
connectionB = new Connection(1,3);
connectionC = new Connection(2,1);

connectionA.equals(connectionB); // returns false
connectionA.equals(connectionC); // returns true

これが私が持っているものです（整数のソースコードから変更されています）：

public class Connection {
    // Simple container for two numbers which are connected.
    // Two Connection objects are equal regardless of the order of from and to.

    int from;
    int to;

    public Connection(int from, int to) {
        this.from = from;
        this.to = to;
    }

    // Modifed from Integer source code
    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Connection) {
            Connection connectionObj = (Connection) obj;
            return ((from == connectionObj.from && to == connectionObj.to) || (from == connectionObj.to && to == connectionObj.from));
        }
        return false;
    }

    @Override
    public int hashCode() {
        return from*to;
    }
}

これは機能しますが、私の質問は次のとおりです。これを達成するためのより良い方法はありますか?

私の主な心配は、 hashcode() メソッドが乗算して同じ数に等しくなる 2 つの整数に対して同じハッシュコードを返すことです。例えば

3*4 = 12
2*6 = 12 // same!

ドキュメントhttp://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Object.html#hashCode()には、次のように記載されています。

equals(java.lang.Object) メソッドに従って 2 つのオブジェクトが等しくない場合、2 つのオブジェクトのそれぞれで hashCode メソッドを呼び出すと、異なる整数結果が生成される必要はありません。ただし、プログラマーは、等しくないオブジェクトに対して個別の整数結果を生成すると、ハッシュテーブルのパフォーマンスが向上する可能性があることに注意する必要があります。

一致するハッシュコードの数を減らす簡単な方法を誰かが見ることができれば、私は答えに感謝します.

ありがとう！

ティム

PS私は、いくつかのインポートの煩わしさを引き起こす可能性のある java.sql.Connection があることを認識しています。このオブジェクトには、実際にはアプリケーション内でより具体的な名前が付けられていますが、簡潔にするために、ここでは Connection に短縮しています。

4

5 に答える 5

6

「機能する」 3 つの解決策が提案されています。（作業では、ハッシュコードの基本的な要件を満たしていることを意味します...異なる入力が異なる出力を与える...そして、OPの追加の「対称性」要件も満たしています。）

これらは：

   # 1
   return from ^ to;

   # 2
   return to*to+from*from;

   # 3
   int res = 17;
   res = res * 31 + Math.min(from, to);
   res = res * 31 + Math.max(from, to);
   return res;

最初のものには、出力の範囲が実際の入力値の範囲によって制限されるという問題があります。したがって、たとえば、入力がそれぞれ 2 iおよび 2 j以下の非負数であると仮定すると、出力は 2 max(i,j)以下になります。これにより、ハッシュ テーブルの「分散」1が低下し、衝突率が高くなる可能性があります。（こんなときも問題ありfrom == to！）

2 番目と 3 番目のものは最初のものよりも優れていますが、fromとtoが小さい場合、望ましいよりも多くの衝突が発生する可能性があります。

fromとの小さな値の衝突を最小限に抑えることが重要な場合は、4 番目の代替案をお勧めしますto。

  #4
  int res = Math.max(from, to);
  res = (res << 16) | (res >>> 16);  // exchange top and bottom 16 bits.
  res = res ^ Math.min(from, to);
  return res;

これには、fromとtoが両方とも 0..2 16 -1 の範囲内にある場合、個別の (順序付けされていない) ペアごとに一意のハッシュコードが得られるという利点があります。

1 - これが正しい技術用語かどうかはわかりません ...

于 2013-04-08T12:13:21.233 に答える
5

これは広く受け入れられているアプローチです。

@Override
public int hashCode() {
    int res = 17;
    res = res * 31 + Math.min(from, to);
    res = res * 31 + Math.max(from, to);
    return res;
}
于 2013-04-08T11:32:38.920 に答える
2

私は、次のようなものだと思います

@Override
public int hashCode() {
    return to*to+from*from;
}

十分です

于 2013-04-08T11:38:40.523 に答える