¿Por qué es importante anular GetHashCode cuando se anula el método Equals?

1445

Dada la siguiente clase

public class Foo
{
    public int FooId { get; set; }
    public string FooName { get; set; }

    public override bool Equals(object obj)
    {
        Foo fooItem = obj as Foo;

        if (fooItem == null) 
        {
           return false;
        }

        return fooItem.FooId == this.FooId;
    }

    public override int GetHashCode()
    {
        // Which is preferred?

        return base.GetHashCode();

        //return this.FooId.GetHashCode();
    }
}

He anulado el Equalsmétodo porque Foorepresenta una fila para la Footabla s. ¿Cuál es el método preferido para anular el GetHashCode?

¿Por qué es importante anular GetHashCode?

David Basarab
fuente
36
Es importante implementar ambos, iguales y gethashcode, debido a colisiones, en particular al usar diccionarios. si dos objetos devuelven el mismo código hash, se insertan en el diccionario con encadenamiento. Al acceder al elemento se utiliza el método igual.
DarthVader

Respuestas:

1320

Sí, es importante si su elemento se utilizará como clave en un diccionario, HashSet<T>etc., ya que se utiliza (en ausencia de una costumbre IEqualityComparer<T>) para agrupar elementos en cubos. Si el código hash para dos elementos no coincide, es posible que nunca se consideren iguales ( simplemente no se llamarán iguales ).

El método GetHashCode () debe reflejar la Equalslógica; las reglas son:

  • si dos cosas son iguales ( Equals(...) == true), entonces deben devolver el mismo valor paraGetHashCode()
  • si el GetHashCode()es igual, es que no es necesario que sean los mismos; Esta es una colisión, y Equalsse llamará para ver si es una igualdad real o no.

En este caso, parece que " return FooId;" es una GetHashCode()implementación adecuada . Si está probando varias propiedades, es común combinarlas usando el código que se muestra a continuación, para reducir las colisiones diagonales (es decir, para que new Foo(3,5)tenga un código hash diferente new Foo(5,3)):

unchecked // only needed if you're compiling with arithmetic checks enabled
{ // (the default compiler behaviour is *disabled*, so most folks won't need this)
    int hash = 13;
    hash = (hash * 7) + field1.GetHashCode();
    hash = (hash * 7) + field2.GetHashCode();
    ...
    return hash;
}

Ah, por conveniencia, también puede considerar proporcionar ==y !=operadores al anular Equalsy GetHashCode.


Una demostración de lo que sucede cuando te equivocas está aquí .

Marc Gravell
fuente
49
¿Puedo preguntar ahy estás multiplicando con tales factores?
Leandro López el
22
En realidad, probablemente podría perder uno de ellos; el punto es tratar de minimizar el número de colisiones, para que un objeto {1,0,0} tenga un hash diferente a {0,1,0} y {0,0,1} (si ves lo que quiero decir) ),
Marc Gravell
13
Ajusté los números para hacerlo más claro (y agregué una semilla). Algunos códigos usan números diferentes; por ejemplo, el compilador de C # (para tipos anónimos) usa una semilla de 0x51ed270b y un factor de -1521134295.
Marc Gravell
76
@Leandro López: Por lo general, los factores se eligen como números primos porque hace que la cantidad de colisiones sea menor.
Andrei Rînea
29
"Oh, por conveniencia, también podría considerar proporcionar operadores == y! = Al anular Equals y GethashCode": Microsoft desaconseja implementar operator == para objetos que no son inmutables - msdn.microsoft.com/en-us/library/ ms173147.aspx - "No es una buena idea anular el operador == en tipos no inmutables".
antiduh
137

En realidad, es muy difícil de implementar GetHashCode()correctamente porque, además de las reglas que Marc ya mencionó, el código hash no debería cambiar durante la vida útil de un objeto. Por lo tanto, los campos que se utilizan para calcular el código hash deben ser inmutables.

