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

Question

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.

¿Alguien me puede mostrar un ejemplo simple en el que, si se infringe, puede causar un problema? Creo que tiene algo que ver con si usas esa clase como el tipo de teclas para Hashmap.

Answer 1

Sure:

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<Test> set = new HashSet<Test>(); 
set.put(new Test(3,4)); 
boolean b = set.contains(new Test(3, 10)); // false 

Técnicamente que debe ser cierto porque m == 3 en ambos casos.

En general, un HashMap funciona de la siguiente manera: 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 dado HashMap 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 (bit a bit) y el hashCode() con 15 (0x0F) obtendrá los últimos 4 bits, lo que equivale 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 existe una entrada en ese cubo se tiene lo que se llama una colisión . Hay varias maneras de solucionar esto, pero el utilizado por HashMap (y es probablemente el más común en general) es agrupando. Todas las entradas con el mismo hashCode enmascarado se ponen en una lista de algún tipo.

Así que para encontrar si una clave es dada en el mapa ya:

1. Calcular el código hash de máscaras;
2. Encuentra el cucharón apropiado;
3. Si está vacío, no se ha encontrado la clave;
4. Si no está vacío, recorra todas las entradas en la comprobación del depósito igual a().

Mirar a través de una cubeta 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)".

Puede 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, una. equals(b) == b.equals(a) == true) pero tienen diferentes códigos hash entonces el HashMap va a buscarles en (probablemente) el cubo equivocado que resulta en un comportamiento impredecible e indefinido.

Answer 2

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.

Answer 3

He aquí un pequeño ejemplo:

Set<Foo> myFoos = new HashSet<Foo>(); 
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. 
} 

Así, imaginemos que el código hash que se crea para firstFoo es 99999 y termina en un punto específico en el myFoos HashSet. Más tarde, cuando obtenga el someFoo y lo busque en el HashSet myFoos, necesita generar el mismo código hash para que pueda encontrarlo.

Answer 4

Los contenedores como HashSet se basan en la función hash para determinar dónde colocarlo y dónde obtenerlo cuando lo solicite. Si A.equals(B), un HashSet espera que A esté en el mismo lugar que B. Si ingresa A con el valor V, y busca B, debería esperar obtener V (ya que ha dicho A.equals(B)). Pero si A.hashcode()! = B.hashcode(), entonces el hashset puede no encontrar dónde lo pones.

Answer 5

Esto se discute en el Tema 8: Siempre anular hashCode cuando se sobrescribe equals de Java eficaz de Joshua Bloch:

Una fuente común de errores es la falta de reemplazar el método hashCode. Debe anular hashCode en todas las clases que anulan iguales. De lo contrario, dará como resultado una violación del contrato general para Object.hashCode, que previene que su clase funcione correctamente en conjunto con todas las recopilaciones basadas en hash, incluyendo HashMap, HashSet y Hashtable.

Aquí es el contrato, copiada de la especificación java.lang.Object:

• Cada vez que se invoca en el mismo objeto más de una vez durante una 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 igual (Objeto), al 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 igual (Objeto), llamar al método hashCode en cada uno de los dos objetos debe producir resultados enteros distintos. Sin embargo, el programador 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 violó cuando usted no puede anular hashCode es la segunda: La igualdad de los objetos deben tener códigos hash iguales. Dos instancias distintas pueden ser lógicamente iguales según el método equals de la clase, pero a el método hashCode de la clase Object, son solo dos objetos con nada en común con . 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 Fax simplista, cuya iguales método se construye de acuerdo a la receta en el punto 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, se podría esperar para volver m.get(new PhoneNumber(408 , 867, 5309))"Jenny", pero devuelve null. Observe que dos instancias de PhoneNumber son involucradas: una se usa para la inserción en HashMap, y una segunda instancia igual, se usa para la recuperación (intento) . El error de la clase PhoneNumber al reemplazar hashCode causa las dos instancias iguales tienen códigos hash desiguales, en violación de el contrato hashCode. Por lo tanto, el método get busca el número de teléfono en un cubo de hash diferente del en el que se almacenó mediante el método . La solución de este problema es como simple, ya que proporciona un método hashCode adecuado para la clase PhoneNumber. [...]

Véase el Chapter 3 para el contenido completo.

Answer 6

Es exactamente debido a las tablas hash.

Debido a la posibilidad de colisiones de códigos 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. Por lo tanto, cada get() en una tabla hash llama al key.equals(potentialMatch) antes de devolver un valor.

Si equals() y hashCode() son inconsistentes, puede tener un comportamiento muy incoherente. Digamos por dos objetos, a y b, a.equals(b) devuelve verdadero, pero a.hashCode() != b.hashCode(). Inserte ay HashSet devolverá falso para .contains(b), pero una lista creada a partir de ese conjunto devolverá verdadero (porque la lista no usa 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.