override equals c# gethashcode

¿Por qué ValueType.GetHashCode() se implementa como es?

Question

De ValueType.cs

**Action: Our algorithm for returning the hashcode is a little bit complex. We look ** for the first non-static field and get it''s hashcode. If the type has no ** non-static fields, we return the hashcode of the type. We can''t take the ** hashcode of a static member because if that member is of the same type as ** the original type, we''ll end up in an infinite loop.

Me picó esto hoy cuando estaba usando KeyValuePair como clave en un Diccionario (almacenaba el nombre del atributo xml (enum) y su valor (cadena)), y esperaba que tuviera su código hash calculado en base a todos sus campos, pero según la implementación, solo consideró la parte clave.

Ejemplo (c / p de Linqpad):

void Main()
{
    var kvp1 = new KeyValuePair<string, string>("foo", "bar");
    var kvp2 = new KeyValuePair<string, string>("foo", "baz");

    // true
    (kvp1.GetHashCode() == kvp2.GetHashCode()).Dump();
}

Supongo que el primer campo no estático significa el primer campo en orden de declaración, lo que también podría causar problemas al cambiar el orden de las variables en la fuente por cualquier razón, y creyendo que no cambia el código semánticamente.

Answer 1

Bueno, existen ventajas y desventajas para cualquier implementación de GetHashCode() . Estas son, por supuesto, las cosas que sopesamos al implementar las nuestras, pero en el caso de ValueType.GetHashCode() existe una dificultad particular en el sentido de que no tienen mucha información sobre cuáles serán los detalles reales del tipo de concreto. Por supuesto, esto nos sucede a menudo cuando creamos una clase abstracta o una que pretende ser la base de clases que agregará mucho más en términos de estado, pero en esos casos tenemos una solución obvia de solo usar la implementación predeterminada de object.GetHashCode() menos que una clase derivada se object.GetHashCode() de object.GetHashCode() allí.

