xorを使用したGetHashCode（）の問題

StackOverflow https://stackoverflow.com/questions/1008633

  •  06-07-2019
  •  | 
  •  

質問

私の理解では、通常、GetHashCode（）でxorを使用してintを生成し、（参照ではなく）値でデータを識別します。以下に簡単な例を示します。

class Foo
{
    int m_a;
    int m_b;

    public int A
    {
        get { return m_a; }
        set { m_a = value; }
    }

    public int B
    {
        get { return m_b; }
        set { m_b = value; }
    }

    public Foo(int a, int b)
    {
        m_a = a;
        m_b = b;
    }

    public override int GetHashCode()
    {
        return A ^ B;
    }

    public override bool Equals(object obj)
    {
        return this.GetHashCode() == obj.GetHashCode();
    }
}

アイデアは、プロパティAとBの値に基づいて、Fooのインスタンスを別のインスタンスと比較したいことです。Foo1.A== Foo2.AおよびFoo1.B == Foo2.Bの場合、同等です。

問題は次のとおりです： 

Foo one = new Foo(1, 2);
Foo two = new Foo(2, 1);

if (one.Equals(two)) { ... }  // This is true!

これらはどちらもGetHashCode（）に対して3の値を生成し、Equals（）がtrueを返します。明らかに、これは些細な例であり、2つのプロパティだけで、Equals（）メソッドの個々のプロパティを簡単に比較できます。ただし、より複雑なクラスでは、これはすぐに手に負えなくなります。

時々、ハッシュコードを1回だけ設定し、常に同じ値を返すのが理にかなっていることを知っています。ただし、平等の評価が必要な可変オブジェクトの場合、これは合理的ではないと思います。

GetHashCode（）を実装するときに簡単に交換できるプロパティ値を処理する最良の方法は何ですか？

  

参照

     

最適なアルゴリズムは何ですかSystem.Object.GetHashCodeをオーバーライドしましたか

役に立ちましたか？

解決

まず-GetHashCode（）の観点からのみEquals（）を実装しないでください-オブジェクトが等しくない場合でもハッシュコードが衝突することがあります。

GetHashCode（）の契約には以下が含まれます。

  • 異なるハッシュコードは、オブジェクトが確実に等しくないことを意味します
  • 同じハッシュコードは、オブジェクトが might 等しいことを意味します（ただし、場合によっては等しくない可能性があります）

アンドリュー・ヘアは彼の答えを取り入れることを提案しました：

こちらを読むことをお勧めしますソリューション（ちなみに、独自のジョンスキートによる）＆quot; better＆quot;ハッシュコードを計算する方法。

  

いいえ、上記は比較的遅く、   あまり役に立たない。一部の人々は使用します   XOR（例：a ^ b ^ c）しかし、私は   Josh Blochの   ＆quot;効果的なJava＆quot;：

public override int GetHashCode()
{
    int hash = 23;
    hash = hash*37 + craneCounterweightID;
    hash = hash*37 + trailerID;
    hash = hash*37 + craneConfigurationTypeCode.GetHashCode();
    return hash;
}
     

23と37は任意の数字です   互いに素です。

     

XORに対する上記の利点   メソッドは、タイプがある場合   次の2つの値があります   頻繁に同じ、それらのXOR   値は常に同じになります   結果（0）に対して上記は   それらを区別しない限り   あなたはとても不運です。

上記のスニペットで述べたように、 Joshua Blochの本もご覧ください。 、有効なJava、には主題の適切な処理が含まれています（ハッシュコードの説明は.NETにも適用されます）。

他のヒント

Andrewは、より良いハッシュコードを生成するための良い例を投稿しましたが、ハッシュコードが一意であることが保証されていないため、ハッシュコードを同等性チェックとして使用すべきではないことにも留意してください。

これが二重オブジェクトと見なされる理由の簡単な例について。 intよりも可能な値があるため、doubleごとに一意のintを持つことはできません。ハッシュは実際には最初のパスであり、キーをすばやく見つける必要がある辞書のような状況で使用されます。最初にハッシュを比較することにより、可能なキーの大部分を除外でき、一致するハッシュを持つキーのみに費用が必要です完全な平等チェック（または他の衝突解決メソッド）。

ハッシュには常に衝突が伴うため、それに対処する必要があります（つまり、ハッシュ値を比較し、それらが等しい場合は、クラス内の値を正確に比較して、クラスが等しいことを確認します）。

単純なXORを使用すると、多くの衝突が発生します。少なくしたい場合は、異なるビットに値を分配する数学関数を使用します（ビットシフト、素数の乗算など）。

ハッシュの迅速な生成と適切な配布

public override int GetHashCode()
{
    return A.GetHashCode() ^ B.GetHashCode();         // XOR
}

通常、ハッシュコードは比較のために悪い考えなので、好奇心から、次のコードを実行する方が良いのではないでしょうか、何か不足していますか？

public override bool Equals(object obj)
{
    bool isEqual = false;
    Foo otherFoo = obj as Foo;
    if (otherFoo != null)
    {
        isEqual = (this.A == otherFoo.A) && (this.B == otherFoo.B);
    }
    return isEqual;
}

いくつかのより良いハッシュ実装があります。たとえば、 FNVハッシュ。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top