Finalmente encontré una solución a este problema cuando estaba trabajando con NHibernate. Mi enfoque es calcular el código hash a partir de la ID del objeto. La ID solo se puede establecer a través del constructor, por lo que si desea cambiar la ID, lo cual es muy poco probable, debe crear un nuevo objeto que tenga una nueva ID y, por lo tanto, un nuevo código hash. Este enfoque funciona mejor con los GUID porque puede proporcionar un constructor sin parámetros que genera aleatoriamente una ID.

Albic
fuente
20
@vanja. Creo que tiene que ver con: si agrega el objeto a un diccionario y luego cambia la identificación del objeto, al buscarlo más adelante, usará un hash diferente para recuperarlo, por lo que nunca lo obtendrá del diccionario.
ANeves
74
La documentación de Microsoft de la función GetHashCode () no establece ni implica que el hash del objeto debe permanecer constante durante su vida útil. De hecho, explica específicamente un caso permisible en el que podría no ser así : "El método GetHashCode para un objeto debe devolver consistentemente el mismo código hash siempre que no haya ninguna modificación en el estado del objeto que determine el valor de retorno del método Equals del objeto ".
PeterAllenWebb
37
"el código hash no debería cambiar durante la vida útil de un objeto", eso no es cierto.
Apocalipsis
77
Una mejor manera de decirlo es que "el código hash (ni la evacuación de iguales) debe cambiar durante el período en que el objeto se usa como clave para una colección" Entonces, si agrega el objeto a un diccionario como clave, debe asegurarse de que GetHashCode e Equals no cambiarán su salida para una entrada determinada hasta que elimine el objeto del diccionario.
Scott Chamberlain
11
@ScottChamberlain Creo que no se olvidó en su comentario, debería ser: "el código hash (ni la evacuación de iguales) NO debería cambiar durante el período en que el objeto se usa como clave para una colección". ¿Derecha?
Stan Prokop
57

Al anular Equals, básicamente estás afirmando que eres el que sabe mejor cómo comparar dos instancias de un tipo determinado, por lo que es probable que seas el mejor candidato para proporcionar el mejor código hash.

Este es un ejemplo de cómo ReSharper escribe una función GetHashCode () para usted:

public override int GetHashCode()
{
    unchecked
    {
        var result = 0;
        result = (result * 397) ^ m_someVar1;
        result = (result * 397) ^ m_someVar2;
        result = (result * 397) ^ m_someVar3;
        result = (result * 397) ^ m_someVar4;
        return result;
    }
}

Como puede ver, solo trata de adivinar un buen código hash basado en todos los campos de la clase, pero dado que conoce el dominio o los rangos de valores de su objeto, aún podría proporcionar uno mejor.

Trampa
fuente
77
¿Esto no siempre devolverá cero? ¡Probablemente debería inicializar el resultado a 1! También necesita unos cuantos puntos y coma más.
Sam Mackrill
16
¿Sabe lo que hace el operador XOR (^)?
Stephen Drew el
1
Como dije, esto es lo que R # escribe para usted (al menos es lo que hizo en 2008) cuando se le solicitó. Obviamente, este fragmento está destinado a ser modificado por el programador de alguna manera. En cuanto a los puntos y comas faltantes ... sí, parece que los dejé fuera cuando copié y pegué el código de una selección de región en Visual Studio. También pensé que la gente resolvería ambos.
Trampa el
3
@SamMackrill He agregado los puntos y coma faltantes.
Matthew Murdoch
55
@SamMackrill No, no siempre devolverá 0. 0 ^ a = a, entonces 0 ^ m_someVar1 = m_someVar1. También podría establecer el valor inicial de resultto m_someVar1.
Millie Smith
41

No olvide comprobar el parámetro obj en contra nullal anular Equals(). Y también compara el tipo.

