7

次の比較ロジックのハッシュコード関数を記述できますか？

My（A、B、C）の少なくとも2つのプロパティが一致する場合、の2つのインスタンスは等しくなります。

Equalsの部分は単純ですが、ハッシュコードの部分に困惑していて、それが不可能かもしれないと思っている部分があります。

class MyOtherComparer : IEqualityComparer<My>
{
    public bool Equals(My x, My y)
    {
        if (Object.ReferenceEquals(x, y)) 
            return true;      

        if (Object.ReferenceEquals(x, null) || Object.ReferenceEquals(y, null)) 
            return false;

        int matches = 0;

        if(x.A == y.A) matches++;

        if(x.B == y.B) matches++;

        if(x.C == y.C) matches++;

        // match on two out of three
        return  (matches > 1)
    }

    // If Equals() returns true for a pair of objects 
    // then GetHashCode() must return the same value for these objects.
    public int GetHashCode(My x)
    {
       // ???
    }
}

更新：Reed Copseyによる正解に加えて、ファジー比較の一般的な有用性に関する非常に重要な点がEthan Brownによって明確に述べられています。この質問/回答の根底にあるものを完全に理解するには、彼の回答も参照してください。

4

6 に答える 6

5

はい、可能です。最も単純な実装は、常に定数を返すことです。 

public int GetHashCode(My x) 
{ 
   return 0;
}

GetHashCodeのドキュメントには次のように記載されています。

Equals メソッドが 2 つのオブジェクト x と y に対して true を返す場合、x の GetHashCode メソッドによって返される値が y に対して返される値と等しくなければならないことを保証する実装が必要です。

ただし、等しくない 2 つのオブジェクトに対して同じハッシュ コードを返すことは完全に自由です。

そうは言っても、多くのハッシュ衝突が発生するため、一部のアルゴリズムのパフォーマンスが低下する可能性があります。ただし、奇数/一意の等価性チェックの性質を考えると、これが必要になる場合があります。

いずれにせよ、これは問題になることに注意してください。ロジックを考えると、 wherecomparer.Equals(foo, bar)==trueとcomparer.Equals(foo, baz)==truebutの 3 つのオブジェクトを持つことができますcomparer.Equals(baz, bar)==false。これは、 が使用される多くの場合に問題になる可能性がありIEqualityComparer<T>ます。

于 2012-06-04T17:52:34.137 に答える
1

ハッシュ コードは、2 つの等しいオブジェクトに対して同じである必要がありますが、2 つの異なるオブジェクトに対して異なる必要はありません。消費者を満足させるためにすべてのオブジェクトに対して同じ値を返すことができますがIEqualityComparer、あなたの状況でハッシュから速度の利点を得る方法はありません。

于 2012-06-04T17:52:07.390 に答える
1

次の比較ロジックのハッシュ コード関数を記述できますか?

はい。いつでもハッシュコードを書くことができます。問題は、それがどれほど効率的かということです。何があっても、いつでも次のことができます。

public int GetHashCode()
{
  return 0;
}

常に機能しますが、恐ろしく*非効率的です*。

于 2012-06-04T17:53:33.053 に答える
1

2 つのオブジェクト A、B があるとします。それぞれにプロパティ p1、p2、および p3 があります。A.p1 == B.p1 と A.p3 == B.p3 を仮定すると、ハッシュ関数が p2 に依存する場合、A と B で異なるため、等しくはなりません。p1 と p3 に基づいてハッシュ関数を計算する場合、ハッシュ関数が正しいハッシュ値を返さない多くの例があり、多くの等しいオブジェクトは等しくありません。可変機能はあり得ないと思います。定数を使用できますが、それを辞書またはハッシュ テーブルのハッシュ キーとして使用する場合、O(1) ほどの複雑さは得られません。

于 2012-06-04T17:56:48.780 に答える
1

非定数ハッシュ関数に到達する際の主な問題は、等価性を超えた推移性を保証できないことです。通常、平等は推移的と見なされます。つまり、A=B および B=C は、A=C であることを意味します (これは、A、B、および C がすべて同じハッシュ コードを持つことをさらに意味します)。ただし、平等の定義では、A=B、B=C、および A!=C にすることができます。理想的には、等しくない要素のハッシュ コードは異なるため、A と C のハッシュ コードは異なります。しかし、どちらも B に等しいため、それはできません。したがって、すべて同じハッシュ コードを持つ必要があります。

非定数ハッシュ関数に到達できる唯一の方法は、コレクション全体について何かを知っている場合です。ビン内の各要素がビン内の他の要素と等しい「等値ビン」にコレクションを分割する必要があります (1 つのビンの可能性を含む)。このパーティショニングが完了したら、それを使用して、ハッシュ コードを生成するための非定数アルゴリズム (複数のビンを取得すると仮定) を生成できます。

等値ビンの考え方については、そのようなビンの構成が多数存在する可能性があるということです。選択基準として、ビンの数を最大化することをお勧めします (ハッシュテーブル ルックアップのパフォーマンスを向上させるため)。変性ケース (Reed Copsey の正解で示されているように) は、すべてを同じビンに入れることです (ただし、以下のコメントで supercat が指摘しているように、「等値ビン」という名前は誤解を招きます)。これは、ハッシュ値の制約のいずれにも違反しませんが、値が非縮退分割を生成することを期待するアルゴリズムのパフォーマンスの低下につながります。

以下で supercat が指摘しているように、ハッシュ値の制約を満たすためには、次のことが真でなければなりません: 2 つの要素が 2 つの異なるビンにある場合、それらは等しくてはなりません (ただし、同じビンにある 2 つの要素が等しい必要はありません)。 .

于 2012-06-04T18:17:10.357 に答える
0

あなたの本当の問題は、Except 拡張メソッドを扱っていることを見て、実際には答えではありませんが、何かを提案することにしました。

public class EqualityComparer<T> : IEqualityComparer<T>
{
    private readonly Func<T, T, bool> _comparer;
    private readonly Func<T, int> _hashCoder;

    public EqualityComparer(Func<T, T, bool> comparer, Func<T, int> hashCoder = null)
    {
        if (comparer == null)
        {
            throw new ArgumentNullException("comparer");
        }

        this._comparer = comparer;
        this._hashCoder = hashCoder ?? (x => 0);
    }

    public bool Equals(T x, T y)
    {
        return this._comparer(x, y);
    }

    public int GetHashCode(T obj)
    {
        return this._hashCoder(obj);
    }
}

そして、次のように使用できます。

arr1.Except(arr2, new EqualityComparer<dynamic>((x, y) =>
     {
         if (ReferenceEquals(x, y))
             return true;

         if (ReferenceEquals(x, null) ||
             ReferenceEquals(y, null))
             return false;

         var matches = 0;

         if (x.A == y.A) matches++;
         if (x.B == y.B) matches++;
         if (x.C == y.C) matches++;

         return (matches > 1);
     }));
于 2012-06-04T18:21:46.160 に答える