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 *