Métodos de objetos de Java: hashCode()

Este artículo es la continuación de una serie de artículos que describen los métodos a menudo olvidados de la clase de objeto base del lenguaje Java. Los siguientes son...

Introducción

Este artículo es una continuación de una serie de artículos que describen los métodos a menudo olvidados de la clase de objeto base del lenguaje Java. Los siguientes son los métodos del Objeto base de Java que están presentes en todos los objetos de Java debido a la herencia implícita de Objeto.

El enfoque de este artículo es el método código hash() que se utiliza para generar una representación numérica del contenido de un objeto y se usa mucho en el marco de las colecciones.

Por qué es importante el método hashCode() {#por qué el método hashcode no es importante}

El propósito del método hashCode() es proporcionar una representación numérica del contenido de un objeto para proporcionar un mecanismo alternativo para identificarlo vagamente.

Por defecto, hashCode() devuelve un número entero que representa la dirección de memoria interna del objeto. Donde esto resulta útil es en la creación y el uso de una importante estructura de datos de informática llamada [tabla de picadillo] (https://en.wikipedia.org/wiki/Hash_table). Las tablas hash asignan claves, que son valores que resultan de una función hash (también conocida como método hashCode()), a un valor de interés (es decir, el objeto en el que se ejecutó el método hashCode()). Esto se convierte en una característica muy útil cuando se trata de colecciones de elementos de moderadas a grandes, porque generalmente es mucho más rápido calcular un valor hash en comparación con la búsqueda lineal de una colección, o tener que cambiar el tamaño y copiar elementos en una matriz que respalda una colección. cuando se alcanza su límite.

La característica principal detrás de una tabla hash eficiente es la capacidad de crear un hash que sea adecuadamente único para cada objeto. Enterrada en esa última oración está la razón por la que enfaticé la necesidad de anular tanto equals(Object) como hashCode() en el artículo anterior.

Si un objeto tiene características de implementación que requieren que sea lógicamente distinto de otros en función de su contenido, entonces necesita producir un hash tan distinto como sea razonablemente posible. Entonces, dos objetos que son lógicamente equivalentes deberían producir el mismo hash, pero a veces es inevitable tener dos objetos lógicamente diferentes que pueden producir el mismo hash, lo que se conoce como [colisión](https://en.wikipedia.org/wiki /Collision_(informática_ciencia)). Cuando ocurren colisiones, los objetos que chocan se colocan en un cubo metafórico y se usa un algoritmo secundario para diferenciarlos dentro de su cubo hash.

Demostración del uso de tablas hash

En Java, el concepto de tabla hash se conceptualiza en la interfaz java.util.Map y se implementa en la clase java.util.HashMap.

Demostraremos una tabla hash y por qué es importante tener un valor hash razonablemente único calculado por hashCode() cuando una implementación de clase garantiza la noción de igualdad lógica, considere la siguiente clase y programa.

Persona.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.time.LocalDate;

public class Person {
    private final String firstName;
    private final String lastName;
    private final LocalDate dob;

    public Person(String firstName, String lastName, LocalDate dob) {
        this.firstName = firstName;
        this.lastName = lastName;
        this.dob = dob;
    }

    // omitting getters for brevity

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof Person)) {
            return false;
        }
        Person p = (Person)o;
        return firstName.equals(p.firstName)
                && lastName.equals(p.lastName)
                && dob.equals(p.dob);
    }
}

Principal.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
import java.time.LocalDate;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Person, String> peopleMap = new HashMap<>();
        Person me = new Person("Adam", "McQuistan", LocalDate.parse("1987-09-23"));
        Person me2 = new Person("Adam", "McQuistan", LocalDate.parse("1987-09-23"));
        System.out.println("Default hash: " + me.hashCode());
        System.out.println("Default hash: " + me2.hashCode());

        peopleMap.put(me, me.toString());
        System.out.println("me and me2 same? " + me.equals(me2));
        System.out.println("me2 in here? " + peopleMap.containsKey(me2));
    }
}

Producción:

1
2
3
4
Default hash: 1166726978
Default hash: 95395916
me and me2 same? true
me2 in here? false

Como puede ver en la salida, el hash predeterminado de me y me2 no son iguales aunque la implementación personalizada de equals(Object) indica que son lógicamente iguales. Esto da como resultado dos entradas distintas en la tabla hash, aunque esperaría solo una, lo que abre las puertas a algunos errores desagradables en un programa si implementara este código.

Permítanme mejorar la clase Person asegurándome de que el método hashCode() devuelva el mismo valor para los objetos de instancias iguales me y me2, así:

Persona.java

1
2
3
4
5
6
7
8
public class Person {
    // omitting all other stuff for brevity

     @Override
    public int hashCode() {
        return 31;
    }
}

