En Java, ¿por qué deben equals () y hashCode () ser consistentes?

Si anulo cualquiera de los métodos en una clase, debe asegurarse de que si A.equals(B) = true entonces (A.hashCode() == B.hashCode) también debe ser verdadero.

¿Puede alguien mostrarme un ejemplo simple donde si esto se viola, causará un problema? Creo que tiene algo que ver con si usas esa clase como el tipo de teclas para Hashmap.

Por supuesto:

 public class Test { private final int m, n; public Test(int m, int n) { this.m = m; this.n = n; } public int hashCode() { return n * m; } public boolean equals(Object ob) { if (ob.getClass() != Test.class) return false; Test other = (Test)ob; return m == other.m; } } 

con:

 Set set = new HashSet(); set.put(new Test(3,4)); boolean b = set.contains(new Test(3, 10)); // false 

Técnicamente, eso debería ser cierto porque m == 3 en ambos casos.

En general, un HashMap funciona así: tiene un número variable de lo que comúnmente se llama “cubos”. El número de depósitos puede cambiar con el tiempo (a medida que se agregan y eliminan entradas) pero siempre es una potencia de 2.

Digamos que un HashMap dado tiene 16 cubos. Cuando llama a put () para agregar una entrada, se calcula el hashCode () de la clave y luego se toma una máscara según el tamaño de las cubetas. Si usted (bitwise) AND hashCode () con 15 (0x0F) obtendrá los últimos 4 bits, lo que equivale a un número entre 0 y 15 inclusive:

 int factor = 4; int buckets = 1 < < (factor-1) - 1; // 16 int mask = buckets - 1; // 15 int code = key.hashCode(); int dest = code & mask; // a number from 0 to 15 inclusive 

Ahora si ya hay una entrada en ese cubo tienes lo que se llama una colisión . Hay varias maneras de lidiar con esto, pero el usado por HashMap (y probablemente el más común en general) es el de la creación de bloques . Todas las entradas con el mismo hashCode enmascarado se ponen en una lista de algún tipo.

Entonces, para encontrar si una clave dada ya está en el mapa:

  1. Calcule el código hash enmascarado;
  2. Encuentra el cubo apropiado;
  3. Si está vacío, no se encontró la clave;
  4. Si no está vacío, recorra todas las entradas en la casilla de comprobación del depósito igual a ().

Mirar a través de un cubo es una operación lineal (O (n)) pero está en un pequeño subconjunto. La determinación del cubo de hashcode es esencialmente constante (O (1)). Si los cubos son suficientemente pequeños, el acceso a un HashMap generalmente se describe como "cerca de O (1)".

Puedes hacer un par de observaciones sobre esto.

En primer lugar, si tiene un grupo de objetos que devuelven 42 como código hash, un HashMap seguirá funcionando, pero funcionará como una lista costosa. El acceso será O (n) (ya que todo estará en el mismo cubo, independientemente de la cantidad de cubos). De hecho, me han preguntado esto en una entrevista.

En segundo lugar, volviendo a su punto original, si dos objetos son iguales (es decir, a. Es equals(b) == b.equals(a) == true ) pero tienen diferentes códigos hash, entonces el HashMap irá buscando (probablemente) el incorrecto cubo que da como resultado un comportamiento impredecible e indefinido.

Esto se discute en el Ítem ​​8: Anule siempre el código hash cuando sobrescriba a Igual a Java efectivo de Joshua Bloch:

Una fuente común de errores es la falla al anular el método hashCode. Debe anular hashCode en cada clase que anule equals. De lo contrario, se producirá una infracción del contrato general de Object.hashCode, que impedirá que su clase funcione correctamente junto con todas las colecciones basadas en hash, incluidos HashMap, HashSet y Hashtable.

Aquí está el contrato, copiado de la especificación java.lang.Object:

  • Cada vez que se invoca en el mismo objeto más de una vez durante la ejecución de una aplicación, el método hashCode debe devolver consistentemente el mismo entero, 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.

  • Si dos objetos son iguales de acuerdo con el método equals (Object), entonces llamar al método hashCode en cada uno de los dos objetos debe producir el mismo resultado entero.

  • No es necesario que si dos objetos son desiguales de acuerdo con el método de igualdad (Objeto), al invocar el método hashCode en cada uno de los dos objetos se produzcan resultados enteros distintos. Sin embargo, el progtwigdor debe tener en cuenta que la producción de resultados enteros distintos para objetos desiguales puede mejorar el rendimiento de las tablas hash.

