¿Cómo garantizar que hashCode() sea coherente 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 cada vez que se anula este método, para mantener el contrato general para el método hashCode, que establece que 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 al comparar objetos según la ubicación de la memoria, simplemente devuelva el entero único dirección del objeto)

¿Cómo se debe anular un método hashCode() para que devuelva un entero único para cada objeto basándose únicamente 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

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 completamente legal que dos objetos no iguales devuelvan el mismo código hash. Sin embargo, cuanto más exclusiva sea una distribución de código hash sobre un conjunto de objetos, mejor rendimiento obtendrá de HashMaps y otras operaciones que usan el código hash.

IDEs como IntelliJ Idea tienen generadores integrados para equals y hashCode que generalmente hacen un trabajo bastante bueno al obtener " suficientemente bueno " código para la mayoría de los objetos (y probablemente mejor que algunas funciones hash demasiado ingeniosas hechas a mano).

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 2

No entraré en los detalles de la unicidad de hashCode ya que Marc ya lo ha abordado. Para su clase People, primero debe decidir qué significa la igualdad de una persona. Tal vez la igualdad se base únicamente en su nombre, tal vez se base en el nombre y la edad. Será de dominio específico. Digamos que la igualdad se basa en el nombre y la edad. Su equals anulado se vería 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 anula hashCode debe anular <=>. Además, <=> no puede usar más campos en su cálculo que <=>. La mayoría de las veces debe agregar o excluir, o el código hash de los diversos campos (el código hash debe ser rápido de calcular). Por lo tanto, un método <=> válido podría verse así:

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

Tenga en cuenta que lo siguiente es no válido ya que utiliza un campo que <=> no lo hizo (altura). En este caso, dos & Quot; es igual a & Quot; los objetos 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 que dos objetos no iguales tengan el mismo código hash:

public int hashCode() {    
    return age;    
}

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

Answer 3

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 esas. 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 calcules el código hash de ese algo, luego modifícalo según 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.

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

También generalmente desea 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 gran matriz con muy pocas entradas y desperdicio de memoria, o una matriz más pequeña donde cada elemento de la matriz es una lista con & Gt; 1 entradas, y perder el tiempo recorriendo. Un hash perfecto asignaría cada objeto a una ubicación única en la matriz, sin desperdiciar espacio.

El término " hash perfecto " es un término real y, en algunos casos, puede crear una función hash que proporcione 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 devolverán 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 hash único de 4 bytes.

Un dato interesante: las matrices hash generalmente se dimensionan en función de los números primos, para dar la mejor oportunidad de asignación aleatoria cuando modifique los resultados, independientemente de cuán aleatorios sean realmente los códigos hash.

Editar basado 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 el JDK 1.5 HashMap. Aunque es menos eficiente en la memoria que una matriz simple, podría decirse que crea menos abandono al volver a escribir (porque las entradas se pueden desvincular de un depósito y volver a vincular a otro).

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

Answer 4

En general, el código hash no puede ser único, ya que hay más valores que los posibles códigos hash (enteros). Un buen código hash distribuye bien los valores entre los enteros. Una mala siempre podría dar el mismo valor y seguir siendo lógicamente correcta, solo conducirí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 encontrarla. O podría 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, generalmente selecciona un subconjunto de los campos a tener en cuenta tanto en el método hashCode () como en el método equals ().

Answer 5

Creo que lo entendiste mal. 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, debe ser idéntico a todos los objetos que son iguales, de lo contrario, cosas como las colecciones estándar no funcionarían (por ejemplo, buscaría algo en el conjunto de hash pero no lo encontraría).

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 6

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

Se puede verificar si hashCode es consistente a través de una prueba unitaria. Escribí una clase abstracta llamada EqualityTestCase , que realiza un puñado de comprobaciones de 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 burdo al comprobar si el hashCode es eficiente.

Answer 7

Esto es lo que la documentación nos dice sobre el método de código hash

@ javadoc

  

Cada vez que se invoca en   el mismo objeto más de una vez durante   una ejecución de una aplicación Java,   el método hashCode debe ser consistente   devolver el mismo número entero, siempre que no   información utilizada en comparaciones iguales   en el objeto se modifica. Esta   entero no necesita permanecer consistente   de una ejecución de una aplicación   a otra ejecución de la misma   aplicación.

Answer 8

Existe una noción de clave empresarial, que determina la unicidad 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 () deben implementarse utilizando los campos, que constituyen una clave empresarial. Esto garantiza que ambos métodos sean coherentes entre sí.