Qual è il ruolo di GetHashCode in IEqualityComparer <T> in .NET?

Question

Sto cercando di capire il ruolo del metodo GetHashCode dell'interfaccia IEqualityComparer.

L'esempio che segue è tratto da MSDN:

using System; 
using System.Collections.Generic; 
class Example { 
    static void Main() { 
     try { 

      BoxEqualityComparer boxEqC = new BoxEqualityComparer(); 

      Dictionary<Box, String> boxes = new Dictionary<Box, 
               string>(boxEqC); 

      Box redBox = new Box(4, 3, 4); 
      Box blueBox = new Box(4, 3, 4); 

      boxes.Add(redBox, "red"); 
      boxes.Add(blueBox, "blue"); 

      Console.WriteLine(redBox.GetHashCode()); 
      Console.WriteLine(blueBox.GetHashCode()); 
     } 
     catch (ArgumentException argEx) { 

      Console.WriteLine(argEx.Message); 
     } 
    } 
} 

public class Box { 
    public Box(int h, int l, int w) { 
     this.Height = h; 
     this.Length = l; 
     this.Width = w; 
    } 
    public int Height { get; set; } 
    public int Length { get; set; } 
    public int Width { get; set; } 
} 

class BoxEqualityComparer : IEqualityComparer<Box> { 

    public bool Equals(Box b1, Box b2) { 
     if (b1.Height == b2.Height & b1.Length == b2.Length 
          & b1.Width == b2.Width) { 
      return true; 
     } 
     else { 
      return false; 
     } 
    } 

    public int GetHashCode(Box bx) { 
     int hCode = bx.Height^bx.Length^bx.Width; 
     return hCode.GetHashCode(); 
    } 
} 

non caso in cui il metodo di implementazione Equals essere sufficiente per confrontare due oggetti di sicurezza? È lì che diciamo al framework la regola usata per confrontare gli oggetti. Perché è necessario il codice GetHash?

Grazie.

Lucian

Answer 1

Un po 'di fondo prima ...

Ogni oggetto in .NET ha un metodo e un metodo GetHashCode Uguale.

Il metodo Equals viene utilizzato per confrontare un oggetto con un altro oggetto, per verificare se i due oggetti sono equivalenti.

Il metodo GetHashCode genera una rappresentazione integer a 32 bit dell'oggetto. Poiché non vi è alcun limite alla quantità di informazioni che un oggetto può contenere, determinati codici hash sono condivisi da più oggetti, quindi il codice hash non è necessariamente univoco.

Un dizionario è una struttura di dati davvero interessante che offre un maggiore ingombro di memoria in cambio di (più o meno) costi costanti per le operazioni Aggiungi/Rimuovi/Acquista. È una scelta sbagliata per l'iterazione però. Internamente, un dizionario contiene una serie di bucket, in cui è possibile memorizzare i valori. Quando aggiungi una chiave e un valore a un dizionario, il metodo GetHashCode viene chiamato sulla chiave. L'hashcode restituito viene utilizzato per determinare l'indice del bucket in cui deve essere memorizzata la coppia chiave/valore.

Quando si desidera accedere al valore, si passa nuovamente alla chiave. Il metodo GetHashCode viene chiamato sulla chiave e il bucket che contiene il valore si trova.

Quando un componente IEquality viene passato nel costruttore di un dizionario, vengono utilizzati i metodi IEqualityComparer.Equals e IEqualityComparer.GetHashCode invece dei metodi sugli oggetti Key.

Ora, per spiegare il motivo per cui sono necessari entrambi i metodi, considerare questo esempio:

BoxEqualityComparer boxEqC = new BoxEqualityComparer(); 

Dictionary<Box, String> boxes = new Dictionary<Box, string>(boxEqC); 

Box redBox = new Box(100, 100, 25); 
Box blueBox = new Box(1000, 1000, 25); 

boxes.Add(redBox, "red"); 
boxes.Add(blueBox, "blue"); 

Utilizzando il metodo BoxEqualityComparer.GetHashCode nel tuo esempio, entrambe queste scatole hanno lo stesso codice hash - 100^100^25 = 1000^1000^25 = 25 - anche se chiaramente non sono lo stesso oggetto. La ragione per cui sono lo stesso hashcode in questo caso è perché si sta utilizzando l'operatore^(bitwise exclusive-OR) in modo che 100^100 si annulli lasciando zero, così come 1000^1000. Quando due oggetti diversi hanno la stessa chiave, la chiamiamo collisione.

Quando aggiungiamo due coppie di chiavi/valori con lo stesso codice hash a un dizionario, sono entrambe memorizzate nello stesso bucket. Quindi, quando vogliamo recuperare un valore, il metodo GetHashCode viene chiamato sulla nostra chiave per individuare il bucket.Poiché esiste più di un valore nel bucket, il dizionario esegue l'iterazione su tutte le coppie chiave/valore nel bucket chiamando il metodo Equals sulle chiavi per trovare quello corretto.

Nell'esempio che hai postato, le due caselle sono equivalenti, quindi il metodo Equals restituisce true. In questo caso il dizionario ha due chiavi identiche, quindi genera un'eccezione.

TLDR

Quindi, in sintesi, il metodo GetHashCode viene utilizzato per generare un indirizzo in cui è memorizzato l'oggetto. Quindi un dizionario non deve cercarlo. Calcola semplicemente l'hashcode e passa a quella posizione. Il metodo Equals è un test migliore di uguaglianza, ma non può essere utilizzato per mappare un oggetto in uno spazio indirizzo.

Speranza che aiuta

Answer 2

GetHashCode è utilizzato in colections dizionario e crea hash per memorizzare gli oggetti in esso. Ecco un bell'articolo perché e come utilizzare IEqualtyComparer e GetHashCodehttp://dotnetperls.com/iequalitycomparer

Answer 3

Mentre sarebbe possibile per un Dictionary<TKey,TValue> per avere il suo GetValue e metodi simili chiamano Equals su ogni singolo tasto memorizzato per vedere se corrisponde a quella ricercata, che sarebbe molto lenta. Al contrario, come molte raccolte basate su hash, si basa su GetHashCode per escludere rapidamente dalla maggior parte dei valori non corrispondenti. Se si chiama GetHashCode su un oggetto ricercato si ottiene 42, e una collezione ha 53.917 oggetti, ma chiamando GetHashCode su 53.914 degli articoli si ottiene un valore diverso da 42, quindi solo 3 elementi dovranno essere confrontati con quelli ricercati. L'altro 53,914 può tranquillamente essere ignorato.

La ragione di un GetHashCode è inclusa in un IEqualityComparer<T> è quello di consentire la possibilità che il consumatore di un dizionario potrebbe voler considerare come oggetti uguali che normalmente non quanto riguarda l'altro come uguali. L'esempio più comune potrebbe essere un chiamante che desidera utilizzare le stringhe come chiavi ma utilizzare confronti senza distinzione tra maiuscole e minuscole. Per fare in modo che funzioni in modo efficiente, il dizionario dovrà avere qualche forma di funzione hash che produrrà lo stesso valore per "Fox" e "FOX", ma si spera che produca qualcos'altro per "box" o "zebra". Poiché il metodo GetHashCode incorporato in String non funziona in questo modo, il dizionario dovrà ottenere tale metodo da un'altra parte e IEqualityComparer<T> è il posto più logico in quanto la necessità di un tale codice hash sarebbe fortemente associata a uno Equals metodo che considera "Fox" e "FOX" identici tra loro, ma non a "box" o "zebra".