Asesoramiento General y las directrices sobre la manera correcta de reemplazar el objeto.GetHashCode()

StackOverflow https://stackoverflow.com/questions/1378686

  •  21-09-2019
  •  | 
  •  

Pregunta

De acuerdo a 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 pueden comparar como la igualdad, la GetHashCode métodos para que los dos objetos no tienen que devolver valores diferentes.

  2. El método GetHashCode para un objeto debe devolver el mismo código hash mientras no hay ninguna modificación en el estado del objeto que determina el valor de retorno del objeto del método Equals.Tenga en cuenta que esto sólo es cierto para la ejecución actual de una aplicación, y que otro código hash puede ser devuelto si la aplicación se ejecuta de nuevo.

  3. Para el mejor desempeño, una función hash debe generar una distribución aleatoria para todas las entradas.

Me encuentro en la siguiente situación:He creado una clase, implementado IEquatable<T> y anulado object.Equals(object). MSDN los estados que:

Tipos que Equivale a anular también deben reemplazar GetHashCode ;de lo contrario, Hashtable podría no funcionar correctamente.

Y, a continuación, por lo general se detiene un poco para mí.Porque, ¿cómo se puede reemplazar correctamente object.GetHashCode()?Nunca sabes por dónde empezar, y lo que parece ser un montón de trampas.

Aquí en StackOverflow, hay bastante un par de preguntas relacionadas con la GetHashCode primordial, pero la mayoría de ellos parece estar en muy determinados casos y temas específicos.Así que, por lo tanto me gustaría obtener una buena compilación de aquí.Un resumen con consejos generales y directrices.Qué hacer, qué no hacer, errores comunes, por donde empezar, etc.

Me gustaría ser dirigido especialmente a C#, pero yo creo que va a trabajar el tipo de la misma manera para los otros .NET languages así(?).