Con ValueType.GetHashCode() no tienen este lujo ya que la principal diferencia entre un tipo de valor y un tipo de referencia es, a pesar de la popularidad de hablar sobre los detalles de implementación de la pila frente a la pila, el hecho de que para una equivalencia de tipo de valor se relaciona valorar mientras que para una equivalencia de tipo de objeto se relaciona con la identidad (incluso cuando un objeto define una forma diferente de equivalencia anulando Equals() y GetHashCode() el concepto de referencia-igualdad todavía existe y sigue siendo útil.

Entonces, para el método Equals() la implementación es obvia; compruebe que los dos objetos son del mismo tipo, y si es así, compruebe también que todos los campos son iguales (en realidad hay una optimización que hace una comparación bit a bit en algunos casos, pero eso es una optimización con la misma idea básica).

Qué hacer para GetHashCode() ? Simplemente no hay una solución perfecta. Una cosa que podrían hacer es algún tipo de mult-then-add o shift-then-xor en cada campo. Eso probablemente daría un código hash bastante bueno, pero podría ser costoso si hubiera muchos campos (no importa que no se recomiende tener tipos de valores que tengan muchos campos, el implementador tiene que considerar que todavía pueden hacerlo, y de hecho incluso puede haber momentos en los que tenga sentido, aunque sinceramente no puedo imaginar un momento en el que tenga sentido y también tiene sentido hacerlo). Si supieran que algunos campos rara vez son diferentes entre instancias, podrían ignorar esos campos y aún tener un código hash bastante bueno, a la vez que ser bastante rápidos. Finalmente, pueden ignorar la mayoría de los campos, y esperan que el (los) que no ignoran varíen en su valor la mayor parte del tiempo. Fueron a la versión más extrema de este último.

(La cuestión de qué se hace cuando no hay campos de instancia es otro asunto y una opción bastante buena, tales tipos de valores son iguales a todas las demás instancias del mismo tipo, y tienen un código hash que coincide con eso).

Por lo tanto, es una implementación que apesta si está mezclando muchos valores donde el primer campo es el mismo (o devuelve el mismo código hash), pero otras implementaciones apestarían en otros casos (Mono utiliza todos los códigos hash de los campos juntos, mejor en tu caso, peor en otros).

La cuestión del cambio de orden de campo no importa, ya que el código de acceso está claramente establecido como válido para la vida útil de un proceso y no es adecuado para la mayoría de los casos en los que podría persistir más allá (puede ser útil en algunas situaciones de almacenamiento en caché donde no hace daño si las cosas no se encuentran correctamente después de un cambio de código).

Entonces, no es genial, pero nada sería perfecto. Muestra que siempre se deben considerar los dos lados de lo que significa "igualdad" cuando se utiliza un objeto como clave. Se arregla fácilmente en tu caso con:

public class KVPCmp<TKey, TValue> : IEqualityComparer<KeyValuePair<TKey, TValue>>, IEqualityComparer
{
  bool IEqualityComparer.Equals(object x, object y)
  {
      if(x == null)
        return y == null;
      if(y == null)
        return false;
      if(!(x is KeyValuePair<TKey, TValue>) || !(y is KeyValuePair<TKey, TValue>))
        throw new ArgumentException("Comparison of KeyValuePairs only.");
      return Equals((KeyValuePair<TKey, TValue>) x, (KeyValuePair<TKey, TValue>) y);
  }
  public bool Equals(KeyValuePair<TKey, TValue> x, KeyValuePair<TKey, TValue> y)
  {
      return x.Key.Equals(y.Key) && x.Value.Equals(y.Value);
  }
  public int GetHashCode(KeyValuePair<TKey, TValue> obj)
  {
      int keyHash = obj.GetHashCode();
      return ((keyHash << 16) | (keyHash >> 16)) ^ obj.Value.GetHashCode();
  }
  public int GetHashCode(object obj)
  {
      if(obj == null)
        return 0;
      if(!(obj is KeyValuePair<TKey, TValue>))
       throw new ArgumentException();
      return GetHashCode((KeyValuePair<TKey, TValue>)obj);
  }
}

Use esto como su comparador al crear su diccionario, y todo debería estar bien (solo necesita los métodos genéricos de comparación realmente, pero dejar el resto no hace daño y puede ser útil tenerlo a veces).

Answer 2

Gracias a todos por las respuestas muy, muy informativas. Sabía que tenía que haber algún fundamento en esa decisión, pero desearía que estuviera mejor documentado. No puedo usar v4 del framework así que no hay Tuple<> , y esa fue la razón principal por la que decidí KeyValuePair estructura KeyValuePair . Pero creo que no hay límites y tendré que hacer mi propia carrera. Una vez más, gracias a todos.

Answer 3

La implementación real de ValueType.GetHashCode () no coincide exactamente con el comentario. Tiene dos versiones del algoritmo, rápido y lento. Primero comprueba si la estructura contiene algún miembro de un tipo de referencia y si hay algún relleno entre los campos. El relleno es un espacio vacío en un valor de estructura, creado cuando el compilador JIT alinea los campos. Hay relleno en una estructura que contiene bool e int (3 bytes) pero sin relleno cuando contiene int e int, se ajustan perfectamente.

Sin una referencia y sin relleno, puede hacer la versión rápida ya que cada bit en el valor de la estructura es un bit que pertenece a un valor de campo. Simplemente xors 4 bytes a la vez. Obtendrás un código hash "bueno" que considera a todos los miembros. Muchos tipos de estructuras simples en el marco .NET se comportan de esta manera, como Punto y Tamaño.

Al fallar esa prueba, se trata de la versión lenta, el equivalente moral de la reflexión. Eso es lo que obtienes, tu KeyValuePair <> contiene referencias. Y este solo verifica el primer campo candidato, como dice el comentario. Esta es seguramente una optimización de perf, evitando quemar demasiado tiempo.

Sí, detalles desagradables y no tan conocidos. Por lo general, se descubre cuando alguien nota que su código de colección es una mierda.

Un detalle más insoportable: la versión rápida tiene un error que bytes cuando la estructura contiene un campo de un tipo decimal. Los valores 12m y 12.0m son lógicamente iguales pero no tienen el mismo patrón de bits. GetHashCode () dirá que no son iguales. Ay.

Answer 4

No lo implementé y no he hablado con las personas que sí lo hicieron. Pero puedo señalar algunas cosas.

(Antes de continuar, tenga en cuenta que aquí estoy hablando específicamente de códigos hash para equilibrar las tablas hash donde el contenido de la tabla es elegido por usuarios no hostiles. Los problemas de los códigos hash para la firma digital, la verificación de redundancia o garantizar el buen rendimiento de una tabla hash cuando algunos de los usuarios están montando ataques de denegación de servicio contra el proveedor de la tabla quedan fuera del alcance de esta discusión).

En primer lugar, como Jon señala correctamente, el algoritmo dado implementa el contrato requerido de GetHashCode. Puede ser subóptimo para sus propósitos, pero es legal. Todo lo que se requiere es que las cosas que se comparan sean iguales tengan códigos hash iguales.

Entonces, ¿qué son los "buenos para tener" además de ese contrato? Una buena implementación del código hash debe ser:

1) rápido ¡Muy rapido! Recuerde, el objetivo del código hash en primer lugar es encontrar rápidamente una ranura relativamente vacía en una tabla hash. Si el cálculo O (1) del código hash es en la práctica más lento que el tiempo O (n) necesario para realizar la búsqueda ingenuamente, entonces la solución del código hash es una pérdida neta.

