TreeMap en Java

Si está leyendo este artículo, lo más probable es que esté familiarizado con la interfaz de mapa y dónde se puede aplicar de manera adecuada. Si no, entonces ven aquí . Hoy hablaremos sobre las características de la implementación de Java TreeMap y, más específicamente, en qué se diferencia de HashMap y cómo usarlo correctamente.

Comparación de TreeMap, HashMap y LinkedHashMap

La implementación más utilizada de la interfaz Map es HashMap. Es fácil de usar y garantiza un acceso rápido a los datos, por lo que es el mejor candidato para resolver la mayoría de los problemas. La mayoría, pero no todos. A veces es necesario almacenar datos de forma estructurada y poder navegar a través de ellos. En este caso, otra implementación de la interfaz Map (TreeMap) viene al rescate. TreeMap implementa la interfaz NavigableMap , que hereda SortedMap , que a su vez hereda la interfaz Map. Al implementar las interfaces NavigableMap y SortedMap , TreeMap recibe una funcionalidad adicional que no está disponible en HashMap, pero paga un precio en términos de rendimiento. También está el LinkedHashMapclass , que también le permite almacenar datos en un orden específico (el orden en que los agrega al mapa). Para entender las diferencias entre estas tres clases, mira esta tabla: Como puede ver, estas clases tienen mucho en común, pero también hay varias diferencias. Aunque la clase TreeMap es la más versátil, no siempre puede almacenar null como clave. Además, acceder a los elementos de un TreeMap lleva la mayor cantidad de tiempo. Por lo tanto, si no necesita almacenar datos en algún orden, es mejor usar HashMap o LinkedHashMap .

árbol rojo-negro

Probablemente haya notado que, bajo el capó, TreeMap usa una estructura de datos llamada árbol rojo-negro. El almacenamiento de datos en esta estructura es precisamente lo que proporciona el ordenamiento de los datos. Entonces, ¿qué clase de árbol es este? ¡Averigüémoslo! Imagina que necesitas almacenar pares de cadenas de números. Los números 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 y 101 serán claves. Si almacena datos en una lista tradicional y necesita encontrar el elemento con la clave 101, deberá recorrer los 13 elementos para encontrarlo. Para 13 elementos, esto no es gran cosa, pero cuando trabajamos con un millón, tendremos grandes problemas. Para resolver estos problemas, los programadores usan estructuras de datos un poco más complejas. ¡Aquí es donde el árbol rojo-negro entra en escena!La búsqueda de un elemento comienza en la raíz del árbol, que en nuestro caso es 61. Luego comparamos los valores de los nodos con el valor que estamos buscando. Si nuestro valor es menor, vamos a la izquierda; si es mayor, entonces vamos a la derecha. Este proceso se repite hasta que encontramos el valor deseado o encontramos un elemento cuyo valor es nulo (una hoja del árbol). Los colores rojo y negro se utilizan para simplificar la navegación y el equilibrio del árbol. Hay reglas que siempre deben observarse al construir un árbol rojo-negro:

• La raíz debe ser negra.
• Las hojas del árbol deben ser negras.
• Un nodo rojo debe tener dos nodos secundarios negros.
• Un nodo negro puede tener nodos secundarios de cualquier color.
• Un camino desde un nodo hasta sus hojas debe contener el mismo número de nodos negros.
• Se agregan nuevos nodos a las hojas.

Si considera las Reglas 3, 4 y 5 juntas, puede comprender cómo el color del nodo nos permite navegar por el árbol más rápidamente: un camino a través de los nodos negros siempre es más corto que uno a través de los nodos rojos. En consecuencia, el tamaño total del árbol está determinado por el número de nodos negros, lo que se denomina "altura negra". La estructura de datos del árbol rojo-negro se implementa en varios lenguajes de programación. Hay muchas implementaciones de Java en Internet, así que no nos detendremos aquí. En cambio, sigamos conociendo la funcionalidad de TreeMap.

Métodos que provienen de las interfaces SortedMap y NavigableMap

Al igual que HashMap, TreeMap implementa la interfaz Map, lo que significa que TreeMap tiene todos los métodos que existen en HashMap. Pero TreeMap también implementa las interfaces SortedMap y NavigableMap y, por lo tanto, obtiene una funcionalidad adicional de ellas. SortedMap es una interfaz que amplía Map y agrega métodos relevantes para un conjunto de datos ordenado:

