Implementación predeterminada para Object.GetHashCode()

Question

¿Cómo funciona la implementación predeterminada para GetHashCode() ¿trabajar?¿Y maneja estructuras, clases, matrices, etc.?eficiente y suficientemente bien?

Estoy tratando de decidir en qué casos debo empaquetar el mío propio y en qué casos puedo confiar con seguridad en que la implementación predeterminada funcionará bien.No quiero reinventar la rueda, si es posible.

Answer 1

namespace System {
    public class Object {
        [MethodImpl(MethodImplOptions.InternalCall)]
        internal static extern int InternalGetHashCode(object obj);

        public virtual int GetHashCode() {
            return InternalGetHashCode(this);
        }
    }
}

InternalGetHashCode se asigna a un ObjectNative :: GetHashCode función en el CLR, que se ve así:

FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {  
    CONTRACTL  
    {  
        THROWS;  
        DISABLED(GC_NOTRIGGER);  
        INJECT_FAULT(FCThrow(kOutOfMemoryException););  
        MODE_COOPERATIVE;  
        SO_TOLERANT;  
    }  
    CONTRACTL_END;  

    VALIDATEOBJECTREF(obj);  

    DWORD idx = 0;  

    if (obj == 0)  
        return 0;  

    OBJECTREF objRef(obj);  

    HELPER_METHOD_FRAME_BEGIN_RET_1(objRef);        // Set up a frame  

    idx = GetHashCodeEx(OBJECTREFToObject(objRef));  

    HELPER_METHOD_FRAME_END();  

    return idx;  
}  
FCIMPLEND

La plena aplicación de GetHashCodeEx es bastante grande, así que es más fácil vincular sólo para el C ++ código fuente .

Answer 2

Para una clase, los valores por defecto son esencialmente Referencia igualdad, y eso es por lo general muy bien. Si escribir una estructura, es más común para anular la igualdad (entre otras cosas para evitar el boxeo), pero es muy raro que escribir una estructura de todos modos!

Al reemplazar la igualdad, siempre debe tener un Equals() a juego y GetHashCode() (es decir, para dos valores, si Equals() devuelve verdadero que debe devolver el mismo hash de código, pero lo contrario es No requiere) - y es común para proporcionar también == / !=operators, y con frecuencia para implementar IEquatable<T> demasiado

.

Para generar el código hash, es común el uso de una suma factorizada, ya que esto evita colisiones en valores apareados - por ejemplo, para un hash básica 2 campo:

unchecked // disable overflow, for the unlikely possibility that you
{         // are compiling with overflow-checking enabled
    int hash = 27;
    hash = (13 * hash) + field1.GetHashCode();
    hash = (13 * hash) + field2.GetHashCode();
    return hash;
}

Esto tiene la ventaja de que:

• el hash de {1,2} no es el mismo que el hash de {2,1}
• el hash de {1,1} no es el mismo que el hash de {2,2}

etc -. Que puede ser común si simplemente usando una suma ponderada, o XOR (^), etc.

Answer 3

La documentación para el método GetHashCode para objeto dice "la implementación predeterminada de este método no debe ser utilizado como un identificador de objeto único para fines de hash." y el de ValueType dice " Si se llama método GetHashCode del tipo derivado, el valor de retorno no es probable que sea adecuado para su uso como una clave en una tabla hash ". .

Los tipos de datos básicos como byte, short, int, long, char y string implementar un buen método GetHashCode. Algunas otras clases y estructuras, como Point por ejemplo, implementar un método GetHashCode que pueden o no pueden ser adecuados para sus necesidades específicas. Sólo tienes que probarlo para ver si es lo suficientemente bueno.

La documentación para cada clase o estructura puede decir si se anula la aplicación predeterminada o no. Si no anula que usted debe utilizar su propia aplicación. Para cualquier clases o estructuras que se crean a sí mismo en que es necesario utilizar el método GetHashCode, usted debe hacer su propia aplicación que utiliza los miembros apropiados para calcular el código hash.

Answer 4

Como no pude encontrar una respuesta que explique por qué deberíamos anular GetHashCode y Equals para estructuras personalizadas y por qué la implementación predeterminada "no es probable que sea adecuada para usarla como clave en una tabla hash", dejaré un enlace a esta publicación de blog, lo que explica por qué con un ejemplo real de un problema que ocurrió.

Recomiendo leer el post completo, pero aquí hay un resumen (énfasis y aclaraciones añadidas).

Razón por la que el hash predeterminado para las estructuras es lento y no muy bueno:

La forma en que está diseñado el CLR, cada llamada a un miembro definido en System.ValueType o System.Enum tipos [pueden] causar una asignación de boxeo [...]

Un implementador de una función hash se enfrenta a un dilema:hacer una buena distribución de la función hash o hacerla rápida.En algunos casos, es posible lograr ambas cosas, pero es difícil hacer esto genéricamente en ValueType.GetHashCode.

