Métodos de objetos de Java: hashCode ()

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 Object base del lenguaje Java. Los siguientes son los métodos del objeto Java base que están presentes en todos los objetos Java debido a la herencia implícita de Object.

• Encadenar
• a clase
• es igual a
• hashCode (estás aquí)
• clon
• finalizar
• esperar y notificar

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

Por qué es importante el método hashCode ()

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

Por defecto el 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 uso de una importante estructura de datos de ciencias de la computación llamada tabla de picadillo. Las tablas hash asignan claves, que son valores que resultan de una función hash (también conocida como hashCode() método), a un valor de interés (es decir, el objeto hashCode() se ejecutó el método). 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) y 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. Por lo tanto, 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. 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.

Demostrar el uso de la tabla 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 la implementación de una clase justifica la noción de igualdad lógica, considere la siguiente clase y programa.

Person.java

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);
    }
}

Main.java

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));
    }
}

Salida:

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 lógicamente son 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.

Déjame mejorar el Person clase asegurándose de que el hashCode() El método devuelve el mismo valor para los objetos de instancia iguales. me y me2, al igual que:

Person.java

public class Person {
    // omitting all other stuff for brevity

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

Main.java

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);
        }
    }
}

Salida:

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>

Ok, 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 como objetos iguales me y me2 se agregan al HashMap. Cuando el me2 Person La instancia se agrega al HashMap que ya contiene el me instancia, el HashMap se da cuenta de que el hash es el mismo y luego determina que también son lógicamente equivalentes a través de la equals(Object) método. Esto da como resultado que HashMap simplemente reemplace el primer me con el segundo me2 en esa ubicación en la tabla hash.

Luego viene el you instancia, que nuevamente tiene el mismo valor hash, pero esta vez el HashMap identifica que es lógicamente diferente del hash existente en ese depósito me2. Esto lleva al HashMap a agregar el you instancia al depósito, convirtiendo ese depósito en una colección similar a una lista. Para pequeñas cantidades de colisiones, esto no tiene un gran impacto, pero en mi ejemplo anterior, donde se garantiza que cada instancia tiene el mismo valor hash, el depósito que representa 31 en el HashMap se degradará rápidamente a una implementación deficiente de una 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, peopleList y peopleMap, de Person instancias con nombres aleatorios y cumpleaños del mismo tamaño 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 se tarda en buscar en cada colección la existencia de una instancia conocida igualmente ubicada, me.

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);
    }
}

Salida:

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 implementación terrible de una estructura similar a una lista. Peor aún es que posiblemente una de las razones principales para usar una tabla hash es tener una búsqueda rápida de O (1) y recuperación de valores a través del acceso por clave, pero como puede ver, eso 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 funcionamiento razonable hashCode() método y los explicaré a continuación.

A. hashCode() manualmente

En el libro Eficaz Java: mejores prácticas para la plataforma Java, tercera edición El gurú de Java Joshua Bloch describe el siguiente algoritmo para implementar su propio hashCode() método.

i) comparar el hash del primer campo de clase determinista utilizado en la implementación de equals(Object) y asignar eso a una variable que llamaré result.
ii) para cada campo determinista restante se utilizó el equals(Object) implementación multiplicar result por 31 y agregue el valor hash del campo determinista.

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

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 crea el List y HashMap midiendo el tiempo de ejecución, debería ver una diferencia significativa.

Salida:

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? los HashMap se construye en casi la mitad del tiempo, más el tiempo necesario para encontrar el me El objeto está en un nivel de magnitud completamente diferente.

B. Usando Objects.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 eficiente, entonces es una buena idea buscar el Objects.hash(...) utility y pasarle los campos deterministas de su objeto. Este es un método de buen rendimiento en general, y si usted es como yo y prefiere 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:

public class Person {
    // omitting all other stuff for brevity

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

Aquí está el resultado del programa de análisis:

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éntico a la implementación enrollada a mano.

C. Autogeneración con IDE

Mi método preferido para implementar tanto el equals(Object) y hashCode() Los métodos son en realidad para usar la funcionalidad de generación automática en mi IDE de Java de elección, Eclipse. La implementación que proporciona Eclipse se muestra a continuación.

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 el resultado del programa de análisis es este:

Microseconds to build list: 53737
Microseconds to build map: 27287
Microseconds to search list is 1500
Microseconds to search map is 22

Una vez más, esta implementación es casi idéntica en rendimiento.

Conclusión

En este artículo, lo mejor que he podido, he explicado la importancia de co-implementar la hashCode() método junto con equals(Object) para trabajar de manera eficiente con estructuras de datos que apliquen la noción de tabla hash. Además de explicar por qué es importante implementar la hashCode() método También demostré cómo implementar algunos algoritmos hash robustos y de rendimiento razonable.

Como siempre, gracias por leer y no dude en comentar o criticar a continuación.