Principal.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class Main {
    public static void main(String[] args) {
        Map<Person, String> peopleMap = new HashMap<>();
        Person me = new Person("Adam", "McQuistan", LocalDate.parse("1987-09-23"));
        Person me2 = new Person("Adam", "McQuistan", LocalDate.parse("1987-09-23"));
        Person you = new Person("Jane", "Doe", LocalDate.parse("1999-12-25"));
        System.out.println("Default hash: " + me.hashCode());
        System.out.println("Default hash: " + me2.hashCode());

        peopleMap.put(me, me.toString());
        System.out.println("me and me2 same? " + me.equals(me2));
        System.out.println("me2 in here? " + peopleMap.containsKey(me2));

        peopleMap.put(me2, me2.toString());
        peopleMap.put(you, you.toString());
        for(Person p : peopleMap.keySet()) {
            String txt = peopleMap.get(p);
            System.out.println(txt);
        }
    }
}

Producción:

1
2
3
4
5
6
Default hash: 31
Default hash: 31
me and me2 same? true
me2 in here? true
<Person: firstName=Adam, lastName=McQuistan, dob=1987-09-23>
<Person: firstName=Jane, lastName=Doe, dob=1999-12-25>

Bien, ahora tengo valores hash iguales para objetos iguales, pero también está claro que los objetos no iguales siempre tendrán los mismos valores hash.

Primero explicaré lo que está sucediendo a medida que se agregan los objetos iguales me y me2 al HashMap. Cuando la instancia me2 Person se agrega al HashMap que ya contiene la instancia me, HashMap nota que el hash es el mismo y luego determina que también son lógicamente equivalentes a través del método equals(Object) . Esto da como resultado que HashMap simplemente reemplace el primer “yo” con el segundo “yo2” en esa ubicación en la tabla hash.

Luego viene la instancia usted, que nuevamente tiene el mismo valor hash, pero esta vez HashMap identifica que es lógicamente diferente del hash existente en ese depósito me2. Esto lleva a HashMap a agregar la instancia “usted” al depósito, convirtiendo ese depósito en una colección similar a una lista. Para un pequeño número de colisiones, esto no tiene un impacto demasiado grande, pero en mi ejemplo anterior, donde se garantiza que cada instancia tenga el mismo valor hash, el depósito que representa 31 en el HashMap se degradará rápidamente a una implementación deficiente de un lista para todo el HashMap.

En este momento, me gustaría demostrar aún más la ineficacia de esta solución con datos concretos para compararlos con la implementación final que seguirá.

A continuación se muestra un programa que crea dos colecciones de igual tamaño, Lista de personas y Mapa de personas, de instancias de Persona con nombres aleatorios de igual tamaño y cumpleaños seleccionados. Mediré la cantidad de tiempo que lleva construir las colecciones para una primera medición de comparación. A continuación, mediré la cantidad de tiempo que lleva buscar en cada colección la existencia de una instancia conocida igualmente ubicada, “yo”.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.time.Duration;
import java.time.LocalDate;
import java.time.LocalDateTime;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.stream.Collectors;

public class Main {
    private static final char[] alphabet = "abcdefghijklmnopqrstuvwxyz".toCharArray();

    public static void main(String[] args) {
        Person me = new Person("Adam", "McQuistan", LocalDate.parse("1987-09-23"));

        LocalDateTime start = LocalDateTime.now();
        List<Person> peopleList = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            if (i == 4999) {
                peopleList.add(me);
            }
            peopleList.add(new Person(getRandomName(), getRandomName(), getRandomDate()));
        }
        System.out.println("Microseconds to build list: " + getTimeElapsed(start, LocalDateTime.now()));

        start = LocalDateTime.now();
        Map<Person, String> peopleMap = new HashMap<>();
        for (int i = 0; i < 10000; i++) {
            if (i == 4999) {
                peopleMap.put(me, me.toString());
            }
            Person p = new Person(getRandomName(), getRandomName(), getRandomDate());
            peopleMap.put(p, p.toString());
        }
        System.out.println("Microseconds to build map: " + getTimeElapsed(start, LocalDateTime.now()));

        start = LocalDateTime.now();
        boolean found = peopleList.contains(me);
        System.out.println("Microseconds to search list is " + getTimeElapsed(start, LocalDateTime.now()));

        start = LocalDateTime.now();
        found = peopleMap.containsKey(me);
        System.out.println("Microseconds to search map is " + getTimeElapsed(start, LocalDateTime.now()));
    }

    public static String getRandomName() {
        int size = alphabet.length;
        Random rand = new Random();
        List<Character> chars = Arrays.asList(
                alphabet[rand.nextInt(size)],
                alphabet[rand.nextInt(size)],
                alphabet[rand.nextInt(size)],
                alphabet[rand.nextInt(size)]
        );
        return chars.stream().map(String::valueOf).collect(Collectors.joining());
    }

    public static LocalDate getRandomDate() {
        Random rand = new Random();
        int min = (int) LocalDate.of(1980, 1, 1).toEpochDay();
        int max = (int) LocalDate.of(2018, 10, 14).toEpochDay();
        long day = min + rand.nextInt(max - min);
        return LocalDate.ofEpochDay(day);
    }

    public static long getTimeElapsed(LocalDateTime start, LocalDateTime end) {
        Duration duration = Duration.between(start, end);
        return Math.round(duration.getNano() / 1000);
    }
}

Producción:

1
2
3
4
Microseconds to build list: 53789
Microseconds to build map: 892043
Microseconds to search list is 450
Microseconds to search map is 672

