27

からValueType.cs

**アクション: ハッシュコードを返すアルゴリズムは少し複雑です。私たちが見ます
** 最初の非静的フィールドのハッシュコードを取得します。タイプにない場合
** 非静的フィールド。型のハッシュコードを返します。私たちは取ることができません
** 静的メンバーのハッシュコード。そのメンバーが
** 元の型では、無限ループに陥ります。

KeyValuePair をディクショナリのキーとして使用していたときに (xml 属性名 (列挙型) とその値 (文字列) を格納していた)、今日これに悩まされ、すべてのフィールドに基づいてハッシュコードが計算されることを期待していました。しかし、実装によれば、キー部分のみを考慮していました。

例 (Linqpad からの c/p):

void Main()
{
    var kvp1 = new KeyValuePair<string, string>("foo", "bar");
    var kvp2 = new KeyValuePair<string, string>("foo", "baz");

    // true
    (kvp1.GetHashCode() == kvp2.GetHashCode()).Dump();
}

私が推測する最初の非静的フィールドは、宣言順の最初のフィールドを意味します。これは、何らかの理由でソース内の変数の順序を変更するときに問題を引き起こす可能性があり、それがコードを意味的に変更しないと信じています。

4

5 に答える 5

45

ValueType.GetHashCode() の実際の実装は、コメントと完全には一致しません。アルゴリズムには、高速と低速の 2 つのバージョンがあります。最初に、構造体に参照型のメンバーが含まれているかどうか、およびフィールド間にパディングがあるかどうかを確認します。パディングは、JIT コンパイラーがフィールドを整列させるときに作成される、構造体値内の空のスペースです。bool と int (3 バイト) を含む構造体にはパディングがありますが、int と int が含まれている場合はパディングがなく、ぴったりと収まります。

構造体値のすべてのビットはフィールド値に属するビットであるため、参照もパディングもなしで高速バージョンを実行できます。一度に 4 バイトを単純に xor します。すべてのメンバーを考慮した「適切な」ハッシュ コードが得られます。Point や Size のように、.NET フレームワークの多くの単純な構造型はこのように動作します。

そのテストに失敗すると、それは遅いバージョンを行います。これは、反射の道徳的同等物です。KeyValuePair<> には参照が含まれています。そして、コメントが言うように、これは最初の候補フィールドのみをチェックします。これは確かにパフォーマンスの最適化であり、時間の浪費を防ぎます。

はい、厄介な詳細であり、それほど広く知られていません. これは通常、コレクション コードが泥を吸い込んでいることに誰かが気付いたときに発見されます。

もう 1 つの耐え難い詳細: 高速バージョンには、構造体に decimal 型のフィールドが含まれている場合にバイトするバグがあります。値 12m と 12.0m は論理的には同じですが、同じビット パターンはありません。GetHashCode() は、それらが等しくないことを示します。ああ。

于 2010-10-01T19:43:47.050 に答える
35

更新: この回答は、(部分的に)私が書いたブログ記事の基礎であり、 の設計特性について詳しく説明していGetHashcodeます。興味深い質問をありがとう!


私はそれを実装しませんでしたし、実装した人々と話をしたこともありません。しかし、私はいくつかのことを指摘することができます。

(先に進む前に、ここでは特に、ハッシュ テーブルの内容が敵意のないユーザーによって選択されるハッシュ テーブルのバランスをとる目的で、ハッシュ コードについて話していることに注意してください。デジタル署名、冗長性チェック、または一部のユーザーがテーブル プロバイダーに対してサービス拒否攻撃を開始している場合に、ハッシュ テーブルの良好なパフォーマンスを保証することは、この議論の範囲を超えています)。

まず、Jon が正しく指摘しているように、与えられたアルゴリズムは GetHashCode の必要なコントラクトを実装します。目的には最適ではないかもしれませんが、合法です。必要なのは、等しいものを比較すると、ハッシュ コードが等しいことだけです。

では、その契約に加えて「持っていると便利なもの」は何ですか? 適切なハッシュ コードの実装は次のようになります。

1) 速い。とても早い!そもそもハッシュ コードの全体的なポイントは、ハッシュ テーブル内の比較的空のスロットをすばやく見つけることです。ハッシュ コードの O(1) 計算が実際に単純にルックアップを行うのにかかる O(n) 時間よりも遅い場合、ハッシュ コードの解決策は純損失です。

