Perché ValueType.GetHashCode() implementato come è?

StackOverflow https://stackoverflow.com/questions/3841602

  •  27-09-2019
  •  | 
  •  

Domanda

Da ValueType.cs

**Action: Our algorithm for returning the hashcode is a little bit complex. We look 
**        for the first non-static field and get it's hashcode.  If the type has no 
**        non-static fields, we return the hashcode of the type. We can't take the
**        hashcode of a static member because if that member is of the same type as 
**        the original type, we'll end up in an infinite loop.

Sono stato morso da oggi, quando stavo usando un KeyValuePair come chiave in un Dizionario (memorizzato nome dell'attributo xml (enum) e valore (stringa)), e per esso previsto è di farlo hashcode calcolata sulla base di tutti i suoi campi, ma secondo implementazione è considerato solo la parte fondamentale.

Esempio (c/p, Linqpad):

void Main()
{
    var kvp1 = new KeyValuePair<string, string>("foo", "bar");
    var kvp2 = new KeyValuePair<string, string>("foo", "baz");

    // true
    (kvp1.GetHashCode() == kvp2.GetHashCode()).Dump();
}

Non e ' un campo statico credo che significa che il primo campo in declaratin ordine, che potrebbe anche causare problemi quando si cambia ordine variabile, in origine, per qualsiasi motivo, e credendo di non modificare il codice semanticamente.

È stato utile?

Soluzione

AGGIORNAMENTO:Questa risposta è stata (in parte) la base di un articolo di blog ho scritto che va in ulteriori dettagli circa le caratteristiche del progetto di GetHashcode.Grazie per l'interessante domanda!

Non ho implementare e non ho parlato di gente che ha fatto.Ma posso segnalare un paio di cose.

(Prima di andare via, di notare che io sono qui specificamente parlando di codici hash ai fini del bilanciamento tabelle di hash in cui il contenuto della tabella, sono scelti dai non utenti ostili.I problemi di codici hash per la firma digitale, il controllo di ridondanza, o di garantire una buona performance di una tabella di hash, quando alcuni utenti di montaggio di tipo denial-of-service (ddos) contro il tavolo provider sono oltre la portata di questa discussione).

In primo luogo, come Jon correttamente le note, il dato algoritmo applica la richiesta contratto di GetHashCode.Potrebbe essere sub-ottimale per i tuoi scopi, ma è legale.Tutto ciò che è richiesto è che le cose che uguali sono uguali codici hash.

Così che cosa sono i "nice to have", oltre a quel contratto?Un buon codice hash di attuazione deve essere:

1) Fast.Molto veloce!Ricordate, il punto del codice hash, in primo luogo, per rapidamente trovare relativamente slot vuoto in una tabella hash.Se l'O(1) calcolo del codice hash, in pratica, è più lento rispetto a O(n) tempo impiegato per fare la ricerca ingenuamente quindi il codice hash soluzione è una perdita netta.

2) Ben distribuiti in tutto lo spazio di 32 bit interi per un determinato distribuzione degli ingressi.Il peggio è la distribuzione in tutta la partita, più come un ingenuo lineare di ricerca la tabella di hash, sta per essere.

Così, come si fa a fare un algoritmo di hash per valore arbitrario tipi di dato quei due in conflitto obiettivi?Ogni volta che si spende su un complesso algoritmo di hash che garantisce una buona distribuzione è tempo mal speso.

Una idea comune è "hash di tutti i campi e poi XOR insieme risultante codici hash".Ma che elemosina la domanda;Uno xor tra due 32 bit int dà solo una buona distribuzione quando gli ingressi stessi sono estremamente ben distribuito e non legati tra loro, e che è improbabile scenario:

// (Updated example based on good comment!)
struct Control
{
    string name;
    int x;
    int y;
}

Qual è la probabilità che x e y sono ben distribuiti su tutta la gamma di 32 bit interi?Molto bassa.Le probabilità sono molto meglio che sono entrambi piccolo e uno vicino all'altro, in questo caso uno xor tra loro codici hash insieme rende le cose peggio, non meglio.uno xor insieme di numeri interi che sono vicino a vicenda zeri la maggior parte dei bit.

Inoltre, questo è O(n) nel numero di campi!Un tipo di valore, con un sacco di piccoli campi vorrebbe un relativamente lungo periodo di tempo per calcolare il codice hash.

Fondamentalmente la situazione in cui ci troviamo, qui, è che l'utente non ha fornito un codice hash attuazione stessi;o non gli interessa, o non si aspettano che questo tipo mai essere utilizzato come una chiave in una tabella hash.Dato che non si hanno nessuna informazione semantica di sorta sul tipo, qual è la cosa migliore da fare?La cosa migliore da fare è tutto ciò che è veloce e dà buoni risultati la maggior parte del tempo.

