2009-07-02 6 views
5

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?

+0

È 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. –

+0

Il più che abbia mai visto in uso effettivo era ~ 200, ma l'uso tipico è <30, quindi probabilmente hai ragione. –

+1

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. –

risposta

4

Non penso che ci sia un problema con l'approccio che hai scelto di usare. Preoccuparsi "troppo" delle collisioni di hash è quasi sempre un'indicazione di un eccesso di riflessione sul problema; finché l'hash è altamente probabile che sia diverso, dovrebbe andare bene.

In definitiva si potrebbe anche voler considerare di lasciare il Description dal proprio hash comunque se è ragionevole aspettarsi che la maggior parte delle volte gli oggetti possano essere distinti in base al titolo e alla data di pubblicazione (libri?).

Si potrebbe anche considerare di ignorare completamente il GUID nella funzione di hash e usarlo solo nell'implementazione Equals per disambiguare il caso improbabile (?) Di conflitti di hash.

+0

Altho, ovviamente, il GUID se presente, è probabile che hash molto più veloce di una stringa di titolo arbitraria ... quindi potrebbe essere un possibile ottimizzazione delle prestazioni. – jerryjvl

+0

La descrizione deve essere inclusa nell'uguaglianza (e quindi nel codice hash) –

+0

Oh, e per la cronologia, articoli RSS. –

7

Un semplicissimo hash code method for custom classes consiste nel mettere in bit per bit tutti i codici hash dei campi. Può essere semplice come questo:

int hash = 0; 
hash ^= this.Title.GetHashCode(); 
hash ^= this.PublishDate.GetHashCode(); 
hash ^= this.Description.GetHashCode(); 
return hash; 

Dal link above:

XOR ha le seguenti proprietà curato:

  • esso non dipende ordine della computazione.
  • Non "spreca" i bit. Se cambi anche solo un bit in uno dei componenti, il valore finale cambierà.
  • È rapido, un singolo ciclo anche sul computer più primitivo.
  • Conserva una distribuzione uniforme. Se i due pezzi che combini sono distribuiti in modo uniforme, così sarà la combinazione. In altre parole, non tende a comprimere l'intervallo del digest in una banda più stretta.

XOR non funziona bene se si aspetta di avere valori duplicati nei campi come valori duplicati si annullano a vicenda, quando XORed. Dato che stai tritando insieme tre campi non correlati che non dovrebbero essere un problema in questo caso.

+7

XOR non dipende dall'ordine di computazione è un'arma a doppio taglio ... se hai oggetti con più campi dello stesso tipo (ad esempio, due date), quando questi vengono scambiati attorno agli oggetti 'appariranno uguali "all'hash. – jerryjvl