• firstKey() : devuelve la clave del primer elemento en el mapa
• lastKey() : devuelve la clave del último elemento
• headMap(K end) : devuelve un mapa que contiene todos los elementos del mapa actual, desde el principio hasta el elemento con la clave final
• tailMap(K start) : devuelve un mapa que contiene todos los elementos del mapa actual, desde el elemento inicial hasta el final
• subMap(K start, K ​​end) : devuelve un mapa que contiene todos los elementos del mapa actual, desde el elemento inicial hasta el elemento con la clave final.

NavigableMap es una interfaz que amplía SortedMap y agrega métodos para navegar entre elementos de un mapa:

• firstEntry() : devuelve el primer par clave-valor
• lastEntry() : devuelve el último par clave-valor
• pollFirstEntry() : devuelve y elimina el primer par
• pollLastEntry() : devuelve y elimina el último par
• CeilingKey(K obj) : devuelve la clave más pequeña k que es mayor o igual que la clave obj. Si no existe tal clave, devuelve nulo
• floorKey(K obj) : devuelve la clave más grande k que es menor o igual que la clave obj. Si no existe tal clave, devuelve nulo
• lowerKey(K obj) : devuelve la clave más grande k que es menor que la clave obj. Si no existe tal clave, devuelve nulo
• highKey(K obj) : devuelve la clave más pequeña k que es más grande que la clave obj. Si no existe tal clave, devuelve nulo
• CeilingEntry(K obj) : similar al método ceilingKey(K obj), solo devuelve un par clave-valor (o nulo)
• floorEntry(K obj) : similar al método floorKey(K obj), solo devuelve un par clave-valor (o nulo)
• lowerEntry(K obj) : similar al método lowerKey(K obj), solo devuelve un par clave-valor (o nulo)
• highEntry(K obj) : similar al método highKey(K obj), solo devuelve un par clave-valor (o nulo)
• descendingKeySet() : devuelve un NavigableSet que contiene todas las claves ordenadas en orden inverso
• descendingMap() : devuelve un NavigableMap que contiene todos los pares ordenados en orden inverso
• navigableKeySet() : devuelve un objeto NavigableSet que contiene todas las claves en el orden en que se almacenan
• headMap(K upperBound, boolean incl) : devuelve un mapa que contiene pares desde el principio hasta el elemento upperBound. El parámetro incl indica si incluir el elemento upperBound en el mapa devuelto
• tailMap(K lowerBound, boolean incl) : funcionalidad similar al método anterior, devuelve solo pares desde lowerBound hasta el final
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl) : al igual que con los métodos anteriores, devuelve pares de lowerBound a upperBound; los argumentos lowIncl y highIncl indican si incluir los elementos de contorno en el nuevo mapa.

Además de los constructores habituales, TreeMap tiene otro constructor que acepta una instancia de un comparador. Este comparador es responsable del orden en que se almacenan los elementos.

Ejemplos de TreeMap

Esta abundancia de métodos adicionales puede parecer innecesaria, pero resulta ser mucho más útil de lo que podría pensar a primera vista. Exploremos juntos el siguiente ejemplo. Imagina que trabajamos en el departamento de marketing de una gran empresa, y tenemos una base de datos de personas a las que queremos mostrar anuncios. Hay dos detalles a tener en cuenta:

• Necesitamos hacer un seguimiento del número de impresiones de cada persona.
• El algoritmo para mostrar anuncios a menores es diferente.

Vamos a crear una clase Person , que almacenará toda la información relevante sobre cada persona:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

Implementamos la lógica en la clase Main :

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map) {}
   public static void showAdvertisementToAdult(Map map) {}
}

En la clase Principal, cree un TreeMap, en el que cada clave represente a una persona específica y cada valor sea el número de impresiones de anuncios este mes. Pasamos al constructor un comparador que clasifica a las personas por edad. Rellenamos el mapa con valores arbitrarios. Ahora queremos obtener una referencia al primer adulto en nuestro pequeño repositorio de datos. Hacemos esto usando la API Stream. Luego obtenemos dos mapas separados, que pasamos a los métodos que muestran anuncios. Hay muchas, muchas maneras en que podríamos haber logrado esta tarea. El arsenal de métodos de la clase TreeMap nos permite crear soluciones personalizadas para cada necesidad. No necesita recordarlos todos, porque siempre puede usar la documentación o los consejos de su IDE. Para reforzar lo que aprendió, le sugerimos que vea una lección en video de nuestro Curso de Java

¡Eso es todo por ahora! Espero que la clase TreeMap le resulte clara ahora y que la aplique correctamente para resolver tareas prácticas de codificación.