[解決済み] .NETのIEqualityComparer<T>のGetHashCodeの役割は何ですか？

質問内容

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();
    }
}

2つのBoxオブジェクトを比較するには、Equalsメソッドの実装で十分ではないでしょうか？そこで、オブジェクトの比較に使用されるルールをフレームワークに伝えるのです。なぜGetHashCodeが必要なのでしょうか？

ありがとうございます。

ルシアン

どのように解決するのですか？

まず、背景を少し...

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

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

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

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

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 という同じハッシュコードになります。この場合、同じハッシュコードになる理由は、^ (ビットごとの排他的論理和) 演算子を使用しているため、100^100 は 1000^1000 と同様に 0 で打ち消されるからです。2 つの異なるオブジェクトが同じキーを持つとき、私たちはそれを衝突と呼びます。

同じハッシュコードを持つ 2 つの Key-Value ペアを辞書に追加すると、それらは両方とも同じバケツに格納されます。そのため、Valueを取得したいときは、Keyに対してGetHashCodeメソッドを呼び出し、バケットを探します。バケツには複数の値があるため、辞書はバケツ内のすべての Key/Value ペアを繰り返し、Key の Equals メソッドを呼び出して正しいものを探します。

投稿された例では、2 つのボックスは同等であるため、Equals メソッドは true を返します。この場合、辞書には 2 つの同じ Keys があるため、例外がスローされます。

TLDR

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