Una guía de TreeMap en Java

1. Información general

En este artículo, vamos a explorar la implementación de TreeMap de la interfaz Map de Java Collections Framework (JCF).

TreeMap es una implementación de mapa que mantiene sus entradas ordenadas de acuerdo con el orden natural de sus claves o mejor aún usando un comparador si lo proporciona el usuario en el momento de la construcción.

Anteriormente, hemos cubierto las implementaciones de HashMap y LinkedHashMap y nos daremos cuenta de que hay bastante información sobre cómo funcionan estas clases que es similar.

Se recomienda leer los artículos mencionados antes de continuar con este.

2. Clasificación predeterminada en TreeMap

De forma predeterminada, TreeMap ordena todas sus entradas según su orden natural. Para un número entero, esto significaría orden ascendente y para cadenas, orden alfabético.

Veamos el orden natural en una prueba:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() { TreeMap map = new TreeMap(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString()); }

Observe que colocamos las claves enteras de manera no ordenada, pero al recuperar el conjunto de claves, confirmamos que de hecho se mantienen en orden ascendente. Este es el orden natural de los números enteros.

Asimismo, cuando usamos cadenas, se ordenarán en su orden natural, es decir, alfabéticamente:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() { TreeMap map = new TreeMap(); map.put("c", "val"); map.put("b", "val"); map.put("a", "val"); map.put("e", "val"); map.put("d", "val"); assertEquals("[a, b, c, d, e]", map.keySet().toString()); }

TreeMap , a diferencia de un mapa hash y un mapa hash vinculado, no emplea el principio de hash en ninguna parte, ya que no utiliza una matriz para almacenar sus entradas.

3. Clasificación personalizada en TreeMap

Si no estamos satisfechos con el ordenamiento natural de TreeMap , también podemos definir nuestra propia regla para ordenar por medio de un comparador durante la construcción de un mapa de árbol.

En el siguiente ejemplo, queremos que las claves enteras estén ordenadas en orden descendente:

@Test public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() { TreeMap map = new TreeMap(Comparator.reverseOrder()); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString()); }

Un mapa hash no garantiza el orden de las claves almacenadas y específicamente no garantiza que este orden seguirá siendo el mismo a lo largo del tiempo, pero un mapa de árbol garantiza que las claves siempre se clasificarán de acuerdo con el orden especificado.

4. Importancia de la clasificación TreeMap

Ahora sabemos que TreeMap almacena todas sus entradas en orden ordenado. Debido a este atributo de los mapas de árbol, podemos realizar consultas como; buscar "más grande", encontrar "más pequeño", encontrar todas las claves menores o mayores que un cierto valor, etc.

El siguiente código solo cubre un pequeño porcentaje de estos casos:

@Test public void givenTreeMap_whenPerformsQueries_thenCorrect() { TreeMap map = new TreeMap(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); Integer highestKey = map.lastKey(); Integer lowestKey = map.firstKey(); Set keysLessThan3 = map.headMap(3).keySet(); Set keysGreaterThanEqTo3 = map.tailMap(3).keySet(); assertEquals(new Integer(5), highestKey); assertEquals(new Integer(1), lowestKey); assertEquals("[1, 2]", keysLessThan3.toString()); assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString()); }

5. Implementación interna de TreeMap

TreeMap implementos NavigableMap interfaz y basa su funcionamiento interno en los principios de árboles rojo-negro:

public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable

El principio de los árboles rojo-negro está más allá del alcance de este artículo, sin embargo, hay cosas clave que recordar para comprender cómo encajan en TreeMap .

En primer lugar , un árbol rojo-negro es una estructura de datos que consta de nodos; imagínese un árbol de mango invertido con su raíz en el cielo y las ramas creciendo hacia abajo. La raíz contendrá el primer elemento agregado al árbol.

La regla es que a partir de la raíz, cualquier elemento en la rama izquierda de cualquier nodo es siempre menor que el elemento en el propio nodo. Los de la derecha son siempre mayores. Lo que define mayor o menor que está determinado por el orden natural de los elementos o el comparador definido en la construcción, como vimos anteriormente.

Esta regla garantiza que las entradas de un mapa de árbol siempre estarán ordenadas y en un orden predecible.

En segundo lugar , un árbol rojo-negro es un árbol de búsqueda binario autoequilibrado. Este atributo y el anterior garantizan que las operaciones básicas como buscar, obtener, poner y quitar toman el tiempo logarítmico O (log n) .

Equilibrarse a sí mismo es clave aquí. Mientras seguimos insertando y eliminando entradas, imagina el árbol creciendo más largo en un borde o más corto en el otro.

Esto significaría que una operación tomaría menos tiempo en la rama más corta y más tiempo en la rama que está más alejada de la raíz, algo que no quisiéramos que sucediera.

Por lo tanto, esto se tiene en cuenta en el diseño de árboles rojo-negro. Para cada inserción y eliminación, la altura máxima del árbol en cualquier borde se mantiene en O (log n), es decir, el árbol se equilibra continuamente.

Al igual que el mapa hash y el mapa hash vinculado, un mapa de árbol no está sincronizado y, por lo tanto, las reglas para usarlo en un entorno de subprocesos múltiples son similares a las de las otras dos implementaciones de mapas.

6. Elegir el mapa correcto

Habiendo analizado las implementaciones de HashMap y LinkedHashMap anteriormente y ahora TreeMap , es importante hacer una breve comparación entre los tres para guiarnos sobre cuál encaja y dónde.

Un mapa hash es bueno como una implementación de mapa de propósito general que proporciona operaciones rápidas de almacenamiento y recuperación. Sin embargo, se queda corto debido a su disposición caótica y desordenada de las entradas.

Esto hace que su rendimiento sea deficiente en escenarios donde hay mucha iteración, ya que toda la capacidad de la matriz subyacente afecta el recorrido, además del número de entradas.

Un mapa hash vinculado posee los buenos atributos de los mapas hash y agrega orden a las entradas. Funciona mejor donde hay mucha iteración porque solo se tiene en cuenta el número de entradas independientemente de la capacidad.

Un mapa de árbol lleva los pedidos al siguiente nivel al proporcionar un control completo sobre cómo se deben ordenar las claves. Por otro lado, ofrece un peor rendimiento general que las otras dos alternativas.

Podríamos decir que un mapa hash vinculado reduce el caos en el orden de un mapa hash sin incurrir en la penalización de rendimiento de un mapa de árbol .

7. Conclusión

En este artículo, hemos explorado la clase Java TreeMap y su implementación interna. Dado que es la última de una serie de implementaciones comunes de la interfaz Map, también pasamos a discutir brevemente dónde encaja mejor en relación con las otras dos.

El código fuente completo de todos los ejemplos utilizados en este artículo se puede encontrar en el proyecto GitHub.