public override bool Equals(object obj)
{
    Foo fooItem = obj as Foo;

    if (fooItem == null)
    {
       return false;
    }

    return fooItem.FooId == this.FooId;
}

La razón de esto es: Equalsdebe devolver falso en comparación con null. Ver también http://msdn.microsoft.com/en-us/library/bsc2ak47.aspx

huha
fuente
66
Esta comprobación de tipo fallará en la situación en la que una subclase se refiere al método de la superclase Equals como parte de su propia comparación (es decir, base.Equals (obj)) - debería usarse como cambio
sweetfa
@sweetfa: depende de cómo se implemente el método Equals de la subclase. También podría llamar a base.Equals ((BaseType) obj)) que estaría funcionando bien.
huha
2
No, no lo hará: msdn.microsoft.com/en-us/library/system.object.gettype.aspx . Y además, la implementación de un método no debe fallar o tener éxito dependiendo de cómo se llame. Si el tipo de tiempo de ejecución de un objeto es una subclase de alguna clase base, entonces Equals () de la clase base debería devolver verdadero si de objhecho es igual a thisno importa cómo se llamó a Equals () de la clase base.
Júpiter
2
Mover fooItemhacia arriba y luego verificar que sea nulo funcionará mejor en el caso de nulo o un tipo incorrecto.
IllidanS4 quiere que Mónica regrese
1
@ 40Alpha Bueno, sí, entonces obj as Foosería inválido.
IllidanS4 quiere que Monica regrese
35

Qué tal si:

public override int GetHashCode()
{
    return string.Format("{0}_{1}_{2}", prop1, prop2, prop3).GetHashCode();
}

Asumiendo que el rendimiento no es un problema :)

Ludmil Tinkov
fuente
1
erm - pero estás devolviendo una cadena para un método basado en int; _0
jim tollan
32
No, llama a GetHashCode () desde el objeto String, que devuelve un int.
Richard Clayton el
3
No espero que esto sea tan rápido como me gustaría, no solo por el boxeo involucrado para los tipos de valor, sino también por el rendimiento de string.Format. Otro geek que he visto es new { prop1, prop2, prop3 }.GetHashCode(). Sin embargo, no puedo comentar cuál sería más lento entre estos dos. No abuses de las herramientas.
nawfal
16
Esto volverá verdadero para { prop1="_X", prop2="Y", prop3="Z" }y { prop1="", prop2="X_Y", prop3="Z_" }. Probablemente no quieras eso.
voetsjoeba
2
Sí, siempre puede reemplazar el símbolo de subrayado con algo no tan común (por ejemplo, •, ▲, ►, ◄, ☺, ☻) y esperar que sus usuarios no usen estos símbolos ... :)
Ludmil Tinkov
13

Tenemos dos problemas que enfrentar.

  1. No puede proporcionar un sensible GetHashCode()si cualquier campo en el objeto se puede cambiar. También, a menudo, un objeto NUNCA se usará en una colección de la que depende GetHashCode(). Por lo tanto, el costo de implementación a GetHashCode()menudo no vale la pena, o no es posible.

  2. Si alguien coloca su objeto en una colección que llama GetHashCode()y usted ha anulado Equals()sin hacer que se GetHashCode()comporte de manera correcta, esa persona puede pasar días rastreando el problema.

Por lo tanto, por defecto lo hago.

public class Foo
{
    public int FooId { get; set; }
    public string FooName { get; set; }

    public override bool Equals(object obj)
    {
        Foo fooItem = obj as Foo;

        if (fooItem == null)
        {
           return false;
        }

        return fooItem.FooId == this.FooId;
    }

