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](https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html). 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 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 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 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 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](http://openjdk.java.net/jeps/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 treeMap = new HashMap<>(); treeMap.put(1, "Baeldung"); treeMap.put(1, "Baeldung"); assertTrue(treeMap.size() == 1); Map 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 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