La maggior parte del tempo, due struct istanze che differiscono variano in più dei loro campi, non solo uno dei loro campi, quindi basta scegliere uno di loro e sperando che sia quello che differisce sembra ragionevole.

La maggior parte del tempo, due struct istanze che differiscono avrà qualche ridondanza nei loro campi, in modo da coniugare i valori hash di molti campi, insieme, è probabile che a diminuire, non aumentare l'entropia dell'valore di hash, anche come si consuma il tempo che l'algoritmo di hash è stato progettato per risparmiare.

Confronta questo con il design di tipi anonimi in C#.Anonymous types noi fare so che è molto probabile che il tipo viene utilizzato come chiave di una tabella.Noi fare so che è molto probabile che ci sarà la ridondanza tra le istanze di tipi anonimi (perché sono i risultati di un prodotto cartesiano o altri join).E quindi facciamo combinare i codici hash di tutti i campi in un codice hash.Se ti dà cattive prestazioni, a causa dell'eccessivo numero di codici hash essere calcolato, si è liberi di utilizzare un custom nominale tipo piuttosto che di tipo anonimo.

Altri suggerimenti

L'attuale implementazione di ValueType.GetHashCode () non corrispondono del tutto il commento. Ha due versioni dell'algoritmo, veloci e lenti. Prima controlla se la struct contiene tutti i membri di un tipo di riferimento e se c'è qualche spaziatura tra i campi. Imbottitura è spazio vuoto in un valore struttura, creata quando il compilatore JIT allinea i campi. C'è imbottitura in una struttura che contiene bool e int (3 byte), ma senza imbottitura quando contiene int e int, appoggino bene insieme.

Senza un riferimento senza imbottitura, può fare la versione veloce poiché ogni bit del valore struttura è un bit che appartiene ad un valore di campo. Si XOR semplicemente 4 byte alla volta. Otterrete un 'buon' codice hash che considera tutti i membri. Molti tipi di struttura semplice nella struttura di .NET si comportano in questo modo, come Point e Size.

In mancanza di prova, lo fa la versione lenta, l'equivalente morale di riflessione. Questo è quello che si ottiene, il vostro KeyValuePair <> contiene riferimenti. E questo controlla solo il primo campo candidato, come il commento dice. Questo è sicuramente un ottimizzazione perf, evitando che brucia troppo tempo.

Sì, brutto particolare e non quello ampiamente conosciuto. Di solito è scoperto quando le comunicazioni qualcuno che il loro codice di raccolta succhia fango.

Un dettaglio più straziante: la versione veloce ha un bug che i byte quando la struttura contiene un campo di tipo decimale. I valori di 12m e 12.0m sono logicamente uguali, ma non hanno lo stesso schema di bit. GetHashCode () dirà che non sono uguali. Ouch.

Si dovrebbe comunque rispettare il contratto di GetHashCode anche se il campo cambia ordine:. Valori uguali avranno codici hash uguali, entro la durata di quel processo

