Anulando hashCode en Java para un caso específico

Question

Sé que hay otras preguntas sobre las mejores prácticas generales mientras se usa el hashCode y es igual, pero tengo una pregunta muy específica.

Tengo una clase que tiene como variable de instancia, una matriz de la misma clase. Para ser más explícitos, aquí está el código:

Class Node{ 
    Node arr[] = new Node[5]; 
} 

necesito para sobrescribir hashCode para el nodo de clase, y la matriz es un factor importante, decisivo para determinar si dos nodos son los mismos. ¿Cómo puedo incorporar la matriz en el cálculo de hashCode de manera efectiva?

--Edit--

Estoy tratando de comprobar si los dos nodos son los mismos, es decir que tienen el mismo número de niños, y que los niños llevan a exactamente los mismos estados. Por lo tanto, intento efectivamente comparar los subárboles en los dos nodos. Me pregunto si puedo usar hash para hacer este control de igualdad.

Creo que realmente necesito hash todo el subárbol, pero no estoy seguro de cómo voy a hacer eso dada la naturaleza recursiva de la definición de mi clase.

Answer 1

Incluye http://download.oracle.com/javase/6/docs/api/java/util/Arrays.html#hashCode (java.lang.Object []) como parte de la implementación de hashCode().

Answer 2

Depende de cuáles sean sus criterios de igualdad. ¿Es importante la orden en la matriz? Si es así, probablemente desee hacer que el código hash dependa del orden de los nodos en la matriz. Si no, puede hacer algo como XOR-ing los códigos hash de todos los nodos dentro de la matriz. Presumiblemente, algunos de los valores pueden ser nulos (así que ten cuidado con eso).

Básicamente, necesita anular hashCode y equals consistentemente de modo que si dos objetos son iguales, tendrán el mismo código hash. Esa es la regla de oro.

Eric Lippert tiene un great blog post about GetHashCode in .NET - el consejo se aplica igualmente bien para Java.

Un problema potencial a tener en cuenta: si termina con un ciclo en sus nodos (una referencia al nodo A que aparece en la matriz del nodo B y viceversa) podría terminar teniendo un ciclo en el código hash cálculo también.

Answer 3

Puede usar los métodos Arrays.hashCode() y Arrays.equals().

Answer 4

Estoy tratando de comprobar si los dos nodos son los mismos, es decir que tienen el mismo número de niños, y que esos niños conducir a exactamente los mismos estados. Por lo tanto, estoy efectivamente tratando de comparar los subárboles en el dos nodos. Me pregunto si puedo usar hash para hacer esta comprobación de igualdad.

No, hash no se debe utilizar para verificar la igualdad. Ese no es su propósito. Eventualmente puede ayudarte a descubrir si los objetos no son iguales, pero no te dirá nada si son iguales.

Los mismos objetos generarán el mismo valor hash, pero dos objetos diferentes que no son iguales también pueden generar el mismo hash.En otras palabras, si los valores de hash son diferentes, usted sabe con certeza que los objetos son diferentes. Eso es.

Si desea probar la igualdad, debe implementar equals. En su caso, existe el peligro de que su método sea recursivo y provoque un desbordamiento de la pila. ¿Qué pasa si tu objeto contiene una referencia a sí mismo?

Si desea generar un hash, podría tener en cuenta el tamaño de la matriz (y el hecho de que es nulo o no), pero no trataría de usar el valor hash de los objetos en la matriz , debido a posibles bucles infinitos. No es perfecto, pero es lo suficientemente bueno.

Hay otro método radical que también puede proporcionar un buen resultado. En lugar de calcular dinámicamente los valores hash, establezca un valor int aleatorio para cada instancia de objeto Node (me refiero a una vez por todas en la creación y siempre devuelvo ese valor). En su caso, no correría el riesgo de bucles infinitos tomando el valor hash de las instancias del objeto en su matriz.

Si los hashes son iguales, entonces tendría que comenzar a comparar instancias de objetos de matriz.

REM: Si los nodos contienen otros atributos, calcule el hash en estos otros atributos y olvídese de la matriz. Comience a investigar sobre el contenido/tamaño de la matriz si y solo si los hash son idénticos entre dos objetos.

REM2: Comentarios menciona gráfico DAG, lo que significa que no vamos a golpear problemas de recursividad. Sin embargo, esa condición no es suficiente para garantizar que deepHashCode() tenga éxito. Además, sería excesivo también. Hay una manera más eficiente de resolver este problema.

Si el método hash utilizado por el nodo solo usa la matriz para calcular un valor hash, entonces deepHashCode() puede funcionar. Pero no sería eficiente. Si el método hash usa otros atributos de nodo, entonces estos atributos tendrían que ser iguales también.

Hay una manera más rápida de comparar nodos para la igualdad. Marque cada instancia de nodo con un número único. Luego, para comparar dos nodos, primero compare su tamaño de matriz. Si es igual, entonces compara los nodos de cada matriz usando su número único. Si una matriz no 'tiene' el otro nodo, entonces no estamos tratando con nodos iguales. Esta solución es mucho más rápida que ir recursiva.

Answer 5

Algunos de los puntos que se agregan a las respuestas actuales, si el rendimiento es de alguna preocupación.

En primer lugar, debe decidir si orden de los nodos secundarios en un nodo es importante. Si no lo hacen, no puede usar el código hash para una matriz. Considere la posibilidad de configurar su función de código hash alrededor de lo definido por java.util.Set. También considere usar algunos pedidos internos para mejorar el rendimiento de igual a igual. Por ejemplo, si las profundidades/alturas de los subárboles son diferentes, puede ordenar por profundidad.

En segundo lugar, si sus subárboles son profundos, su código de hash puede ser muy costoso. Así que almacenaría en caché el código hash, y lo calcularía en el momento de la construcción (si su nodo es inmutable), o lo invalidaría luego de una mutación y lo recalcularía a pedido.

En tercer lugar, si sus subárboles son profundos, compruebe el código hash en igual() y devuelva falso anticipadamente. Sí, hashcode es inspeccionado por las implementaciones de Map, pero hay lugares donde el código simplemente compara dos objetos usando equals(), y pueden pagar un gran precio.

Por último, considere el uso de matrices.asList() (si el orden secundario es importante) o HashSet (si el orden no importa y no hay dos nodos secundarios iguales) en lugar de una matriz simple. Entonces equals y hashcode se reducen a la delegación de la llamada a la instancia del contenedor ... con el almacenamiento en caché apropiado de hashcode, por supuesto.