Wie funktioniert c # Figur aus dem Hash-Code für ein Objekt?

Question

Diese Frage kommt aus der Diskussion über die Tupel .

Ich begann über den Hash-Code zu denken, dass ein Tupel haben sollte. Was passiert, wenn wir KeyValuePair-Klasse als Tupel akzeptieren? Es überschreibt nicht die GetHashCode () -Methode, so wird es wahrscheinlich auch nicht der Hash-Codes von ihm ist „Kinder“ ... Also, Laufzeit Object.GetHashCode rufen bewusst sein (), die nicht bewusst das ist reales Objekt Struktur.

Dann können wir zwei Instanzen einiger Referenztyp machen, die eigentlich gleich sind, weil der überladenen GetHashCode () und equals (). Und sie als „Kinder“ in Tupeln das Wörterbuch zu „betrügen“.

Aber es funktioniert nicht! Laufzeit irgendwie Zahlen die Struktur unseres Tupel aus und ruft das überladene GetHashCode unserer Klasse!

Wie funktioniert es? Was ist die Analyse gemacht durch Object.GetHashCode ()?

Kann es die Leistung in einigen schlechten Szenario beeinflussen, wenn wir einige komplizierte Schlüssel verwenden? (Wahrscheinlich, unmöglich Szenario ... aber immer noch)

Betrachten Sie diesen Code als Beispiel:

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

Aktualisieren Ich glaube, ich habe eine Erklärung dafür gefunden, wie in meiner Antwort unten angegeben. Die wichtigsten Ergebnisse davon sind:

• Seien Sie vorsichtig mit Ihren Schlüssel und deren Hash-Codes: -)
• Für komplizierte Dictionary-Schlüssel müssen Sie Equals überschreiben () und GetHashCode () korrekt.

Answer 1

Es scheint, dass ich jetzt einen Anhaltspunkt haben.

Ich dachte, KeyValuePair ist ein Referenz-Typ, aber es ist nicht, es ist eine Struktur ist. Und so nutzt es ValueType.GetHashCode () -Methode. MSDN für es sagt:. „Ein oder mehr Felder des abgeleiteten Typs verwendet werden, um den Rückgabewert zu berechnen“

Wenn Sie einen echten Referenz-Typ als ein „Tupel-Provider“ nehmen Sie das Wörterbuch betrügen (oder sich selbst ...).

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

Answer 2

Sie überschreiben GetHashCode nicht () und equals () auf veränderbare Klassen, außer Kraft setzt nur auf unveränderlichen Klassen oder Strukturen, sonst, wenn Sie ein Objekt ändern als Schlüssel verwendet, die Hash-Tabelle richtig nicht mehr funktioniert (Sie werden nicht Lage sein, den Wert abzurufen, um den Schlüssel zugeordnet ist, nachdem der Schlüsselobjekt geändert wurde)

Auch Hash-Tabellen nicht verwenden Hashcodes Objekte, die sie die wichtigsten Objekte themselfes als Bezeichner verwenden, um zu identifizieren, ist es nicht erforderlich, dass alle Schlüssel, die Einträge in einer Hash-Tabelle verschiedene Hashcodes zurückkehren werden verwendet, um hinzuzufügen, aber es wird empfohlen, dass sie tun , sonst Leistung leidet stark.

Answer 3

Hier sind die richtigen Hash und Gleichheit Implementierungen für die Quad-Tupel (enthält 4 Tupel Komponenten im Inneren). Dieser Code sorgt für die richtige Verwendung dieses spezifischen Tupel in HashSets und die Wörterbücher.

Mehr zum Thema (einschließlich Quellcode) hier .

Hinweis Verwendung des nicht markiert Schlüsselwort (zur Vermeidung von Überlauf) und wirft Nullreferenceexception, wenn obj null ist (wie durch die Basismethode erforderlich)

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

Answer 4

Sehen Sie sich diese Post von Brad Abrams und auch der Kommentar von Brian Grunkemeyer für einige weitere Informationen, wie Object.GetHashCode funktioniert. Werfen Sie auch einen Blick auf den ersten Kommentar über Ayande Blog Post . Ich weiß nicht, ob die aktuellen Versionen des Rahmen noch diese Regeln befolgen, oder wenn sie es tatsächlich wie Brad geändert haben impliziert werden.

Answer 5

Ich habe das Buch nicht Bezug mehr, und ich werde es nur finden, um zu bestätigen, aber ich dachte, der Standard-Basis-Hash nur zusammen alle Mitglieder des Objekts gehasht. Es hat Zugang zu ihnen wegen der Art und Weise der CLR gearbeitet, so war es nicht etwas, das man genauso gut schreiben konnte, wie sie hatte.

Das ist völlig aus dem Gedächtnis von etwas, das ich so nehmen Sie es kurz zu lesen, was Sie wollen.

Edit: Das Buch ist Innen C # von MS Press. Der mit dem Sägeblatt auf der Abdeckung. Der Autor verbrachte eine Menge Zeit zu erklären, wie die Dinge in der CLR implementiert wurden, wie die Sprache zu MSIL übersetzt unten, ect. ect. Wenn Sie das Buch finden können, ist es keine schlechte Lese.

Edit: bildet die Verbindung vorausgesetzt, es sieht aus wie

  

Object.GetHashCode () verwendet ein   internes Feld in der Klasse System.Object den Hash-Wert zu erzeugen. Jeder   Objekt erstellt wird einen einzigartigen Objektschlüssel zugeordnet ist, als eine ganze Zahl gespeichert wird, wenn es   geschaffen. Diese Schlüssel bei 1 beginnen und jedes Mal ein neues Objekt erhöht von   jede Art erstellt wird.

Hmm ich glaube, ich muss ein paar meiner eigenen Hash-Codes schreiben, wenn ich Objekte zu verwenden, als Hash-Schlüssel erwartet.

Answer 6

  

so wahrscheinlich nicht bewusst sein, der Hash-Codes von ihm ist „Kinder“.

Ihr Beispiel sonst für den Schlüssel MyClass und den Wert 1 :-) Der Hash-Code zu beweisen scheint, ist das gleiche für beide KeyValuePair ist. Die KeyValuePair Implementierung muss sowohl mit seinem Key und Value für seinen eigenen Hash-Code

auffahren, die Wörterbuch-Klasse will eindeutige Schlüssel. Es wird mit dem Hash-Code von jedem Schlüssel versehen, Dinge herauszufinden. Denken Sie daran, dass die Laufzeit nicht Aufruf Object.GetHashCode() wird, aber es ist der Aufruf der GetHashCode () Implementierung durch die Instanz vorausgesetzt, Sie geben es.

einen komplexeren Fall vor:

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

}

Im Grunde ... im Fall von meinem Beispiel, würden Sie zwei Objekte wollen, die den gleichen Abstand sind für Equals „true“ zurück, aber noch verschiedene Hash-Codes zurück.