Comparativa Entre HashMap y TreeMap en Java: ¿Cuál Elegir para Tu Proyecto?

1. Introducción

En este artículo, vamos a comparar dos implementaciones de Map: TreeMap y HashMap. Ambas implementaciones forman una parte integral del marco de colecciones de Java y almacenan datos en pares de clave-valor. Entender las diferencias y similitudes entre estas dos estructuras de datos es fundamental para escoger la más adecuada según los requisitos de tu aplicación.

2. Diferencias

2.1. Implementación

Comencemos hablando del HashMap, que es una implementación basada en tabla hash. HashMap extiende la clase AbstractMap y también implementa la interfaz Map. Funciona bajo el principio de hashing.

Esta implementación de Map generalmente actúa como una tabla hash con agrupación, pero cuando los grupos se vuelven demasiado grandes, se transforman en nodos de TreeNodes, que están estructurados de manera similar a los de java.util.TreeMap.

Por otro lado, el TreeMap también extiende la clase AbstractMap e implementa la interfaz NavigableMap. Un TreeMap almacena los elementos del mapa en un árbol de Rojo-Negro, que es un Árbol de Búsqueda Binaria Auto-Balanceado.

2.2. Orden

HashMap no proporciona ninguna garantía sobre la forma en que se organizan los elementos dentro del Map. Esto significa que no podemos asumir ningún orden al iterar sobre las claves y valores de un HashMap:

@Test
public void whenInsertObjectsHashMap_thenRandomOrder() {
    Map<Integer, String> hashmap = new HashMap<>();
    hashmap.put(3, "TreeMap");
    hashmap.put(2, "vs");
    hashmap.put(1, "HashMap");

    assertThat(hashmap.keySet(), containsInAnyOrder(1, 2, 3));
}

Sin embargo, los objetos de un TreeMap están ordenados según su orden natural, permitiendo que los elementos se recuperen en un orden predecible:

@Test
public void whenInsertObjectsTreeMap_thenNaturalOrder() {
    Map<Integer, String> treemap = new TreeMap<>();
    treemap.put(3, "TreeMap");
    treemap.put(2, "vs");
    treemap.put(1, "HashMap");
    
    assertThat(treemap.keySet(), contains(1, 2, 3));
}

2.3. Valores Nulos

HashMap permite almacenar como máximo una clave null y muchos valores null:

@Test
public void whenInsertNullInHashMap_thenInsertsNull() {
    Map<Integer, String> hashmap = new HashMap<>();
    hashmap.put(null, null);
    
    assertNull(hashmap.get(null));
}

Por otro lado, TreeMap no permite una clave null pero puede contener muchos valores null. Esto se debe a que un null no es válido en el contexto de los métodos compareTo() o compare(), que lanzarían un NullPointerException:

@Test(expected = NullPointerException.class)
public void whenInsertNullInTreeMap_thenException() {
    Map<Integer, String> treemap = new TreeMap<>();
    treemap.put(null, "NullPointerException");
}

Si estamos usando un TreeMap con un Comparator definido por el usuario, la forma en que se manejan los null depende de la implementación del método compare().

3. Análisis de Rendimiento

El rendimiento es la métrica más crítica que nos ayuda a entender la idoneidad de una estructura de datos dado un caso de uso específico. En esta sección, proporcionaremos un análisis integral del rendimiento de HashMap y TreeMap.

3.1. HashMap

HashMap, siendo una implementación basada en tabla hash, utiliza internamente una estructura de datos basada en arrays para organizar sus elementos de acuerdo a la función hash. Proporciona un rendimiento de tiempo constante adecuado de O(1) para la mayoría de las operaciones como add(), remove() y contains(), lo que lo hace significativamente más rápido que un TreeMap.

El tiempo promedio para buscar un elemento en una tabla hash, bajo la suposición razonable de uniformidad, es O(1). Sin embargo, una implementación incorrecta de la función hash puede dar lugar a una distribución pobre de valores, justificada por:

Sobrecarga de memoria: muchos cubos permanecen sin usar.
Degradación del rendimiento: cuanto mayor sea el número de colisiones, menor será el rendimiento.

Antes de Java 8, se utilizaba principalmente el Encadenamiento Separado para manejar colisiones, que se implementa usando listas vinculadas. Es decir, si hay una colisión, ambos elementos se almacenan en la misma lista vinculada. Por lo tanto, buscar un elemento en un HashMap en el peor de los casos podría llevar tanto tiempo como buscar un elemento en una lista vinculada, es decir, O(n).

