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 が必要なのはなぜでしょうか。
ありがとう。
ルシアン
ベストアンサー1
まず少し背景を説明します...
.NET のすべてのオブジェクトには、Equals メソッドと GetHashCode メソッドがあります。
Equals メソッドは、1 つのオブジェクトを別のオブジェクトと比較し、2 つのオブジェクトが同等かどうかを確認するために使用されます。
GetHashCode メソッドは、オブジェクトの 32 ビット整数表現を生成します。オブジェクトに格納できる情報量に制限はないため、特定のハッシュ コードは複数のオブジェクトで共有されます。そのため、ハッシュ コードは必ずしも一意であるとは限りません。
ディクショナリは、メモリ使用量が増える代わりに、追加/削除/取得操作のコストが (多かれ少なかれ) 一定になるという、非常に優れたデータ構造です。ただし、反復処理には適していません。内部的には、ディクショナリには、値を格納できるバケットの配列が含まれています。ディクショナリにキーと値を追加すると、キーに対して GetHashCode メソッドが呼び出されます。返されるハッシュコードは、キー/値のペアを格納するバケットのインデックスを決定するために使用されます。
値にアクセスする場合は、キーを再度渡します。キーに対して GetHashCode メソッドが呼び出され、値を含むバケットが検索されます。
When an IEqualityComparer is passed into the constructor of a dictionary, the IEqualityComparer.Equals and IEqualityComparer.GetHashCode methods are used instead of the methods on the Key objects.
Now to explain why both methods are necessary, consider this example:
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");
Using the BoxEqualityComparer.GetHashCode method in your example, both of these boxes have the same hashcode - 100^100^25 = 1000^1000^25 = 25 - even though they are clearly not the same object. The reason that they are the same hashcode in this case is because you are using the ^ (bitwise exclusive-OR) operator so 100^100 cancels out leaving zero, as does 1000^1000. When two different objects have the same key, we call that a collision.
When we add two Key/Value pairs with the same hashcode to a dictionary, they are both stored in the same bucket. So when we want to retrieve a Value, the GetHashCode method is called on our Key to locate the bucket. Since there is more than one value in the bucket, the dictionary iterates over all of the Key/Value pairs in the bucket calling the Equals method on the Keys to find the correct one.
In the example that you posted, the two boxes are equivalent, so the Equals method returns true. In this case the dictionary has two identical Keys, so it throws an exception.
TLDR
So in summary, the GetHashCode method is used to generate an address where the object is stored. So a dictionary doesn't have to search for it. It just computes the hashcode and jumps to that location. The Equals method is a better test of equality, but cannot be used to map an object into an address space.