Guía de hashCode () en Java

Programación

1. Información general

El hash es un concepto fundamental de la informática.

En Java, los algoritmos de hash eficientes respaldan algunas de las colecciones más populares que tenemos disponibles, como HashMap (para una mirada en profundidad a HashMap , no dude en consultar este artículo) y HashSet.

En este artículo, nos centraremos en cómo funciona hashCode () , cómo se integra en las colecciones y cómo implementarlo correctamente.

2. Uso de hashCode () en estructuras de datos

Las operaciones más simples sobre cobros pueden resultar ineficaces en determinadas situaciones.

Por ejemplo, esto desencadena una búsqueda lineal que es altamente ineficaz para listas de grandes tamaños:

List words = Arrays.asList("Welcome", "to", "Baeldung"); if (words.contains("Baeldung")) { System.out.println("Baeldung is in the list"); }

Java proporciona una serie de estructuras de datos para tratar este problema específicamente; por ejemplo, varias implementaciones de la interfaz Map son tablas hash.

Cuando se usa una tabla hash, estas colecciones calculan el valor hash para una clave dada usando el método hashCode () y usan este valor internamente para almacenar los datos, de modo que las operaciones de acceso sean mucho más eficientes.

3. La comprensión de cómo hashCode () Obras

En pocas palabras, hashCode () devuelve un valor entero, generado por un algoritmo hash.

Los objetos que son iguales (según su igual () ) deben devolver el mismo código hash. No es necesario que diferentes objetos devuelvan diferentes códigos hash.

El contrato general de hashCode () establece:

  • Siempre que se invoca en el mismo objeto más de una vez durante la ejecución de una aplicación Java, hashCode () debe devolver constantemente el mismo valor, siempre que no se modifique la información utilizada en las comparaciones iguales del objeto. Este valor no necesita permanecer consistente de una ejecución de una aplicación a otra ejecución de la misma aplicación.
  • Si dos objetos son iguales según el método equals (Object) , entonces llamar al método hashCode () en cada uno de los dos objetos debe producir el mismo valor
  • No es necesario que si dos objetos no son iguales según el método equals (java.lang.Object) , la llamada al método hashCode en cada uno de los dos objetos debe producir resultados enteros distintos. Sin embargo, los desarrolladores deben tener en cuenta que la producción de resultados enteros distintos para objetos desiguales mejora el rendimiento de las tablas hash.

“Por mucho que sea razonablemente práctico, el método hashCode () definido por la clase Object devuelve enteros distintos para objetos distintos. (Esto generalmente se implementa convirtiendo la dirección interna del objeto en un número entero, pero el lenguaje de programación JavaTM no requiere esta técnica de implementación) ".

4. Un Naive hashCode () Implementación

En realidad, es bastante sencillo tener una implementación de hashCode () ingenua que se adhiera completamente al contrato anterior.

Para demostrar esto, vamos a definir una clase de usuario de muestra que anula la implementación predeterminada del método:

public class User { private long id; private String name; private String email; // standard getters/setters/constructors @Override public int hashCode() { return 1; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null) return false; if (this.getClass() != o.getClass()) return false; User user = (User) o; return id == user.id && (name.equals(user.name) && email.equals(user.email)); } // getters and setters here }

La clase User proporciona implementaciones personalizadas para equals () y hashCode () que se adhieren completamente a los contratos respectivos. Aún más, no hay nada ilegítimo en que hashCode () devuelva un valor fijo.

Sin embargo, esta implementación degrada la funcionalidad de las tablas hash a básicamente cero, ya que todos los objetos se almacenarían en el mismo depósito único.

En este contexto, la búsqueda de una tabla hash se realiza de forma lineal y no nos da ninguna ventaja real; más sobre esto en la sección 7.

5. Mejora de la hashCode () Implementación

Mejoremos un poco la implementación actual de hashCode () incluyendo todos los campos de la clase User para que pueda producir resultados diferentes para objetos desiguales:

@Override public int hashCode() { return (int) id * name.hashCode() * email.hashCode(); }

Este algoritmo de hash básico es definitivamente mucho mejor que el anterior, ya que calcula el código hash del objeto simplemente multiplicando los códigos hash de los campos de nombre y correo electrónico y la identificación .

En términos generales, podemos decir que esta es una implementación hashCode () razonable , siempre que mantengamos la implementación equals () consistente con ella.

6. Norma hashCode () Implementaciones

Cuanto mejor sea el algoritmo hash que utilizamos para calcular códigos hash, mejor será el rendimiento de las tablas hash.

Echemos un vistazo a una implementación "estándar" que usa dos números primos para agregar aún más singularidad a los códigos hash calculados:

@Override public int hashCode() { int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (name == null ? 0 : name.hashCode()); hash = 31 * hash + (email == null ? 0 : email.hashCode()); return hash; }

Si bien es esencial comprender los roles que juegan los métodos hashCode () y equals () , no tenemos que implementarlos desde cero cada vez, ya que la mayoría de los IDE pueden generar implementaciones personalizadas de hashCode () y equals () y desde Java 7, tenemos un método de utilidad Objects.hash () para un hash cómodo:

Objects.hash(name, email)

IntelliJ IDEA genera la siguiente implementación:

@Override public int hashCode() { int result = (int) (id ^ (id >>> 32)); result = 31 * result + name.hashCode(); result = 31 * result + email.hashCode(); return result; }

Y Eclipse produce este:

@Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((email == null) ? 0 : email.hashCode()); result = prime * result + (int) (id ^ (id >>> 32)); result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; }

Además de las implementaciones hashCode () basadas en IDE anteriores , también es posible generar automáticamente una implementación eficiente, por ejemplo, usando Lombok. En este caso, la dependencia lombok-maven debe agregarse a pom.xml :

 org.projectlombok lombok-maven 1.16.18.0 pom

It's now enough to annotate the User class with @EqualsAndHashCode:

@EqualsAndHashCode public class User { // fields and methods here }

Similarly, if we want Apache Commons Lang's HashCodeBuilder class to generate a hashCode() implementation for us, the commons-lang Maven dependency must be included in the pom file:

 commons-lang commons-lang 2.6

And hashCode() can be implemented like this:

public class User { public int hashCode() { return new HashCodeBuilder(17, 37). append(id). append(name). append(email). toHashCode(); } }

In general, there's no universal recipe to stick to when it comes to implementing hashCode(). We highly recommend reading Joshua Bloch's Effective Java, which provides a list of thorough guidelines for implementing efficient hashing algorithms.

What can be noticed here is that all those implementations utilize number 31 in some form – this is because 31 has a nice property – its multiplication can be replaced by a bitwise shift which is faster than the standard multiplication:

31 * i == (i << 5) - i

7. Handling Hash Collisions

The intrinsic behavior of hash tables raises up a relevant aspect of these data structures: even with an efficient hashing algorithm, two or more objects might have the same hash code, even if they're unequal. So, their hash codes would point to the same bucket, even though they would have different hash table keys.

This situation is commonly known as a hash collision, and various methodologies exist for handling it, with each one having their pros and cons. Java's HashMap uses the separate chaining method for handling collisions:

“When two or more objects point to the same bucket, they're simply stored in a linked list. In such a case, the hash table is an array of linked lists, and each object with the same hash is appended to the linked list at the bucket index in the array.

In the worst case, several buckets would have a linked list bound to it, and the retrieval of an object in the list would be performed linearly.”

Hash collision methodologies show in a nutshell why it's so important to implement hashCode() efficiently.

Java 8 brought an interesting enhancement to HashMap implementation – if a bucket size goes beyond the certain threshold, the linked list gets replaced with a tree map. This allows achieving O(logn) look up instead of pessimistic O(n).

8. Creating a Trivial Application

To test the functionality of a standard hashCode() implementation, let's create a simple Java application that adds some User objects to a HashMap and uses SLF4J for logging a message to the console each time the method is called.

Here's the sample application's entry point:

public class Application { public static void main(String[] args) { Map users = new HashMap(); User user1 = new User(1L, "John", "[email protected]"); User user2 = new User(2L, "Jennifer", "[email protected]"); User user3 = new User(3L, "Mary", "[email protected]"); users.put(user1, user1); users.put(user2, user2); users.put(user3, user3); if (users.containsKey(user1)) { System.out.print("User found in the collection"); } } }

And this is the hashCode() implementation:

public class User { // ... public int hashCode() { int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (name == null ? 0 : name.hashCode()); hash = 31 * hash + (email == null ? 0 : email.hashCode()); logger.info("hashCode() called - Computed hash: " + hash); return hash; } }

The only detail worth stressing here is that each time an object is stored in the hash map and checked with the containsKey() method, hashCode() is invoked and the computed hash code is printed out to the console:

[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819 [main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -282948472 [main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -1540702691 [main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819 User found in the collection

9. Conclusion

It's clear that producing efficient hashCode() implementations often requires a mixture of a few mathematical concepts, (i.e. prime and arbitrary numbers), logical and basic mathematical operations.

Regardless, it's entirely possible to implement hashCode() effectively without resorting to these techniques at all, as long as we make sure the hashing algorithm produces different hash codes for unequal objects and is consistent with the implementation of equals().

Como siempre, todos los ejemplos de código que se muestran en este artículo están disponibles en GitHub.