implementazione predefinita per Object.GetHashCode ()

Question

Come funziona l'implementazione di default per il lavoro GetHashCode()? E maneggia strutture, classi, gli array, ecc in modo efficiente e abbastanza bene?

sto cercando di decidere in quali casi dovrei imballare il mio proprio e in quali casi posso tranquillamente contare sulla implementazione di default per fare bene. Non voglio reinventare la ruota, se possibile.

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 è mappata a un ObjectNative :: GetHashCode funzione nel CLR, che assomiglia a questo:

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

La piena attuazione della GetHashCodeEx è abbastanza grande, quindi è più facile da collegare solo per il codice sorgente C ++ .

Answer 2

Per una classe, le impostazioni predefinite sono essenzialmente riferimento uguaglianza, e che di solito va bene. Se la scrittura di una struct, è più comune di ignorare l'uguaglianza (se non altro per evitare di pugilato), ma è molto raro che si scrive una struct comunque!

Quando si esegue l'override l'uguaglianza, si dovrebbe sempre avere un Equals() di corrispondenza e GetHashCode() (vale a dire per due valori, se Equals() ritorna vero che deve restituire lo stesso hash-code, ma il contrario è non necessario) - ed è comune a fornire anche == / !=operators, e spesso per implementare IEquatable<T> troppo

.

Per generare il codice hash, è comune utilizzare una somma fattorizzata, in quanto ciò evita le collisioni sui valori accoppiati - per esempio, per un semplice hash 2 campo:

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

Questo ha il vantaggio che:

• l'hash di {1,2} non è lo stesso che l'hash di {2,1}
• l'hash di {1,1} non è lo stesso che l'hash di {2,2}

ecc. - che può essere comune se solo utilizzando una somma ponderata, o xor (^), etc

Answer 3

La documentazione per il metodo GetHashCode per oggetto "l'implementazione predefinita di questo metodo non deve essere usato come un identificatore di oggetto unico per scopi di hashing." e quella per ValueType dice " Se si chiama il metodo GetHashCode del tipo derivato, il valore di ritorno non è probabile che sia adatto per l'uso come un chiave in una tabella di hash. ".

I tipi di dati di base come byte, short, int, long, char e string implementano un buon metodo GetHashCode. Alcune altre classi e strutture, come Point per esempio, implementare un metodo GetHashCode che può o non può essere adatto per le vostre esigenze specifiche. Non vi resta che provarlo per vedere se è abbastanza buono.

La documentazione per ogni classe o la struttura può dire se si sostituisce l'implementazione predefinita o meno. Se non ignorare che si dovrebbe usare una propria implementazione. Per tutte le classi o struct create voi stessi in cui è necessario utilizzare il metodo GetHashCode, si dovrebbe fare una propria implementazione che utilizza i membri appropriati per calcolare il codice hash.

Answer 4

Dato che non riuscivo a trovare una risposta che spiega perché che dovremmo ignorare GetHashCode e Equals per le strutture personalizzate e perché l'implementazione di default "non è probabile che sia adatto per l'uso come una chiave in una tabella di hash", vi lascio un link al questo post blog, il che spiega il motivo per cui, con un vero e proprio caso-esempio di un problema quello che è successo.

vi consiglio di leggere l'intero post, ma qui è un riassunto (enfasi e chiarimenti aggiunti).

La ragione l'hash di default per le strutture è lento e non molto buono:

  

Il modo in cui il CLR è stato progettato, ogni chiamata a un membro definito System.ValueType o System.Enum tipi [può] causare un allocazione boxe [...]

     

Un realizzatore di una funzione di hash si trova di fronte a un dilemma: fare una buona distribuzione della funzione di hash o per renderlo veloce. In alcuni casi, è possibile ottenere tutti e due, ma è difficile fare questo genericamente in ValueType.GetHashCode.

     

