HashMap y TreeMap en Java: diferencias y similitudes

    El rendimiento de un programa Java y el uso adecuado de los recursos a menudo dependen de una colecci贸n que el desarrollador elija para almacenar datos. Por lo tanto, es muy importante comprender la diferencia entre las implementaciones. Es por eso que las preguntas relacionadas con las colecciones est谩n en la parte superior de las entrevistas para los solicitantes de desarrolladores de Java Junior.

    En este art铆culo, echamos un vistazo a dos implementaciones de la interfaz Map, HashMap y TreeMap, y tratamos de responder la pregunta sobre sus diferencias y cu谩ndo el programador deber铆a usar la primera y la segunda.

    Espero que el lector est茅 familiarizado con los conceptos de interfaz e implementaci贸n, y solo dar茅 las definiciones b谩sicas para hacer esta lectura m谩s simple. Tambi茅n me permitir茅 algunas referencias a otros art铆culos y documentaci贸n para aquellos que hayan olvidado algunos detalles.

    Qu茅 es Map

    los Interfaz de mapa <clave, valor> es parte del marco de Java Collection. Puede imaginar Map como una especie de diccionario, donde cada elemento representa un par clave-valor. Tanto las claves como los valores son objetos. Map le permite buscar un objeto con una clave determinada. Un objeto asociado con la clave es un valor. Todas las claves son 煤nicas, mientras que los valores se pueden duplicar. Algunas implementaciones de mapas permiten claves nulas y valores nulos. Las principales operaciones de cualquier mapa son la inserci贸n, eliminaci贸n y b煤squeda de elementos.

    Entonces, una clave es un identificador 煤nico de un objeto en Map. Por ejemplo, Map<String, Student> contiene una clave como una cadena: la identificaci贸n 煤nica del estudiante que est谩 conectada a alg煤n objeto Student.

    Tanto HashMap como TreeMap son implementaciones de interfaces Map. En resumen, HashMap es una estructura de datos que utiliza claves hash, y TreeMap utiliza el orden natural de las claves para organizar un 谩rbol de b煤squeda.

    驴Qu茅 es HashMap?

    HashMap es una estructura de datos que implementa Map<Key,Value> interfaz y se basa en el principio de hash. Si nunca ha o铆do hablar de esta estructura, intente un art铆culo para principiantes y echar un vistazo a docs.

    Para comprender qu茅 es Hashmap, primero debe conocer las funciones hash y hash. Los detalles algor铆tmicos est谩n m谩s all谩 del alcance de este art铆culo, pero le dar茅 una definici贸n de la funci贸n hash (as铆 como un 谩rbol binario para el otro tema de este art铆culo, TreeMap) y una breve descripci贸n del trabajo interno de HashMap para una mejor comprensi贸n.

    Principio hash

    Una funci贸n hash es una funci贸n que convierte datos de entrada de cualquier tama帽o (generalmente grande) en datos de tama帽o fijo, generalmente compactos. El resultado de esta funci贸n de trabajo se llama c贸digo hash.

    Cada objeto Java tiene un c贸digo hash. Suele ser un n煤mero y se calcula utilizando el m茅todo hashCode de la clase Object. La buena idea es anular este m茅todo para sus propias clases junto con el equals m茅todo asociado con 茅l.

    Los c贸digos hash ayudan a que los programas se ejecuten m谩s r谩pido. Supongamos que comparamos objetos de volumen s1 y s2 del Student escriba y declare que la operaci贸n s1.equals(s2) tarda unos 500 ms. En ese caso, la comparaci贸n de los c贸digos hash s1.hashCode() == s2.hashCode() tarda unos 20 ms.

    Funciones hash son ampliamente utilizados en criptograf铆a y tambi茅n en otras 谩reas. Sin embargo, la magia no es para el desarrollo de software: no se puede poner algo grande en un recipiente peque帽o sin p茅rdidas.

    Las principales reglas de los c贸digos hash:

    • Un objeto en particular siempre tiene el mismo c贸digo hash.
    • Si los objetos son iguales, sus c贸digos hash son los mismos, pero no al rev茅s.
    • Si los c贸digos hash son diferentes, los objetos definitivamente no son iguales.
    • Diferentes objetos pueden (aunque es muy poco probable) tener los mismos c贸digos hash. Bueno … 隆aqu铆 hemos encontrado p茅rdida de datos! Esta situaci贸n se llama colisi贸n. El c贸digo hash “bueno” deber铆a minimizar la probabilidad de colisiones.

    Dentro del HashMap

    HashMap nos permite almacenar claves seg煤n el principio de hash. Hay dos m茅todos principales: put(key, value) y get(key) para almacenar y recuperar objetos de HashMap. Los pares clave-valor se almacenan en los llamados “dep贸sitos”, todos los dep贸sitos juntos son una “tabla”, una especie de matriz interna de listas enlazadas.

    Entonces, el primer elemento de la lista vinculada se almacena en el dep贸sito. Esta lista enlazada es una cadena de objetos y cada uno de ellos tiene un enlace al siguiente objeto de la cadena. Por lo tanto, teniendo el primer elemento se puede llegar a la cadena de todos los elementos de la lista. Un elemento de lista vinculado es un objeto de la Entry clase que contiene una clave, un valor y un enlace al siguiente Entry.

    Cuando llamamos put(key, value), HashMap llama hashCode m茅todo en el key objeto. Luego aplica el c贸digo hash que obtuvimos en su propia funci贸n de hash, que ayuda a encontrar una ubicaci贸n de dep贸sito para almacenar un Entry objeto. Tiendas HashMap key y value objetos como Map.Entry en un balde.

    驴Qu茅 es TreeMap?

    Java TreeMap es una estructura de datos que implementa Map<Key,Value> interfaz y se basa en la estructura de datos del 谩rbol Rojo-Negro.

    脕rbol rojo-negro

    UN 脕rbol es una estructura de datos jer谩rquica que consta de “nodes” y l铆neas que conectan nodes (“ramas”). El node “ra铆z” est谩 en la parte superior del 谩rbol y desde la ra铆z pueden existir ramas y nodes (“hijos” de la ra铆z). Cada node hijo tambi茅n puede tener sus propios hijos (nodes que se encuentran m谩s abajo). Los nodes sin hijos se denominan “nodes hoja”, “nodes finales” u “hojas”.

    En un 谩rbol binario, cada node tiene cero, uno o dos hijos. Cada node interno de un 谩rbol de b煤squeda binaria almacena una clave (y a veces un valor asociado) y tiene dos sub谩rboles distinguidos, com煤nmente denominados “izquierda” y “derecha”. Puede imaginar este 谩rbol como la realizaci贸n de un algoritmo de b煤squeda binaria.

    UN 谩rbol de b煤squeda binaria autoequilibrado es un 谩rbol de b煤squeda binario que mantiene autom谩ticamente su altura (o el n煤mero m谩ximo de niveles por debajo de la ra铆z) peque帽a frente a las inserciones y eliminaciones de elementos arbitrarios.

    脕rbol rojo-negro es un 谩rbol binario equilibrado con las siguientes propiedades:

    • Cada node es rojo o negro
    • La ra铆z siempre es negra
    • Cada hoja es un node NIL y es negro
    • Si un node es rojo, sus dos hijos son negros. Por lo tanto, un node rojo no puede tener un hijo rojo.
    • Cada ruta simple de un node a una hoja descendiente contiene el mismo n煤mero de nodes negros.

    Consulte este art铆culo para obtener m谩s informaci贸n sobre 脕rboles rojo-negros

    TreeMap

    TreeMap es una implementaci贸n de Map que mantiene sus entradas ordenadas seg煤n el orden natural de sus claves. Para n煤meros significa orden ascendente, para cadenas, orden alfab茅tico. Sin embargo, es posible utilizar un comparador si necesita cambiar la l贸gica del pedido.

    “Genial”, puedes pensar … “Ahora puedo llamar al toString y obtener todos los objetos ordenados o iterarlos de forma natural “y tendr谩 raz贸n. Sin embargo, esa no es la principal ventaja de la implementaci贸n de TreeMap. Lo bueno de esto es que puede encontrar algunos objetos usando diferentes filtros y condiciones .

    Por ejemplo, elijamos todos los gatos de las letras “b” a “s” de una colecci贸n de gatos. Vamos a utilizar un subMap() m茅todo para esto.

    public class Solution {
        public static void main(String[] args) throws Exception {
            String[] cats = new String[]{"Fluffy", "Abby", "Boris", "Ginger", "Grey", "Snowy", "Boss", "Waldo", "Tom", "Garfield"};
    
            TreeMap<String, Cat> treeMap = addCatsToTreeMap(cats);
            System.out.println(treeMap.subMap("Boris", true,"Snowy",true));
        }
    
        public static TreeMap<String, Cat> addCatsToTreeMap(String[] cats) {
            TreeMap<String,Cat> myCats = new TreeMap<String, Cat>();
            for (int i = 0; i < cats.length; i++) {
                Cat cat = new Cat(cats[i]);
                myCats.put(cat.name, cat);
            }
            return myCats;
        }
    
        public static class Cat {
            String name;
    
            public Cat(String name) {
                this.name = name;
            }
    
            @Override
            public String toString() {
                return name != null ? name.toUpperCase() : null;
            }
        }
    }
    

    La salida:

    {Boris=BORIS, Boss=BOSS, Fluffy=FLUFFY, Garfield=GARFIELD, Ginger=GINGER, Grey=GREY, Snowy=SNOWY}
    

    Aqu铆 tenemos todos los Gatos ordenados desde Boris hasta Snowy en orden alfab茅tico. Seguro que podemos hacer lo mismo con un HashMap, pero deber铆amos codificar toda la l贸gica de clasificaci贸n y dem谩s.

    HashMap vs TreeMap: principales diferencias

    Ordenar

    HashMap no est谩 ordenado, mientras que TreeMap ordena por clave. La forma en que se almacenan los elementos depende de la funci贸n hash de las teclas y parece ser ca贸tica.

    TreeMap, que implementa no solo Map sino tambi茅n NavigableMap ordena autom谩ticamente los pares por sus 贸rdenes naturales de claves (seg煤n su compareTo() m茅todo o un suministro externo Comparator).

    Ejemplo. Tengamos dos mapas, HashMap y TreeMap, donde las claves son nombres de gatos de un String Array.

    import java.util.HashMap;
    import java.util.TreeMap;
    
    public class Test {
        public static void main(String[] args) throws Exception {
            String[] cats = new String[]{"Fluffy", "Abby", "Boris", "Ginger", "Grey", "Snowy", "Boss", "Waldo", "Tom", "Garfield"};
            Integer age;
            HashMap<String, Integer> hMap = new HashMap<>();
            for (int i = 0; i < cats.length; i++) {
                hMap.put(cats[i], i);
            }
            System.out.println("HashMap ordered by hash:");
            System.out.println(hMap);
            System.out.println();
    
            TreeMap<String, Integer> tMap = new TreeMap<>();
            for (int i = 0; i < cats.length; i++) {
                tMap.put(cats[i], i);
            }
            System.out.println("TreeMap ordered by keys (alphabetical order of the cats' names:");
            System.out.println(tMap);
    
        }
    }
    

    La salida:

    HashMap ordered by hash:
    {Fluffy=0, Boss=6, Snowy=5, Tom=8, Garfield=9, Abby=1, Boris=2, Waldo=7, Ginger=3, Grey=4}
    

    TreeMap ordenado por teclas (orden alfab茅tico de los nombres de los gatos):

    {Abby=1, Boris=2, Boss=6, Fluffy=0, Garfield=9, Ginger=3, Grey=4, Snowy=5, Tom=8, Waldo=7}
    

    Actuaci贸n

    HashMap es m谩s r谩pido y proporciona un rendimiento de tiempo constante promedio O(1) para las operaciones b谩sicas get() y put(), si la funci贸n hash dispersa los elementos correctamente entre los dep贸sitos. Por lo general, funciona como est谩, pero en realidad a veces ocurren colisiones. En este caso, HashMap maneja la colisi贸n utilizando una lista enlazada para almacenar elementos colisionados y el rendimiento se reduce hasta O(n).

    Para mejorar el rendimiento en caso de colisiones frecuentes, en JDK 8 se usa 谩rbol balanceado en lugar de lista enlazada. JDK8 cambia a 谩rbol equilibrado en caso de m谩s de 8 entradas en un dep贸sito, mejora el rendimiento en el peor de los casos de O(n) a O(log (n)).

    Seg煤n su estructura, HashMap requiere m谩s memoria que solo para mantener sus elementos. El rendimiento de un mapa hash depende de dos par谩metros: capacidad inicial y factor de carga. La capacidad inicial es una cantidad de dep贸sitos de un nuevo HashMap creado. El factor de carga mide un porcentaje de plenitud. La capacidad inicial predeterminada es 16 y el factor de carga predeterminado es 0,75. Podemos cambiar estos valores.

    TreeMap se basa en un 谩rbol binario que proporciona rendimiento en el tiempo O(log(n)).

    Por lo tanto, HashMap casi siempre funciona m谩s r谩pido que TreeMap. Cuanto m谩s grande sea el objeto almacenado, m谩s r谩pido ser谩 HashMap en comparaci贸n con TreeMap. Sin embargo, un TreeMap usa la cantidad 贸ptima de memoria para contener sus elementos, a diferencia de un HashMap.

    Claves nulas y valores nulos

    HashMap le permite almacenar una clave nula y varios valores nulos. Mantiene la entrada con una clave nula en index[0] de un cubo interno. HashMap tambi茅n permite almacenar muchos valores nulos. Ejemplo:

    import java.util.HashMap;
    
    public class Test {
        public static void main(String[] args) throws Exception {
    
            HashMap<String, Integer> hashMap = new HashMap<>();
            hashMap.put(null, null);
            hashMap.put ("Fluffy", 7);
            hashMap.put("Kid", null);
    
            System.out.println(hashMap);
        }
    }
    

    En la salida obtendremos un HashMap con tres elementos, primero con una clave y valor nulos, el segundo es uno “ordinario” y el tercero tambi茅n con un valor nulo.

    {null=null, Fluffy=7, Kid=null}
    

    驴Qu茅 pasa si intentamos agregar un elemento m谩s con una clave nula?

    import java.util.HashMap;
    
    public class Test {
        public static void main(String[] args) throws Exception {
    
            HashMap<String, Integer> hashMap = new HashMap<>();
            hashMap.put(null, null);
            hashMap.put(null, 5);
            hashMap.put ("Fluffy", 7);
            hashMap.put("Kid", null);
    
            System.out.println(hashMap);
        }
    }
    

    La nueva entrada se mantiene index[0] de un dep贸sito interno, por lo que se sobrescribir谩:

    {null=5, Fluffy=7, Kid=null}
    

    TreeMap ordena los elementos en orden natural y no permite claves nulas porque compareTo() arroja el m茅todo NullPointerException si se compara con nulo.

    Entonces, si intentamos ejecutar el siguiente c贸digo:

    TreeMap<String, Integer> treeMap = new TreeMap<>();
    treeMap.put(null, 5);
    treeMap.put ("Fluffy", 7);
    treeMap.put("Kid", null);
    
    System.out.println(treeMap);
    

    Tenemos un java.lang.NullPointerException.

    Si est谩 utilizando TreeMap con definido por el usuario Comparator, trabajar con entradas nulas depende de la implementaci贸n de compare() m茅todo.

    驴Qu茅 hay en com煤n?

    Tanto TreeMap como HashMap implementan la interfaz Map, por lo que no admiten claves duplicadas.

    No son seguros para subprocesos, por lo que no puede usarlos de forma segura en una aplicaci贸n de subprocesos m煤ltiples.

    Conclusiones

    HashMap es una implementaci贸n de mapas de prop贸sito general. Proporciona un rendimiento de O(1), mientras que TreeMap proporciona un rendimiento de O(log(n)) para agregar, buscar y eliminar elementos. Por lo tanto, HashMap suele ser m谩s r谩pido.

    Un TreeMap utiliza la memoria de una manera m谩s eficaz, por lo que es una buena implementaci贸n de Map para usted si no est谩 seguro de la cantidad de elementos que deben almacenarse en la memoria.

    Utilice un TreeMap si necesita mantener todas las entradas en orden natural.

    Etiquetas:

    Deja una respuesta

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