¡Vaya, eso es tremendamente ineficiente! Esta gran implementación de tabla hash en HashMap se ha degradado por completo a una terrible implementación de una estructura similar a una lista. Incluso peor es que podría decirse que una de las razones principales para usar una tabla hash es tener una búsqueda y recuperación rápida de valores O (1) a través del acceso clave, pero como puede ver, en realidad está funcionando peor que buscar una lista estándar linealmente debido a mi implementación de un hashCode() que no tiene capacidad de diferenciación. ¡Ay!

Déjame arreglar esto. Hay algunas formas que conozco de abordar la implementación de un método hashCode() que funcione razonablemente y las explicaré a continuación.

A. hashCode() a mano

In the book Java eficaz: mejores prácticas para la plataforma Java, 3.ª edición Java guru Joshua Bloch describes the following algorithm for implementing your own hashCode() method.

i) Calcular el hash del primer campo de clase determinista utilizado en la implementación de equals(Object) y asignarlo a una variable que llamaré result.
ii) para cada campo determinista restante utilizado en la implementación equals(Object), multiplique resultado por 31 y agregue el valor hash del campo determinista.

En mi clase de ejemplo Persona, este enfoque se parece a esto:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Person {
    private final String firstName;
    private final String lastName;
    private final LocalDate dob;

    // omitting all other stuff for brevity

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof Person)) {
            return false;
        }
        Person p = (Person)o;
        return firstName.equals(p.firstName)
                && lastName.equals(p.lastName)
                && dob.equals(p.dob);
    }

    @Override
    public int hashCode() {
        int result = dob == null ? 1 : dob.hashCode();
        result = 31 * result + firstName == null ? 0 : firstName.hashCode();
        result = 31 * result + lastName == null ? 0 : lastName.hashCode();
        return result;
    }
}

Ahora, si vuelvo a ejecutar el mismo programa que construye la Lista y HashMap midiendo el tiempo de ejecución, debería ver una diferencia significativa.

Producción:

1
2
3
4
Microseconds to build list: 54091
Microseconds to build map: 35528
Microseconds to search list is 582
Microseconds to search map is 20

Bastante impactante ¿verdad? El ‘HashMap’ en sí se construye en casi la mitad del tiempo, más el tiempo requerido para encontrar el objeto ‘yo’ está en un nivel de magnitud completamente diferente.

B. Usando Objetos.hash(...)

Si está buscando una forma más sencilla de implementar un valor hash personalizado y no es extremadamente reacio a no tener la implementación más eficaz, entonces es una buena idea buscar la utilidad Objects.hash (...) y pasarle el campos deterministas de su objeto. Este es un método que generalmente funciona bien, y si usted es como yo y está a favor de poder enviar código rápidamente en lugar de optimizar prematuramente el rendimiento, esta es una excelente ruta para resolver este problema.

A continuación se muestra un ejemplo de esta implementación para la clase Person:

1
2
3
4
5
6
7
8
public class Person {
    // omitting all other stuff for brevity

     @Override
    public int hashCode() {
        return Objects.hash(dob, firstName, lastName);
    }
}

Aquí está la salida para el programa de análisis:

1
2
3
4
Microseconds to build list: 56438
Microseconds to build map: 38112
Microseconds to search list is 733
Microseconds to search map is 24

Como puede ver, es esencialmente idéntica a la implementación manual.

C. Autogeneración con IDE

Mi método preferido para implementar los métodos equals(Object) y hashCode() es en realidad usar la funcionalidad de autogeneración en mi IDE de Java de elección Eclipse. La implementación que proporciona Eclipse se muestra a continuación.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Person {

    // omitting all other stuff for brevity

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((dob == null) ? 0 : dob.hashCode());
        result = prime * result + ((firstName == null) ? 0 : firstName.hashCode());
        result = prime * result + ((lastName == null) ? 0 : lastName.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Person other = (Person) obj;
        if (dob == null) {
            if (other.dob != null)
                return false;
        } else if (!dob.equals(other.dob))
            return false;
        if (firstName == null) {
            if (other.firstName != null)
                return false;
        } else if (!firstName.equals(other.firstName))
            return false;
        if (lastName == null) {
            if (other.lastName != null)
                return false;
        } else if (!lastName.equals(other.lastName))
            return false;
        return true;
    }
}

Y la salida del programa de análisis es esta:

1
2
3
4
Microseconds to build list: 53737
Microseconds to build map: 27287
Microseconds to search list is 1500
Microseconds to search map is 22

De nuevo, esta implementación es casi idéntica en rendimiento.

Conclusión

En este artículo, lo mejor que pude, expliqué la importancia de implementar conjuntamente el método hashCode() junto con equals(Object) para trabajar de manera eficiente con estructuras de datos que aplican la noción de un hash. mesa. Además de explicar por qué es importante implementar el método hashCode(), también demostré cómo implementar algunos algoritmos hash robustos y con un rendimiento razonable.

Como siempre, gracias por leer y no se avergüence de comentar o criticar a continuación.

Licensed under CC BY-NC-SA 4.0