Sin embargo, con la llegada de JEP 180, hubo un cambio sutil en la implementación sobre cómo se organizan los elementos. Según la especificación, cuando los cubos contienen demasiados nodos, se transforman en nodos de TreeNodes, lo que mejora el rendimiento en casos de muchas colisiones, reduciendo el tiempo de espera en el peor caso de O(n) a O(log n).

3.2. TreeMap

Un TreeMap almacena sus datos en un árbol jerárquico con la capacidad de ordenar los elementos con la ayuda de un Comparator personalizado. Aquí hay un resumen de su rendimiento:

TreeMap proporciona un rendimiento de O(log(n)) para las operaciones add(), remove() y contains().
Un TreeMap puede ahorrar memoria en comparación con un HashMap, ya que solo usa la cantidad de memoria necesaria para contener sus elementos.
Un árbol necesita mantener su equilibrio para mantener su rendimiento previsto, lo que requiere un esfuerzo considerable, complicando así la implementación.

Debemos optar por un TreeMap cuando:

Se deben considerar limitaciones de memoria.
No sabemos cuántos elementos deben almacenarse en memoria.
Queremos extraer objetos en un orden natural.
Si los elementos se agregarán y se eliminarán de manera constante.
Estamos dispuestos a aceptar un tiempo de búsqueda de O(log n).

4. Similitudes

4.1. Elementos Únicos

Tanto TreeMap como HashMap no soportan claves duplicadas. Si se agrega una clave existente, se sobrescribe el elemento anterior (sin generar un error ni una excepción):

@Test
public void givenHashMapAndTreeMap_whenputDuplicates_thenOnlyUnique() {
    Map<Integer, String> treeMap = new HashMap<>();
    treeMap.put(1, "Baeldung");
    treeMap.put(1, "Baeldung");

    assertTrue(treeMap.size() == 1);

    Map<Integer, String> treeMap2 = new TreeMap<>();
    treeMap2.put(1, "Baeldung");
    treeMap2.put(1, "Baeldung");

    assertTrue(treeMap2.size() == 1);
}

4.2. Acceso Concurrente

Ambas implementaciones de Map no están sincronizadas, y debemos gestionar el acceso concurrente por nuestra cuenta. Deben sincronizarse externamente siempre que múltiples hilos accedan a ellos concurrentemente y al menos uno de los hilos los modifique. Usamos explícitamente Collections.synchronizedMap(mapName) para obtener una vista sincronizada de un mapa proporcionado.

4.3. Iteradores Rápidos

El Iterator lanza un ConcurrentModificationException si el Map se modifica de alguna manera después de que se ha creado el iterador. Además, podemos utilizar el método remove del iterador para alterar el Map durante la iteración.

@Test
public void whenModifyMapDuringIteration_thenThrowExecption() {
    Map<Integer, String> hashmap = new HashMap<>();
    hashmap.put(1, "One");
    hashmap.put(2, "Two");

    Executable executable = () -> hashmap.forEach((key, value) -> hashmap.remove(1));

    assertThrows(ConcurrentModificationException.class, executable);
}

5. ¿Qué Implementación Usar?

En general, ambas implementaciones tienen sus respectivos pros y contras; sin embargo, se trata de entender la expectativa y el requisito subyacentes que deben gobernar nuestra elección respecto a la misma. Resumiendo:

Debemos usar un TreeMap si queremos mantener nuestras entradas ordenadas.
Debemos usar un HashMap si priorizamos el rendimiento sobre el consumo de memoria.
Debido a que un TreeMap tiene una mayor localidad, podríamos considerarlo si queremos acceder a objetos que son relativamente cercanos entre sí según su orden natural.
El HashMap puede ajustarse usando initialCapacity y loadFactor, lo cual no es posible para el TreeMap.
Podemos usar el LinkedHashMap si queremos preservar el orden de inserción mientras beneficiamos de acceso en tiempo constante.

6. Conclusión

En este artículo, mostramos las diferencias y similitudes entre TreeMap y HashMap. La elección correcta entre estas dos implementaciones depende de los requisitos específicos de tu proyecto. Conociendo sus características, puedes tomar decisiones más informadas y optimizar el rendimiento de tus aplicaciones en Java.

Comparativa de HashMap y TreeMap en Java