Implementación predeterminada para Object.GetHashCode ()

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

Estoy tratando de decidir en qué casos debo empacar el mío y en qué casos puedo confiar de manera segura en que la implementación predeterminada funcione bien. No quiero reinventar la rueda, si es posible.

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 una función ObjectNative :: GetHashCode 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 implementación completa de GetHashCodeEx es bastante grande, por lo que es más fácil simplemente vincular al código fuente de C ++ .

Para una clase, los valores predeterminados son esencialmente igualdad de referencia, y eso generalmente está bien. Si escribe una estructura, es más común anular la igualdad (no menos importante para evitar el boxeo), ¡pero es muy raro que escriba una estructura de todos modos!

Al anular la igualdad, siempre debe tener una coincidencia Equals()y GetHashCode()(es decir, para dos valores, si Equals()devuelve verdadero, deben devolver el mismo código hash, pero no es necesario lo inverso ), y es común también proporcionar ==/ !=operadores, y a menudo implementar IEquatable<T>también.

Para generar el código hash, es común usar una suma factorizada, ya que esto evita colisiones en valores emparejados, por ejemplo, para un hash básico de 2 campos:

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 lo mismo que el hash de {2,1}
• el hash de {1,1} no es lo mismo que el hash de {2,2}

etc., que puede ser común si solo usa una suma no ponderada, o xor ( ^), etc.

La documentación del GetHashCodemétodo para Object dice que "la implementación predeterminada de este método no debe usarse como un identificador de objeto único para propósitos de hash". y el de ValueType dice "Si llama al método GetHashCode del tipo derivado, es probable que el valor de retorno no sea adecuado para usarlo como clave en una tabla hash". .

Los tipos de datos básicos como byte, short, int, long, chary stringponer en práctica un método GetHashCode buena. Algunas otras clases y estructuras, como Pointpor ejemplo, implementan un GetHashCodemétodo que puede o no ser adecuado para sus necesidades específicas. Solo tienes que probarlo para ver si es lo suficientemente bueno.

La documentación para cada clase o estructura puede decirle si anula la implementación predeterminada o no. Si no lo anula, debe usar su propia implementación. Para cualquier clase o estructura que cree usted mismo donde necesite usar el GetHashCodemétodo, debe hacer su propia implementación que use los miembros apropiados para calcular el código hash.

Como no pude encontrar una respuesta que explique por qué deberíamos anular GetHashCodey Equalspara estructuras personalizadas y por qué la implementación predeterminada "no es probable que sea adecuada para usar como clave en una tabla hash", dejaré un enlace a este blog post , que explica por qué con un ejemplo de caso real de un problema que sucedió.

Recomiendo leer la publicación completa, pero aquí hay un resumen (énfasis y aclaraciones añadidas).

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

La forma en que está diseñado el CLR, cada llamada a un miembro definido en System.ValueTypeo System.Enumtipos [puede] 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 alcanzar a los dos, pero es difícil hacer esto de forma genérica en ValueType.GetHashCode.

La función hash canónica de una estructura "combina" códigos hash de todos los campos. Pero la única forma de obtener un código hash de un campo en un ValueTypemétodo es usar la reflexión . Por lo tanto, los autores de CLR decidieron cambiar la velocidad sobre la distribución y la GetHashCodeversión predeterminada solo devuelve un código hash de un primer campo no nulo y lo "combina" con una identificación de tipo [...] Este es un comportamiento razonable a menos que no sea . Por ejemplo, si tiene la mala suerte y el primer campo de su estructura tiene el mismo valor para la mayoría de las instancias, 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.Equalsy ValueType.GetHashCodetienen una optimización especial. Si un tipo no tiene "punteros" y está empaquetado [...] correctamente, se utilizan versiones más óptimas: GetHashCodeitera sobre una instancia y bloques XOR de 4 bytes y el Equalsmétodo compara dos instancias usando memcmp. [...] Pero la optimización es muy complicada. Primero, es difícil saber cuándo se habilita la optimización [...] Segundo, una comparación de memoria no necesariamente le dará los resultados correctos . Aquí hay un ejemplo simple: [...] -0.0y +0.0son 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; }
}

Utilizamos 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 el número de elementos en el conjunto aumentó significativamente causando un problema de rendimiento real, tomando minutos para inicializar una colección con decenas de miles de elementos.

Por lo tanto, para responder la pregunta "en qué casos debo empacar el mío y en qué casos puedo confiar con seguridad en la implementación predeterminada", al menos en el caso de las estructuras , debe anular Equalsy GetHashCodecada vez que su estructura personalizada se pueda usar como clave en una tabla hash o Dictionary.
También recomendaría implementar IEquatable<T>en este caso, para evitar el boxeo.

Como dicen las otras respuestas, si está escribiendo una clase , el hash predeterminado que usa la igualdad de referencia generalmente está bien, por lo que no me molestaría en este caso, a menos que necesite anular Equals(entonces tendría que anular en GetHashCodeconsecuencia).

En términos generales, si anula Iguales, desea anular GetHashCode. La razón de esto es porque ambos se usan para comparar la igualdad de su clase / estructura.

Igual se utiliza cuando se verifica Foo A, B;

si (A == B)

Como sabemos que no es probable que el puntero 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 generalmente es utilizado por tablas hash. El código hash generado por su clase siempre debe ser el mismo para un estado de entrega de clases.

Normalmente lo hago,

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

    return HashCode;
}

Algunos dirán que el código hash solo debe calcularse una vez por vida útil del objeto, pero no estoy de acuerdo con eso (y probablemente estoy equivocado).

Usando la implementación predeterminada proporcionada por el objeto, a menos que tenga la misma referencia a una de sus clases, no serán iguales entre sí. Al anular Equals y GetHashCode, puede informar la igualdad basada en valores internos en lugar de la referencia de objetos.

Si solo está tratando con POCO, puede usar esta utilidad para simplificar un poco su vida:

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