La disposición clave que se infringe cuando no se puede anular hashCode es la segunda: los objetos iguales deben tener códigos hash iguales. Dos instancias distintas pueden ser lógicamente iguales según el método equals de la clase, pero para el método hashCode de la clase Object, son solo dos objetos sin mucho en común. Por lo tanto, el método hashCode del objeto devuelve dos números aparentemente aleatorios en lugar de dos números iguales según lo requerido por el contrato.

Por ejemplo, considere la siguiente clase simple PhoneNumber, cuyo método equals se construye de acuerdo con la receta en el Ítem 7:

 public final class PhoneNumber { private final short areaCode; private final short exchange; private final short extension; public PhoneNumber(int areaCode, int exchange, int extension) { rangeCheck(areaCode, 999, "area code"); rangeCheck(exchange, 999, "exchange"); rangeCheck(extension, 9999, "extension"); this.areaCode = (short) areaCode; this.exchange = (short) exchange; this.extension = (short) extension; } private static void rangeCheck(int arg, int max, String name) { if (arg < 0 || arg > max) throw new IllegalArgumentException(name +": " + arg); } public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof PhoneNumber)) return false; PhoneNumber pn = (PhoneNumber)o; return pn.extension == extension && pn.exchange == exchange && pn.areaCode == areaCode; } // No hashCode method! ... // Remainder omitted } 

Supongamos que intenta utilizar esta clase con un HashMap:

 Map m = new HashMap(); m.put(new PhoneNumber(408, 867, 5309), "Jenny"); 

En este punto, puede esperar m.get(new PhoneNumber(408 , 867, 5309)) para devolver "Jenny" , pero devuelve null . Tenga en cuenta que dos instancias de PhoneNumber están involucradas: una se usa para la inserción en HashMap, y una segunda instancia igual se utiliza para la recuperación (intentada). La falla de la clase PhoneNumber para anular hashCode hace que las dos instancias iguales tengan códigos hash desiguales, en violación del contrato hashCode. Por lo tanto, el método get busca el número de teléfono en un cubo de hash diferente del que fue almacenado por el método put. La solución de este problema es tan simple como proporcionar un método hashCode adecuado para la clase PhoneNumber. […]

Vea el Capítulo 3 para el contenido completo.

Contenedores como HashSet confían en la función hash para determinar dónde colocarla y de dónde obtenerla cuando la solicite. Si A.equals(B) , entonces un HashSet espera que A esté en el mismo lugar que B Si coloca A con el valor V y busca B , debería esperar recuperar a V (ya que ha dicho A.equals(B) ). Pero si A.hashcode ()! = B.hashcode (), entonces el hashset puede no encontrar dónde lo pones.

Aquí hay un pequeño ejemplo:

 Set myFoos = new HashSet(); Foo firstFoo = new Foo(123,"Alpha"); myFoos.add(firstFoo); // later in the processing you get another Foo from somewhere Foo someFoo = //use imagination here...; // maybe you get it from a database... and it's equal to Foo(123,"Alpha) if (myFoos.contains(someFoo)) { // maybe you win a million bucks. } 

Por lo tanto, imagine que el hashCode que se crea para firstFoo es 99999 y termina en un punto específico en myFoos HashSet. Más tarde, cuando obtenga el someFoo y lo busque en el myFoos HashSet, necesita generar el mismo hashCode para que pueda encontrarlo.

Es exactamente debido a las tablas hash.

Debido a la posibilidad de colisiones de código hash, las tablas hash también deben verificar la identidad, de lo contrario, la tabla no puede determinar si encontró el objeto que estaba buscando, o uno con el mismo código hash. Entonces cada get() en una tabla hash llama a key.equals(potentialMatch) antes de devolver un valor.

Si equals() y hashCode() son inconsistentes, puede obtener un comportamiento muy inconsistente. Digamos por dos objetos, a y b , a.equals(b) devuelve true, pero a.hashCode() != b.hashCode() . Inserte un y un HashSet devolverá falso para .contains(b) , pero una lista creada a partir de ese conjunto devolverá verdadero (porque la lista no utiliza códigos hash).

 HashSet set = new HashSet(); set.add(a); set.contains(b); // false new ArrayList(set).contains(b); // true 

Obviamente, eso podría ser malo.

La idea detrás de esto es que dos objetos son “iguales” si todos sus campos tienen valores iguales. Si todos los campos tienen valores iguales, los dos objetos deben tener el mismo valor hash.