Problema GetHashCode () utilizzando xor

Question

La mia comprensione è che in genere dovresti usare xor con GetHashCode () per produrre un int per identificare i tuoi dati in base al loro valore (al contrario del suo riferimento). Ecco un semplice esempio:

class Foo
{
    int m_a;
    int m_b;

    public int A
    {
        get { return m_a; }
        set { m_a = value; }
    }

    public int B
    {
        get { return m_b; }
        set { m_b = value; }
    }

    public Foo(int a, int b)
    {
        m_a = a;
        m_b = b;
    }

    public override int GetHashCode()
    {
        return A ^ B;
    }

    public override bool Equals(object obj)
    {
        return this.GetHashCode() == obj.GetHashCode();
    }
}

L'idea è che voglio confrontare un'istanza di Foo con un'altra in base al valore delle proprietà A e B. Se Foo1.A == Foo2.A e Foo1.B == Foo2.B, allora abbiamo uguaglianza .

Ecco il problema:

Foo one = new Foo(1, 2);
Foo two = new Foo(2, 1);

if (one.Equals(two)) { ... }  // This is true!

Entrambi producono un valore di 3 per GetHashCode (), facendo sì che Equals () restituisca true. Ovviamente, questo è un esempio banale e con solo due proprietà ho potuto semplicemente confrontare le singole proprietà nel metodo Equals (). Tuttavia, con una classe più complessa, ciò sfuggirebbe rapidamente alla mano.

So che a volte ha senso impostare il codice hash una sola volta e restituire sempre lo stesso valore. Tuttavia, per gli oggetti mutabili in cui è necessaria una valutazione dell'uguaglianza, non credo sia ragionevole.

Qual è il modo migliore per gestire i valori delle proprietà che potrebbero essere facilmente scambiati durante l'implementazione di GetHashCode ()?

  

Vedi anche

     

Qual è l'algoritmo migliore per un sovrascritto System.Object.GetHashCode?

Answer 1

Prima di tutto - Non implementare Equals () solo in termini di GetHashCode () - gli hashcode a volte si scontrano anche quando gli oggetti non sono uguali.

Il contratto per GetHashCode () include quanto segue:

• diversi hashcode significa che gli oggetti non sono assolutamente uguali
• stessi hashcode significa che gli oggetti potrebbero essere uguali (ma forse no)

Andrew Hare mi ha suggerito di incorporare la sua risposta:

Ti consiglio di leggere questo soluzione (dalla nostra Jon Skeet , a proposito) per un "migliore" modo per calcolare un hashcode.

  

No, quanto sopra è relativamente lento e   non aiuta molto. Alcune persone usano   XOR (es. A ^ b ^ c) ma preferisco il   tipo di metodo mostrato in Josh Bloch   " Java efficace " ;:

public override int GetHashCode()
{
    int hash = 23;
    hash = hash*37 + craneCounterweightID;
    hash = hash*37 + trailerID;
    hash = hash*37 + craneConfigurationTypeCode.GetHashCode();
    return hash;
}

     

Il 23 e il 37 sono numeri arbitrari   che sono co-prime.

     

Il vantaggio di cui sopra rispetto a XOR   il metodo è che se hai un tipo   che ha due valori che sono   spesso lo stesso, XORing quelli   i valori daranno sempre lo stesso   risultato (0) mentre lo farà sopra   distinguere tra loro a meno che   sei molto sfortunato.

Come menzionato nello snippet sopra, potresti anche guardare Il libro di Joshua Bloch , Effective Java, che contiene un buon trattamento dell'argomento (la discussione dell'hashcode si applica anche a .NET).

Answer 2

Andrew ha pubblicato un buon esempio per generare un codice hash migliore, ma ricorda anche che non dovresti usare i codici hash come controllo di uguaglianza, dal momento che non è garantito che siano univoci.

Per un banale esempio del perché questo è considerato un doppio oggetto. Ha più valori possibili di un int quindi è impossibile avere un int univoco per ogni doppio. Gli hash sono in realtà solo un primo passaggio, utilizzati in situazioni come un dizionario quando è necessario trovare rapidamente la chiave, confrontando prima gli hash è possibile escludere una grande percentuale delle possibili chiavi e solo le chiavi con hash corrispondenti devono avere le spese di un controllo completo sull'uguaglianza (o altri metodi di risoluzione delle collisioni )

Answer 3

L'hashing comporta sempre delle collisioni e devi affrontarlo (ad esempio, confrontare i valori di hash e, se sono uguali, confrontare esattamente i valori all'interno delle classi per essere sicuri che le classi siano uguali).

Usando un semplice XOR, otterrai molte collisioni. Se vuoi di meno, usa alcune funzioni matematiche che distribuiscono valori tra bit diversi (bit shift, moltiplicando con numeri primi, ecc.).

Answer 4

Leggi Sovrascrivere GetHashCode per oggetti mutabili? C # e pensa all'implementazione di IEquatable<T>

Answer 5

Una rapida generazione e una buona distribuzione dell'hash

public override int GetHashCode()
{
    return A.GetHashCode() ^ B.GetHashCode();         // XOR
}

Answer 6

Per curiosità dato che gli hashcode sono in genere una cattiva idea per il confronto, non sarebbe meglio semplicemente fare il seguente codice o mi sto perdendo qualcosa?

public override bool Equals(object obj)
{
    bool isEqual = false;
    Foo otherFoo = obj as Foo;
    if (otherFoo != null)
    {
        isEqual = (this.A == otherFoo.A) && (this.B == otherFoo.B);
    }
    return isEqual;
}

Answer 7

Esistono diverse implementazioni di hash migliori. hash FNV per esempio.