example c# .net hashcode gethashcode

example - gethashcode c# override



Consejos generales y directrices sobre cómo anular correctamente object.GetHashCode() (11)

Según MSDN , una función hash debe tener las siguientes propiedades:

  1. Si dos objetos se comparan como iguales, el método GetHashCode para cada objeto debe devolver el mismo valor. Sin embargo, si dos objetos no se comparan como iguales, los métodos GetHashCode para los dos objetos no tienen que devolver valores diferentes.

  2. El método GetHashCode para un objeto debe devolver constantemente el mismo código hash siempre que no haya ninguna modificación en el estado del objeto que determine el valor de retorno del método Equals del objeto. Tenga en cuenta que esto es cierto solo para la ejecución actual de una aplicación y que se puede devolver un código hash diferente si la aplicación se ejecuta de nuevo.

  3. Para obtener el mejor rendimiento, una función hash debe generar una distribución aleatoria para todas las entradas.

Me sigo encontrando en el siguiente escenario: he creado una clase, IEquatable<T> implementado IEquatable<T> y anulado object.Equals(object) . MSDN declara que:

Los tipos que anulan Igals también deben anular GetHashCode; de lo contrario, Hashtable podría no funcionar correctamente.

Y luego por lo general se detiene un poco para mí. Porque, ¿cómo anulas correctamente object.GetHashCode() ? Nunca se sabe realmente por dónde empezar, y parece que hay muchos escollos.

Aquí en StackOverflow, hay bastantes preguntas relacionadas con la anulación de GetHashCode, pero la mayoría de ellas parece ser en casos muy particulares y problemas específicos. Por lo tanto, por lo tanto, me gustaría obtener una buena compilación aquí. Una visión general con consejos generales y directrices. Qué hacer, qué no hacer, errores comunes, dónde empezar, etc.

Me gustaría que estuviera especialmente dirigido a C #, pero creo que funcionará de la misma manera para otros lenguajes .NET también (?).

Creo que tal vez la mejor manera es crear una respuesta por tema con una respuesta rápida y corta primero (cerca de una sola línea si es posible), luego tal vez un poco más de información y terminar con preguntas relacionadas, discusiones, publicaciones de blogs, etc. , si hay alguno. Luego puedo crear una publicación como la respuesta aceptada (para ponerla en la parte superior) con solo una "tabla de contenido". Intenta que sea breve y conciso. Y no solo enlace a otras preguntas y publicaciones del blog. Intente tomar la esencia de ellos y luego vincularlos a la fuente (especialmente porque la fuente podría desaparecer. Además, intente editar y mejorar las respuestas en lugar de crear muchas similares).

No soy un muy buen escritor técnico, pero al menos intentaré dar formato a las respuestas para que se parezcan, crear la tabla de contenidos, etc. También intentaré buscar algunas de las preguntas relacionadas aquí en SO que responden a partes de Estos y tal vez sacan la esencia de los que puedo manejar. Pero como no soy muy estable en este tema, intentaré mantenerme alejado en su mayor parte: p

Tabla de contenido

