.netのiequalitycomparer でのGethashcodeの役割は何ですか?
-
28-09-2019 - |
質問
インターフェイスIequalityCompererの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つのボックスオブジェクトを比較するのに十分ではありませんか?それが、オブジェクトを比較するためにルールを使用したフレームワークを伝える場所です。 GethashCodeが必要なのはなぜですか?
ありがとう。
ルシアン
解決
最初に少しの背景...
.NET内のすべてのオブジェクトには、等しいメソッドとGethashCodeメソッドがあります。
Equalsメソッドは、1つのオブジェクトを別のオブジェクトと比較するために使用されます - 2つのオブジェクトが同等であるかどうかを確認します。
GethashCodeメソッドは、オブジェクトの32ビット整数表現を生成します。オブジェクトに含まれる情報の量に制限がないため、特定のハッシュコードは複数のオブジェクトによって共有されます。したがって、ハッシュコードは必ずしも一意ではありません。
辞書は、操作を追加/削除/取得するための(多かれ少なかれ)一定のコストと引き換えに、より高いメモリフットプリントを交換する非常にクールなデータ構造です。しかし、反復するのは貧弱な選択です。内部的には、辞書には、値を保存できるバケツの配列が含まれています。辞書にキーと値を追加すると、gethashcodeメソッドがキーに呼び出されます。返されたハッシュコードは、キー/値ペアを保存するバケットのインデックスを決定するために使用されます。
値にアクセスしたい場合は、キーをもう一度渡します。 GethashCodeメソッドはキーで呼び出され、値を含むバケットが配置されます。
IequalityComparerが辞書のコンストラクターに渡されると、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-は、明らかに同じオブジェクトではありません。この場合、それらが同じハッシュコードである理由は、1000^1000と同様に、^(bitwise duclusive-or)演算子を使用しているため、ゼロを離れる100^100がキャンセルしているためです。 2つの異なるオブジェクトが同じキーを持っている場合、それを衝突と呼びます。
辞書に同じハッシュコードを持つ2つのキー/値ペアを追加すると、どちらも同じバケットに保存されます。したがって、値を取得したい場合、GethashCodeメソッドがバケツを見つけるためにキーで呼び出されます。バケットには複数の値があるため、辞書はバケツ内のすべてのキー/値のペアを反復し、キーの等しいメソッドを呼び出して正しいものを見つけます。
投稿した例では、2つのボックスが同等であるため、等しいメソッドがtrueを返します。この場合、辞書には2つの同一のキーがあるため、例外をスローします。
tldr
そのため、要約すると、GethashCodeメソッドを使用して、オブジェクトが保存されるアドレスを生成します。したがって、辞書はそれを検索する必要はありません。ハッシュコードを計算し、その場所にジャンプします。 Equalsメソッドは平等のより良いテストですが、オブジェクトをアドレス空間にマッピングするために使用することはできません。
それが役立つことを願っています
他のヒント
GethashCode 辞書コレクションで使用され、オブジェクトを保存するためのハッシュを作成します。これが素晴らしい記事です理由と使用方法 iequaltycomperer と GethashCode http://dotnetperls.com/iequalitycomparer
aは可能ですが Dictionary<TKey,TValue>
それを持っている GetValue
同様の方法が呼び出されます Equals
保存されているすべてのキーで、求められているものと一致するかどうかを確認すると、それは非常に遅いでしょう。代わりに、多くのハッシュベースのコレクションのように、それは GetHashCode
ほとんどの非一致値を考慮から迅速に除外します。電話する場合 GetHashCode
求められているアイテムには42が得られ、コレクションには53,917のアイテムがありますが、呼び出します GetHashCode
53,914のアイテムが42以外の値を生成し、求められているものと比較する必要があるアイテムは3つだけです。他の53,914は安全に無視される場合があります。
理由a GetHashCode
に含まれています IEqualityComparer<T>
辞書の消費者が通常の等しいオブジェクトと見なしたいと思うかもしれない可能性を許すことです いいえ お互いを平等だと考えてください。最も一般的な例は、文字列をキーとして使用したいが、ケース非感受性比較を使用したい発信者です。その作業を効率的にするために、辞書には「フォックス」と「フォックス」と同じ値をもたらすが、「ボックス」または「ゼブラ」に何か他のものを生成する何らかの形のハッシュ関数が必要です。以来 GetHashCode
内に組み込まれています String
そのようには機能しません、辞書は他の場所からそのような方法を取得する必要があり、 IEqualityComparer<T>
そのようなハッシュコードの必要性は非常に強く関連しているため、最も論理的な場所です Equals
「フォックス」と「キツネ」を互いに同一と見なしますが、「ボックス」や「ゼブラ」ではないと見なす方法。