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 seguente è 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();
    }
}

L'implementazione del metodo Equals non dovrebbe essere sufficiente per confrontare due oggetti Box?È qui che diciamo al framework la regola utilizzata per confrontare gli oggetti.Perché è necessario GetHashCode?

Grazie.

Luciano

Answer 1

Prima un po' di background...

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

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

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

Un dizionario è una struttura dati davvero interessante che scambia un ingombro di memoria maggiore in cambio di costi (più o meno) costanti per le operazioni Aggiungi/Rimuovi/Ottieni.Tuttavia è una scelta sbagliata su cui ripetere.Internamente, un dizionario contiene una serie di contenitori in cui è possibile archiviare 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 archiviata la coppia chiave/valore.

Quando vuoi accedere al valore, passi nuovamente la chiave.Il metodo GetHashCode viene chiamato sulla chiave e viene individuato il bucket contenente il valore.

Quando un oggetto IEqualityComparer viene passato al costruttore di un dizionario, vengono utilizzati i metodi IEqualityComparer.Equals e IEqualityComparer.GetHashCode anziché i metodi sugli oggetti Key.

Ora per spiegare perché entrambi i metodi sono necessari, considera 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 caselle hanno lo stesso hashcode - 100^100^25 = 1000^1000^25 = 25 - anche se chiaramente non sono lo stesso oggetto.Il motivo per cui in questo caso sono lo stesso hashcode è perché stai utilizzando l'operatore ^ (OR esclusivo bit per bit), quindi 100^100 si annulla lasciando zero, così come 1000^1000.Quando due oggetti diversi hanno la stessa chiave, si parla di collisione.

Quando aggiungiamo due coppie chiave/valore con lo stesso hashcode a un dizionario, vengono entrambe archiviate nello stesso bucket.Pertanto, quando vogliamo recuperare un valore, il metodo GetHashCode viene chiamato sulla nostra chiave per individuare il bucket.Poiché nel bucket è presente più di un valore, il dizionario esegue un'iterazione su tutte le coppie chiave/valore nel bucket chiamando il metodo Equals sulle chiavi per trovare quello corretto.

Nell'esempio che hai pubblicato, 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 è archiviato l'oggetto.Quindi un dizionario non deve cercarlo.Calcola semplicemente l'hashcode e salta a quella posizione.Il metodo Equals è un test migliore dell'uguaglianza, ma non può essere utilizzato per mappare un oggetto in uno spazio di indirizzi.

Spero possa aiutare

Answer 2

GetHashCode viene utilizzato in colections dizionario e crea hash per memorizzare gli oggetti in esso. Ecco un articolo bello perché e come utilizzare IEqualtyComparer e GetHashCode http: //dotnetperls.com/iequalitycomparer

Answer 3

Anche se sarebbe possibile per un Dictionary<TKey,TValue> per avere il suo GetValue e metodi simili chiamare Equals su ogni singolo tasto memorizzato per vedere se corrisponde a quello ricercato, che sarebbe molto lento. Invece, come molte collezioni hash-based, si basa su di GetHashCode rapidamente escludere la maggior parte dei valori non corrispondenti dalla considerazione. Se chiamando GetHashCode su un elemento di essere ricercato rendimenti 42, e una collezione ha 53,917 articoli, ma chiamando GetHashCode su 53.914 delle voci dato un valore diverso da 42, allora solo 3 articoli dovranno essere rispetto a quelle ricercate. L'altro 53.914 possono essere ignorati.

Il motivo una GetHashCode è incluso in un IEqualityComparer<T> è quello di consentire la possibilità che il consumatore di un dizionario potrebbe voler considerare come oggetti uguali che normalmente non considerare l'altro come uguali. L'esempio più comune sarebbe un chiamante che vuole usare le stringhe come chiavi ma i confronti case-insensitive uso. Per fare quel lavoro in modo efficiente, il dizionario avrà bisogno di avere una qualche forma di funzione di hash che consentiranno di ottenere lo stesso valore per "Fox" e "Fox", ma si spera che produrre qualcosa di diverso per "box" o "zebra". Poiché il metodo GetHashCode integrato in String non funziona in questo modo, il dizionario avrà bisogno di ottenere un tale metodo da qualche altra parte, e IEqualityComparer<T> è il posto più logico dal momento che la necessità di un tale codice hash sarebbe fortemente associato ad un Equals metodo che considera "Fox" e "FOX" uguali tra loro, ma non "box" o "zebra".