Cosas que me gustaría que me cubrieran, pero que aún no han sido:

  • Cómo crear el entero (de todos modos, cómo "convertir" un objeto en un int no era muy obvio para mí).
  • En qué campos basar el código hash.
    • Si solo debería estar en campos inmutables, ¿qué pasa si solo hay campos mutables?
  • Cómo generar una buena distribución aleatoria. (Propiedad # 3 de MSDN)
    • Parte de esto, parece elegir un buen número primo mágico (se han visto 17, 23 y 397), pero ¿cómo lo elige y para qué sirve exactamente?
  • Cómo asegurarse de que el código hash permanezca igual durante toda la vida útil del objeto. (Propiedad # 2 de MSDN)
    • Especialmente cuando la igualdad se basa en campos mutables. (Propiedad # 1 de MSDN)
  • Cómo tratar con los campos que son tipos complejos (no entre los tipos C # incorporados ).
    • Objetos y estructuras complejas, matrices, colecciones, listas, diccionarios, tipos genéricos, etc.
    • Por ejemplo, aunque la lista o el diccionario pueden ser de solo lectura, eso no significa que su contenido lo sea.
  • Cómo lidiar con las clases heredadas.
    • ¿Debería de alguna manera incorporar base.GetHashCode() en su código hash?
  • ¿Podrías técnicamente ser perezoso y devolver 0? Rompería en gran medida la directriz número 3 de MSDN, pero al menos se aseguraría de que los números 1 y 2 siempre fueran verdaderos: P
  • Escollos comunes y trampas.

¿Cuáles son esos números mágicos que se ven a menudo en las implementaciones de GetHashCode?

Son números primos. Los números primos se utilizan para crear códigos hash porque los números primos maximizan el uso del espacio del código hash.

Específicamente, comience con el número primo pequeño 3 y considere solo los nybbles de bajo orden de los resultados:

  • 3 * 1 = 3 = 3 (mod 8) = 0011
  • 3 * 2 = 6 = 6 (mod 8) = 1010
  • 3 * 3 = 9 = 1 (mod 8) = 0001
  • 3 * 4 = 12 = 4 (mod 8) = 1000
  • 3 * 5 = 15 = 7 (mod 8) = 1111
  • 3 * 6 = 18 = 2 (mod 8) = 0010
  • 3 * 7 = 21 = 5 (mod 8) = 1001
  • 3 * 8 = 24 = 0 (mod 8) = 0000
  • 3 * 9 = 27 = 3 (mod 8) = 0011

Y comenzamos de nuevo. Pero notará que los múltiplos sucesivos de nuestro primo generaron cada permutación posible de bits en nuestro nybble antes de comenzar a repetir. Podemos obtener el mismo efecto con cualquier número primo y cualquier número de bits, lo que hace que los números primos sean óptimos para generar códigos hash casi aleatorios. La razón por la que generalmente vemos primos más grandes en lugar de primos pequeños como 3 en el ejemplo anterior es que, para un mayor número de bits en nuestro código hash, los resultados obtenidos al usar un primo pequeño no son ni siquiera pseudoaleatorios, son simplemente una secuencia creciente hasta que se encuentra un desbordamiento. Para una aleatoriedad óptima, debe usarse un número primo que resulte en un desbordamiento para coeficientes bastante pequeños, a menos que pueda garantizar que sus coeficientes no serán pequeños.

Enlaces relacionados:

¿Cuándo object.GetHashCode() ?

Como dice MSDN :

Los tipos que anulan Igals también deben anular GetHashCode; de lo contrario, Hashtable podría no funcionar correctamente.

Enlaces relacionados:

¿En qué campos basar el código hash? Si solo debería estar en campos inmutables, ¿qué pasa si solo hay campos mutables?

No necesita basarse solo en campos inmutables. Lo basaría en los campos que determinan el resultado del método de iguales.

¿Por qué tengo que anular object.GetHashCode() ?

La anulación de este método es importante porque la siguiente propiedad siempre debe permanecer verdadera:

Si dos objetos se comparan como iguales, el método GetHashCode para cada objeto debe devolver el mismo valor.

La razón, según lo declarado por JaredPar en una publicación de blog sobre la implementación de la igualdad, es que

Muchas clases usan el código hash para clasificar un objeto. En particular, las tablas hash y los diccionarios tienden a colocar objetos en cubos según su código hash. Al verificar si un objeto ya está en la tabla hash, primero lo buscará en un cubo. Si dos objetos son iguales pero tienen diferentes códigos hash, se pueden colocar en diferentes cubos y el diccionario no buscará el objeto.

Enlaces relacionados:

Cómo asegurarse de que el código hash permanezca igual durante toda la vida útil del objeto. (Propiedad # 2 de MSDN) Especialmente cuando la igualdad se basa en campos mutables. (Propiedad # 1 de MSDN)

Parece que entiendes mal la Propiedad # 2. El código hash no necesita permanecer igual durante toda la vida útil de los objetos. Solo debe permanecer igual mientras no se cambien los valores que determinan el resultado del método equals. Entonces, lógicamente, basas el código hash en esos valores solamente. Entonces no debería haber un problema.

A) Debe anular tanto Equals como GetHashCode si desea emplear la igualdad de valores en lugar de la igualdad de referencia predeterminada. Con el último, dos referencias de objeto se comparan como iguales si ambas se refieren a la misma instancia de objeto. Con el primero, se comparan como iguales si su valor es el mismo, incluso si se refieren a objetos diferentes. Por ejemplo, es probable que desee emplear la igualdad de valores para los objetos Date, Money y Point.

B) Para implementar la igualdad de valores, debe anular Equals y GetHashCode. Ambos deben depender de los campos del objeto que encapsulan el valor. Por ejemplo, Date.Year, Date.Month and Date.Day; o Money.Currency and Money.mount; o Point.X, Point.Y y Point.Z. También debe considerar anular operador ==, operador! =, Operador <y operador>.

C) El código hash no tiene que permanecer constante durante toda la vida útil del objeto. Sin embargo, debe permanecer inmutable mientras participa como clave en un hash. De MSDN doco para Diccionario: "Siempre que un objeto se use como clave en el Diccionario <(Of <(TKey, TValue>)>), no debe cambiar de ninguna manera que afecte su valor hash". Si debe cambiar el valor de una clave, elimine la entrada del diccionario, cambie el valor de la clave y reemplace la entrada.

D) OMI, simplificará su vida si sus objetos de valor son en sí mismos inmutables.

Debe anularlo siempre que tenga una medida significativa de igualdad para los objetos de ese tipo (es decir, anule Igals). Si supiera que el objeto no se iba a romper por cualquier motivo, podría dejarlo, pero es poco probable que lo sepa de antemano.

El hash debe basarse solo en las propiedades del objeto que se utilizan para definir la igualdad, ya que dos objetos que se consideran iguales deberían tener el mismo código hash. En general, normalmente harías algo como:

public override int GetHashCode() { int mc = //magic constant, usually some prime return mc * prop1.GetHashCode() * prop2.GetHashCode * ... * propN.GetHashCode(); }

Generalmente supongo que multiplicar los valores juntos producirá una distribución bastante uniforme, asumiendo que la función de código de hash de cada propiedad hace lo mismo, aunque esto puede ser incorrecto. Usando este método, si las propiedades que definen la igualdad de los objetos cambian, entonces también es probable que cambie el código hash, lo cual es aceptable dada la definición # 2 en su pregunta. También se ocupa de todos los tipos de manera uniforme.

Podría devolver el mismo valor para todas las instancias, aunque esto hará que los algoritmos que usan el hash (como los diccionarios) sean muy lentos; esencialmente, todas las instancias estarán en el mismo grupo y la búsqueda se convertirá en O (n) en lugar de la esperada O (1). Por supuesto, esto niega cualquier beneficio de usar dichas estructuras para la búsqueda.

public override int GetHashCode() { return IntProp1 ^ IntProp2 ^ StrProp3.GetHashCode() ^ StrProp4.GetHashCode ^ CustomClassProp.GetHashCode; }

Haga lo mismo en el método GetHasCode de GetHasCode . Funciona de maravilla.