Creo que tal vez la mejor manera es crear una respuesta para cada tema con una rápida y respuesta corta primero (cerca de la línea si es posible), entonces tal vez algo más de información y final con preguntas relacionadas, debates, blogs, etc., si hay alguna.A continuación, puedo crear un post como el aceptado la respuesta (en la parte superior) con sólo una "tabla de contenidos".Trate de mantenerlo corto y conciso.Y no sólo se vinculan a otras preguntas y entradas de blog.Trate de tomar la esencia de ellos y, a continuación, más bien el enlace a la fuente (especialmente desde el origen podría desaparecer.También, por favor intente modificar y mejorar las respuestas en lugar de crearse un montón de muy similares.

Yo no soy muy buen escritor técnico, pero voy a intentar al menos el formato de respuestas, de modo que se ven iguales, crear la tabla de contenido, etc.También voy a tratar de buscar algunas de las preguntas relacionadas con aquí en ASÍ que las respuestas de las partes de estos y tal vez sacar la esencia de los que puede manejar.Pero como no soy muy estable en este tema, voy a tratar de mantenerse alejado de la mayoría de la parte :p

¿Fue útil?

Solución

Tabla de contenidos

Las cosas que me gustaría ser cubiertos, pero no han sido aún:

  • ¿Cómo crear el número entero (Cómo "convertir" un objeto en un int no era muy obvio para mí de todos modos).
  • ¿Qué campos de basar el código hash sobre.
    • Si sólo debe estar en campos inmutables, ¿y si los hay solamente mutables?
  • ¿Cómo generar una buena distribución aleatoria. (MSDN Propiedad # 3)
    • Parte de esto, parece que elegir un buen número primo mágica (han visto 17, 23 y 397 han utilizado), pero ¿cómo elegirlo, y para qué sirve exactamente?
  • ¿Cómo hacer que el código hash se mantiene igual durante toda la duración del objeto. (MSDN Propiedad # 2)
    • Especialmente cuando la igualdad se basa en los campos mutables. (MSDN Propiedad # 1)
  • ¿Cómo lidiar con los campos que son tipos complejos (no entre los incorporado en C # tipos ).
    • Los objetos complejos y estructuras, matrices, colecciones, listas, diccionarios, tipos genéricos, etc.
    • Por ejemplo, a pesar de que la lista o diccionario podría ser de sólo lectura, eso no significa que los contenidos de la misma son.
  • ¿Cómo lidiar con las clases heredadas.
    • En caso de que alguna manera incorporar base.GetHashCode() en su código hash?
  • Podría técnicamente simplemente ser perezoso y devolver 0? Sería muy romper MSDN lineamiento número # 3, pero que al menos asegúrese # 1 y # 2 fueron siempre es cierto: P
  • trampas y errores comunes.

Otros consejos

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

Son números primos. Los números primos son utilizados para la creación de códigos hash porque número primo maximizar el uso del espacio de código hash.

En concreto, comenzar con el pequeño número primo 3, y considerar sólo el bajo pedido nybbles 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 empezamos de nuevo. Sin embargo, se dará cuenta de que los múltiplos sucesivos de nuestro primer generan cada posible permutación de bits en nuestra 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 óptima para generar códigos hash casi al azar. La razón por la que normalmente vemos los números primos más grandes en lugar de números 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 del uso de un pequeño primer ni siquiera son pseudo-aleatorio - son simplemente una el aumento de secuencia hasta que se encuentra un desbordamiento. Para aleatoriedad óptima, un número primo que tiene como resultado el desbordamiento de bastante pequeños coeficientes se debe utilizar, a menos que usted puede garantizar que sus coeficientes no serán pequeñas.

Enlaces relacionados:

Se debe reemplazar cada vez que tenga una medida significativa de la igualdad para objetos de ese tipo (es decir, que es igual de anulación). Si conocieras el objeto no iba a ser desmenuzada por cualquier razón usted podría salir de ella, pero es poco probable que usted podría saber esto de antemano.

El hash debe basarse sólo en las propiedades del objeto que se utilizan para definir la igualdad ya que dos objetos que se consideran iguales deben tener el mismo código hash. En general que se suele hacer algo como: 


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

Por lo general Asumo la multiplicación de los valores en conjunto producirá una distribución bastante uniforme, asumiendo la función de código hash de cada propiedad hace lo mismo, aunque esto puede estar equivocado. Usando este método, si los objetos propiedades de igualdad que define el cambio, entonces el código hash también es probable que cambie, lo cual es aceptable teniendo en cuenta la definición # 2 en su pregunta. También se ocupa de todos los tipos de una manera uniforme.

Se puede devolver el mismo valor para todos los casos, aunque esto hará que cualquier algoritmo que utilizan hash (como dictionarys) muy lento - esencialmente todos los casos serán, ordenadas por el mismo cubo y la búsqueda se convertirá entonces en O (n) en vez de la O esperado (1). Esto, por supuesto niega cualquier beneficios del uso de tales estructuras para la búsqueda.

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

La anulación de este método es importante porque la siguiente propiedad que debe permanecer siempre 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 un blog en la aplicación de la igualdad, es que

Muchas clases de utilizar el código hash para clasificar un objeto.En particular, tablas hash y diccionarios tienden a colocar los objetos en cubos basados en su código hash.Cuando la comprobación de si un objeto ya está en la tabla hash se buscará primero en un balde.Si dos objetos son iguales, pero tienen diferentes códigos hash que se pueden poner en diferentes cubos y el diccionario no serían capaces de buscar el objeto.

Enlaces relacionados:

A) debe invalidar ambos iguales y GetHashCode si desea emplear valor de la igualdad en lugar de la igualdad de referencia por defecto. Con la tarde, dos referencias a objetos resultan ser iguales si ambos se refieren a la misma instancia de objeto. Con el primero se comparan como iguales si su valor es el mismo, aunque se refieran a objetos diferentes. Por ejemplo, es probable que desee emplear la igualdad de valor de Fecha, dinero y objetos Point.

B) Con el fin de poner en práctica la igualdad de valor debe invalidar iguales y GetHashCode. Ambos deben depender de los campos del objeto que encapsulan el valor. Por ejemplo, Date.Year, Date.Month y Date.Day; o Money.Currency y Money.Amount; o punto.x, Punto.y y Point.Z. También debe considerar el operador == primordial, el operador! =, Operador <, y el operador>.

C) El código hash no tiene que permanecer constante durante toda la duración del objeto. Sin embargo, debe permanecer inmutable, mientras participa como la llave en un hash. De MSDN mana para Dictionary: "Siempre y cuando un objeto se utiliza como una clave en el Diccionario <(Of <(TKey, TValue>)>), no debe cambiar en forma alguna que afecte a su valor hash." Si tiene que cambiar el valor de una clave de eliminar la entrada del diccionario, cambie el valor de la clave, y vuelva a colocar la entrada.

D) de la OMI, que va a simplificar su vida si sus objetos de valor son en sí mismos inmutable.

Cuando puedo reemplazar object.GetHashCode()?

MSDN :

  

Tipos que sobrescribir equals también debe reemplazar GetHashCode; de lo contrario, Hashtable podría no funcionar correctamente.

Enlaces relacionados:

¿Qué campos de basar el código hash sobre? Si sólo debe estar en campos inmutables, lo que si hay únicos mutables?

No necesita estar basada únicamente en los campos inmutables. Me basarlo en los campos que determinan el resultado del método es igual.

¿Cómo hacer que el código hash permanece igual durante toda la duración del objeto. (MSDN Propiedad # 2) Sobre todo cuando la igualdad se basa en los campos mutables. (MSDN Propiedad # 1)

Parece que malinterpretar Propiedad # 2. El código hash no tiene que permanecer igual thoughout el tiempo de vida de objetos. Simplemente tiene que permanecer igual, siempre y cuando los valores que determinan el resultado del método es igual no se cambian. Por lo tanto, lógicamente, se basa el código hash de sólo aquellos valores. Entonces no debería ser un problema. 

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

Haga lo mismo en el método de la GetHasCode CustomClass. Funciona como un encanto.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top