Implementación predeterminada para Object.GetHashCode ()

162

¿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.

Fung
fuente
Eche un vistazo al comentario que dejé en el artículo: stackoverflow.com/questions/763731/gethashcode-extension-method
Paul Westcott
34
Aparte: puede obtener el código hash predeterminado (incluso cuando GetHashCode()se ha anulado) usandoSystem.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(obj)
Marc Gravell
@MarcGravell gracias por contribuir con esto, estaba buscando exactamente esta respuesta.
Andrew Savinykh
@MarcGravell Pero, ¿cómo haría esto con otro método?
Tomáš Zato - Restablece a Monica el

Respuestas:

86
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 ++ .

David Brown
fuente
55
Esa cita de documentación debe provenir de una versión muy temprana. Ya no se escribe así en los artículos actuales de MSDN, probablemente porque está bastante mal.
Hans Passant
44
Cambiaron la redacción, sí, pero todavía dice básicamente lo mismo: "En consecuencia, la implementación predeterminada de este método no debe usarse como un identificador de objeto único para propósitos de hash".
David Brown
77
¿Por qué la documentación afirma que la implementación no es particularmente útil para el hash? Si un objeto es igual a sí mismo y nada más, cualquier método de código hash que siempre devolverá el mismo valor para una instancia de objeto determinada, y generalmente devolverá diferentes valores para diferentes instancias, ¿cuál es el problema?
supercat
3
@ ta.speot.is: si lo que desea es determinar si una instancia en particular ya se ha agregado a un diccionario, la igualdad de referencia es perfecta. Con las cadenas, como notará, uno generalmente está más interesado en saber si una cadena que contiene la misma secuencia de caracteres ya se ha agregado. Es por eso que stringanula GetHashCode. Por otro lado, suponga que desea llevar un recuento de cuántas veces varios controles procesan Painteventos. Puede usar un Dictionary<Object, int[]>(cada int[]almacenado contendría exactamente un elemento).
supercat
66
@ It'sNotALie. Entonces agradezca a Archive.org por tener una copia ;-)
RobIII
88

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.

Marc Gravell
fuente
Excelente punto sobre el beneficio de un algoritmo de suma factorizada; ¡algo que no me había dado cuenta antes!
Laguna
¿La suma factorizada (como se escribió anteriormente) no ocasionará excepciones de desbordamiento ocasionalmente?
sinelaw
44
@sinelaw sí, debe realizarse unchecked. Afortunadamente, uncheckedes el valor predeterminado en C #, pero sería mejor hacerlo explícito; editado
Marc Gravell
7

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.

Guffa
fuente
2
No estoy de acuerdo con que deba agregar rutinariamente su propia implementación. Simplemente, la gran mayoría de las clases (en particular) nunca serán evaluadas para la igualdad, o donde estén, la igualdad de referencia incorporada está bien. En la ocasión (ya rara) de escribir una estructura, sería más común, cierto.
Marc Gravell
@Marc Gravel: Eso no es lo que quise decir. Ajustaré el último párrafo. :)
Guffa
Los tipos de datos básicos no implementan un buen método GetHashCode, al menos en mi caso. Por ejemplo, GetHashCode para int devuelve el número en sí: (123). GetHashCode () devuelve 123.
fdermishin
55
@ user502144 ¿Y qué hay de malo en eso? Es un identificador único perfecto que es fácil de calcular, sin falsos positivos sobre la igualdad ...
Richard Rast
@Richard Rast: está bien, excepto que las claves pueden estar mal distribuidas cuando se usan en un Hashtable. Eche un vistazo a esta respuesta: stackoverflow.com/a/1388329/502144
fdermishin
5

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).

geekley
fuente
1

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.

Bennett Dill
fuente
2
El enfoque ^ = no es un enfoque particularmente bueno para generar un hash: tiende a generar muchas colisiones comunes / predecibles, por ejemplo si Prop1 = Prop2 = 3.
Marc Gravell
Si los valores son los mismos, no veo un problema con la colisión ya que los objetos son iguales. Sin embargo, el 13 * Hash + NewHash parece interesante.
Bennett Dill
2
Ben: pruébalo para Obj1 {Prop1 = 12, Prop2 = 12} y Obj2 {Prop1 = 13, Prop2 = 13}
Tomáš Kafka
0

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;
    }
}
Daniel Marshall
fuente