152

IEqualityComparerインターフェイスのGetHashCodeメソッドの役割を理解しようとしています。

次の例はMSDNから抜粋したものです。

using System;
using System.Collections.Generic;
class Example {
    static void Main() {
        try {

            BoxEqualityComparer boxEqC = new BoxEqualityComparer();

            Dictionary<Box, String> boxes = new Dictionary<Box,
                                                string>(boxEqC);

            Box redBox = new Box(4, 3, 4);
            Box blueBox = new Box(4, 3, 4);

            boxes.Add(redBox, "red");
            boxes.Add(blueBox, "blue");

            Console.WriteLine(redBox.GetHashCode());
            Console.WriteLine(blueBox.GetHashCode());
        }
        catch (ArgumentException argEx) {

            Console.WriteLine(argEx.Message);
        }
    }
}

public class Box {
    public Box(int h, int l, int w) {
        this.Height = h;
        this.Length = l;
        this.Width = w;
    }
    public int Height { get; set; }
    public int Length { get; set; }
    public int Width { get; set; }
}

class BoxEqualityComparer : IEqualityComparer<Box> {

    public bool Equals(Box b1, Box b2) {
        if (b1.Height == b2.Height & b1.Length == b2.Length
                            & b1.Width == b2.Width) {
            return true;
        }
        else {
            return false;
        }
    }

    public int GetHashCode(Box bx) {
        int hCode = bx.Height ^ bx.Length ^ bx.Width;
        return hCode.GetHashCode();
    }
}

Equalsメソッドの実装は、2つのBoxオブジェクトを比較するのに十分ではありませんか？ここで、オブジェクトの比較に使用されるルールをフレームワークに通知します。GetHashCodeが必要なのはなぜですか？

ありがとう。

ルシアン

4

3 に答える 3

214

最初に少し背景を...

.NET のすべてのオブジェクトには、Equals メソッドと GetHashCode メソッドがあります。

Equals メソッドは、あるオブジェクトを別のオブジェクトと比較して、2 つのオブジェクトが等しいかどうかを確認するために使用されます。

GetHashCode メソッドは、オブジェクトの 32 ビット整数表現を生成します。オブジェクトに含めることができる情報の量に制限がないため、特定のハッシュ コードは複数のオブジェクトで共有されます。したがって、ハッシュ コードは必ずしも一意ではありません。

ディクショナリは、追加/削除/取得操作の (多かれ少なかれ) 一定のコストと引き換えに、より高いメモリ フットプリントを交換する、非常に優れたデータ構造です。ただし、反復処理には適していません。内部的には、ディクショナリには値を格納できるバケットの配列が含まれています。Key と Value をディクショナリに追加すると、GetHashCode メソッドが Key で呼び出されます。返されたハッシュコードは、キーと値のペアを格納するバケットのインデックスを決定するために使用されます。

Value にアクセスする場合は、もう一度 Key を渡します。Key に対して GetHashCode メソッドが呼び出され、Value を含むバケットが特定されます。

IEqualityComparer がディクショナリのコンストラクターに渡されると、Key オブジェクトのメソッドの代わりに IEqualityComparer.Equals および IEqualityComparer.GetHashCode メソッドが使用されます。

両方の方法が必要な理由を説明するために、次の例を考えてみましょう。

BoxEqualityComparer boxEqC = new BoxEqualityComparer(); 

Dictionary<Box, String> boxes = new Dictionary<Box, string>(boxEqC); 

Box redBox = new Box(100, 100, 25);
Box blueBox = new Box(1000, 1000, 25);

boxes.Add(redBox, "red"); 
boxes.Add(blueBox, "blue");

あなたの例で BoxEqualityComparer.GetHashCode メソッドを使用すると、これらのボックスは両方とも同じハッシュコード - 100^100^25 = 1000^1000^25 = 25 - であっても、明らかに同じオブジェクトではありません。この場合、それらが同じハッシュコードである理由は、^ (ビット単位の排他的 OR) 演算子を使用しているためで、100^100 はゼロを残してキャンセルされ、1000^1000 も同様です。2 つの異なるオブジェクトが同じキーを持つ場合、それを衝突と呼びます。

同じハッシュコードを持つ 2 つのキーと値のペアを辞書に追加すると、それらは両方とも同じバケットに格納されます。したがって、Value を取得する場合は、Key で GetHashCode メソッドを呼び出してバケットを見つけます。バケットには複数の値があるため、ディクショナリはバケット内のすべてのキーと値のペアを繰り返し処理し、キーの Equals メソッドを呼び出して正しい値を見つけます。

投稿した例では、2 つのボックスは同等であるため、Equals メソッドは true を返します。この場合、ディクショナリには 2 つの同一のキーがあるため、例外がスローされます。

TLDR

つまり、GetHashCode メソッドを使用して、オブジェクトが格納されているアドレスを生成します。したがって、辞書はそれを検索する必要はありません。ハッシュコードを計算してその場所にジャンプするだけです。Equals メソッドは同等性のより優れたテストですが、オブジェクトをアドレス空間にマップするために使用することはできません。

于 2010-11-04T12:46:41.117 に答える
9

GetHashCodeはディクショナリコレクションで使用され、オブジェクトを格納するためのハッシュを作成します。IEqualtyComparerとGetHashCode を使用する理由と方法についてのすばらしい記事がありますhttp://dotnetperls.com/iequalitycomparer

于 2010-11-04T09:47:12.283 に答える
5

は、保存されているすべてのキーに対してDictionary<TKey,TValue>そのGetValueメソッドと同様のメソッドを呼び出して、探しているキーと一致するかどうかを確認することができますが、それは非常に遅くなります。代わりに、多くのハッシュベースのコレクションと同様に、ほとんどの一致しない値を考慮から迅速に除外するEqualsことに依存しています。GetHashCodeシーク対象のアイテムを呼び出すGetHashCodeと 42 が返され、コレクションに 53,917 のアイテムがあり、そのうちの 53,914GetHashCodeのアイテムを呼び出すと 42 以外の値が返された場合、シークされているアイテムと比較する必要があるのは 3 つのアイテムだけです。残りの 53,914 は無視しても問題ありません。

GetHashCodeaが an に含まれる理由は、辞書の消費者が、通常はお互いを同等と見なさないIEqualityComparer<T>同等のオブジェクトと見なしたい可能性を考慮に入れるためです。最も一般的な例は、文字列をキーとして使用したいが、大文字と小文字を区別しない比較を使用したい呼び出し元です。これを効率的に機能させるために、ディクショナリには、"Fox" と "FOX" に対して同じ値を生成する何らかの形式のハッシュ関数が必要ですが、できれば "box" または "zebra" に対して別の値を生成します。に組み込まれているメソッドはそのようには機能しないため、辞書はそのようなメソッドを別の場所から取得する必要があります。GetHashCodeStringIEqualityComparer<T>Equals"Fox" と "FOX" を同一のものと見なしますが、"box" や "zebra" とは見なしません。

于 2015-03-18T17:49:00.453 に答える