vulnerability - object equals java

¿Cómo asegurar que hashCode() sea consistente con equals()?

Question

Al anular la función equals () de java.lang.Object, los javadocs sugieren que,

generalmente es necesario anular el método hashCode siempre que se anule este método, a fin de mantener el contrato general para el método hashCode, que establece que los objetos iguales deben tener códigos hash iguales.

El método hashCode () debe devolver un entero único para cada objeto (esto es fácil de hacer cuando se comparan objetos basados ​​en la ubicación de la memoria, simplemente devuelve la dirección entera única del objeto)

¿Cómo debe anularse un método hashCode () para que devuelva un entero único para cada objeto basado solo en las propiedades de ese objeto?

public class People{
   public String name;
   public int age;

   public int hashCode(){
      // How to get a unique integer based on name and age?
   }
}
/*******************************/
public class App{
   public static void main( String args[] ){
       People mike = new People();
       People melissa = new People();
       mike.name = "mike";
       mike.age = 23;
       melissa.name = "melissa";
       melissa.age = 24;
       System.out.println( mike.hasCode() );  // output?
       System.out.println( melissa.hashCode(); // output?
   }
}

Answer 1

Creo que lo malentendiste. El código hash no tiene que ser exclusivo para cada objeto (después de todo, es un código hash) aunque obviamente no desea que sea idéntico para todos los objetos. Sin embargo, es necesario que sea idéntico a todos los objetos que son iguales, de lo contrario las cosas como las colecciones estándar no funcionarían (por ejemplo, buscarías algo en el conjunto de hash pero no lo encontrarías).

Para atributos sencillos, algunos IDE tienen constructores de funciones de código hash.

Si no usa IDEs, considere usar Apahce Commons y la clase HashCodeBuilder

Answer 2

En general, el código hash no puede ser único, ya que hay más valores que posibles códigos hash (enteros). Un buen código hash distribuye los valores bien sobre los enteros. Una mala siempre podría dar el mismo valor y seguir siendo lógicamente correcta, simplemente llevaría a tablas hash inaceptablemente ineficientes.

Los valores iguales deben tener el mismo valor hash para que las tablas hash funcionen correctamente. De lo contrario, podría agregar una clave a una tabla hash, luego tratar de buscarla a través de un valor igual con un código hash diferente y no encontrarlo. O puede poner un valor igual con un código hash diferente y tener dos valores iguales en diferentes lugares en la tabla hash.

En la práctica, normalmente selecciona un subconjunto de los campos que se deben tener en cuenta tanto en el método hashCode () como en el método equals ().

Answer 3

Esto es lo que nos dice la documentación en cuanto al método de código hash

@ javadoc

Cada vez que se invoca en el mismo objeto más de una vez durante la ejecución de una aplicación Java, el método hashCode debe devolver el mismo entero de forma consistente, siempre que no se modifique la información utilizada en comparaciones iguales en el objeto. Este entero no necesita ser consistente desde una ejecución de una aplicación hasta otra ejecución de la misma aplicación.

Answer 4

Existe una noción de clave comercial, que determina la singularidad de instancias separadas del mismo tipo. Cada tipo específico (clase) que modela una entidad separada del dominio objetivo (por ejemplo, un vehículo en un sistema de flota) debe tener una clave comercial, que está representada por uno o más campos de clase. Los métodos equals () y hasCode () deberían implementarse utilizando los campos, que constituyen una clave comercial. Esto asegura que ambos métodos sean consistentes entre sí.

Answer 5

La única obligación contractual para hashCode es que sea coherente . Los campos utilizados para crear el valor hashCode deben ser el mismo o un subconjunto de los campos utilizados en el método equals. Esto significa que devolver 0 para todos los valores es válido, aunque no eficiente.

Uno puede verificar si hashCode es consistente a través de una prueba unitaria. Escribí una clase abstracta llamada EqualityTestCase , que hace un puñado de verificaciones hashCode. Uno simplemente tiene que extender el caso de prueba e implementar dos o tres métodos de fábrica. La prueba hace un trabajo muy crudo de prueba si el hashCode es eficiente.

Answer 6

No dice que el código hash para un objeto tiene que ser completamente único, solo que el código hash para dos objetos iguales devuelve el mismo código hash. Es totalmente legal que dos objetos no iguales devuelvan el mismo código hash. Sin embargo, cuanto más única es la distribución de un código de hash sobre un conjunto de objetos, mejor será el rendimiento que obtendrá de HashMaps y otras operaciones que usen el código hash.

Los IDEs como IntelliJ Idea tienen generadores incorporados para equals y hashCode que generalmente hacen un muy buen trabajo al encontrar el código "suficientemente bueno" para la mayoría de los objetos (y probablemente mejor que algunas funciones hash demasiado ingeniosas).

Por ejemplo, aquí hay una función hashCode que Idea genera para su clase People:

public int hashCode() {
    int result = name != null ? name.hashCode() : 0;
    result = 31 * result + age;
    return result;
}

Answer 7

No entraré en los detalles de la singularidad de hashCode, ya que Marc ya lo ha abordado. Para su clase de People , primero necesita decidir qué significa la igualdad de una persona. Tal vez la igualdad se basa únicamente en su nombre, tal vez se basa en el nombre y la edad. Será específico del dominio. Digamos que la igualdad se basa en el nombre y la edad. Tus equals anulados se verían como

public boolean equals(Object obj) {
    if (this==obj) return true;
    if (obj==null) return false;
    if (!(getClass().equals(obj.getClass())) return false;
    Person other = (Person)obj;
    return (name==null ? other.name==null : name.equals(other.name)) &&
        age==other.age;
}

Cada vez que anule hashCode debe anular hashCode . Además, hashCode no puede usar más campos en su cálculo que los equals . La mayoría de las veces debe agregar o excluir, o el código hash de los diversos campos (hashCode debe ser rápido de calcular). Entonces, un método hashCode válido podría verse así:

public int hashCode() {
    return (name==null ? 17 : name.hashCode()) ^ age;
}

Tenga en cuenta que lo siguiente no es válido, ya que utiliza un campo que equals no (altura). En este caso, dos objetos "iguales" podrían tener un código hash diferente.

public int hashCode() {
    return (name==null ? 17 : name.hashCode()) ^ age ^ height;
}

Además, es perfectamente válido para dos objetos no iguales tener el mismo código hash:

public int hashCode() {    
    return age;    
}

En este caso, Jane de 30 años no es igual a Bob de 30 años, pero ambos códigos hash son 30. Si bien esto es válido, esto no es deseable para el rendimiento en colecciones basadas en hash.

Answer 8

Otra pregunta pregunta si hay algunas cosas básicas de bajo nivel que todos los programadores deberían saber, y creo que las búsquedas de hash son una de ellas. Así que aquí va.

Una tabla hash (tenga en cuenta que no estoy usando un nombre de clase real) es básicamente una matriz de listas vinculadas. Para encontrar algo en la tabla, primero se calcula el código hash de ese algo, luego se modifica por el tamaño de la tabla. Este es un índice en la matriz, y obtienes una lista vinculada en ese índice. Luego recorre la lista hasta que encuentre su objeto.

Como la recuperación de matriz es O (1), y el recorrido de la lista enlazada es O (n), desea una función de dispersión que cree una distribución lo más aleatoria posible, de modo que los objetos se hereden a diferentes listas. Cada objeto podría devolver el valor 0 como su código hash, y una tabla hash aún funcionaría, pero esencialmente sería una larga lista enlazada en el elemento 0 de la matriz.

También generalmente quiere que la matriz sea grande, lo que aumenta las posibilidades de que el objeto esté en una lista de longitud 1. Java HashMap, por ejemplo, aumenta el tamaño de la matriz cuando el número de entradas en el mapa es> 75 % del tamaño de la matriz. Aquí hay una compensación: puede tener una matriz enorme con muy pocas entradas y memoria inútil, o una matriz más pequeña donde cada elemento de la matriz es una lista con> 1 entrada, y perder el tiempo atravesando. Un hash perfecto asignaría cada objeto a una ubicación única en la matriz, sin espacio desperdiciado.

El término "hash perfecto" es un término real, y en algunos casos puede crear una función hash que proporciona un número único para cada objeto. Esto solo es posible cuando conoce el conjunto de todos los valores posibles. En el caso general, no puede lograr esto, y habrá algunos valores que devuelven el mismo código hash. Esto es matemática simple: si tiene una cadena de más de 4 bytes de longitud, no puede crear un código de hash único de 4 bytes.

Un tidbit interesante: los arrays hash generalmente se clasifican según los números primos, para dar la mejor oportunidad de asignación aleatoria cuando se modifican los resultados, independientemente de cuán aleatorios sean realmente los códigos hash.

Edición basada en comentarios:

1) Una lista vinculada no es la única forma de representar los objetos que tienen el mismo código hash, aunque ese es el método utilizado por JDK 1.5 HashMap. Aunque es menos eficiente en cuanto a la memoria que una matriz simple, sin duda crea menos abandono cuando se vuelve a procesar (porque las entradas se pueden desvincular de una categoría y volver a vincular a otra).

2) A partir de JDK 1.4, la clase HashMap usa una matriz de tamaño como potencia de 2; antes de eso, usé 2 ^ N + 1, que creo que es primo para N <= 32. Esto no acelera la indexación de arrays per se, pero sí permite que el índice de matriz se compute con un AND a nivel de bit en lugar de una división, como lo señaló Neil Coffey. Personalmente, cuestionaría esto como una optimización prematura, pero dada la lista de autores en HashMap, asumiré que hay algún beneficio real.