In che modo c # calcola il codice hash per un oggetto?
https://stackoverflow.com/questions/102690
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Questa domanda viene fuori dalla discussione su tuple .
Ho iniziato a pensare al codice hash che dovrebbe avere una tupla. E se accetteremo la classe KeyValuePair come tupla? Non sovrascrive il metodo GetHashCode (), quindi probabilmente non sarà a conoscenza dei codici hash del suo " children " ... Quindi, il runtime chiamerà Object.GetHashCode (), di cui non è a conoscenza la vera struttura dell'oggetto.
Quindi possiamo creare due istanze di qualche tipo di riferimento, che in realtà sono uguali, a causa del sovraccarico GetHashCode () e Equals (). E usali come " figli " in tuple per "imbrogliare" il dizionario.
Ma non funziona! Il runtime in qualche modo capisce la struttura della nostra tupla e chiama il GetHashCode sovraccarico della nostra classe!
Come funziona? Qual è l'analisi fatta da Object.GetHashCode ()?
Può influire sulle prestazioni in uno scenario negativo, quando utilizziamo alcuni tasti complicati? (probabilmente, scenario impossibile ... ma comunque)
Considera questo codice come esempio:
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;
}
}
}
Aggiorna Penso di aver trovato una spiegazione per questo come indicato di seguito nella mia risposta. I principali risultati sono:
- Fai attenzione con le tue chiavi e i loro codici hash :-)
- Per chiavi di dizionario complicate è necessario sovrascrivere correttamente Equals () e GetHashCode ().
Soluzione 4
Sembra che ora ho un indizio.
Pensavo che KeyValuePair fosse un tipo di riferimento, ma non lo è, è una struttura. E quindi utilizza il metodo ValueType.GetHashCode (). MSDN per questo dice: " Uno o più campi del tipo derivato viene utilizzato per calcolare il valore di ritorno " ;.
Se prenderai un vero tipo di riferimento come " tuple-provider " imbrogliare il dizionario (o te stesso ...).
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;
}
}
}
Altri suggerimenti
Non sovrascrivere GetHashcode () e Equals () su classi mutabili, sovrascriverlo solo su classi o strutture immutabili, altrimenti se si modifica un oggetto usato come chiave la tabella hash non funzionerà più correttamente (non essere in grado di recuperare il valore associato alla chiave dopo che l'oggetto chiave è stato modificato)
Inoltre le tabelle hash non usano gli hashcode per identificare gli oggetti che usano essi stessi stessi come identificatori, non è necessario che tutte le chiavi utilizzate per aggiungere voci in una tabella hash restituiscano hashcode diversi, ma si consiglia di farlo , altrimenti le prestazioni ne risentono notevolmente.
Ecco le implementazioni corrette di hash e uguaglianza per la tupla Quad (contiene 4 componenti di tupla all'interno). Questo codice garantisce il corretto utilizzo di questa tupla specifica in HashSet e dizionari.
Ulteriori informazioni sull'argomento (incluso il codice sorgente) qui .
Nota utilizzo della parola chiave non selezionata (per evitare overflow) e generazione di NullReferenceException se obj è null (come richiesto dal metodo di base)
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);
}
Dai un'occhiata a questo post di Brad Abrams e anche il commento di Brian Grunkemeyer per ulteriori informazioni su come funziona object.GetHashCode. Inoltre, dai un'occhiata al primo commento sul blog di Ayande post . Non so se le attuali versioni del Framework seguano ancora queste regole o se le abbiano effettivamente modificate come implicito da Brad.
Non ho più il riferimento al libro, e dovrò trovarlo solo per confermare, ma ho pensato che l'hash di base predefinito abbia appena eseguito il hash di tutti i membri del tuo oggetto. Ha avuto accesso a loro a causa del modo in cui il CLR ha funzionato, quindi non era qualcosa che si potesse scrivere così come avevano.
Questo è completamente dalla memoria di qualcosa che ho letto brevemente, quindi prendilo per quello che vuoi.
Modifica: il libro era Inside C # da MS Press. Quello con la lama per sega sulla copertina. L'autore ha trascorso molto tempo a spiegare come sono state implementate le cose nel CLR, come la lingua tradotta in MSIL, ecc. ect. Se riesci a trovare il libro non è una cattiva lettura.
Modifica: forma il collegamento a condizione che appaia
Object.GetHashCode () utilizza un campo interno nella classe System.Object per generare il valore hash. Ogni all'oggetto creato viene assegnata una chiave oggetto univoca, memorizzata come numero intero, quando è creato. Questi tasti iniziano da 1 e incrementano ogni volta che un nuovo oggetto di viene creato qualsiasi tipo.
Hmm immagino di dover scrivere alcuni dei miei codici hash, se mi aspetto di usare oggetti come chiavi hash.
quindi probabilmente non sarà a conoscenza dei codici hash dei suoi "quotazioni".
Il tuo esempio sembra dimostrare il contrario :-) Il codice hash per la chiave MyClass e il valore 1 è lo stesso per entrambi KeyValuePair 'S . L'implementazione di KeyValuePair deve utilizzare sia il Key che il Value per il proprio codice hash
Salendo, la classe del dizionario vuole chiavi uniche. Sta usando l'hashcode fornito da ogni chiave per capire le cose. Ricorda che il runtime non sta chiamando Object.GetHashCode () , ma sta chiamando l'implementazione GetHashCode () fornita dall'istanza assegnata.
Prendi in considerazione un caso più complesso:
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;
}
}
Fondamentalmente ... nel caso del mio esempio, vorresti che due oggetti con la stessa distanza restituissero "vero" per uguali, ma restituisce codici hash diversi.