2) 与えられた入力の分布に対して、32 ビット整数の空間全体に十分に分布している。int 間の分布が悪いほど、ハッシュ テーブルは素朴な線形ルックアップのようになります。

では、これら 2 つの相反する目標が与えられた場合、任意の値型のハッシュ アルゴリズムをどのように作成しますか? 適切な分散を保証する複雑なハッシュ アルゴリズムに費やす時間は、無駄に費やされた時間です。

一般的な提案は、「すべてのフィールドをハッシュし、結果のハッシュ コードを XOR で結合する」です。しかし、それは疑問を投げかけています。2 つの 32 ビット int の XOR は、入力自体が非常に適切に分散されていて、互いに関連していない場合にのみ適切な分散が得られます。これはありそうもないシナリオです。

// (Updated example based on good comment!)
struct Control
{
    string name;
    int x;
    int y;
}

x と y が 32 ビット整数の範囲全体に十分に分布している可能性は? とても低い。両者が小さく互いに近いほど、オッズははるかに高くなります。互いに近い整数を xor すると、ほとんどのビットがゼロになります。

さらに、これはフィールド数で O(n) です。小さなフィールドがたくさんある値型は、ハッシュ コードの計算に比較的長い時間がかかります。

基本的に、ここでの状況は、ユーザーがハッシュ コードの実装を自分で提供しなかったということです。彼らは気にしないか、この型がハッシュテーブルのキーとして使用されることを期待していません。型に関するセマンティック情報がまったくない場合、どうするのが最善でしょうか? 最善の方法は、高速で、ほとんどの場合良い結果が得られるものです。

ほとんどの場合、異なる 2 つの構造体インスタンスは、フィールドの1 つだけでなく、ほとんどのフィールドで異なります。

ほとんどの場合、異なる 2 つの構造体インスタンスのフィールドには冗長性があるため、多くのフィールドのハッシュ値を結合すると、ハッシュ値のエントロピーが増加するのではなく減少する可能性があります。ハッシュ アルゴリズムは保存するように設計されています。

これを C# の匿名型の設計と比較してください。匿名型の場合、その型がテーブルのキーとして使用されている可能性が高いことがわかっています匿名型のインスタンス間で冗長性が生じる可能性が高いことはわかっています (それらはデカルト積またはその他の結合の結果であるため) したがって、すべてのフィールドのハッシュ コードを 1 つのハッシュ コードに結合します。計算されるハッシュ コードの数が多すぎるためにパフォーマンスが低下する場合は、匿名型ではなくカスタム ノミナル型を自由に使用できます。

于 2010-10-01T18:04:44.293 に答える
9

フィールドの順序が変更された場合でも、 の契約に従う必要がありGetHashCodeます。そのプロセスの存続期間内で、等しい値は等しいハッシュ コードを持ちます。

特に:

  • 等しくない値は、等しくないハッシュ コードを持つ必要はありません
  • ハッシュ コードはプロセス全体で一貫している必要はありません (実装を変更して再構築しても、すべてが機能するはずです。基本的に、ハッシュ コードを永続化するべきではありません)。

ここで、ValueType の実装が素晴らしいアイデアだと言っているわけではありません。さまざまな方法でパフォーマンスが低下しますが、実際に壊れているとは思いません。

于 2010-10-01T17:32:27.550 に答える
3

まあ、どの実装にも長所と短所がありGetHashCode()ます。これらはもちろん、独自のものを実装する際に検討するものですValueType.GetHashCode()が、具象型の実際の詳細がどうなるかについて多くの情報を持っていないという点で特に問題があります。もちろん、これは、抽象クラスや、状態に関してさらに多くを追加するクラスのベースになることを意図したクラスを作成しているときによく起こりますが、そのような場合、デフォルトの実装を使用するだけの明らかな解決策があります。object.GetHashCode()派生クラスがそこでオーバーライドすることを気にしない限り。