2) Bien distribuido en el espacio de enteros de 32 bits para la distribución de entradas dada. Cuanto peor es la distribución entre los ints, más parecida a una búsqueda lineal ingenua que va a ser la tabla hash.

Entonces, ¿cómo harías un algoritmo hash para tipos de valores arbitrarios dados esos dos objetivos conflictivos ? Cada vez que gasta en un algoritmo de hash complejo que garantiza una buena distribución es tiempo mal empleado.

Una sugerencia común es "hash todos los campos y luego XOR juntos los códigos hash resultantes". Pero eso es mendigar la pregunta; XORing dos bits de 32 bits solo ofrece una buena distribución cuando las entradas mismas están muy bien distribuidas y no están relacionadas entre sí, y ese es un escenario poco probable:

// (Updated example based on good comment!)
struct Control
{
    string name;
    int x;
    int y;
}

¿Cuál es la probabilidad de que xey estén bien distribuidos en todo el rango de enteros de 32 bits? Muy bajo. Las probabilidades son mucho mejores de que sean pequeñas y cercanas entre sí , en cuyo caso, el hecho de combinar sus códigos hash hace que las cosas empeoren , no mejor . Al juntar enteros que están cerca uno del otro, se cierra la mayoría de los bits.

¡Además, esto es O (n) en el número de campos! Un tipo de valor con muchos campos pequeños tomaría un tiempo relativamente largo para calcular el código hash.

Básicamente, la situación en la que estamos aquí es que el usuario no proporcionó una implementación de código hash; o no les importa, o no esperan que este tipo sea utilizado alguna vez como clave en una tabla hash. Dado que no tienes información semántica sobre el tipo, ¿qué es lo mejor que puedes hacer? Lo mejor que puede hacer es lo que sea rápido y le da buenos resultados la mayor parte del tiempo.

La mayoría de las veces, dos instancias de estructura que difieren serán diferentes en la mayoría de sus campos, no solo en uno de sus campos, por lo que solo elegir uno de ellos y esperar que sea el que difiere parece razonable.

La mayoría de las veces, dos instancias de estructura que difieren tendrán cierta redundancia en sus campos, por lo que la combinación de los valores hash de muchos campos juntos probablemente disminuirá, no aumentará, la entropía en el valor hash, incluso si consume el tiempo que el algoritmo hash está diseñado para guardar.

Compare esto con el diseño de tipos anónimos en C #. Con los tipos anónimos, sabemos que es muy probable que el tipo se utilice como clave de una tabla. Sabemos que es muy probable que exista redundancia en las instancias de tipos anónimos (porque son resultados de un producto cartesiano u otra combinación). Y, por lo tanto, combinamos los códigos hash de todos los campos en un código hash. Si eso le da un mal rendimiento debido al exceso de códigos hash que se calculan, puede usar un tipo nominal personalizado en lugar del tipo anónimo.

Answer 5

Todavía debe obedecer el contrato de GetHashCode incluso si el orden de campo cambia: los valores iguales tendrán los mismos códigos hash, dentro de la duración de ese proceso.

En particular:

• Los valores no iguales no tienen que tener códigos hash no iguales
• Los códigos Hash no tienen que ser coherentes en todos los procesos (puede cambiar una implementación, reconstruir y todo debería funcionar, por lo que no debería haber códigos hash persistentes)

Ahora no digo que la implementación de ValueType sea una gran idea: causará succión de rendimiento de varias maneras ... pero no creo que esté realmente rota .