Standardimplementierung für Object.GetHashCode ()

Question

Wie funktioniert die Standardimplementierung für GetHashCode() Arbeit? Und macht damit umgehen Strukturen, Klassen, Arrays, usw. effizient und gut genug?

Ich versuche, in welchen Fällen zu entscheiden, soll ich meine eigenen packen und in welchen Fällen ich auf der Default-Implementierung sicher verlassen kann gut zu machen. Ich will nicht das Rad neu erfinden, wenn überhaupt möglich.

Answer 1

namespace System {
    public class Object {
        [MethodImpl(MethodImplOptions.InternalCall)]
        internal static extern int InternalGetHashCode(object obj);

        public virtual int GetHashCode() {
            return InternalGetHashCode(this);
        }
    }
}

InternalGetHashCode wird gemappt ein ObjectNative :: GetHashCode Funktion in der CLR, die wie folgt aussieht:

FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {  
    CONTRACTL  
    {  
        THROWS;  
        DISABLED(GC_NOTRIGGER);  
        INJECT_FAULT(FCThrow(kOutOfMemoryException););  
        MODE_COOPERATIVE;  
        SO_TOLERANT;  
    }  
    CONTRACTL_END;  

    VALIDATEOBJECTREF(obj);  

    DWORD idx = 0;  

    if (obj == 0)  
        return 0;  

    OBJECTREF objRef(obj);  

    HELPER_METHOD_FRAME_BEGIN_RET_1(objRef);        // Set up a frame  

    idx = GetHashCodeEx(OBJECTREFToObject(objRef));  

    HELPER_METHOD_FRAME_END();  

    return idx;  
}  
FCIMPLEND

Die vollständige Umsetzung der GetHashCodeEx ist ziemlich groß, so dass es einfacher ist, nur eine Verknüpfung zu die C ++ Quellcode .

Answer 2

Für eine Klasse, sind die Standardwerte im wesentlichen Gleichheit verweisen, und das ist in der Regel in Ordnung. Wenn eine Struktur zu schreiben, es ist häufiger Gleichheit außer Kraft zu setzen (nicht zuletzt zu vermeiden Boxen), aber es ist sehr selten, man eine Struktur sowieso schreiben!

Wenn Gleichheit überschreiben, sollten Sie immer eine passende Equals() und GetHashCode() haben (dh für zwei Werte, wenn Equals() true zurück, sie muss geben den gleichen Hash-Code, aber das Gegenteil ist nicht erforderlich) - und es ist üblich, auch == / !=operators zu bieten und oft IEquatable<T> zu implementieren

.

Für den Hash-Code zu erzeugen, ist es üblich, eine einkalkuliert Summe zu verwenden, da diese Kollisionen vermeiden Werte gepaart - zum Beispiel für einen einfachen 2-Feld hash:

unchecked // disable overflow, for the unlikely possibility that you
{         // are compiling with overflow-checking enabled
    int hash = 27;
    hash = (13 * hash) + field1.GetHashCode();
    hash = (13 * hash) + field2.GetHashCode();
    return hash;
}

Dies hat den Vorteil, dass:

• die Hash von {1,2} ist nicht das gleiche wie die Hash von {2,1}
• die Hash von {1,1} ist nicht das gleiche wie die Hash von {2,2}

etc -., Die gemeinsam sein kann, wenn nur eine ungewichtete Summe, oder xor (^), etc

Answer 3

Die Dokumentation für die GetHashCode Methode für rel="noreferrer"> sagt „die Standardimplementierung dieser Methode nicht als eindeutige Objektkennung für Hashing Zwecke verwendet werden müssen.“ und ein .

Die Grunddatentypen wie byte, short, int, long, char und string eine gute GetHashCode-Methode implementieren. Einige andere Klassen und Strukturen, wie Point zum Beispiel implementieren eine GetHashCode Methode, die für Ihre spezifischen Bedürfnisse geeignet sein kann oder auch nicht. Sie müssen nur um es auszuprobieren, um zu sehen, ob es gut genug ist.

Die Dokumentation für jede Klasse oder Struktur kann Ihnen sagen, wenn es die Standardimplementierung oder nicht außer Kraft setzt. Wenn es es nicht außer Kraft setzen, sollten Sie Ihre eigene Implementierung verwenden. Für alle Klassen oder Strukturen, die Sie selbst erstellen, wo Sie die GetHashCode Methode verwenden müssen, sollten Sie Ihre eigene Implementierung machen, die die entsprechenden Mitglieder verwendet den Hash-Code zu berechnen.

