GetHashCodeを使用してEqualsで等しいかどうかをテストする

Question

Equalsオーバーライド内からの等価性をテストする方法としてGetHashCodeを呼び出すことはできますか？

たとえば、このコードは受け入れ可能ですか？

public class Class1 
{ 
    public string A 
    { 
    get; 
    set; 
    } 

    public string B 
    { 
    get; 
    set; 
    } 

    public override bool Equals(object obj) 
    { 
    Class1 other = obj as Class1; 
    return other != null && other.GetHashCode() == this.GetHashCode(); 
    } 

    public override int GetHashCode() 
    { 
    int result = 0; 
    result = (result^397)^(A == null ? 0 : A.GetHashCode()); 
    result = (result^397)^(B == null ? 0 : B.GetHashCode()); 
    return result; 
    } 
} 

Answer 1

その他は正しいです。あなたの平等の操作は壊れています。説明するために：

public static void Main() 
{ 
    var c1 = new Class1() { A = "apahaa", B = null }; 
    var c2 = new Class1() { A = "abacaz", B = null }; 
    Console.WriteLine(c1.Equals(c2)); 
} 

を私はあなたがそのプログラムの出力は「偽」になりたいが、平等のあなたの定義と、それはCLRのいくつかの実装上の「真」であると想像します。

ハッシュコードは約40億個しかないことに注意してください。 40億文字以上の文字列があり、なので、少なくとも2つは同じハッシュコードです。私はあなたに2つを示しました。無限に多くがあります。

一般に、n個の可能なハッシュコードがあると、n個の要素の平方根についていえば、衝突が発生する確率は劇的に上昇することが期待できます。これは、いわゆる「誕生日のパラドックス」です。あなたが見る、平等のためのハッシュコードに頼るべきではない理由についての私の記事について：

http://blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx

Answer 2

それはない

equality <=> hashcode equalityだからいいえ、それは、OKではありません。

それはちょうど

equality => hashcode equalityです。

または他の方向：

hashcode inequality => inequality。 http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspxを引用

：2つのオブジェクトが等しいとした場合、各オブジェクトのGetHashCodeメソッドが同じ値を返す必要があり

。ただし、2つのオブジェクトが等しいと比較されない場合、2つのオブジェクトのGetHashCodeメソッドは異なる値を返す必要はありません。

Answer 3

これは、等価性をテストするための許容可能な方法ではありません。 2つの等しいでない値が同じハッシュコードを持つことは非常に可能です。 Equalsは基本的に、あなたのタイプのために「と同じハッシュコードを持っていません」その後、なし、理由は2を意味するためにあなたがしたい場合を除き、それは、私が言うfalse

Answer 4

を返すべきとき、これはEqualsの実装がtrueを返すために、原因となります文字列は異なるかもしれませんが、同じハッシュコードを共有します。確率は小さいかもしれないが、ゼロではない。

Answer 5

あなたはアイテムが等しくないをしているかどうかを判断するためにGetHashCodeを呼び出すことができますが、2つのオブジェクトが同じハッシュコードを返した場合、それは彼らがある等しいという意味ではありません。 2つのアイテムは同じハッシュコードを持つことができますが、等しくはありません。

2つのアイテムを比較するのに費用がかかる場合は、ハッシュコードを比較できます。彼らが不平等であれば、あなたは保釈することができます。それ以外の場合（ハッシュコードは等しい）、完全な比較を行う必要があります。例えば

：

public override bool Equals(object obj) 
    { 
    Class1 other = obj as Class1; 
    if (other == null || other.GetHashCode() != this.GetHashCode()) 
     return false; 
    // the hash codes are the same so you have to do a full object compare. 
    } 

Answer 6

あなたははハッシュコードが等しいという理由だけで、その後のオブジェクトが同じでなければならないと言うことはできません。

GetHashCodeをEqualsと呼ぶ唯一の時間は、等価性をチェックするよりもオブジェクトのハッシュ値を計算するほうが安かったということでした。その場合、if (this.GetHashCode() != other.GetHashCode()) return false;と言うことができるので、オブジェクトが等しくないことを素早く確認することができます。

だから、いつこのことをしますか？私は定期的な間隔でスクリーンショットを取得し、スクリーンが変更されてからどれぐらいの時間が経過しているかを調べるコードを書いた。私のスクリーンショットは8MBで、スクリーンショットの間隔内で変化するピクセルが比較的少ないので、それらのリストを検索してどれが同じであるかを見つけるのはかなり高価です。ハッシュ値は小さく、スクリーンショットごとに計算するだけでよく、既知の非等価なものを簡単に削除することができます。実際には、私のアプリケーションでは、同じハッシュを持つことが同等であると判断して、Equalsオーバーロードを実装することを邪魔しなかったので、C＃コンパイラがGetHashCodeにオーバーロードされていないことを警告するようになりました。Equals。

