Java TreeMap vs HashMap

Programación

1. Introducción

En este artículo, vamos a comparar dos implementaciones de Map : TreeMap y HashMap .

Ambas implementaciones forman una parte integral de Java Collections Framework y almacenan datos como pares clave-valor .

2. Diferencias

2.1. Implementación

Primero hablaremos sobre HashMap, que es una implementación basada en tablas hash. Extiende la clase AbstractMap e implementa la interfaz Map . Un HashMap funciona según el principio de hash .

Esta implementación de Map generalmente actúa como una tabla hash agrupada , pero cuando los depósitos se vuelven demasiado grandes, se transforman en nodos de TreeNodes , cada uno estructurado de manera similar a los de java.util.TreeMap.

Puede encontrar más información sobre los aspectos internos de HashMap en el artículo que se centra en él.

Por otro lado, TreeMap extiende la clase AbstractMap e implementa la interfaz NavigableMap . Un TreeMap tiendas de elementos del mapa en un Rojo-Negro árbol, que es un auto-equilibrio de búsqueda binaria árbol .

Y también puede encontrar más sobre los aspectos internos de TreeMap en el artículo que se centra en él aquí.

2.2. Orden

HashMap no ofrece ninguna garantía sobre la forma en que se organizan los elementos en el mapa .

Significa que no podemos asumir ningún orden mientras iteramos sobre 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 elementos de un TreeMap se ordenan según su orden natural .

Si los objetos de TreeMap no se pueden ordenar de acuerdo con el orden natural, entonces podemos hacer uso de un Comparador o Comparable para definir el orden en el que los elementos están dispuestos dentro del Mapa:

@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 nula y muchos valores nulos .

Veamos un ejemplo:

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

Sin embargo, TreeMap no permite una clave nula, pero puede contener muchos valores nulos .

No se permite una clave nula porque el método compareTo () o compare () arroja una NullPointerException:

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

Si estamos usando un TreeMap con un Comparador definido por el usuario , entonces depende de la implementación del método compare () cómo se manejan los valores nulos .

3. Análisis de desempeño

El rendimiento es la métrica más crítica que nos ayuda a comprender la idoneidad de una estructura de datos dado un caso de uso.

En esta sección, proporcionaremos un análisis completo del rendimiento de HashMap y TreeMap.

3.1. HashMap

HashMap, al ser una implementación basada en tablas hash, utiliza internamente una estructura de datos basada en matrices para organizar sus elementos de acuerdo con la función hash .

HashMap proporciona el rendimiento esperado en tiempo constante O (1) para la mayoría de las operaciones como add () , remove () y contains (). Por lo tanto, es significativamente más rápido que un TreeMap .

El tiempo promedio para buscar un elemento bajo un supuesto razonable, en una tabla hash es O (1). Pero, una implementación incorrecta de la función hash puede conducir a una mala distribución de valores en los depósitos, lo que da como resultado:

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

Antes de Java 8, el encadenamiento separado era la única forma preferida de manejar las colisiones. Por lo general, se implementa mediante listas vinculadas, es decir , si hay alguna colisión o dos elementos diferentes tienen el mismo valor hash, entonces almacene ambos elementos en la misma lista vinculada.

Por lo tanto, la búsqueda de un elemento en un HashMap, en el peor de los casos, podría haber llevado tanto tiempo como buscar un elemento en una lista vinculada, es decir, O (n) tiempo.

Sin embargo, con JEP 180 entrando en escena, ha habido un cambio sutil en la implementación de la forma en que se organizan los elementos en un HashMap.

De acuerdo con la especificación, cuando los depósitos se vuelven demasiado grandes y contienen suficientes nodos, se transforman en modos de TreeNodes , cada uno estructurado de manera similar a los de TreeMap .

Por lo tanto, en el caso de colisiones de hash altas, el rendimiento en el peor de los casos mejorará de O (n) a O (log n).

El código que realiza esta transformación se ilustra a continuación:

if(binCount >= TREEIFY_THRESHOLD - 1) { treeifyBin(tab, hash); }

El valor de TREEIFY_THRESHOLD es ocho, lo que denota efectivamente el recuento de umbral para usar un árbol en lugar de una lista vinculada para un depósito.

Es evidente que:

  • Un HashMap requiere mucha más memoria de la necesaria para almacenar sus datos
  • Un HashMap no debe tener más del 70% - 75% de su capacidad. Si se acerca, cambia de tamaño y las entradas se repiten
  • Rehacer requiere n operaciones, lo cual es costoso en el que nuestra inserción de tiempo constante se vuelve de orden O (n)
  • Es el algoritmo hash el que determina el orden de inserción de los objetos en el HashMap.

The performance of a HashMap can be tuned by setting the custom initial capacity and the load factor, at the time of HashMap object creation itself.

However, we should choose a HashMap if:

  • we know approximately how many items to maintain in our collection
  • we don't want to extract items in a natural order

Under the above circumstances, HashMap is our best choice because it offers constant time insertion, search, and deletion.

3.2. TreeMap

A TreeMap stores its data in a hierarchical tree with the ability to sort the elements with the help of a custom Comparator.

A summary of its performance:

  • TreeMap provides a performance of O(log(n)) for most operations like add(), remove() and contains()
  • A Treemap can save memory (in comparison to HashMap) because it only uses the amount of memory needed to hold its items, unlike a HashMap which uses contiguous region of memory
  • A tree should maintain its balance in order to keep its intended performance, this requires a considerable amount of effort, hence complicates the implementation

We should go for a TreeMap whenever:

  • memory limitations have to be taken into consideration
  • we don't know how many items have to be stored in memory
  • we want to extract objects in a natural order
  • if items will be consistently added and removed
  • we're willing to accept O(log n) search time

4. Similarities

4.1. Unique Elements

Both TreeMap and HashMap don't support duplicate keys. If added, it overrides the previous element (without an error or an exception):

@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. Concurrent Access

Both Map implementations aren't synchronized and we need to manage concurrent access on our own.

Both must be synchronized externally whenever multiple threads access them concurrently and at least one of the threads modifies them.

We have to explicitly use Collections.synchronizedMap(mapName) to obtain a synchronized view of a provided map.

4.3. Fail-Fast Iterators

The Iterator throws a ConcurrentModificationException if the Map gets modified in any way and at any time once the iterator has been created.

Additionally, we can use the iterator’s remove method to alter the Map during iteration.

Let's see an example:

@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. Which Implementation to Use?

In general, both implementations have their respective pros and cons, however, it's about understanding the underlying expectation and requirement which must govern our choice regarding the same.

Summarizing:

  • We should use a TreeMap if we want to keep our entries sorted
  • We should use a HashMap if we prioritize performance over memory consumption
  • Dado que un TreeMap tiene una localidad más significativa, podríamos considerarlo si queremos acceder a objetos que están relativamente cerca unos de otros de acuerdo con su orden natural.
  • HashMap se puede ajustar usando initialCapacity y loadFactor , que no es posible para TreeMap
  • Podemos usar LinkedHashMap si queremos preservar el orden de inserción mientras nos beneficiamos del acceso de tiempo constante

6. Conclusión

En este artículo, mostramos las diferencias y similitudes entre TreeMap y HashMap .

Como siempre, los ejemplos de código de este artículo están disponibles en GitHub.