In particolare:

  • I valori non uguali non devono avere non uguale codici hash
  • I codici hash non devono essere coerenti tra processi (si può cambiare un'implementazione, la ricostruzione, e tutto dovrebbe funzionare - non si dovrebbe essere persistente codici hash, in fondo)

Ora non sto dicendo che l'attuazione di ValueType è una grande idea -. Causerà suckage prestazioni in vari modi ... ma non credo che in realtà è rotto

Bene, ci sono pro e contro a qualsiasi implementazione di GetHashCode(). Questi sono naturalmente le cose che pesano fino in sede di attuazione il nostro, ma nel caso di ValueType.GetHashCode() v'è una particolare difficoltà, nel senso che non hanno molte informazioni su quali saranno i dati reali del tipo concreto. Naturalmente, questo accade spesso a noi quando stiamo creando una classe astratta o di una intenzione di essere la base di classi che aggiungeranno molto di più in termini di stato, ma in quei casi abbiamo una soluzione ovvia del solo utilizzando l'implementazione predefinita di meno che un object.GetHashCode() cure classe derivata per ignorare lì.

Con ValueType.GetHashCode() non hanno questo lusso come la differenza principale tra un tipo di valore e un tipo di riferimento è, nonostante la popolarità di parlare di dettagli di implementazione dello stack contro mucchio, il fatto che per un tipo di valore di equivalenza si riferisce a valore mentre per un tipo di oggetto equivalenza riguarda identità (anche quando un oggetto definisce una diversa forma di equivalenza sovrascrivendo Equals() e GetHashCode() il concetto di riferimento uguaglianza esiste ancora ed è ancora utile.

Quindi, per il metodo Equals() l'implementazione è ovvio; controllare i due oggetti sono dello stesso tipo, e se è quindi controllare anche che tutti i campi sono uguali (in realtà c'è un'ottimizzazione che fa un confronto bit per bit, in alcuni casi, ma questa è un'ottimizzazione sulla stessa idea di base).

Cosa fare per GetHashCode()? Semplicemente non c'è soluzione perfetta. Una cosa che potevano fare è una sorta di mult-allora-add o shift-allora-XOR su ogni campo. Questo sarebbe probabilmente dare un buon codice hash, ma potrebbe essere costoso se c'erano un sacco di campi (non importa che la sua non è raccomandato di avere valore tipi che hanno un sacco di campi, il realizzatore deve considerare che ancora possono, e anzi ci potrebbe anche essere momenti in cui ha un senso, anche se onestamente non riesco a immaginare un tempo in cui sia ha un senso e ha anche senso di hash). Se sapessero alcuni campi erano raramente diversi tra istanze potevano ignorare quei campi e avere ancora un buon codice hash, mentre anche essere abbastanza veloce. Infine, possono ignorare la maggior parte dei campi, e la speranza che l'uno (s) che non ignorano variano in termini di valore la maggior parte del tempo. Sono andati per la versione più estrema di questi ultimi.

(La questione di ciò che viene fatto quando non ci sono campi di istanza è un'altra questione e una scelta abbastanza buona, tali tipi di valore sono uguali a tutte le altre istanze dello stesso tipo, e hanno un codice hash che corrisponde a quella).

Quindi, è un'implementazione che fa schifo se si sta hashing un sacco di valori in cui il primo campo è la stessa (o altrimenti restituisce lo stesso codice hash), ma altre implementazioni avrebbe fatto schifo in altri casi (Mono va per XOR tutti i campi codici hash insieme, meglio nel tuo caso, peggio in altri).

La questione di cambiare l'ordine dei campi non importa, come hashcode è chiaramente indicato come unica rimasta valida per la durata di un processo e non è adatto nella maggior parte dei casi in cui potrebbero essere mantenuta oltre che (può essere utile in alcuni caching situazioni in cui non fa male se le cose non si trovano correttamente dopo una modifica del codice).

Quindi, non grande, ma nulla sarebbe perfetto. Questo dimostra che si deve sempre considerare entrambi i lati cosa significa "uguaglianza" quando si utilizza un oggetto come chiave. E 'facilmente risolto nel vostro caso con: 

public class KVPCmp<TKey, TValue> : IEqualityComparer<KeyValuePair<TKey, TValue>>, IEqualityComparer
{
  bool IEqualityComparer.Equals(object x, object y)
  {
      if(x == null)
        return y == null;
      if(y == null)
        return false;
      if(!(x is KeyValuePair<TKey, TValue>) || !(y is KeyValuePair<TKey, TValue>))
        throw new ArgumentException("Comparison of KeyValuePairs only.");
      return Equals((KeyValuePair<TKey, TValue>) x, (KeyValuePair<TKey, TValue>) y);
  }
  public bool Equals(KeyValuePair<TKey, TValue> x, KeyValuePair<TKey, TValue> y)
  {
      return x.Key.Equals(y.Key) && x.Value.Equals(y.Value);
  }
  public int GetHashCode(KeyValuePair<TKey, TValue> obj)
  {
      int keyHash = obj.GetHashCode();
      return ((keyHash << 16) | (keyHash >> 16)) ^ obj.Value.GetHashCode();
  }
  public int GetHashCode(object obj)
  {
      if(obj == null)
        return 0;
      if(!(obj is KeyValuePair<TKey, TValue>))
       throw new ArgumentException();
      return GetHashCode((KeyValuePair<TKey, TValue>)obj);
  }
}

Usa questa come di confronto durante la creazione del dizionario, e tutti dovrebbero essere bene (è necessario solo i metodi di confronto generici davvero, ma lasciando il resto in non fa male e può essere utile avere a volte).

Grazie a tutti delle risposte molto, molto informativi. Sapevo che ci doveva essere qualche logica in questa decisione, ma vorrei che fosse documentato meglio. Io non sono in grado di utilizzare v4 del quadro quindi non c'è Tuple<>, e che è stato il motivo principale per cui ho deciso di spalle su KeyValuePair struct. Ma credo che non v'è alcuna angoli di taglio e dovrò rotolare il mio. Ancora una volta, grazie a tutti.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top