Answer 7

等価比較にショートカットとしてのハッシュコードを使用することは理にかなっている一つのケースがあります。

ハッシュテーブルまたはハッシュセットを構築する場合を考えてみましょう。実際、ハッシュセットを考えてみましょう（ハッシュテーブルは値を保持することでそれを拡張しますが、それは関係ありません）。

さまざまなアプローチがありますが、いずれもハッシュ値を入れることができるスロット数は少なく、オープンまたはクローズドアプローチをとっています。反対の専門用語を他者に使用する）。同じスロットに2つの異なるオブジェクトを衝突させた場合、同じスロットにオブジェクトを格納するか（実際にオブジェクトが格納されているリンクされたリストなど）、別のスロットを選択するために再プロービングすることができますこのための戦略）。

どちらのアプローチでも、私たちはハッシュテーブルでO（1）の複雑さからO（n）の複雑さに近づいています。このリスクは利用可能なスロットの数に反比例するので、あるサイズの後でハッシュテーブルのサイズを変更します（すべてが理想的だったとしても、格納されたアイテムの数がスロット）。

リサイズにアイテムを再挿入することは、明らかにハッシュコードに依存します。このため、オブジェクト内にGetHashCode()をメモすることはめったにありませんが（ほとんどのオブジェクトでは頻繁に呼び出されることはありません）、ハッシュテーブル自体の中でメモを取ることは確かに意味があります（または、あなたが悪いGetHashCode()の実装によって引き起こされた損害を減らすためにWang/Jenkinsハッシュで再ハッシュした場合など）。今

、我々はロジックのようなものになるだろう挿入するために来る：

1. オブジェクトのハッシュコードを取得します。
2. オブジェクトのスロットを取得します。
3. スロットが空の場合は、オブジェクトを配置して戻ってください。
4. スロットに等しいオブジェクトが含まれている場合は、ハッシュセットが完了し、ハッシュテーブルの値を置き換える位置になります。これを行い、帰ってください。
5. 衝突の戦略に従って次のスロットを試して、アイテム3に戻ります（これをあまりにも頻繁に繰り返す場合はおそらくサイズ変更します）。

したがって、この場合、ハッシュコードを取得してから、同等かどうかを比較する必要があります。すでにサイズ変更が可能な既存のオブジェクトのハッシュコードも事前に計算されています。

private bool IsMatch(KeyType newItem, KeyType storedItem, int newHash, int oldHash) 
{ 
    return ReferenceEquals(newItem, storedItem) // fast, false negatives, no false positives (only applicable to reference types) 
    || 
    (
     newHash == oldHash // fast, false positives, no fast negatives 
     && 
     _cmp.Equals(newItem, storedItem) // slow for some types, but always correct result. 
    ); 
} 

明らかに、これの利点は_cmp.Equalsの複雑さによって異なります。これら二つの事実の組み合わせは、それがのようにアイテム4のための私達の比較を実装することは理にかなっていることを意味します。私たちの鍵タイプがintだった場合、これは完全に無駄になります。文字列と私たちが大文字と小文字を区別しないUnicodeで正規化された等価比較を使用していたキータイプ（長さに合わせてショートカットすることさえできない）なら、保存する価値があります。

一般的にmemoisingハッシュコードはパフォーマンス勝利には十分な頻度で使用されていないため意味がありませんが、ハッシュセットまたはハッシュテーブル自体に格納することは意味があります。

Answer 8

1. 他の理由が述べられているように、間違った実装です。

2. あなたはず短絡のようなGetHashCodeを使用して等価性チェック：大多数ではありませんあなたが特定している場合にのみEquals方法で

   if (other.GetHashCode() != this.GetHashCode() 
       return false; 
   

   等しいその後の実装ははるかに高価GetHashCodeより症例の

3. この1つの実装では、が壊れていないだけでなく、非常に遅いも表示されています（このケースの99％です）。そして理由は？ プロパティのハッシュ値を計算することは、確かにそれらを比較するよりも遅くなるでしょう（）ので、パフォーマンスの面でさえ得られません。適切なGetHashCodeを実装することの利点は、ハッシュが一度だけ計算される（そしてその値が比較に使用される）ハッシュテーブルのキータイプにクラスを使用できることです。あなたのケースでは、GetHashCodeはコレクションに含まれている場合、複数回呼び出されます。 GetHashCode自体は高速でなければなりませんが、相当のEqualsよりも高速ではありません。

   、（現在のハッシュベースの実装を取り出し、適切な実装）あなたのEqualsを実行するベンチマーク

   、ここ

   var watch = Stopwatch.StartNew(); 
   for (int i = 0; i < 100000; i++) 
   { 
       action(); //Equals and GetHashCode called here to test for performance. 
   } 
   watch.Stop(); 
   Console.WriteLine(watch.Elapsed.TotalMilliseconds);