java - vulnerability - ¿Cómo garantizar que equals() y hashCode() estén sincronizados?

object equals java

Question

Estamos escribiendo una clase que requiere una lógica muy complicada para calcular equals () y hashCode (). Algo a lo largo de las líneas con:

@Getters @Setters @FieldDefaults(level=AccessLevel.PRIVATE)
public class ExternalData {
  TypeEnum type;
  String data;
  List<ExternalData> children;
} 

No construimos estos objetos, se deserializan desde XML desde un sistema complejo externo. Hay más de 20 tipos y, según el tipo, los datos pueden ignorarse, procesarse con hijos o procesarse sin hijos, y la comparación de datos para cada tipo de nodo depende del tipo.

Creamos equals () y hashCode () para reflejar todas esas reglas, pero recientemente nos encontramos con un problema que hashCode perdió la sincronización con iguales, lo que causó que se agregaran objetos iguales dos veces a un HashSet. Creo que HashMap (y HashSet para el caso) se implementan de esta manera en Java: https://en.wikipedia.org/wiki/Hash_table La implementación primero pone los objetos en cubos basados ​​en hashCode y luego, para cada uno, la verificación de los cubos es igual. En un escenario desafortunado en el que 2 objetos iguales irán a diferentes cubos, nunca serán comparados por iguales (). Por "fuera de sincronización" aquí quiero decir que entran en diferentes cubos.

¿Cuál es la mejor manera de asegurarse de que equals y hashCode no estén desincronizados?

Edición : esta pregunta es diferente de ¿Qué problemas se deben tener en cuenta cuando se reemplaza a equals y hashCode en Java? Allí preguntan sobre orientación genérica y la respuesta aceptada no se aplica a mi situación. Dicen "hacer que los iguales y el código hash sean consistentes", aquí estoy preguntando cómo hago exactamente eso.

Answer 1

Guava testlib library tiene una clase llamada EqualsTester que puede usarse para escribir pruebas para tus implementaciones equals() y hashCode() .

Agregar pruebas te ayuda a asegurarte de que el código es correcto ahora y también asegura que se mantenga correcto si lo modificas en el futuro.

Answer 2

Si a.equals(b) , esto implica a.hashcode() == b.hashcode() .

Sin embargo, ten cuidado . !a.equals(b) NO implica a.hashcode() != b.hashcode() .

Esto se debe simplemente a que las colisiones de hash pueden ser un problema grave dependiendo de su algoritmo y de una gran cantidad de factores. En general, si dos objetos son iguales, su código hash siempre será igual. Sin embargo, no puede determinar si dos objetos son iguales solo comparando hashcode, ya que a.hashode() == b.hashcode() tampoco implica a.equals(b) .

Answer 3

Si el algoritmo de recorrido es lo suficientemente complejo como para evitar repetirse, aísle el algoritmo en un método que puedan usar tanto equals como hashCode .

Veo dos opciones, que (como suele ser el caso) de intercambio entre ser de amplia aplicación y eficiencia.

Ampliamente aplicable

La primera opción es escribir un método de recorrido bastante general que acepte una interfaz funcional y le devuelva la llamada en cada etapa del recorrido, de modo que pueda pasar un lambda o instancia en él que contenga la lógica real que desea realizar durante el desplazamiento; El patrón de visitante . Esa interfaz querría tener una manera de decir "dejar de atravesar" (por ejemplo, para que equals pueda cancelarse cuando sabe que la respuesta es "no igual"). Conceptualmente , eso se vería algo así como:

private boolean traverse(Visitor visitor) {
    while (/*still traversing*/) {
        if (!visitor.visitNode(thisNode)) {
            return false;
        }
        /*determine next node to visit and whether done*/
    }
    return true;
}

Luego, equals y hashCode utilizan para implementar la verificación de igualdad o la creación de código hash sin tener que conocer el algoritmo de recorrido.

He elegido arriba para que el método devuelva una marca para saber si el recorrido finalizó antes, pero eso es un detalle de diseño. Es posible que no devuelva nada, o que devuelva this para el encadenamiento, lo que sea adecuado para su situación.

Sin embargo, el problema es que usarlo significa asignar una instancia (o usar un lambda, pero entonces probablemente deba asignar algo para que el lamba se actualice de todos modos para hacer un seguimiento de lo que está haciendo) y hacer muchas llamadas a métodos. Tal vez eso está bien en tu caso; tal vez es un asesino de rendimiento porque su aplicación necesita usar equals a mucho. :-)

Específico y eficiente

... y, por lo tanto, es posible que desee escribir algo específico para este caso, escribir algo que tenga la lógica para equals y el hashCode incorporado. hashCode el código hash cuando lo use el código hash, o un valor de hashCode para equals (0 = no igual hashCode 0 = igual). Ya no es generalmente útil, pero evita la creación de una instancia de visitante para pasar la sobrecarga de / lambda / sobrecarga de llamada. Conceptualmente , esto podría parecer algo como:

private int equalsHashCodeWorker(Object other, boolean forEquals) {
    int code = 0;

    if (forEquals && other == null) {
        // not equal
    } else {
        while (/*still traversing*/) {
            /*update `code` depending on the results for this node*/
        }
    }

    return code;    
}

Una vez más, los detalles serán, um, específicos para su caso, así como su guía de estilo y demás. Algunas personas hacen que el other argumento sirva para dos propósitos (tanto la bandera como el "otro" objeto) haciendo que equals maneje el other == null caso other == null sí mismo y solo llame a este trabajador cuando no tenga un objeto null . Prefiero evitar duplicar el significado de argumentos como ese, pero lo ves a menudo.

Pruebas

Independientemente del modo en que vaya, si está en una tienda con una cultura de pruebas, naturalmente, querrá realizar pruebas para los casos complejos que ya ha visto fracasar, así como otros casos en los que ve oportunidades de fracaso.

Nota al hashCode sobre hashCode

Independientemente de lo anterior, si espera que hashCode se llame mucho, puede considerar almacenar el resultado en un campo de instancia. Si el objeto con el que estás haciendo esto es mutable (y parece que lo es), invalidarás el código hash almacenado cada vez que mates el estado del objeto. De esa manera, si el objeto no ha cambiado, no tiene que repetir el recorrido en las llamadas subsiguientes a hashCode . Pero, por supuesto, si olvida invalidar el código hash incluso en uno de sus métodos de mutación ...

Answer 4

Una opción para condsider puede ser la generación de código. Básicamente, usted escribe una lista de cosas que deben compararse y tiene un programa que genera tanto un método igual como un método de código hash. Dado que ambos métodos se generan a partir de la misma lista de cosas para comparar, no deben quedar desincronizadas (siempre que los elementos individuales no lo hagan, por supuesto).