Características de TreeMap en Java

Si estás leyendo este artículo, es probable que estés familiarizado con la interfaz del Mapa y sus usos. Si no, aquí tienes. Hoy hablaremos sobre las características de implementación de 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, lo que lo convierte en el mejor candidato para la mayoría de las tareas. La mayoría, pero no todos. A veces es necesario almacenar datos de forma estructurada con la capacidad de navegar a través de ellos. En este caso, otra implementación de la interfaz Map viene al rescate : TreeMap . TreeMap implementa la interfaz NavigableMap , que hereda de SortedMap , que a su vez hereda de la interfaz Map . Al implementar las interfaces NavigableMap y SortedMap , TreeMap obtiene una funcionalidad adicional que HashMap no tiene , pero esto tiene un precio en términos de rendimiento. También hay una clase LinkedHashMap , que también le permite almacenar datos en un orden determinado, en el orden en que se agregaron. Para ayudarle a comprender las diferencias entre estas tres clases, consulte esta tabla: Como puedes ver, estas clases tienen mucho en común, pero también hay algunas diferencias. Aunque la clase TreeMapes la más multifuncional, no siempre se puede almacenar nullcomo clave. Además, el tiempo de acceso a los elementos de TreeMap será el mayor. Por lo tanto, si no necesita almacenar datos ordenados, es mejor utilizar HashMapo LinkedHashMap.

Árbol de ébano rojo

Como probablemente habrás notado, bajo el capó TreeMaputiliza una estructura de datos llamada árbol rojo-negro. Es el almacenamiento de datos en esta estructura lo que garantiza el orden en el que se almacenan los datos. ¿Qué es este árbol? ¡Vamos a resolverlo! Imagine que necesita almacenar pares de números y cadenas. Los números 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 serán las claves. Si almacena datos en una lista tradicional y necesita encontrar un elemento con la clave 101, deberá recorrer los 13 elementos para encontrarlo. Para 13 elementos esto no es crítico; cuando trabajemos con un millón tendremos grandes problemas. Para resolver estos problemas, los programadores utilizan estructuras de datos un poco más complejas. ¡Por lo tanto, conoce el árbol rojo-negro!

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

La búsqueda del elemento requerido comienza desde la raíz del árbol, en nuestro caso es 61. A continuación se realiza una comparación con el valor requerido. Si nuestro valor es menor vamos a la izquierda, si es mayor vamos a la derecha. Esto sucede hasta que encontramos el valor requerido o llegamos a un elemento con un valor null(una hoja de un árbol). Los colores rojo y negro se utilizan para hacer que el árbol sea más fácil de navegar y equilibrar. Hay reglas que siempre se deben seguir al construir un árbol rojo-negro:

• La raíz debe ser de color negro.
• Las hojas del árbol deben ser negras.
• Un nodo rojo debe tener dos nodos secundarios negros.
• Un nodo negro puede tener nodos secundarios.
• El camino desde un nodo hasta sus hojas debe contener la misma cantidad de nodos negros.
• Se agregan nuevos nodos en lugar de hojas.

Si observa las reglas 3, 4 y 5 juntas, podrá comprender cómo colorear los nodos acelera la navegación a través del árbol: el camino a través de los nodos negros siempre es más corto que a través de los rojos. Por lo tanto, el tamaño total del árbol está determinado por la cantidad de nodos negros, y este tamaño se denomina "altura negra". El árbol rojo-negro se implementa en diferentes lenguajes de programación. Hay muchas implementaciones para Java en Internet, por lo que no nos detendremos en ello por mucho tiempo, pero continuaremos familiarizándonos con la funcionalidad TreeMap.

Métodos derivados de las interfaces SortedMap y NavigableMap

Implementa la interfaz HashMap, lo que significa que tiene todos los métodos que . Pero además, implementa interfaces y , obteniendo de ellas funcionalidad adicional. - una interfaz que amplía y agrega métodos relevantes para un conjunto de datos ordenados: TreeMapMapTreeMapHashMapTreeMapSortedMapNavigableMapSortedMapMap

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

NavigableMap— una interfaz que amplía SortedMapy agrega métodos para navegar entre elementos del 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 dicha clave, devuelve nulo;
• floorKey(K obj): Devuelve la clave k más grande que es menor o igual que la clave obj. Si no existe dicha clave, devuelve nulo;
• lowerKey(K obj): Devuelve la clave k más grande que es más pequeña que la clave obj. Si no existe dicha clave, devuelve nulo;
• higherKey(K obj): Devuelve la clave más pequeña k que es mayor que la clave obj. Si no existe dicha clave, devuelve nulo;
• ceilingEntry(K obj): similar al método techoKey(K obj), pero devuelve un par clave-valor (o nulo);
• floorEntry(K obj): similar al método FloorKey(K obj), pero devuelve un par clave-valor (o nulo);
• lowerEntry(K obj): similar al método lowerKey(K obj), pero devuelve un par clave-valor (o nulo);
• higherEntry(K obj): similar al método lowerKey(K obj), pero 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 orden de almacenamiento;
• headMap(K upperBound, boolean incl): devuelve un mapa que contiene pares desde el principio hasta el elemento límite superior. El argumento incl especifica si el elemento UpperBound debe incluirse en el mapa devuelto;
• tailMap(K lowerBound, boolean incl): la funcionalidad es similar al método anterior, solo se devuelven los pares desde el límite inferior hasta el final;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Como en los métodos anteriores, se devuelven pares desde límite inferior hasta límite superior, y los argumentos lowIncl y highIncl indican si se deben incluir los elementos de límite en el nuevo mapa.

En la implementación misma TreeMap, además de los constructores que conocemos, se agrega uno más que acepta una instancia del comparador. Este comparador será responsable del orden en el que se almacenen los elementos.

Ejemplos de uso de TreeMap

Tal abundancia de métodos adicionales puede parecer innecesaria, pero muy a menudo resultan mucho más útiles de lo que parecía inicialmente. Veamos este ejemplo contigo. Imaginemos que trabajamos en el departamento de marketing de una gran empresa y tenemos una base de datos de personas a las que queremos mostrar publicidad. Hay dos matices en esto:

• necesitamos realizar un seguimiento del número de impresiones de cada persona;
• El algoritmo para mostrar publicidad a menores es diferente.

Creemos una clase Personque almacenará toda la información disponible para nosotros sobre una 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("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 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 Mainque creamos TreeMap, donde keyes una persona específica y valuees el número de impresiones de anuncios este mes. En el constructor pasamos un comparador que ordenará a las personas por edad. Rellenar con mapvalores aleatorios. Ahora necesitamos obtener una referencia al primer adulto en nuestro mini almacén de datos. Hacemos esto usando la API Stream. Después de esto, obtenemos dos mapas independientes, que pasamos a los métodos que muestran publicidad. Hay muchas, muchas maneras en que se podría resolver este problema. El arsenal de métodos de la clase TreeMaple permite inventar soluciones para todos los gustos. No es necesario recordarlos todos, porque siempre puedes utilizar la documentación o sugerencias del entorno de desarrollo. ¡Eso es todo! Espero que la clase ya TreeMapte resulte clara y que encuentres una aplicación precisa para resolver problemas prácticos.