Si nunca utilizo HashSet, ¿debería implementar GetHashCode?

Question

Nunca necesito almacenar objetos en una tabla hash. La razón es doble:

• viene con una buena función hash es difícil y propenso a errores.
• un árbol AVL es casi siempre lo suficientemente rápido, y simplemente requiere un estricto orden de predicado, que es mucho más fácil de implementar.

La operación Equals() por otro lado es una función que se usa con mucha frecuencia.

Por lo tanto, me pregunto si es necesario implementar GetHashCode (que nunca necesito) al implementar la función Equals (que a menudo necesito)?

Answer 1

mi consejo - si no desea usarlo, anule y throw new NotImplementedException(); para que pueda ver dónde lo necesita.

Answer 2

No necesita implementarlo. Si escribe su propio método Equals(), le recomendaría utilizar alguna implementación de GetHashCode que no rompa el HashSet. Por ejemplo, podría devolver un valor estático (generalmente 42). El rendimiento de HashSet se reducirá drásticamente, pero al menos funcionará; nunca sabrá quién usará/editará/mantendrá su código en el futuro. (Edit: es posible que desee registrar una advertencia si dicha clase se utiliza en una estructura de hash con el fin de los primeros problemas de rendimiento spot)

EDIT: no sólo el uso XOR para combinar códigos hash de sus propiedades

Ya han dicho otros que simplemente puede combinar los códigos hash de todas sus propiedades. Sin embargo, en lugar de solo usar XOR, animo a multiplicar los resultados. XOR puede dar como resultado un valor de 0 si ambos valores son iguales (por ejemplo, 0xA^0xA == 0x0). Esto se puede mejorar fácilmente usando 0xA * 0xA, 0xA * 31 + 0xA o 0xA^(0xA * 31).

Aún así, la intención de mi respuesta es que cualquier función hash es mejor que una que no es consistente con iguales, incluso si solo devuelve un valor estático. Simplemente seleccione cualquier subconjunto de propiedades (de ninguna a todas) que use para igualdad y arroje los resultados juntos. Al seleccionar propiedades para código hash, prefiera esos subconjuntos pequeños cuyas combinaciones son bastante únicas (por ejemplo, nombre, apellido, fecha de nacimiento - no es necesario agregar toda la dirección)

Answer 3

Si usa Dictionary o SortedList, y anula Equals, necesita tener una función de hash, de lo contrario se romperán. Equals también se utiliza en todo el lugar en el BCL, y si alguien más usa sus objetos, esperarán que GetHashCode se comporte con sensatez.

Tenga en cuenta que una función hash no tiene por qué ser tan complicada. Una versión básica es tomar el hash de cualquier variable de miembro que esté utilizando para igualdad, multiplicar cada una con un número de coprime por separado y XOR juntas.

Answer 4

Próximamente adecuada función hash es no difícil. Muy a menudo, un simple XOR de los resultados de GetHashCode() de todos los campos es suficiente.

Answer 5

Creo que está bastante equivocado si cree que implementar un predicado de orden estricto es mucho más fácil de implementar que una función hash; necesita manejar una gran cantidad de casos extremos (valores nulos, jerarquías de clase). Y funciones hash aren't that difficult, realmente.

Answer 6

Si invalida equivalentes, debe anular GetHashCode() de MSDN: "Se recomienda que cualquier clase que anule Igual también anule System.Object.GetHashCode". http://msdn.microsoft.com/en-us/library/ms173147.aspx

Las dos funciones deben coincidir en el sentido de que si dos objetos son iguales deben tener el mismo valor hash. Eso no quiere decir que si dos objetos tienen el mismo hash, deberían ser iguales. No necesita un algoritmo hash demasiado complejo, pero debe intentar distribuirse bien a través del espacio entero.

Answer 7

Un árbol AVL será mucho más lento que una tabla hash. Si se trata de solo unos pocos artículos, entonces no será un gran problema. Las tablas hash tienen O (1) inserciones, eliminaciones y búsquedas, pero un árbol AVL tiene operaciones O (log (n)).

Me gustaría anular GetHashCode y Equals por dos razones.

• Realmente no es tan difícil obtener una distribución decente mediante el uso de una implementación XOR trivial.
• Si sus clases son parte de una API pública, entonces alguien más podría querer almacenarlas en una tabla hash.

Además, tengo que cuestionar la elección de BST. Los árboles AVL están un poco fuera de moda en estos días. Hay otras BST más modernas que son más fáciles de implementar y funcionan igual de bien (a veces mejor). Si realmente necesita una estructura de datos que mantenga el orden, considere estas alternativas.

• Red Black Tree - ya aplicadas por SortedDictionary.
• Skip List
• Scapegoat Tree
• Splay Tree

---

La estrategia XOR tiene un problema asociatividad sutil que puede provocar colisiones en algunos casos desde a^b = b^a. Hay una solución de Effective Java que ha logrado un reconocimiento similar al de un culto que es bastante simple de implementar también.