49

MSDNによると、ハッシュ関数には次のプロパティが必要です。

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

  2. オブジェクトの GetHashCode メソッドは、オブジェクトの Equals メソッドの戻り値を決定するオブジェクトの状態に変更がない限り、一貫して同じハッシュ コードを返す必要があります。これはアプリケーションの現在の実行にのみ当てはまり、アプリケーションが再度実行されると別のハッシュ コードが返される可能性があることに注意してください。

  3. 最高のパフォーマンスを得るには、ハッシュ関数がすべての入力に対してランダムな分布を生成する必要があります。

私は次のシナリオで自分自身を見つけ続けています: クラスを作成し、実装IEquatable<T>してオーバーライドしobject.Equals(object)ました。MSDNは次のように述べています。

Equals をオーバーライドする型は、 GetHashCode もオーバーライドする必要があります。そうしないと、Hashtable が正しく機能しない可能性があります。

そして、それは通常、私にとっては少し止まります。なぜなら、どのように適切にオーバーライドするのobject.GetHashCode()ですか? どこから始めればよいか分からず、多くの落とし穴があるようです。

ここ StackOverflow では、GetHashCode のオーバーライドに関連する質問がかなりありますが、それらのほとんどは、非常に特殊なケースや特定の問題に関するものであるようです。したがって、ここで適切なコンパイルを取得したいと思います。一般的なアドバイスとガイドラインを含む概要。何をすべきか、何をすべきでないか、よくある落とし穴、どこから始めるべきかなど。

特に C# 向けにしたいのですが、他の .NET 言語でも同じように機能すると思います (?)。

おそらく最善の方法は、トピックごとに 1 つの回答を作成し、最初に簡単で短い回答を作成し (可能であればワンライナーに近いものにする)、次にさらに情報を追加して、関連する質問、ディスカッション、ブログ投稿などで終了することだと思います。 、もしあれば。次に、「目次」だけを使用して、受け入れられた回答として (一番上に表示されるように) 1 つの投稿を作成できます。短く簡潔にするようにしてください。また、他の質問やブログ投稿へのリンクだけにしないでください。それらの本質を理解し、ソースにリンクするようにしてください (特に、ソースが消える可能性があるため)。また、非常によく似た回答をたくさん作成するのではなく、回答を編集して改善するようにしてください。

私はあまり優れたテクニカル ライターではありませんが、少なくとも回答が似ているように書式を設定したり、目次を作成したりします。また、SO で関連する質問の一部を検索して、私が扱えるもののエッセンスを引き出すかもしれません。しかし、私はこのトピックについてあまり安定していないので、ほとんどの場合、近づかないようにします :p

4

11 に答える 11

11

目次

