0

クラスのハッシュコードの実装があり、ハッシュコードの実装はEclipseが生成するものと一致しており、ここで説明されている最も一般的に受け入れられているプラ​​クティスとも一致しています

これが私のハッシュコードの実装です（このメソッドで使用されるすべてのIDがオブジェクトのキーを構成します）：

public int hashCode() {
    final int prime = 31;
    int hashCode = 1;
    if(uId != null){
        hashCode = prime * hashCode + uId.hashCode();
    }
    if(rId != null){
        hashCode = prime * hashCode + rId.hashCode();
    }
    if(bId != null){
        hashCode = prime * hashCode + bId.hashCode();
    }
    if(reId != null){
        hashCode = prime * hashCode + reId.hashCode();
    }
    if(cId != null){
        hashCode = prime * hashCode + cId.hashCode();
    }
    return hashCode;
}

非常に大規模なデータ セットをテストしていて、コレクションにこのクラスのオブジェクトの期待数がないというシナリオに遭遇しました。よく見ると、以下の 2 つのデータ セットは同じハッシュコード : 50268236873 になり、ハッシュコードが同じであるため、レコードはコレクションに追加された最後のレコードに置き換えられました。

  Existing record :
  Record@2c0781cd[uId=54046,rId=10967,bId=177,reId=1728,cId=50194] 

  Record being inserted into the collection :
  Record@20dad050[uId=53806,rId=18389,bId=177,reId=19026,cId=50194]

Both of these had the hashCode value = 50268236873

したがって、質問:

1] これは、2 つの異なるオブジェクトのハッシュ コードが同じ値を持つ明確なケースです。では、これがどのデータセットでも起こらないようにする方法は? 素数は大きい方がいいですか?

2] 実装の hashCode 変数をよく見ると、最大値が 2^31 - 1 = 2147483647 である int データ型であり、上記のデータ セットに対して計算されるハッシュコード = 50268236873 よりも大きいため、オーバーフローが発生します。 . hashCode 値の型として long を使用する結果はありますか?

ありがとう
Nohsib

編集 ：

私はHashSetを使用しており、投稿された回答を読んだ後、以下のようにequalsの実装を調べました.equalsでは、2つのオブジェクトのhashCodesが同じかどうかを確認し、それを使用してそれらが同じかどうかを判断するためだと思います.同じオブジェクトがこの問題を引き起こしています。

これを確認できる人はいますか？

@Override
    public boolean equals(Object paramObject) {
        boolean equals = false;
        if (paramObject != null) {
            ACRecord other = (ACRecord) paramObject;
            if ((this.hashCode() == other.hashCode()) // I think this is where I am going wrong
                    || (this.uId.equals(other.getUId())
                            && this.rId.equals(other.getRId())
                            && this.reId.equals(other.getReId())
                            && this.bId.equals(other.getBId()) 
                            && this.cId.equals(other.getCId))) {
                equals = true;
            }
        }
        return equals;
    }

解決策 : hashCode を使用して 2 つのオブジェクトが等しいかどうかを判断したため、equals メソッドの実装が間違っていました。equals メソッドの実装を修正すると、ハッシュセットが既存のレコードを置き換えていたという問題が解決しました。

4

5 に答える 5

9

通常、ハッシュ コードは一意性を保証しません。HashMap の実装は、通常、裏でリストを保存することによって衝突に対処しますが、リスト内のすべてを一致として取得するのではなく、実際に一致するものだけを取得することを保証するチェックが含まれています。

つまり、map.get("foo") を実行して衝突が発生した場合、ハッシュ マップは各結果 (ハッシュされていない) をチェックして、実際に "foo" と一致するかどうかを確認します。次に、完全一致のみを返します。

また、ハッシュコードのコントラクトでは、equals() に真に応答する 2 つのオブジェクトは同じハッシュコードを持つべきであると規定されていますが、その逆は必ずしも真ではないことにも注意してください。

于 2015-03-20T00:24:59.213 に答える
3

Java 8 ドキュメント (要約) からのhashCodeのコントラクトを次に示します。

  1. 同じオブジェクトでメソッドを 2 回呼び出した場合、(JVM インスタンスごとに) 同じ値になる必要があります。

  2. 2 つのオブジェクトaとbが に従って等しい場合a.equals(b)、hashCodes は同じでなければなりません。

上記を満たす最小限の定義は次のとおりです。

public int hashCode() {
  return 0;
}

すべてのjava.util.*コレクションはこのコントラクトを好み、これHashTableにHashMap準拠しており、上記の例のように過度に重複した場合でも、重複する hashCode が原因でアイテムをドロップすることはありません。遅くなりますが、正しいでしょう。

代わりに、ハッシュ ベースのコレクションを追加または取得するときに予期しない結果が生じる一般的な理由には、次のようなものがあります。

  • 実行時にハッシュコードが変わるような方法でオブジェクトを再利用/変更する (#1 の違反)
  • オーバーライドしない.equals(Object)
  • コントラクトで指定されてjava.*いる以上のことを前提とするバグのあるコレクション ( の外部) を使用する。hashCode
于 2015-03-20T00:50:51.233 に答える
0

hashCode が一意である必要はありません。2 つのオブジェクトが等しい場合、それらのハッシュも等しくなければなりません。

可能なオブジェクト空間がこの数を超える場合、衝突が発生する必要があることに気付いたように、ハッシュの衝突は予想され、避けられない原因です。

hashCode はすでに int として定義されているため、long に変更することはできません。これが使用されます。

hashMap や HashSet などのコレクションは衝突の可能性を認識しており、衝突の影響を受けません。カスタム コードも衝突防止でなければなりません。

于 2015-03-20T00:40:36.323 に答える
0

ハッシュコードは通常、広い範囲の値を狭い範囲の値にマップします。これは、データの最も完璧なハッシュ アルゴリズムでさえ、可能なハッシュ値の数であるn + 1値に到達すると衝突が発生することを意味します ( int をハッシュ コードとして使用する場合) 。n2^32

実装では、オブジェクトのすべてのメンバーを完全にチェックして実際に等しいことを確認することにより、このような衝突を処理する必要があります。

ハッシュは通常、結果を検証するために必要なチェックの量を減らすことにより、完全なチェックを大幅に減らします。これは、データに完全に一致するものが見つかるまで、同じハッシュ コードを持つ値に対してのみチェックする必要があるためです。マップには存在しません。

ハッシュ マップの実装の簡単な説明については、この回答を参照してください。

于 2015-03-20T00:50:00.740 に答える