Problema de GetHashCode () al usar xor

Question

Entiendo que normalmente se supone que debes usar xor con GetHashCode () para producir un int para identificar tus datos por su valor (en lugar de por su referencia). Aquí hay un ejemplo simple:

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

La idea es que quiero comparar una instancia de Foo con otra en función del valor de las propiedades A y B. Si Foo1.A == Foo2.A y Foo1.B == Foo2.B, entonces tenemos igualdad .

Aquí está el problema:

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

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

Ambos producen un valor de 3 para GetHashCode (), lo que hace que Equals () devuelva verdadero. Obviamente, este es un ejemplo trivial, y con solo dos propiedades, simplemente podría comparar las propiedades individuales en el método Equals (). Sin embargo, con una clase más compleja esto se saldría de control rápidamente.

Sé que a veces tiene sentido establecer el código hash solo una vez y siempre devolver el mismo valor. Sin embargo, para los objetos mutables donde es necesaria una evaluación de la igualdad, no creo que sea razonable.

¿Cuál es la mejor manera de manejar los valores de propiedad que podrían intercambiarse fácilmente al implementar GetHashCode ()?

  

Ver también

     

¿Cuál es el mejor algoritmo para un System.Object.GetHashCode?

reemplazado

Answer 1

Primero apagado - No implemente Equals () solo en términos de GetHashCode () - los códigos hash a veces colisionarán incluso cuando los objetos no sean iguales.

El contrato para GetHashCode () incluye lo siguiente:

• códigos hash diferentes significa que los objetos definitivamente no son iguales
• los mismos códigos hash significan que los objetos podrían ser iguales (pero posiblemente no)

Andrew Hare sugirió que incorporara su respuesta:

Recomiendo que lea esto solución (por nuestra propia Jon Skeet , por cierto) para un " mejor " forma de calcular un código hash.

  

No, lo anterior es relativamente lento y   no ayuda mucho Algunas personas usan   XOR (p. Ej. A ^ b ^ c) pero prefiero el   tipo de método que se muestra en Josh Bloch   " Java efectivo " ;:

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

     

Los números 23 y 37 son números arbitrarios   que son primos.

     

El beneficio de lo anterior sobre el XOR   método es que si tienes un tipo   que tiene dos valores que son   con frecuencia lo mismo, XORing esos   los valores siempre darán lo mismo   resultado (0) mientras que lo anterior será   diferenciar entre ellos a menos que   eres muy desafortunado.

Como se mencionó en el fragmento anterior, también puede consultar el el libro de Joshua Bloch , Java efectivo, que contiene un buen tratamiento del tema (la discusión del código hash también se aplica a .NET).

Answer 2

Andrew ha publicado un buen ejemplo para generar un mejor código hash, pero también tenga en cuenta que no debe usar códigos hash como comprobación de igualdad, ya que no se garantiza que sean únicos.

Para un ejemplo trivial de por qué esto se considera un objeto doble. Tiene más valores posibles que un int, por lo que es imposible tener un int único para cada doble. Los hashes son realmente solo un primer paso, se usan en situaciones como un diccionario cuando necesita encontrar la clave rápidamente, al comparar primero los hashes, se puede descartar un gran porcentaje de las claves posibles y solo las claves con hashes coincidentes deben tener el gasto de una verificación de igualdad completa (u otros métodos de resolución de colisión ).

Answer 3

El hash siempre implica colisiones y hay que lidiar con él (es decir, comparar valores hash y, si son iguales, comparar exactamente los valores dentro de las clases para asegurarse de que las clases sean iguales).

Usando un XOR simple, obtendrá muchas colisiones. Si quiere menos, use algunas funciones matemáticas que distribuyen valores a través de diferentes bits (cambios de bits, multiplicación con primos, etc.).

Answer 4

Leer ¿Reemplazar GetHashCode para objetos mutables? C # y piense en implementar IEquatable<T>

Answer 5

Una generación rápida y buena distribución de hash

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

Answer 6

Por curiosidad ya que los códigos hash suelen ser una mala idea para la comparación, ¿no sería mejor simplemente hacer el siguiente código, o me estoy perdiendo algo?

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

Hay varias implementaciones de hash mejores. FNV hash por ejemplo.