    public override int GetHashCode()
    {
        // Some comment to explain if there is a real problem with providing GetHashCode() 
        // or if I just don't see a need for it for the given class
        throw new Exception("Sorry I don't know what GetHashCode should do for this class");
    }
}
Ian Ringrose
fuente
55
Lanzar una excepción de GetHashCode es una violación del contrato de Object. No hay dificultad para definir una GetHashCodefunción de modo que dos objetos que sean iguales devuelvan el mismo código hash; return 24601;y return 8675309;ambos serían implementaciones válidas de GetHashCode. El rendimiento de Dictionarysolo será decente cuando el número de elementos es pequeño, y se volverá muy malo si el número de elementos aumenta, pero en cualquier caso funcionará correctamente.
supercat
2
@supercat, no es posible implementar GetHashCode de manera sensata si los campos de identificación en el objeto pueden cambiar, ya que el código hash nunca debe cambiar. Hacer lo que dices podría llevar a alguien a tener que pasar muchos días rastreando el problema de rendimiento, luego muchas semanas en un gran rediseño del sistema para eliminar el uso de los diccionarios.
Ian Ringrose
2
Solía ​​hacer algo así para todas las clases que definí que necesitaban Equals (), y donde estaba completamente seguro de que nunca usaría ese objeto como clave en una colección. Entonces, un día, un programa en el que había usado un objeto como ese como entrada a un control DevExpress XtraGrid se bloqueó. Resulta que XtraGrid, a mis espaldas, estaba creando una HashTable o algo basado en mis objetos. Tuve una pequeña discusión con la gente de soporte de DevExpress sobre esto. Dije que no era inteligente que basaran la funcionalidad y confiabilidad de sus componentes en una implementación desconocida del cliente de un método oscuro.
RenniePet
La gente de DevExpress era bastante sarcástica, básicamente diciendo que debía ser un idiota para lanzar una excepción en un método GetHashCode (). Todavía creo que deberían encontrar un método alternativo para hacer lo que están haciendo: recuerdo a Marc Gravell en un hilo diferente que describe cómo construye un diccionario de objetos arbitrarios sin depender de GetHashCode (); no puedo recordar cómo lo hizo aunque.
RenniePet
44
@RenniePet, debe estar mejor enamorado de tirar una excepción, y luego tener un error muy difícil de encontrar debido a una implementación no válida.
Ian Ringrose
12

Esto se debe a que el marco requiere que dos objetos que sean iguales tengan el mismo código hash. Si anula el método de igualdad para hacer una comparación especial de dos objetos y el método considera que los dos objetos son iguales, entonces el código hash de los dos objetos también debe ser el mismo. (Los diccionarios y las tablas hash se basan en este principio).

kemiller2002
fuente
11

Solo para agregar las respuestas anteriores:

Si no anula Equals, el comportamiento predeterminado es que se comparan las referencias de los objetos. Lo mismo se aplica al código hash: la implicación predeterminada generalmente se basa en una dirección de memoria de la referencia. Debido a que reemplazó a Equals, significa que el comportamiento correcto es comparar lo que haya implementado en Equals y no las referencias, por lo que debe hacer lo mismo para el código hash.

Los clientes de su clase esperarán que el código hash tenga una lógica similar al método equals, por ejemplo, los métodos linq que usan un IEqualityComparer primero comparan los códigos hash y solo si son iguales compararán el método Equals () que podría ser más costoso para ejecutar, si no implementamos el código hash, el objeto igual probablemente tendrá códigos hash diferentes (porque tienen una dirección de memoria diferente) y se determinará erróneamente como no igual (Equals () ni siquiera golpeará).

