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.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *