Utilizzando GetHashCode all'uguaglianza prova Equals di override

Question

E 'ok per chiamare GetHashCode come un metodo per l'uguaglianza di prova da dentro l'override Uguale?

Ad esempio, è questo codice accettabile?

public class Class1
{
  public string A
  {
    get;
    set;
  }

  public string B
  {
    get;
    set;
  }

  public override bool Equals(object obj)
  {
    Class1 other = obj as Class1;
    return other != null && other.GetHashCode() == this.GetHashCode();
  }

  public override int GetHashCode()
  {
    int result = 0;
    result = (result ^ 397) ^ (A == null ? 0 : A.GetHashCode());
    result = (result ^ 397) ^ (B == null ? 0 : B.GetHashCode());
    return result;
  }
}

Answer 1

Gli altri sono a destra; l'operazione uguaglianza è rotto. Facciamo un esempio:

public static void Main()
{
    var c1 = new Class1() { A = "apahaa", B = null };
    var c2 = new Class1() { A = "abacaz", B = null };
    Console.WriteLine(c1.Equals(c2));
}

immagino si desidera che l'uscita di quel programma di essere "falsa", ma con la tua definizione di uguaglianza che è "vero" in alcune implementazioni del CLR.

Ricordate, ci sono solo circa quattro miliardi di possibili codici di hash. Ci sono molto più di quattro miliardi di possibili sei stringhe di lettere, e pertanto almeno due di loro hanno lo stesso codice hash . Vi ho mostrato due; esistono infiniti altri.

In generale, ci si può aspettare che se ci sono n possibili codici hash quindi le probabilità di ottenere un aumento di collisione drasticamente una volta che si hanno circa la radice quadrata di n elementi in gioco. Questo è il cosiddetto "paradosso del compleanno". Per il mio articolo su cui non si dovrebbe fare affidamento su codici hash per l'uguaglianza, vedi:

http: //blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx

Answer 2

No, non va bene, perché è non

equality <=> hashcode equality.

E ' solo

equality => hashcode equality.

o nell'altra direzione:

hashcode inequality => inequality.

http://msdn.microsoft.com/en -us / library / system.object.gethashcode.aspx :

  

    

Se due oggetti risultano uguali, il metodo GetHashCode per ogni oggetto deve restituire lo stesso valore. Tuttavia, se due oggetti non risultano uguali, i metodi GetHashCode per i due oggetti non devono restituire valori diversi.

  

Answer 3

direi, a meno che non si desidera per Equals fondamentalmente media "ha lo stesso codice hash come" per il tipo, quindi non , in quanto due stringhe possono essere diversi, ma condividono lo stesso codice hash. La probabilità può essere piccola, ma non è pari a zero.

Answer 4

No questo non è un modo accettabile per banco di prova per l'uguaglianza. E 'molto probabile per 2 valori non uguali hanno lo stesso codice hash. Ciò causerebbe l'implementazione di Equals per true ritorno quando deve restituire false

Answer 5

È possibile chiamare GetHashCode per determinare se gli elementi sono non uguale, ma se due oggetti restituiscono lo stesso codice hash, che non significa che sono uguali. Due elementi possono avere lo stesso codice hash, ma non essere uguali.

Se è costoso per confrontare due elementi, quindi è possibile confrontare i codici hash. Se essi non sono uguali, allora si può cauzione. In caso contrario (i codici hash sono uguali), si deve fare il confronto completo.

Ad esempio:

public override bool Equals(object obj)
  {
    Class1 other = obj as Class1;
    if (other == null || other.GetHashCode() != this.GetHashCode())
        return false;
    // the hash codes are the same so you have to do a full object compare.
  }

Answer 6

non può dire che solo perché i codici hash sono uguali, allora gli oggetti devono essere uguali.

L'unica volta che si sarebbe chiamata GetHashCode all'interno di Equals era se era molto più economico per calcolare un valore hash per un oggetto (ad esempio, perché si memorizza nella cache) che per verificare l'uguaglianza. In questo caso si potrebbe dire if (this.GetHashCode() != other.GetHashCode()) return false; modo che si potrebbe verificare rapidamente che gli oggetti non erano uguali.

Quindi, quando vorresti mai fare questo? Ho scritto un codice che prende screenshot a intervalli periodici e cerca di trovare quanto tempo è passato da quando lo schermo è cambiato. Dal momento che i miei screenshot sono 8MB e hanno relativamente pochi pixel che cambiano all'interno della schermata dell'intervallo è abbastanza costoso per cercare un elenco di loro di trovare quelli che sono gli stessi. Un valore hash è piccolo e deve solo essere calcolato una volta per schermata, rendendo più facile eliminare noti quelli non uguali. In realtà, nella mia richiesta ho deciso che avere hash identici era abbastanza vicino alla parità che non ho nemmeno la briga di implementare il sovraccarico di Equals, causando il compilatore C # per avvertire me che ero il sovraccarico GetHashCode senza sovraccaricare Equals.

Answer 7

C'è un caso in cui utilizzando codici hash come scorciatoia sulla confronti di uguaglianza ha un senso.

