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 un desarrollador eligió para almacenar datos. Por eso es muy importante...

El rendimiento de un programa Java y el uso adecuado de los recursos a menudo dependen de una colección que un desarrollador eligió 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 se encuentran en la parte superior de las entrevistas para los solicitantes de desarrollo de Java Junior.

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

Espero que el lector esté bien familiarizado con los conceptos de interfaz e implementación, y solo daré las definiciones básicas para simplificar esta lectura. También me permitiré algunas referencias a otros artículos y documentación para aquellos que hayan olvidado algunos detalles.

¿Qué es el mapa

El Mapa de Interfaz es parte del marco de la Colección Java. Puedes imaginar Map como una especie de diccionario, donde cada elemento representa un par clave-valor. Tanto las claves como los valores son objetos. Mapa le permite buscar un objeto por una clave dada. 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 — ID único del estudiante que está conectado a algún objeto Student.

Tanto HashMap como TreeMap son implementaciones de interfaces Map. Brevemente, HashMap es una estructura de datos que codifica claves, y TreeMap usa el orden natural de las claves para organizar un árbol de búsqueda.

{.img-responsive}

¿Qué es HashMap

HashMap es una estructura de datos que implementa la interfaz Map<Key,Value> y se basa en el principio de hashing. Si nunca has oído hablar de esta estructura, prueba un artículo para principiantes y echa un vistazo a [documentos](https://docs. oracle.com/javase/8/docs/api/java/util/HashMap.html).

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 les daré una definición de 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 mejor entendimiento.

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 del trabajo de esta función 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 método equals asociado con él.

Los códigos hash ayudan a que los programas se ejecuten más rápido. Supongamos que comparamos los objetos de volumen s1 y s2 del tipo Student y declaramos 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 utilizadas en criptografía, y también en otras áreas. Sin embargo, la magia no está en 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, entonces los objetos definitivamente no son iguales.
  • Diferentes objetos pueden (aunque es muy poco probable) tener los mismos códigos hash. Bien... ¡aquí hemos encontrado pérdida de datos! Esta situación se llama colisión. El código hash "bueno" debe minimizar la probabilidad de colisiones.

Dentro del HashMap

HashMap nos permite almacenar claves según el principio de hashing. 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 "cubos", todos los cubos juntos forman una "tabla", una especie de matriz interna de [listas enlazadas](/colecciones-java-la-interfaz-de- la-lista/).

{.img-responsive}

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

Cuando llamamos a put(key, value), HashMap llama al método hashCode en el objeto key. Luego, aplica el código hash que obtuvimos en su propia función hash, que ayuda a encontrar una ubicación de depósito para almacenar un objeto Entrada. HashMap almacena los objetos clave y valor como Map.Entry en un depósito.

¿Qué es TreeMap

Java TreeMap es una estructura de datos que implementa la interfaz Map<Key,Value> y se basa en la estructura de datos de árbol rojo-negro.

Árbol rojo-negro

Un Árbol es una estructura de datos jerárquica que consiste en "nodos" y líneas que conectan nodos ("ramas"). El nodo "raíz" está en la parte superior del árbol y desde la raíz pueden surgir ramas y los nodos ("hijos" de la raíz). Cada nodo hijo también puede tener sus propios hijos (nodos que se encuentran más abajo). Los nodos sin hijos se denominan "nodos de hoja", "nodos finales" o "hojas".

En un árbol binario, cada nodo tiene cero, uno o dos hijos. Cada nodo interno de un árbol de búsqueda binaria almacena una clave (ya veces un valor asociado) y tiene dos subárboles diferenciados, comúnmente denominados "izquierda" y "derecha". Puedes imaginar este árbol como una realización del algoritmo de búsqueda binaria.

Un árbol de búsqueda binaria autoequilibrado es un árbol de búsqueda binaria que automáticamente mantiene pequeña su altura (o el número máximo de niveles por debajo de la raíz) frente a las inserciones y eliminaciones arbitrarias de elementos.

Árbol rojo-negro es un árbol binario balanceado con las siguientes propiedades:

  • Cada nodo es rojo o negro
  • La raíz es siempre negra.
  • Cada hoja es un nodo NIL y es negro
  • Si un nodo es rojo, sus dos hijos son negros. Por lo tanto, un nodo rojo no puede tener un hijo rojo.
  • Todo camino simple de un nodo a una hoja descendiente contiene el mismo número de nodos negros.

{.img-responsive}

Consulta este artículo para obtener más información sobre Árboles rojo-negros

Mapa de árbol

TreeMap es una implementación de mapa 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 de pedido.

"Genial", puedes pensar... "Ahora puedo llamar al método toString y ordenar todos los objetos o iterarlos de forma natural" y tendrás razón. Sin embargo, esa no es la principal ventaja de la implementación de TreeMap. Lo bueno de esto es que puedes 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 usar un método subMap() para 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
30
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:

1
{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. Claro que podemos hacer lo mismo con un HashMap, pero debemos codificar toda la lógica de clasificación, etc.

HashMap vs TreeMap: principales diferencias

Pedidos

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 claves y parece ser caótica.

TreeMap, que implementa no solo Map sino también NavegableMapa clasifica automáticamente los pares por orden natural de sus claves (según su método compareTo() o un Comparator suministrado externamente).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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:

1
2
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 claves (orden alfabético de los nombres de los gatos):

1
{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 cubos. Por lo general, funciona como está, pero en realidad a veces ocurren colisiones. En este caso, HashMap maneja la colisión usando 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 utiliza un árbol equilibrado en lugar de una lista enlazada. JDK8 cambia a árbol balanceado en caso de más de 8 entradas en un depósito, mejora el desempeño en el peor de los casos de O(n) a O(log (n)).

De acuerdo con su estructura, HashMap requiere más memoria que solo para mantener sus elementos. El rendimiento de un mapa hash depende de dos parámetros: la capacidad inicial y el factor de carga. La Capacidad inicial es una cantidad de cubos de un HashMap recién 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 un rendimiento temporal 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 almacenar sus elementos, a diferencia de un HashMap.

Claves nulas y valores nulos

HashMap le permite almacenar una clave nula y múltiples valores nulos. Mantiene la entrada con una clave nula en index[0] de un depósito interno. HashMap también permite almacenar muchos valores nulos. Ejemplo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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 un valor nulos, el segundo es uno "ordinario" y el tercero también con un valor nulo.

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

¿Qué sucede si intentamos agregar un elemento más con una clave nula?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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 en index[0] de un depósito interno, por lo que se sobrescribirá:

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

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

Entonces, si intentamos ejecutar el siguiente código:

1
2
3
4
5
6
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put(null, 5);
treeMap.put ("Fluffy", 7);
treeMap.put("Kid", null);

System.out.println(treeMap);

Tenemos una java.lang.NullPointerException.

Si está utilizando TreeMap con Comparator definido por el usuario, el trabajo con entradas nulas depende de la implementación del método compare().

¿Qué hay en común? {#lo que no es 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 mapa 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 usa la memoria de manera más efectiva, por lo que es una buena implementación de mapa 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.

Sobre el autor

John Selawsky es desarrollador senior de Java y tutor de Java en los cursos de programación de Learning Tree International. Visite su [blog mediano] personal (https://medium.com/@johnythecoder) para leer más pensamientos y consejos sobre Java de John. Java de John.