La funzione di hash canonica di una struttura "combina" codici hash di tutti i campi. Ma l'unico modo per ottenere un codice hash di un campo in un metodo ValueType è quello di l'uso di riflessione . Così, CLR gli autori hanno deciso di scambiare la velocità sopra la distribuzione e la versione di default GetHashCode solo restituisce un codice hash di un primo campo non nullo e "munges" con un tipo di id [...] Questo è un comportamento ragionevole a meno che non lo è. Per esempio, se siete abbastanza sfortunati e il primo campo della struct ha lo stesso valore per la maggior parte dei casi, quindi una funzione di hash fornirà lo stesso risultato per tutto il tempo. E, come si può immaginare, questo causerà un impatto sulle prestazioni drastica se questi casi sono memorizzati in un set hash o una tabella hash.

     

[...] implementazione Riflessione-based è lento . Molto lento.

     

[...] Sia ValueType.Equals e ValueType.GetHashCode hanno un'ottimizzazione speciale. Se un tipo non ha "puntatori" ed è correttamente imballato [...] poi versioni più ottimali vengono utilizzati: itera GetHashCode sopra un'istanza e XOR blocchi di 4 byte e metodo Equals confronta due istanze utilizzando memcmp. [...] Ma l'ottimizzazione è molto difficile. In primo luogo, è difficile sapere quando l'ottimizzazione è attivata [...] In secondo luogo, un confronto memoria non necessariamente dare i giusti risultati . Ecco un semplice esempio:. [...] -0.0 e +0.0 sono uguali ma hanno diverse rappresentazioni binarie

problema reale-mondo descritto nel 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; }
}

  

Abbiamo usato una tupla che conteneva una struct personalizzato con l'attuazione di uguaglianza predefinito. E purtroppo, la struct ha avuto un primo campo opzionale che era quasi sempre uguale a [stringa vuota] . La performance è stata OK fino a quando il numero di elementi nel set aumentato in modo significativo causando un problema di prestazioni reali, prendendo minuti per inizializzare una collezione con decine di migliaia di oggetti.

Quindi, per rispondere alla domanda "in quali casi dovrei imballare il mio proprio e in quali casi posso tranquillamente contare sulla implementazione di default", almeno nel caso di struct , si dovrebbe ignorare Equals e GetHashCode ogni volta che lo struct personalizzato potrebbe essere utilizzato come una chiave in una tabella hash o Dictionary.
Auspico inoltre attuazione IEquatable<T> in questo caso, al fine di evitare la boxe.

Come le altre risposte hanno detto, se si sta scrivendo un class , l'hash predefinito utilizzando l'uguaglianza di riferimento è di solito bene, quindi non mi preoccuperei, in questo caso, meno è necessario eseguire l'override Equals (allora si dovrebbe ignorare GetHashCode di conseguenza).

Answer 5

In generale, se si sta sovrascrivendo Equals, si desidera ignorare GetHashCode. La ragione di questo è perché entrambi sono utilizzati per confrontare l'uguaglianza della vostra classe / struttura.

Equals viene utilizzato durante il controllo Foo A, B;

if (A == B)

Dato che sappiamo che il puntatore non è probabile che corrisponda, siamo in grado di confrontare i membri interni.

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 è generalmente utilizzato per le tabelle hash. Il codice hash generato dalla tua classe dovrebbe essere sempre lo stesso per un danno lezioni di stato.

Io di solito faccio,

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

    return HashCode;
}

Alcuni diranno che il codice hash dovrebbe essere calcolato solo una volta per durata degli oggetti, ma io non sono d'accordo con quello (e io sono probabilmente sbagliato).

Utilizzando l'implementazione di default fornito da oggetto, se non si ha lo stesso riferimento ad una delle classi, essi non saranno uguali tra loro. Sovrascrivendo Equals e GetHashCode, è possibile segnalare l'uguaglianza sulla base di valori interni piuttosto che il riferimento oggetti.

Answer 6

Se siete appena trattare con pocos è possibile utilizzare questa utilità per semplificare la tua vita in qualche modo:

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