カバーしたいが、まだカバーしていないこと:

  • 整数の作成方法 (オブジェクトを int に「変換」する方法は、とにかく私にはあまり明白ではありませんでした)。
  • ハッシュ コードのベースとなるフィールド。
    • 不変フィールドのみにある必要がある場合、可変フィールドのみがある場合はどうなりますか?
  • 適切なランダム分布を生成する方法。(MSDN プロパティ #3)
    • これの一部として、適切な魔法の素数 (17、23、および 397 が使用されているのを見てきました) を選択しているように見えますが、どのようにそれを選択し、正確には何のために使用するのでしょうか?
  • オブジェクトの存続期間中、ハッシュ コードが常に同じであることを確認する方法。(MSDN プロパティ #2)
    • 特に、等価性が可変フィールドに基づいている場合。(MSDN プロパティ #1)
  • 複雑な型のフィールドを処理する方法 (組み込みの C# 型ではない)。
    • 複雑なオブジェクトと構造体、配列、コレクション、リスト、辞書、ジェネリック型など。
    • たとえば、リストまたは辞書が読み取り専用であっても、その内容が読み取り専用であるとは限りません。
  • 継承されたクラスを処理する方法。
    • 何らかの方法でハッシュ コードに組み込む必要がありますbase.GetHashCode()か?
  • 技術的に怠惰で 0 を返すことはできますか? MSDN ガイドライン #3 を大幅に破りますが、少なくとも #1 と #2 が常に真であることを確認します :P
  • よくある落とし穴と落とし穴。
于 2009-09-04T12:17:55.880 に答える
8

GetHashCode の実装でよく見られるマジック ナンバーは何ですか?

それらは素数です。素数はハッシュコードスペースの使用を最大化するため、ハッシュコードの作成に素数が使用されます。

具体的には、小さな素数 3 から始めて、結果の下位ニブルのみを考慮します。

  • 3 * 1 = 3 = 3(mod 8) =0011
  • 3 * 2 = 6 = 6(mod 8) =1010
  • 3 * 3 = 9 = 1(mod 8) =0001
  • 3 * 4 = 12 = 4(mod 8) =1000
  • 3 * 5 = 15 = 7(mod 8) =1111
  • 3 * 6 = 18 = 2(mod 8) =0010
  • 3 * 7 = 21 = 5(mod 8) =1001
  • 3 * 8 = 24 = 0(mod 8) =0000
  • 3 * 9 = 27 = 3(mod 8) =0011

そして、最初からやり直します。しかし、素数の連続した倍数が、反復を開始する前に、ニブル内の可能なすべてのビット順列を生成したことに気付くでしょう。任意の素数と任意のビット数で同じ効果を得ることができるため、素数はランダムに近いハッシュ コードの生成に最適です。上記の例の 3 のような小さな素数ではなく、大きな素数がよく見られる理由は、ハッシュ コードのビット数が多い場合、小さな素数を使用して得られる結果は疑似乱数でさえないためです。オーバーフローが発生するまでシーケンスを増やします。ランダム性を最適化するには、係数が小さくないことが保証されない限り、かなり小さい係数でオーバーフローが発生する素数を使用する必要があります。

関連リンク：

于 2009-09-04T12:20:30.547 に答える
3

Eric Lippert によるGetHashCode のガイドラインとルールを確認してください。

于 2011-03-01T13:35:47.387 に答える
3

なぜオーバーライドする必要があるのobject.GetHashCode()ですか?

次のプロパティは常に true のままにする必要があるため、このメソッドをオーバーライドすることは重要です。

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

JaredParが平等の実装に関するブログ投稿で述べているように、その理由は次のとおりです。

多くのクラスは、ハッシュ コードを使用してオブジェクトを分類します。特に、ハッシュ テーブルと辞書は、ハッシュ コードに基づいてオブジェクトをバケットに配置する傾向があります。オブジェクトがハッシュ テーブルに既に存在するかどうかを確認する場合、まずバケット内でオブジェクトを探します。2 つのオブジェクトが等しいが、ハッシュ コードが異なる場合、それらは異なるバケットに配置される可能性があり、ディクショナリはオブジェクトの検索に失敗します。

関連リンク：

于 2009-09-04T11:53:52.793 に答える
2

A) デフォルトの参照の等価性の代わりに値の等価性を採用する場合は、Equals と GetHashCode の両方をオーバーライドする必要があります。後者では、2 つのオブジェクト参照は、両方が同じオブジェクト インスタンスを参照している場合に等しいと見なされます。前者では、異なるオブジェクトを参照していても値が同じであれば等しいと比較されます。たとえば、おそらく、Date、Money、および Point オブジェクトに対して値の等価性を採用する必要があります。

B) 値の等価性を実装するには、Equals と GetHashCode をオーバーライドする必要があります。どちらも、値をカプセル化するオブジェクトのフィールドに依存する必要があります。たとえば、Date.Year、Date.Month、Date.Day などです。または Money.Currency および Money.Amount; または Point.X、Point.Y、および Point.Z。operator ==、operator !=、operator <、operator > のオーバーライドも検討する必要があります。

C) ハッシュコードは、オブジェクトの存続期間を通じて一定である必要はありません。ただし、ハッシュのキーとして参加している間は不変のままでなければなりません。Dictionary の MSDN doco から: 「オブジェクトが Dictionary<(Of <(TKey, TValue>)>) でキーとして使用されている限り、そのハッシュ値に影響を与えるような方法で変更してはなりません。」キーの値を変更する必要がある場合は、エントリをディクショナリから削除し、キーの値を変更して、エントリを置き換えます。

D）IMO、値オブジェクト自体が不変であれば、生活が簡素化されます。

于 2010-05-04T21:06:59.220 に答える
2

そのタイプのオブジェクトに対して意味のある同等の尺度がある場合はいつでも、それをオーバーライドする必要があります (つまり、Equals をオーバーライドします)。なんらかの理由でオブジェクトがハッシュ化されないことがわかっている場合は、そのままにしておくことができますが、これを事前に知ることはまずありません。

等しいと見なされる 2 つのオブジェクトは同じハッシュ コードを持つ必要があるため、ハッシュは、等しいことを定義するために使用されるオブジェクトのプロパティのみに基づく必要があります。一般に、通常は次のようにします。


public override int GetHashCode()
{
    int mc = //magic constant, usually some prime
    return mc * prop1.GetHashCode() * prop2.GetHashCode * ... * propN.GetHashCode();
}

通常、各プロパティのハッシュコード関数が同じであると仮定すると、値を乗算するとかなり均一な分布が生成されると想定しますが、これは間違っている可能性があります。このメソッドを使用すると、オブジェクトの等価性を定義するプロパティが変更された場合、ハッシュ コードも変更される可能性が高くなります。これは、質問の定義 #2 を考えると許容されます。また、すべてのタイプを統一された方法で処理します。

すべてのインスタンスに対して同じ値を返すこともできますが、これにより、ハッシュを使用するアルゴリズム (辞書など) が非常に遅くなります。基本的にすべてのインスタンスが同じバケットにハッシュされ、ルックアップが期待値ではなく O(n) になります。 O(1)。もちろん、これはルックアップにそのような構造を使用する利点を無効にします。

于 2009-09-04T11:45:37.397 に答える
1

いつオーバーライドしますobject.GetHashCode()か?

MSDNが述べているように:

Equals をオーバーライドする型は、 GetHashCode もオーバーライドする必要があります。そうしないと、Hashtable が正しく機能しない可能性があります。

関連リンク：

于 2009-09-04T11:36:09.677 に答える
0

ハッシュ コードのベースとなるフィールドは? 不変フィールドのみにある必要がある場合、可変フィールドのみがある場合はどうなりますか?

不変フィールドのみに基づく必要はありません。equals メソッドの結果を決定するフィールドに基づいています。

于 2010-01-14T13:34:04.983 に答える
0

オブジェクトの存続期間中、ハッシュ コードが常に同じであることを確認する方法。(MSDN プロパティ #2) 特に、等価性が可変フィールドに基づいている場合。(MSDN プロパティ #1)

プロパティ＃2を誤解しているようです。ハッシュコードは、オブジェクトの存続期間中ずっと同じである必要はありません。equals メソッドの結果を決定する値が変更されない限り、同じままである必要があります。したがって、論理的には、これらの値のみに基づいてハッシュコードを作成します。それなら問題ないはずです。

于 2010-01-14T13:34:26.217 に答える
-2 
public override int GetHashCode()
{
    return IntProp1 ^ IntProp2 ^ StrProp3.GetHashCode() ^ StrProp4.GetHashCode ^ CustomClassProp.GetHashCode;
}

customClass のGetHasCodeメソッドでも同じことを行います。魅力のように機能します。

于 2009-09-19T05:38:53.347 に答える