Answer 4

Since I couldn't find an answer that explains why we should override GetHashCode and Equals for custom structs and why the default implementation "is not likely to be suitable for use as a key in a hash table", I'll leave a link to this blog post, which explains why with a real-case example of a problem that happened.

I recommend reading the whole post, but here is a summary (emphasis and clarifications added).

Reason the default hash for structs is slow and not very good:

The way the CLR is designed, every call to a member defined in System.ValueType or System.Enum types [may] cause a boxing allocation [...]

An implementer of a hash function faces a dilemma: make a good distribution of the hash function or to make it fast. In some cases, it's possible to achieve them both, but it is hard to do this generically in ValueType.GetHashCode.

The canonical hash function of a struct "combines" hash codes of all the fields. But the only way to get a hash code of a field in a ValueType method is to use reflection. So, the CLR authors decided to trade speed over the distribution and the default GetHashCode version just returns a hash code of a first non-null field and "munges" it with a type id [...] This is a reasonable behavior unless it's not. For instance, if you're unlucky enough and the first field of your struct has the same value for most instances, then a hash function will provide the same result all the time. And, as you may imagine, this will cause a drastic performance impact if these instances are stored in a hash set or a hash table.

[...] Reflection-based implementation is slow. Very slow.

[...] Both ValueType.Equals and ValueType.GetHashCode have a special optimization. If a type does not have "pointers" and is properly packed [...] then more optimal versions are used: GetHashCode iterates over an instance and XORs blocks of 4 bytes and Equals method compares two instances using memcmp. [...] But the optimization is very tricky. First, it is hard to know when the optimization is enabled [...] Second, a memory comparison will not necessarily give you the right results. Here is a simple example: [...] -0.0 and +0.0 are equal but have different binary representations.

Real-world issue described in the post:

private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;
readonly struct ErrorLocation
{
    // Empty almost all the time
    public string OptionalDescription { get; }
    public string Path { get; }
    public int Position { get; }
}

We used a tuple that contained a custom struct with default equality implementation. And unfortunately, the struct had an optional first field that was almost always equals to [empty string]. The performance was OK until the number of elements in the set increased significantly causing a real performance issue, taking minutes to initialize a collection with tens of thousands of items.

So, to answer the question "in what cases I should pack my own and in what cases I can safely rely on the default implementation", at least in the case of structs, you should override Equals and GetHashCode whenever your custom struct might be used as a key in a hash table or Dictionary.
I would also recommend implementing IEquatable<T> in this case, to avoid boxing.

As the other answers said, if you're writing a class, the default hash using reference equality is usually fine, so I wouldn't bother in this case, unless you need to override Equals (then you would have to override GetHashCode accordingly).

Answer 5

Generally speaking, if you're overriding Equals, you want to override GetHashCode. The reason for this is because both are used to compare equality of your class/struct.

Equals is used when checking Foo A, B;

if (A == B)

Since we know the pointer isn't likely to match, we can compare the internal members.

Equals(obj o)
{
    if (o == null) return false;
    MyType Foo = o as MyType;
    if (Foo == null) return false;
    if (Foo.Prop1 != this.Prop1) return false;

    return Foo.Prop2 == this.Prop2;
}

GetHashCode is generally used by hash tables. The hashcode generated by your class should always be the same for a classes give state.

I typically do,

GetHashCode()
{
    int HashCode = this.GetType().ToString().GetHashCode();
    HashCode ^= this.Prop1.GetHashCode();
    etc.

    return HashCode;
}

Some will say that the hashcode should only be calculated once per object lifetime, but I don't agree with that (and I'm probably wrong).

Using the default implementation provided by object, unless you have the same reference to one of your classes, they will not be equal to each other. By overriding Equals and GetHashCode, you can report equality based on internal values rather than the objects reference.

Answer 6

If you're just dealing with POCOs you can use this utility to simplify your life somewhat:

var hash = HashCodeUtil.GetHashCode(
           poco.Field1,
           poco.Field2,
           ...,
           poco.FieldN);

...

public static class HashCodeUtil
{
    public static int GetHashCode(params object[] objects)
    {
        int hash = 13;

        foreach (var obj in objects)
        {
            hash = (hash * 7) + (!ReferenceEquals(null, obj) ? obj.GetHashCode() : 0);
        }

        return hash;
    }
}