10

基本的に、私はこれまでのところ以下を持っています：

class Foo {
    public override bool Equals(object obj)
    {
        Foo d = obj as Foo ;
        if (d == null)
            return false;

        return this.Equals(d);
    }

    #region IEquatable<Foo> Members

    public bool Equals(Foo other)
    {
        if (this.Guid != String.Empty && this.Guid == other.Guid)
            return true;
        else if (this.Guid != String.Empty || other.Guid != String.Empty)
            return false;

        if (this.Title == other.Title &&
            this.PublishDate == other.PublishDate &&
            this.Description == other.Description)
            return true;

        return false;
    }
}

したがって、問題は次のとおりですGuid。一意の識別子である必須ではないフィールドがあります。これが設定されていない場合は、2 つのオブジェクトが等しいかどうかを判断する試みとして、精度の低いメトリックに基づいて等しいかどうかを判断する必要があります。これはうまくいきますが、GetHashCode()面倒になります...どうすればいいですか？単純な実装は次のようになります。

public override int GetHashCode() {
    if (this.Guid != String.Empty)
        return this.Guid.GetHashCode();

    int hash = 37;
    hash = hash * 23 + this.Title.GetHashCode();
    hash = hash * 23 + this.PublishDate.GetHashCode();
    hash = hash * 23 + this.Description.GetHashCode();
    return hash;
}

しかし、2 種類のハッシュが衝突する可能性はどのくらいでしょうか? 確かに、そうなるとは思いません1 in 2 ** 32。これは悪い考えですか? もしそうなら、どうすればいいですか?

4

2 に答える 2

10

カスタム クラスの非常に簡単なハッシュ コード メソッドは、各フィールドのハッシュ コードをビット単位で XOR することです。次のように簡単にできます。

int hash = 0;
hash ^= this.Title.GetHashCode();
hash ^= this.PublishDate.GetHashCode();
hash ^= this.Description.GetHashCode();
return hash;

上記のリンクから：

XOR には、次の優れたプロパティがあります。

  • 計算の順序には依存しません。
  • ビットを「無駄にする」ことはありません。コンポーネントの 1 つでも 1 ビットでも変更すると、最終的な値が変更されます。
  • 最も原始的なコンピューターでも 1 サイクルで済みます。
  • 一様分布を維持します。組み合わせた 2 つのピースが均一に分布している場合、組み合わせは均一になります。つまり、ダイジェストの範囲を狭帯域に崩す傾向がありません。

フィールドに重複する値があると予想される場合、XOR はうまく機能しません。重複した値は XOR されると互いに相殺されるからです。この場合、問題にならない 3 つの無関係なフィールドを一緒にハッシュしているためです。

于 2009-07-02T01:53:11.663 に答える
5

あなたが使用することを選択したアプローチに問題はないと思います。ハッシュの衝突について「あまりにも多く」心配することは、ほとんどの場合、問題を考えすぎていることを示しています。ハッシュが異なる可能性が高い限り、問題はありません。

Description最終的には、ほとんどの場合、オブジェクトがタイトルと発行日（本？）に基づいて区別できると期待できる場合は、とにかくハッシュからを除外することを検討することもできます。

ハッシュ関数のGUIDを完全に無視することを検討し、それをEquals実装でのみ使用して、ハッシュクラッシュのありそうもない（？）ケースを明確にすることもできます。

于 2009-07-02T02:10:39.210 に答える