La función hash canónica de una estructura "combina" códigos hash de todos los campos.Pero la única manera de obtener un código hash de un campo en un ValueType El método es utilizar la reflexión.Entonces, los autores de CLR decidieron cambiar la velocidad por encima de la distribución y el valor predeterminado. GetHashCode versión simplemente devuelve un código hash de un primer campo no nulo y lo "mordisquea" con una identificación de tipo [...] Este es un comportamiento razonable a menos que no lo sea.Por ejemplo, Si tiene mala suerte y el primer campo de su estructura tiene el mismo valor en la mayoría de los casos, entonces una función hash proporcionará el mismo resultado. todo el tiempo.Y, como puede imaginar, esto causará un impacto drástico en el rendimiento si estas instancias se almacenan en un conjunto hash o una tabla hash.

[...] La implementación basada en la reflexión es lenta.Muy lento.

[...] Ambos ValueType.Equals y ValueType.GetHashCode tener una optimización especial.Si un tipo no tiene "punteros" y está empaquetado correctamente [...] entonces se utilizan versiones más óptimas: GetHashCode itera sobre una instancia y realiza XOR en bloques de 4 bytes y Equals El método compara dos instancias usando memcmp.[...] Pero la optimización es muy complicada.Primero, es difícil saber cuándo está habilitada la optimización [...] Segundo, una comparación de memoria no necesariamente le dará los resultados correctos.Aquí hay un ejemplo simple:[...] -0.0 y +0.0 son iguales pero tienen diferentes representaciones binarias.

Problema del mundo real descrito en la publicación:

private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;
readonly struct ErrorLocation
{
    // Empty almost all the time
    public string OptionalDescription { get; }
    public string Path { get; }
    public int Position { get; }
}

Usamos una tupla que contenía una estructura personalizada con implementación de igualdad predeterminada.Y desafortunadamente, la estructura tenía un primer campo opcional que casi siempre era igual a [cadena vacía].El rendimiento estuvo bien hasta que la cantidad de elementos en el conjunto aumentó significativamente, lo que provocó un problema de rendimiento real, lo que llevó unos minutos inicializar una colección con decenas de miles de elementos.

Entonces, para responder a la pregunta "en qué casos debo empaquetar el mío y en qué casos puedo confiar con seguridad en la implementación predeterminada", al menos en el caso de estructuras, deberías anular Equals y GetHashCode siempre que su estructura personalizada pueda usarse como clave en una tabla hash o Dictionary.
También recomendaría implementar IEquatable<T> en este caso, para evitar el boxeo.

Como decían las otras respuestas, si estás escribiendo un clase, el hash predeterminado que usa igualdad de referencia suele estar bien, por lo que no me molestaría en este caso, a menos que necesitas anular Equals (entonces tendrías que anular GetHashCode respectivamente).

Answer 5

En general, si usted está anulando los Iguales, desea reemplazar GetHashCode. La razón de esto se debe a que ambos se utilizan para comparar la igualdad de la clase / estructura.

Es igual a se utiliza en la comprobación Foo A, B;

si (A == B)

Como sabemos el puntero no es probable que coincida, podemos comparar los miembros internos.

Equals(obj o)
{
    if (o == null) return false;
    MyType Foo = o as MyType;
    if (Foo == null) return false;
    if (Foo.Prop1 != this.Prop1) return false;

    return Foo.Prop2 == this.Prop2;
}

GetHashCode es generalmente utilizado por las tablas hash. El código hash generado por su clase debe ser siempre la misma durante las clases dan estado.

Me suelen hacer,

GetHashCode()
{
    int HashCode = this.GetType().ToString().GetHashCode();
    HashCode ^= this.Prop1.GetHashCode();
    etc.

    return HashCode;
}

Algunos dirán que el código hash sólo debe ser calculada una vez por duración de los objetos, pero no estoy de acuerdo con eso (y probablemente estoy equivocado).

Uso de la aplicación por defecto proporcionada por objeto, a menos que tenga la misma referencia a una de sus clases, no van a ser iguales entre sí. Anulando iguales y GetHashCode, puede informar de la igualdad basada en los valores internos en lugar de la referencia de objetos.

Answer 6

Si sólo se trata de POCOs puede usar esta utilidad para simplificar su vida algo:

var hash = HashCodeUtil.GetHashCode(
           poco.Field1,
           poco.Field2,
           ...,
           poco.FieldN);

...

public static class HashCodeUtil
{
    public static int GetHashCode(params object[] objects)
    {
        int hash = 13;

        foreach (var obj in objects)
        {
            hash = (hash * 7) + (!ReferenceEquals(null, obj) ? obj.GetHashCode() : 0);
        }

        return hash;
    }
}