1. Overview
En este artículo, vamos a explorar la implementación de TreeMap de la interfaz Map del 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, utilizando un comparador si es proporcionado por el usuario en el momento de la construcción.
En artículos anteriores, hemos cubierto las implementaciones 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 seguir con este.
2. Ordenamiento por Defecto en TreeMap
Por defecto, TreeMap ordena todas sus entradas de acuerdo con su orden natural. Para un número entero, esto significaría un orden ascendente y para cadenas, un orden alfabético.
Veamos el orden natural en una prueba:
@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() {
TreeMap<Integer, String> 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 en un orden desordenado, pero al recuperar el conjunto de claves, confirmamos que, de hecho, se mantienen en orden ascendente. Este es el orden natural de los enteros.
Del mismo modo, cuando usamos cadenas, se ordenarán en su orden natural, es decir, alfabéticamente:
@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() {
TreeMap<String, String> 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 hash map y un linked hash map, no emplea el principio de hashing en ningún lugar, ya que no utiliza un array para almacenar sus entradas.
3. Ordenamiento Personalizado en TreeMap
Si no estamos satisfechos con el orden natural de TreeMap, también podemos definir nuestra propia regla de ordenamiento mediante un comparador durante la construcción de un árbol mapa.
En el siguiente ejemplo, queremos que las claves enteras se ordenen en orden descendente:
@Test
public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() {
TreeMap<Integer, String> 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 hash map no garantiza el orden de las claves almacenadas y específicamente no garantiza que este orden se mantenga con el tiempo, pero un árbol mapa garantiza que las claves siempre estarán ordenadas según el orden especificado.
4. Importancia del Ordenamiento en TreeMap
Ahora sabemos que TreeMap almacena todas sus entradas en orden. Debido a esta característica, podemos realizar consultas como: encontrar “el mayor”, encontrar “el menor”, encontrar todas las claves menores o mayores que un cierto valor, etc.
El siguiente código cubre solo un pequeño porcentaje de estos casos:
@Test
public void givenTreeMap_whenPerformsQueries_thenCorrect() {
TreeMap<Integer, String> 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<Integer> keysLessThan3 = map.headMap(3).keySet();
Set<Integer> 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());
}
El TreeMap permite realizar estas operaciones de manera eficiente gracias a su estructura interna.
5. Implementación Interna de TreeMap
TreeMap implementa la interfaz NavigableMap y basa su funcionamiento interno en los principios de los árboles rojo-negro:
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, 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 entender cómo se ajustan a TreeMap.
En primer lugar, un árbol rojo-negro es una estructura de datos que consiste en nodos; imagina 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 comenzando desde la raíz, cualquier elemento en la rama izquierda de cualquier nodo es siempre menor que el elemento en el nodo mismo. Aquellos en la derecha son siempre mayores. Lo que define mayor o menor 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 árbol mapa siempre estarán en un orden ordenado y predecible.
En segundo lugar, un árbol rojo-negro es un árbol de búsqueda binaria auto-balanceado. Este atributo, junto con el anterior, garantiza que las operaciones básicas como búsqueda, obtener, poner y eliminar tomen un tiempo logarítmico O(log n).
Ser auto-balanceado es clave aquí. A medida que seguimos insertando y eliminando entradas, imagina que el árbol crece más largo de un lado o más corto del otro. Esto significaría que una operación tomaría menos tiempo en la rama corta y más tiempo en la rama que está más lejos de la raíz, algo que no querríamos que sucediera.
Por lo tanto, esto se cuida en el diseño de los á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 hash map y el linked hash map, un tree map no está sincronizado y, por lo tanto, las reglas para usarlo en un entorno multihilo son similares a las de las otras dos implementaciones de mapas.
6. Elegir el Mapa Adecuado
Habiendo revisado las implementaciones de HashMap y LinkedHashMap, y ahora TreeMap, es importante hacer una breve comparación entre los tres para guiarnos sobre cuál encaja mejor en qué lugar.
- Un hash map es bueno como una implementación de mapa de propósito general que proporciona operaciones de almacenamiento y recuperación rápidas. Sin embargo, se queda corto debido a su disposición caótica y desordenada de entradas. Esto causa que funcione mal en escenarios donde hay mucha iteración, ya que toda la capacidad del array subyacente afecta la travesía además de solo el número de entradas.
- Un linked hash map posee las buenas características de los hash maps y añade 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 tree map lleva el ordenamiento al siguiente nivel al proporcionar control total sobre cómo deben ordenarse las claves. Por el contrario, ofrece un rendimiento general peor que las otras dos alternativas.
Podríamos afirmar que un linked hash map reduce el caos en el ordenamiento de un hash map sin incurrir en la penalización de rendimiento de un tree map.
7. Conclusión
En este artículo, hemos explorado la clase TreeMap de Java y su implementación interna. Dado que es el último en una serie de implementaciones comunes de la interfaz Map, también discutimos brevemente dónde se adapta mejor en relación con las otras dos.
Para programadores que se especializan en el lenguaje de programación Java, aquí hay algunos consejos prácticos:
- Conocimiento de Estructuras de Datos: Familiarizarse con las estructuras de datos como los árboles rojo-negro puede ayudarte a entender mejor cómo funcionan los TreeMaps y optimizar el uso de tu código.
- Uso de Comparadores: Aprovecha la capacidad de usar comparadores para ordenar tus entradas de manera que se adapten mejor a tus necesidades específicas.
- Considerar el Contexto de Uso: Selecciona el tipo de mapa que mejor se ajuste a las características específicas de tus datos y a la naturaleza de las operaciones que realizarás con ellos.
La comprensión de TreeMap y su correcta implementación en tus proyectos no solo mejorará la eficiencia, sino que también te ayudará a desarrollar aplicaciones de calidad superior en el ecosistema Java.