値型と参照型の主な違いは、ValueType.GetHashCode()スタックとヒープの実装の詳細について話すのが一般的であるにもかかわらず、値型の等価性は値に関連し、オブジェクト型の等価性は同一性に関連します (オブジェクトがオーバーライドによって異なる形式の等価性を定義し、Equals()参照GetHashCode()等価性の概念がまだ存在し、依然として有用である場合でも.

したがって、Equals()メソッドの実装は明らかです。2 つのオブジェクトが同じ型であることを確認し、同じ型である場合は、すべてのフィールドが等しいことも確認します (実際には、場合によってはビットごとの比較を行う最適化がありますが、それは同じ基本的な考え方に基づいた最適化です)。

何のためにするのかGetHashCode()? 完全な解決策はありません。彼らができることの 1 つは、すべてのフィールドで、ある種の複数してから追加するか、シフトしてから xor することです。それはおそらくかなり良いハッシュコードを与えるでしょうが、多くのフィールドがある場合は高価になる可能性があります(多くのフィールドを持つ値型を持つことは推奨されていないことを気にしないでください.実装者はそれらがまだ可能であることを考慮する必要があります.それが理にかなっている場合もあるかもしれませんが、正直なところ、それが理にかなっていて、それをハッシュすることも理にかなっているとは想像できません)。一部のフィールドがインスタンス間でめったに変わらないことを知っていれば、それらのフィールドを無視しても、非常に高速でありながら、非常に優れたハッシュコードを保持できます。最後に、彼らはほとんどのフィールドを無視することができ、無視しないフィールドの値がほとんどの場合変化することを期待します。

(インスタンス フィールドがない場合に何が行われるかは別の問題であり、かなり良い選択です。そのような値の型は、同じ型の他のすべてのインスタンスと等しく、それに一致するハッシュコードを持っています)。

したがって、最初のフィールドが同じである(または同じハッシュコードを返す)多くの値をハッシュしている場合、それはうまくいかない実装ですが、他の場合は他の実装がうまくいかないでしょう(Monoはすべてのフィールドのハッシュコードを一緒にxorし、あなたの場合は良く、他の場合は悪い)。

フィールドの順序を変更することは重要ではありません。ハッシュコードは、プロセスの存続期間中のみ有効であり、それを超えて永続化できるほとんどの場合には適していないことが明確に述べられているためです (一部のキャッシング状況で役立ちます)コードの変更後に正しく検出されなくても問題はありません)。

ですから、素晴らしいことではありませんが、完璧なものはありません。オブジェクトをキーとして使用する場合、「平等」が意味することの両面を常に考慮しなければならないことを示しています。あなたのケースでは、次のように簡単に修正できます。

public class KVPCmp<TKey, TValue> : IEqualityComparer<KeyValuePair<TKey, TValue>>, IEqualityComparer
{
  bool IEqualityComparer.Equals(object x, object y)
  {
      if(x == null)
        return y == null;
      if(y == null)
        return false;
      if(!(x is KeyValuePair<TKey, TValue>) || !(y is KeyValuePair<TKey, TValue>))
        throw new ArgumentException("Comparison of KeyValuePairs only.");
      return Equals((KeyValuePair<TKey, TValue>) x, (KeyValuePair<TKey, TValue>) y);
  }
  public bool Equals(KeyValuePair<TKey, TValue> x, KeyValuePair<TKey, TValue> y)
  {
      return x.Key.Equals(y.Key) && x.Value.Equals(y.Value);
  }
  public int GetHashCode(KeyValuePair<TKey, TValue> obj)
  {
      int keyHash = obj.GetHashCode();
      return ((keyHash << 16) | (keyHash >> 16)) ^ obj.Value.GetHashCode();
  }
  public int GetHashCode(object obj)
  {
      if(obj == null)
        return 0;
      if(!(obj is KeyValuePair<TKey, TValue>))
       throw new ArgumentException();
      return GetHashCode((KeyValuePair<TKey, TValue>)obj);
  }
}

ディクショナリを作成するときにこれをコンパレータとして使用すると、すべてがうまくいくはずです(実際にはジェネリックコンパレータメソッドのみが必要ですが、残りを残しても害はなく、場合によっては便利です)。

于 2010-10-01T17:59:05.987 に答える
0

非常に有益な回答をありがとうございました。その決定には何らかの理由が必要であることはわかっていましたが、それがより適切に文書化されていることを望みます. 私はフレームワークの v4 を使用できないため、 はありません。それが、構造体Tuple<>にピギーバックすることにした主な理由でしたKeyValuePair。しかし、私は手抜きはないと思います。改めまして、皆様ありがとうございました。

于 2010-10-02T14:15:56.443 に答える