Implementación predeterminada para Object.GetHashCode ()

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

Estoy tratando de decidir en qué casos debo empacar el mío y en qué casos puedo confiar en la implementación predeterminada para que me vaya 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 es correcto. Si escribes una estructura, es más común anular la igualdad (no menos importante para evitar el boxeo), ¡pero es muy raro que escribas una estructura de todos modos!

Al anular la igualdad, siempre debe tener Equals() y GetHashCode() equivalentes (es decir, para dos valores, si Equals() devuelve true, deben devolver el mismo código hash, pero no se requiere el inverso), y es común para proporcionar también operadores == / != , y a menudo para implementar IEquatable también.

Para generar el código hash, es común usar una sum factorizada, ya que esto evita las colisiones en los 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 se usa una sum no ponderada, o xor ( ^ ), etc.

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

Los tipos de datos básicos como byte , short , int , long , char y string implementan un buen método GetHashCode. Algunas otras clases y estructuras, como Point por ejemplo, implementan un método GetHashCode 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 de cada clase o estructura puede indicarle si invalida 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 método GetHashCode , debe hacer su propia implementación que use los miembros apropiados para calcular el código hash.

En términos generales, si está reemplazando a Equals, quiere anular GetHashCode. El motivo es que ambos se usan para comparar la igualdad de tu clase / estructura.

Igual se usa cuando se comprueba Foo A, B;

si (A == B)

Como sabemos que el puntero no coincide, 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 se usa en tablas hash. El hashcode generado por tu clase siempre debe ser el mismo para las clases que dan el estado.

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 la duración 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 en función de los valores internos en lugar de la referencia de los objetos.

Como no pude encontrar una respuesta que explique por qué deberíamos anular GetHashCode e Equals para las estructuras personalizadas y por qué la implementación predeterminada “no es adecuada para su uso como clave en una tabla hash”, dejaré un enlace a esta publicación de blog , 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).

Motivo por el que el hash predeterminado para las estructuras es lento y no muy bueno:

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

Un implementador de una función hash enfrenta un dilema: hacer una buena distribución de la función hash o hacerlo rápido. En algunos casos, es posible lograr ambos, pero es difícil hacerlo 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 forma de obtener un código hash de un campo en un método ValueType es usar la reflexión . Por lo tanto, los autores de CLR decidieron cambiar la velocidad de la distribución y la versión predeterminada de GetHashCode simplemente devuelve un código hash de un primer campo no nulo y lo “munges” con un id tipo […] Este es un comportamiento razonable a menos que sea no. 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 de almohadilla proporcionará el mismo resultado todo el tiempo. Y, como se puede imaginar, esto causará un impacto de rendimiento drástico si estas instancias se almacenan en un conjunto de hash o una tabla de hash.

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

[…] ValueType.Equals y ValueType.GetHashCode tienen una optimización especial. Si un tipo no tiene “punteros” y está empaquetado […] correctamente, entonces se usan más versiones óptimas: GetHashCode itera sobre una instancia y bloques XOR de 4 bytes y el método Equals compara dos instancias usando memcmp . […] Pero la optimización es muy engañosa. En primer lugar, es difícil saber cuándo se habilita la optimización […] En segundo lugar, 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ó de manera significativa causando un problema de rendimiento real, tomando minutos para inicializar una colección con decenas de miles de elementos.

Entonces, para responder la pregunta “¿en qué casos debo empaquetar la mía y en qué casos puedo confiar en la implementación predeterminada?”, Al menos en el caso de las estructuras , debe anular Equals y GetHashCode siempre que su estructura personalizada pueda ser utilizada como una clave en una tabla hash o Dictionary .
También recomendaría implementar IEquatable en este caso, para evitar el boxeo.

Como dicen las otras respuestas, si estás escribiendo una clase , el hash predeterminado usando la igualdad de referencia generalmente está bien, así que no me molestaría en este caso, a menos que necesites anular Equals (entonces deberías anular GetHashCode consecuencia) .