5

オブジェクトのハッシュを生成するための次のコードがありました。

public int GetHashCode(MyType obj)
{
   return (obj.Prop1.GetHashCode() + obj.Prop2.GetHashCode() + obj.Prop3.GetHashCode()).GetHashCode();
}

つまり、すべてのプロパティのハッシュコードを追加してから、このハッシュを取得します。

レビューでは、同僚はこれがあまりにも頻繁に衝突することを示唆しました。これが正しいかどうかはわかりません。理由は次のとおりです。

  1. ハッシュコードが正の数と負の数の間で同じ頻度で選択され、それらが折り返されることを考えると、数自体ではなく、これらの数の合計の可能性について私たちが得る追加情報はないと思います
  2. それらの合計がランダムでない限り、ハッシュコードは、「互いに近い」数値が「離れた」数値になるように設計されているため、関数に不均一に分散された値をフィードすることは問題になりません。

誰が正しいですか？

答えが言語固有の場合に備えて、C＃です。

4

3 に答える 3

6

はい。

Prop1、Prop2などがタイプであると仮定しますint。通常、より低い範囲の整数のみが使用されます。合計アプローチは、必要以上に頻繁に衝突します。

のHasCode7は7であり、それ自体でハッシュする場合は完全に理にかなっintています。ただし、コードを使用すると<7, 3>、タプルはすべて同じハッシュになります。Additionの代わりに単純なXORでも同じです。<3, 7><8, 2>

一般的なアプローチは、いくつかの（素数）数を追加してシフトすることです。

public int GetHashCode(MyType obj)
{
  int hash = 0;
  unchecked
  {         
     hash += 19 * obj.Prop1.GetHashCode();
     hash += 31 * obj.Prop2.GetHashCode();
     hash += 37 * obj.Prop3.GetHashCode();
  }
  return hash;
}

19、31、37という数字はそれほど重要ではありません。また、必要に応じて、の代わりにORまたはXORを使用できます+。

于 2011-06-08T22:01:54.227 に答える
2

XORingの方が良いでしょう：

public int GetHashCode(MyType obj)
{
   return obj.Prop1.GetHashCode() ^ 
          obj.Prop2.GetHashCode() ^ 
          obj.Prop3.GetHashCode();
}
于 2011-06-08T22:01:03.320 に答える
0

変更されたFNVHashCodeジェネレーターを使用できます。非常によく似た質問に（私が） ここで回答しました。

于 2011-06-28T02:24:43.450 に答える