Si consideri il caso in cui si sta costruendo una tabella hash o hashset. In realtà, diciamo solo considerano hashsets (hashtables estendere che anche in possesso di un valore, ma che non è rilevante).

Ci sono vari differenti approcci si può prendere, ma in ognuno di essi si dispone di un piccolo numero di slot dei valori hash possono essere messi in, e noi prendere sia l'approccio aperto o chiuso (che solo per divertimento, alcune persone usano il gergo opposto per gli altri); se si scontrano nello stesso slot per due diversi oggetti possiamo o memorizzarli nella stessa scanalatura (ma avendo una lista collegata o tali per cui gli oggetti vengono effettivamente memorizzati) o ri-sondaggio per scegliere un altro slot (ci sono vari strategie per questo).

Ora, con entrambi gli approcci, ci stiamo allontanando dalla O (1) la complessità che vogliamo con una tabella hash, e verso una (n) la complessità O. Il rischio di questo è inversamente proporzionale al numero di slot disponibili, così dopo una certa dimensione che ridimensionare la tabella hash (anche se tutto era ideale, avremmo alla fine dobbiamo fare questo se il numero di elementi memorizzati fosse superiore al numero di slot).

Re-inserimento delle voci su un ridimensionamento ovviamente dipenderà dai codici hash. A causa di questo, mentre si rende raramente senso memoise GetHashCode() in un oggetto (semplicemente non viene chiamato spesso abbastanza sulla maggior parte degli oggetti), lo fa di certo senso per memoise entro la tabella di hash per sé (o forse, per un prodotto memoise risultato, ad esempio se si ri-hashed con un hash Wang / Jenkins per ridurre i danni causati da cattive implementazioni GetHashCode()).

Ora, quando arriviamo a inserire la nostra logica sta per essere qualcosa di simile:

1. Get codice hash per oggetto.
2. Get slot per oggetto.
3. Se slot è vuoto, posto oggetto in esso e ritorno.
4. Se slot contiene uguale oggetto, abbiamo finito per un hashset e hanno il grado di sostituire il valore di una tabella hash. Fate questo, e ritorno.
5. Prova slot successivo in base alla strategia di collisione, e ritorno al punto 3 (forse il ridimensionamento se ciclo troppo spesso).

Quindi, in questo caso, dobbiamo ottenere il codice hash, prima mettiamo a confronto per l'uguaglianza. Abbiamo anche il codice hash per gli oggetti esistenti già pre-calcolate per permettere il ridimensionamento. La combinazione di questi due mezzi fatti che ha senso per implementare il nostro confronto per il punto 4 come:

private bool IsMatch(KeyType newItem, KeyType storedItem, int newHash, int oldHash)
{
  return ReferenceEquals(newItem, storedItem) // fast, false negatives, no false positives (only applicable to reference types)
    ||
    (
      newHash == oldHash // fast, false positives, no fast negatives
      &&
      _cmp.Equals(newItem, storedItem) // slow for some types, but always correct result.
    );
}

Ovviamente, il vantaggio di questo dipende dalla complessità della _cmp.Equals. Se il nostro tipo di chiave era int allora questo sarebbe uno spreco totale. Se il nostro tipo di chiave dove stringa e usavamo confronti di uguaglianza Unicode-normalizzati case-insensitive (quindi non può nemmeno scorciatoia alla durata), il risparmio potrebbe essere valsa la pena.

In generale memoising codici hash non ha senso perché non sono utilizzati abbastanza spesso per essere una vittoria di prestazioni, ma la loro memorizzazione nella HashSet o in sé tabella hash può avere senso.

Answer 8

1. E 'implementazione sbagliato, come altri hanno detto perché.

2. Si dovrebbe corto circuito il controllo di uguaglianza con GetHashCode come:

   if (other.GetHashCode() != this.GetHashCode()
       return false;
   

   nel metodo Equals solo se si è certi è uguale alla conseguente implementazione è molto più costoso di GetHashCode , che non è stragrande maggioranza dei casi.

3. In questa implementazione hai mostrato (che è il 99% dei casi) la sua non è solo rotto, la sua anche molto più lento . E il motivo? INFORMATICA l'hash delle vostre proprietà sarebbe quasi certamente essere più lento di confrontandoli , quindi non sei nemmeno guadagnando in termini di prestazioni. Il vantaggio di attuazione di un GetHashCode corretta è quando la classe può essere il tipo di chiave per le tabelle hash in cui hash viene calcolato solo una volta (e tale valore viene utilizzato per il confronto). Nel tuo caso GetHashCode sarà chiamato più volte se è in una collezione. Anche se GetHashCode stesso dovrebbe essere veloce, non è per lo più veloce di equivalente Equals.

   Per riferimento, eseguire il Equals (una corretta attuazione, tirando fuori l'attuale implementazione basata hash) e GetHashCode qui

   var watch = Stopwatch.StartNew();
   for (int i = 0; i < 100000; i++) 
   {
       action(); //Equals and GetHashCode called here to test for performance.
   }
   watch.Stop();
   Console.WriteLine(watch.Elapsed.TotalMilliseconds);