C# はオブジェクトのハッシュ コードをどのように計算するのでしょうか?
https://stackoverflow.com/questions/102690
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
この質問は、次の議論から生まれました。 タプル.
タプルが持つべきハッシュコードについて考え始めました。KeyValuePair クラスをタプルとして受け入れる場合はどうなるでしょうか?GetHashCode() メソッドをオーバーライドしないため、おそらくその「子」のハッシュ コードを認識しないでしょう...したがって、ランタイムは Object.GetHashCode() を呼び出しますが、実際のオブジェクト構造は認識されません。
次に、オーバーロードされた GetHashCode() と Equals() により、実際には Equal である何らかの参照型の 2 つのインスタンスを作成できます。そして、それらをタプルの「子」として使用して、辞書を「騙す」ことができます。
でもそれはうまくいきません！ランタイムは何らかの方法でタプルの構造を認識し、クラスのオーバーロードされた GetHashCode を呼び出します。
どのように機能するのでしょうか?Object.GetHashCode() によって行われる分析は何ですか?
複雑なキーを使用すると、悪いシナリオでパフォーマンスに影響を与える可能性がありますか?（おそらく不可能なシナリオです...それでも）
次のコードを例として考えてみましょう。
namespace csharp_tricks
{
class Program
{
class MyClass
{
int keyValue;
int someInfo;
public MyClass(int key, int info)
{
keyValue = key;
someInfo = info;
}
public override bool Equals(object obj)
{
MyClass other = obj as MyClass;
if (other == null) return false;
return keyValue.Equals(other.keyValue);
}
public override int GetHashCode()
{
return keyValue.GetHashCode();
}
}
static void Main(string[] args)
{
Dictionary<object, object> dict = new Dictionary<object, object>();
dict.Add(new KeyValuePair<MyClass,object>(new MyClass(1, 1), 1), 1);
//here we get the exception -- an item with the same key was already added
//but how did it figure out the hash code?
dict.Add(new KeyValuePair<MyClass,object>(new MyClass(1, 2), 1), 1);
return;
}
}
}
アップデート 私の答えで以下に述べたように、これについての説明が見つかったと思います。その主な成果は次のとおりです。
- キーとそのハッシュコードには注意してください:-)
- 複雑な辞書キーの場合は、Equals() と GetHashCode() を正しくオーバーライドする必要があります。
解決 4
どうやら今、手がかりが得られたようです。
KeyValuePair は参照型だと思っていましたが、そうではなく、構造体です。したがって、ValueType.GetHashCode() メソッドを使用します。MSDN には次のように書かれています。「戻り値の計算には、派生型の 1 つ以上のフィールドが使用されます。」
実際の参照型を「タプルプロバイダー」として使用すると、辞書 (または自分自身...) を騙すことになります。
using System.Collections.Generic;
namespace csharp_tricks
{
class Program
{
class MyClass
{
int keyValue;
int someInfo;
public MyClass(int key, int info)
{
keyValue = key;
someInfo = info;
}
public override bool Equals(object obj)
{
MyClass other = obj as MyClass;
if (other == null) return false;
return keyValue.Equals(other.keyValue);
}
public override int GetHashCode()
{
return keyValue.GetHashCode();
}
}
class Pair<T, R>
{
public T First { get; set; }
public R Second { get; set; }
}
static void Main(string[] args)
{
var dict = new Dictionary<Pair<int, MyClass>, object>();
dict.Add(new Pair<int, MyClass>() { First = 1, Second = new MyClass(1, 2) }, 1);
//this is a pair of the same values as previous! but... no exception this time...
dict.Add(new Pair<int, MyClass>() { First = 1, Second = new MyClass(1, 3) }, 1);
return;
}
}
}
他のヒント
GetHashcode() と Equals() を可変クラスでオーバーライドしないでください。不変クラスまたは構造体でのみオーバーライドしてください。そうしないと、キーとして使用されるオブジェクトを変更すると、ハッシュ テーブルが正しく機能しなくなります (キーオブジェクトが変更された後にキーに関連付けられた値を取得します)
また、ハッシュ テーブルは、オブジェクトを識別するためにハッシュコードを使用しません。キー オブジェクト自体を識別子として使用します。ハッシュ テーブルにエントリを追加するために使用されるすべてのキーが異なるハッシュコードを返す必要はありませんが、そうすることが推奨されます。そうしないとパフォーマンスが低下します。大いに苦しむ。
以下は、クワッド タプル (内部に 4 つのタプル コンポーネントを含む) の適切なハッシュと等価性の実装です。このコードにより、HashSet および辞書でこの特定のタプルが適切に使用されるようになります。
主題の詳細 (ソースコードを含む) ここ.
注記 の使用法 チェックされていない キーワード (オーバーフローを避けるため) と、obj が null の場合に NullReferenceException をスローする (基本メソッドで要求される)
public override bool Equals(object obj)
{
if (ReferenceEquals(null, obj))
throw new NullReferenceException("obj is null");
if (ReferenceEquals(this, obj)) return true;
if (obj.GetType() != typeof (Quad<T1, T2, T3, T4>)) return false;
return Equals((Quad<T1, T2, T3, T4>) obj);
}
public bool Equals(Quad<T1, T2, T3, T4> obj)
{
if (ReferenceEquals(null, obj)) return false;
if (ReferenceEquals(this, obj)) return true;
return Equals(obj.Item1, Item1)
&& Equals(obj.Item2, Item2)
&& Equals(obj.Item3, Item3)
&& Equals(obj.Item4, Item4);
}
public override int GetHashCode()
{
unchecked
{
int result = Item1.GetHashCode();
result = (result*397) ^ Item2.GetHashCode();
result = (result*397) ^ Item3.GetHashCode();
result = (result*397) ^ Item4.GetHashCode();
return result;
}
}
public static bool operator ==(Quad<T1, T2, T3, T4> left, Quad<T1, T2, T3, T4> right)
{
return Equals(left, right);
}
public static bool operator !=(Quad<T1, T2, T3, T4> left, Quad<T1, T2, T3, T4> right)
{
return !Equals(left, right);
}
私はもうその書籍のリファレンスを持っていないので、確認するために見つける必要がありますが、デフォルトのベースハッシュはオブジェクトのすべてのメンバーを一緒にハッシュしただけだと思いました。CLR の動作方法によってこれらにアクセスできるようになったので、CLR のようにうまく記述できるものではありませんでした。
これは完全に私が簡単に読んだものの記憶によるものですので、ご自由にお受け取りください。
編集： その本は、 C# の内部 MSプレスより。カバーに鋸刃が付いているもの。著者は、CLR での実装方法、言語が MSIL にどのように変換されるかなどを説明するのに多くの時間を費やしました。など。この本を見つけることができれば、読んでみるのも悪くありません。
編集： 次のようなリンクを作成してください
Object.gethashCode（）は、System.Objectクラスの内部フィールドを使用してハッシュ値を生成します。作成された各オブジェクトには、作成されたときに整数として保存された一意のオブジェクトキーが割り当てられます。これらのキーは、任意のタイプの新しいオブジェクトが作成されるたびに1から始まり、増分します。
うーん、オブジェクトをハッシュキーとして使用する場合は、独自のハッシュコードをいくつか記述する必要があると思います。
そのため、おそらく、その「子」のハッシュ コードを認識しないでしょう。
あなたの例はそうでないことを証明しているようです:-) キーのハッシュコード MyClass そしてその値 1 どちらも同じです KeyValuePairの。KeyValuePair 実装では、その両方を使用する必要があります。 Key そして Value 独自のハッシュコード用
上に進むと、辞書クラスには一意のキーが必要になります。各キーによって提供されるハッシュコードを使用して、物事を理解しています。ランタイムが呼び出しているわけではないことに注意してください Object.GetHashCode(), ですが、指定したインスタンスによって提供される GetHashCode() 実装を呼び出しています。
より複雑なケースを考えてみましょう。
public class HappyClass
{
enum TheUnit
{
Points,
Picas,
Inches
}
class MyDistanceClass
{
int distance;
TheUnit units;
public MyDistanceClass(int theDistance, TheUnit unit)
{
distance = theDistance;
units = unit;
}
public static int ConvertDistance(int oldDistance, TheUnit oldUnit, TheUnit newUnit)
{
// insert real unit conversion code here :-)
return oldDistance * 100;
}
/// <summary>
/// Figure out if we are equal distance, converting into the same units of measurement if we have to
/// </summary>
/// <param name="obj">the other guy</param>
/// <returns>true if we are the same distance</returns>
public override bool Equals(object obj)
{
MyDistanceClass other = obj as MyDistanceClass;
if (other == null) return false;
if (other.units != this.units)
{
int newDistance = MyDistanceClass.ConvertDistance(other.distance, other.units, this.units);
return distance.Equals(newDistance);
}
else
{
return distance.Equals(other.distance);
}
}
public override int GetHashCode()
{
// even if the distance is equal in spite of the different units, the objects are not
return distance.GetHashCode() * units.GetHashCode();
}
}
static void Main(string[] args)
{
// these are the same distance... 72 points = 1 inch
MyDistanceClass distPoint = new MyDistanceClass(72, TheUnit.Points);
MyDistanceClass distInch = new MyDistanceClass(1, TheUnit.Inch);
Debug.Assert(distPoint.Equals(distInch), "these should be true!");
Debug.Assert(distPoint.GetHashCode() != distInch.GetHashCode(), "But yet they are fundimentally different values");
Dictionary<object, object> dict = new Dictionary<object, object>();
dict.Add(new KeyValuePair<MyDistanceClass, object>(distPoint, 1), 1);
//this should not barf
dict.Add(new KeyValuePair<MyDistanceClass, object>(distInch, 1), 1);
return;
}
}
基本的に...この例の場合、同じ距離にある 2 つのオブジェクトが Equals に対して「true」を返し、それでも異なるハッシュ コードを返すようにする必要があります。
