Fondamentalmente, ho il seguente finora:Come devo implementare Object.GetHashCode() per l'uguaglianza complessa?
class Foo {
public override bool Equals(object obj)
{
Foo d = obj as Foo ;
if (d == null)
return false;
return this.Equals(d);
}
#region IEquatable<Foo> Members
public bool Equals(Foo other)
{
if (this.Guid != String.Empty && this.Guid == other.Guid)
return true;
else if (this.Guid != String.Empty || other.Guid != String.Empty)
return false;
if (this.Title == other.Title &&
this.PublishDate == other.PublishDate &&
this.Description == other.Description)
return true;
return false;
}
}
Quindi, il problema è questo: ho un campo non richiesto Guid
, che è un identificatore univoco. Se questo non è impostato, allora ho bisogno di provare a determinare l'uguaglianza basata su metriche meno accurate come tentativo di determinare se due oggetti sono uguali. Funziona bene, ma rende GetHashCode()
disordinato ... Come dovrei farlo? Un'implementazione ingenuo sarebbe qualcosa di simile:
public override int GetHashCode() {
if (this.Guid != String.Empty)
return this.Guid.GetHashCode();
int hash = 37;
hash = hash * 23 + this.Title.GetHashCode();
hash = hash * 23 + this.PublishDate.GetHashCode();
hash = hash * 23 + this.Description.GetHashCode();
return hash;
}
Ma quali sono le probabilità dei due tipi di hash collisione? Certamente, non mi aspetterei che sia 1 in 2 ** 32
. È una cattiva idea, e se sì, come dovrei farlo?
È più importante che l'algoritmo di hash sia in accordo con l'algoritmo di uguaglianza di quanto la distribuzione sia uniforme. Ricorda, lo scopo dell'hash è solo quello di ottenere una distribuzione decente in una tabella hash; Finché non si è massicciamente inclinati su un determinato bucket, le probabilità sono buone, starai bene. Se sei preoccupato, scegli uno scenario ragionevole che è probabile che il consumatore del tuo oggetto incontri - diciamo, mettendone alcune centinaia in un dizionario, se è ragionevole - e fai qualche prova perfetta per vedere se ottieni un accettabile risultati. –
Il più che abbia mai visto in uso effettivo era ~ 200, ma l'uso tipico è <30, quindi probabilmente hai ragione. –
Heck, con meno di 30 elementi, una ricerca lineare in un elenco collegato è probabilmente abbastanza efficiente. È possibile restituire sempre un codice hash di zero, avere il 100% di possibilità di collisione e ottenere comunque prestazioni accettabili. Il punto di avere una buona distribuzione dei codici hash è di fare scala delle prestazioni quando le dimensioni del dizionario diventano grandi. Puoi avere una distribuzione schifosa e ottenere comunque buoni risultati se hai intenzione di mettere solo un piccolo numero di oggetti nella tabella. –