9

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;
  }
}
4

8 に答える 8

15

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

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 億しかないことに注意してください。6 文字の文字列は 40 億を超える可能性があるため、そのうちの少なくとも 2 つが同じハッシュ コードを持っています。2 つ紹介しました。他にも無限にあります。

一般に、考えられるハッシュ コードが n 個ある場合、n 個の要素の平方根が作用するようになると、衝突が発生する確率が劇的に上昇すると予想できます。これがいわゆる「誕生日のパラドックス」です。等価性のためにハッシュ コードに頼るべきではない理由に関する私の記事については、以下を参照してください。

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

于 2010-11-22T21:29:45.750 に答える
7

いいえ、そうではないので、大丈夫ではありません

equality <=> hashcode equality.

それはちょうどです

equality => hashcode equality.

または他の方向に：

hashcode inequality => inequality.

http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspxを引用:

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

于 2010-11-22T18:55:20.747 に答える
2

Equals基本的に、タイプに対して「と同じハッシュコードを持っている」という意味にしたい場合を除いて、2つの文字列は異なる可能性がありますが、同じハッシュコードを共有するため、いいえと言います。確率は小さいかもしれませんが、ゼロではありません。

于 2010-11-22T18:56:27.757 に答える
1

いいえ、これは同等性をテストするための許容できる方法ではありません。2つの等しくない値が同じハッシュコードを持つ可能性は非常に高いです。これにより、実装がEquals戻るtrue必要があるときに戻るようになりますfalse

于 2010-11-22T18:55:34.943 に答える
1

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.
  }
于 2010-11-22T18:58:51.560 に答える
1

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

GetHashCode内部で呼び出すのEqualsは、オブジェクトのハッシュ値を計算する方が、等しいかどうかをチェックするよりもはるかに安価である場合（たとえば、オブジェクトをキャッシュするため）のみです。その場合if (this.GetHashCode() != other.GetHashCode()) return false;、オブジェクトが等しくないことをすばやく確認できるように言うことができます。

では、いつこれを行うのでしょうか。定期的にスクリーンショットを撮り、画面が変わってからの経過時間を確認するコードを作成しました。私のスクリーンショットは8MBで、スクリーンショットの間隔内で変化するピクセルが比較的少ないため、それらのリストを検索して同じものを見つけるのはかなり費用がかかります。ハッシュ値は小さく、スクリーンショットごとに1回だけ計算する必要があるため、既知の等しくないものを簡単に削除できます。実際、私のアプリケーションでは、同じハッシュを使用することで、オーバーロードを実装することすらしなかったのとほぼ同じであると判断し、C＃コンパイラは、オーバーロードせずEqualsにオーバーロードしていることを警告しました。GetHashCodeEquals

于 2010-11-22T19:10:29.237 に答える
0

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

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

さまざまなアプローチがありますが、それらのすべてに、ハッシュ値を配置できる少数のスロットがあり、オープンアプローチまたはクローズドアプローチのいずれかを採用しています (楽しみのために、反対の専門用語を使用する人もいます)他の人のために）; 2 つの異なるオブジェクトの同じスロットで衝突した場合、それらを同じスロットに格納する (ただし、オブジェクトが実際に格納されている場所のリンク リストなどがある) か、別のスロットを選択するために再プローブする (さまざまなオブジェクトがあります)そのための戦略）。

現在、どちらのアプローチでも、ハッシュテーブルで必要な O(1) の複雑さから離れて、O(n) の複雑さに向かっています。このリスクは、利用可能なスロットの数に反比例するため、特定のサイズの後にハッシュテーブルのサイズを変更します (すべてが理想的だったとしても、保存されているアイテムの数がスロット）。

サイズ変更時にアイテムを再挿入することは、明らかにハッシュ コードに依存します。このため、オブジェクトでメモ化することはほとんど意味GetHashCode()がありませんが (ほとんどのオブジェクトで十分な頻度で呼び出されるわけではありません)、ハッシュ テーブル自体の中でメモ化する (または、生成された結果をメモ化する) ことは確かに理にかなっています。 、Wang/Jenkins ハッシュで再ハッシュして、不適切なGetHashCode()実装による被害を軽減した場合など)。

さて、挿入するロジックは次のようになります。

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

したがって、この場合、等価性を比較する前にハッシュ コードを取得する必要があります。また、サイズ変更を可能にするために事前に計算された既存のオブジェクトのハッシュ コードもあります。これら 2 つの事実の組み合わせは、項目 4 の比較を次のように実装することが理にかなっていることを意味します。

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ます。キーのタイプが だった場合int、これは完全に無駄になります。キーの型が string で、大文字と小文字を区別しない Unicode で正規化された等価比較を使用していた場合 (したがって、長さを短縮することさえできません)、節約する価値は十分にあります。

一般に、ハッシュコードをメモすることは、パフォーマンスが向上するほど頻繁に使用されないため意味がありませんが、ハッシュセットまたはハッシュテーブル自体に保存することは理にかなっています。

于 2010-11-29T18:35:49.740 に答える