Además, excepto el problema de que es posible que no pueda encontrar su objeto si lo usó en un diccionario (porque fue insertado por un código hash y cuando lo busca, el código hash predeterminado probablemente será diferente y nuevamente Equals () ni siquiera será llamado, como explica Marc Gravell en su respuesta, también introduce una violación del concepto de diccionario o hashset que no debería permitir claves idénticas: ya declaró que esos objetos son esencialmente los mismos cuando anula Iguales, por lo que no No los quiero a ambos como claves diferentes en una estructura de datos que supone tener una clave única. Pero debido a que tienen un código hash diferente, la clave "misma" se insertará como una clave diferente.

BornToCode
fuente
8

El código hash se usa para colecciones basadas en hash como Dictionary, Hashtable, HashSet, etc. El propósito de este código es ordenar previamente muy rápidamente un objeto específico colocándolo en un grupo específico (bucket). Esta clasificación previa ayuda enormemente a encontrar este objeto cuando necesita recuperarlo de la colección hash porque el código tiene que buscar su objeto en un solo cubo en lugar de en todos los objetos que contiene. La mejor distribución de los códigos hash (mejor singularidad) la recuperación más rápida. En una situación ideal donde cada objeto tiene un código hash único, encontrarlo es una operación O (1). En la mayoría de los casos se acerca a O (1).

Maciej
fuente
7

No es necesariamente importante; depende del tamaño de sus colecciones y sus requisitos de rendimiento y de si su clase se utilizará en una biblioteca donde es posible que no conozca los requisitos de rendimiento. Con frecuencia sé que los tamaños de mi colección no son muy grandes y mi tiempo es más valioso que unos pocos microsegundos de rendimiento obtenidos al crear un código hash perfecto; entonces (para deshacerme de la molesta advertencia del compilador) simplemente uso:

   public override int GetHashCode()
   {
      return base.GetHashCode();
   }

(Por supuesto, también podría usar un #pragma para desactivar la advertencia, pero prefiero de esta manera).

Cuando se encuentre en la posición que usted no necesita el rendimiento de todos los problemas mencionados por otros aquí se aplican, por supuesto. Lo más importante : de lo contrario, obtendrá resultados incorrectos cuando recupere elementos de un conjunto o diccionario de hash : el código de hash no debe variar con la vida útil de un objeto (más exactamente, durante el tiempo cada vez que se necesita el código de hash, como una clave en un diccionario): por ejemplo, lo siguiente es incorrecto ya que Value es público y, por lo tanto, se puede cambiar externamente a la clase durante el tiempo de vida de la instancia, por lo que no debe usarlo como base para el código hash:


   class A
   {
      public int Value;

      public override int GetHashCode()
      {
         return Value.GetHashCode(); //WRONG! Value is not constant during the instance's life time
      }
   }    

Por otro lado, si el valor no se puede cambiar, está bien usarlo:


   class A
   {
      public readonly int Value;

      public override int GetHashCode()
      {
         return Value.GetHashCode(); //OK  Value is read-only and can't be changed during the instance's life time
      }
   }
ILoveFortran
fuente
3
Voto negativo Esto es simplemente incorrecto. Incluso Microsoft declara en MSDN ( msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx ) que el valor de GetHashCode DEBE cambiar cuando el estado del objeto cambia de una manera que puede afectar el valor de retorno de una llamada to Equals (), e incluso en sus ejemplos también muestra implementaciones de GetHashCode que dependen completamente de valores públicamente modificables.
Sebastian PR Gingter
Sebastian, no estoy de acuerdo: si agrega un objeto a una colección que utiliza códigos hash, se colocará en un contenedor dependiente del código hash. Si ahora cambia el código hash, no volverá a encontrar el objeto en la colección, ya que se buscará el contenedor incorrecto. Esto es, de hecho, algo que ha sucedido en nuestro código y es por eso que me pareció necesario señalarlo.
ILoveFortran
2
Sebastian, además, no puedo ver una declaración en el enlace ( msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx ) que GetHashCode () debe cambiar. Por el contrario, NO debe cambiar siempre que Equals devuelva el mismo valor para el mismo argumento: "El método GetHashCode para un objeto debe devolver consistentemente el mismo código hash siempre que no haya ninguna modificación en el estado del objeto que determina el valor de retorno del método Equals del objeto. "Esta afirmación no implica lo contrario, que debe cambiar si el valor de retorno para Equals cambia.
ILoveFortran
2
@Joao, está confundiendo el lado del cliente / consumidor del contrato con el productor / implementador. Estoy hablando de la responsabilidad del implementador, que anula GetHashCode (). Estás hablando del consumidor, el que está usando el valor.
ILoveFortran
1
Completo malentendido ... :) La verdad es que el código hash debe cambiar cuando el estado del objeto cambia a menos que el estado sea irrelevante para la identidad del objeto. Además, nunca debe usar un objeto MUTABLE como clave en sus colecciones. Use objetos de solo lectura para este propósito. GetHashCode, Equals ... y algunos otros métodos cuyos nombres no recuerdo en este mismo momento NUNCA deberían arrojarse.
darlove el
0

Siempre debe garantizar que si dos objetos son iguales, según lo definido por Equals (), deberían devolver el mismo código hash. Como dicen algunos de los otros comentarios, en teoría esto no es obligatorio si el objeto nunca se usará en un contenedor basado en hash como HashSet o Dictionary. Sin embargo, te aconsejaría que sigas siempre esta regla. La razón es simplemente porque es demasiado fácil para alguien cambiar una colección de un tipo a otro con la buena intención de mejorar realmente el rendimiento o simplemente transmitir la semántica del código de una mejor manera.

Por ejemplo, supongamos que mantenemos algunos objetos en una Lista. Algún tiempo después, alguien se da cuenta de que un HashSet es una alternativa mucho mejor debido a las mejores características de búsqueda, por ejemplo. Aquí es cuando podemos meternos en problemas. List utilizaría internamente el comparador de igualdad predeterminado para el tipo, lo que significa Igual en su caso, mientras que HashSet utiliza GetHashCode (). Si los dos se comportan de manera diferente, también lo hará su programa. Y tenga en cuenta que tales problemas no son los más fáciles de solucionar.

He resumido este comportamiento con algunas otras dificultades de GetHashCode () en una publicación de blog donde puede encontrar más ejemplos y explicaciones.

Vasil Kosturski
fuente
0

A partir del .NET 4.7método preferido de anulación GetHashCode()se muestra a continuación. Si apunta a versiones anteriores de .NET, incluya el paquete nuget System.ValueTuple .

// C# 7.0+
public override int GetHashCode() => (FooId, FooName).GetHashCode();

En términos de rendimiento, este método superará a la mayoría de las implementaciones de código hash compuesto . El ValueTuple es un structmodo que no habrá ninguna basura, y el algoritmo subyacente es tan rápido como es posible.

l33t
fuente
-1

Tengo entendido que el GetHashCode original () devuelve la dirección de memoria del objeto, por lo que es esencial anularlo si desea comparar dos objetos diferentes.

EDITADO: Eso fue incorrecto, el método GetHashCode () original no puede asegurar la igualdad de 2 valores. Aunque los objetos que son iguales devuelven el mismo código hash.

usuario2855602
fuente
-6

A continuación, usar la reflexión me parece una mejor opción teniendo en cuenta las propiedades públicas, ya que con esto no tiene que preocuparse por la adición / eliminación de propiedades (aunque no es un escenario tan común). Esto me pareció funcionar mejor también. (Tiempo comparado usando cronómetro de Diagonistics).

    public int getHashCode()
    {
        PropertyInfo[] theProperties = this.GetType().GetProperties();
        int hash = 31;
        foreach (PropertyInfo info in theProperties)
        {
            if (info != null)
            {
                var value = info.GetValue(this,null);
                if(value != null)
                unchecked
                {
                    hash = 29 * hash ^ value.GetHashCode();
                }
            }
        }
        return hash;  
    }
Guanxi
fuente
12
Se espera que la implementación de GetHashCode () sea muy ligera. No estoy seguro de que el uso de la reflexión sea notable con StopWatch en miles de llamadas, pero seguramente está en millones (piense en llenar un diccionario de una lista).
bohdan_trotsenko