18

次のコードを検討してください。

struct Vec2 : IEquatable<Vec2>
{
    double X,Y;

    public bool Equals(Vec2 other)
    {
        return X.Equals(other.X) && Y.Equals(other.Y);
    }

    public override bool Equals(object obj)
    {
        if (obj is Vec2)
        {
            return Equals((Vec2)obj);
        }
        return false;
    }

    // this will return the same value when X, Y are swapped
    public override int GetHashCode()
    {
        return X.GetHashCode() ^ Y.GetHashCode();
    }

}

double の等価性を比較するという会話 (これは単なるデモ コードです) を超えて、私が懸念しているのは、X と Y の値が入れ替わったときにハッシュの衝突が発生することです。例えば：

Vec2 A = new Vec2() { X=1, Y=5 };
Vec2 B = new Vec2() { X=5, Y=1 };

bool test1 = A.Equals(B);  // returns false;
bool test2 = A.GetHashCode() == B.GetHashCode() // returns true !!!!!

これは、辞書コレクションに大混乱をもたらすはずです。したがって、問題はGetHashCode()、結果が対称ではなく、ハッシュが衝突しないように、2、3、または 4 つの浮動小数点値の関数をどのようにプロパティ化するかです。

編集1：

Point不適切なx ^ y解決策を実装し、PointFラップしValueType.GetHashCode()ます。

Rectangle(((X ^ ((Y << 13) | (Y >> 19))) ^ ((Width << 26) | (Width >> 6))) ^ ((Height << 7) | (Height >> 25)))は、ハッシュ コードの非常に独特な表現を持っていますが、これは期待どおりに機能しているようです。

編集2：

「System.Double」には、各ビットが等しく重要であるとは見なされないため、優れた実装があります

public override unsafe int GetHashCode() //from System.Double
{
    double num = this;
    if (num == 0.0)
    {
        return 0;
    }
    long num2 = *((long*) &num);
    return (((int) num2) ^ ((int) (num2 >> 32)));
}
4

5 に答える 5

21

Jon skeet はこれをカバーしています:

オーバーライドされた System.Object.GetHashCode に最適なアルゴリズムは何ですか?

   public override int GetHashCode()
   {
       unchecked // Overflow is fine, just wrap
       {
           int hash = 17;
           // Suitable nullity checks etc, of course :)
           hash = hash * 23 + X.GetHashCode();
           hash = hash * 23 + Y.GetHashCode();
           return hash;
       }
   }

また、Equals(object)実装を次のように変更します。

return Equals(obj as FVector2);

ただし、これにより派生型が等しいと認識される可能性があることに注意してください。それを望まない場合は、ランタイム型を比較す​​る必要がありますother.GetType()(typeof(FVector2)そして nullity チェックを忘れないでください) 。それが構造体であることを指摘してくれてありがとう、LukH

Resharper には、等価性とハッシュ コードの優れたコード生成があります。

于 2011-03-07T15:22:11.997 に答える
0

ハッシュ コード アプローチは整数座標に対しては機能しますが、浮動小数点値に対しては推奨されません。浮動小数点座標を使用すると、ソートされたシーケンス構造を使用してポイント セット/プールを作成できます。

ソートされたシーケンスは、リーフ バージョンのバランスの取れたバイナリ ツリーです。

ここでのキーはポイント座標になります。

于 2015-01-08T02:46:01.883 に答える