El TreeMap en Java se utiliza para implementar Interfaz de mapa y NavigableMap junto con la clase AbstractMap. El mapa se ordena según el orden natural de sus claves, o por un Comparador proporcionado en el momento de la creación del mapa, dependiendo del constructor que se utilice. Esta demuestra ser una forma eficaz de ordenar y almacenar los pares clave-valor. El orden de almacenamiento mantenido por el mapa de árbol debe ser consistente con iguales como cualquier otro mapa ordenado, independientemente de los comparadores explícitos. La implementación del mapa de árbol no está sincronizada en el sentido de que si varios subprocesos acceden a un mapa simultáneamente y al menos uno de los subprocesos modifica el mapa estructuralmente, debe sincronizarse externamente.
TreeMap en Java es una implementación concreta de la interfaz java.util.SortedMap. Proporciona una colección ordenada de pares clave-valor, donde las claves se ordenan según su orden natural o un Comparador personalizado pasado al constructor.
Un TreeMap se implementa utilizando un árbol Rojo-Negro, que es un tipo de árbol de búsqueda binario autoequilibrado. Esto proporciona un rendimiento eficiente para operaciones comunes como agregar, eliminar y recuperar elementos, con una complejidad de tiempo promedio de O (log n).
A continuación se muestra un ejemplo de cómo utilizar la clase TreeMap:
Java
import> java.util.Map;> import> java.util.TreeMap;> public> class> Main {> >public> static> void> main(String[] args) {> >Map treeMap =>new> TreeMap();> >// Adding elements to the tree map> >treeMap.put(>'A'>,>1>);> >treeMap.put(>'C'>,>3>);> >treeMap.put(>'B'>,>2>);> >// Getting values from the tree map> >int> valueA = treeMap.get(>'A'>);> >System.out.println(>'Value of A: '> + valueA);> >// Removing elements from the tree map> >treeMap.remove(>'B'>);> >// Iterating over the elements of the tree map> >for> (String key : treeMap.keySet()) {> >System.out.println(>'Key: '> + key +>', Value: '> + treeMap.get(key));> >}> >}> }> |
>
>Producción
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Características de un TreeMap
Algunas características importantes del mapa de árbol son las siguientes:
- Esta clase es miembro de la Colecciones Java Estructura.
- La clase implementa Interfaces de mapas incluido NavigableMap, SortedMap y extiende la clase AbstractMap.
- TreeMap en Java no permite claves nulas (como Map) y, por lo tanto, se genera una excepción NullPointerException. Sin embargo, se pueden asociar varios valores nulos con diferentes claves.
- Los pares de entradas devueltos por los métodos de esta clase y sus vistas representan instantáneas de las asignaciones en el momento en que se produjeron. No admiten el método Entry.setValue.
Ahora avancemos y analicemos TreeMap sincronizado. La implementación de un TreeMap no está sincronizada. Esto significa que si varios subprocesos acceden a un conjunto de árboles al mismo tiempo y al menos uno de los subprocesos modifica el conjunto, debe sincronizarse externamente. Normalmente, esto se logra utilizando el método Collections.synchronizedSortedMap. Es mejor hacerlo en el momento de la creación, para evitar el acceso accidental y no sincronizado al conjunto. Esto se puede hacer como:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Geeks, ahora deben preguntarse cómo funciona TreeMap internamente.
Los métodos en un TreeMap, mientras obtienen conjuntos de claves y valores, devuelven un iterador que es de naturaleza rápida. Por lo tanto, cualquier modificación simultánea generará una excepción ConcurrentModificationException. Un TreeMap se basa en una estructura de datos de árbol rojo-negro.
Cada nodo del árbol tiene:
- 3 variables ( Tecla K=Clave, valor V=Valor, color booleano=Color )
- 3 Referencias ( Entrada izquierda = Izquierda, Entrada derecha = Derecha, Entrada padre = Padre )
Constructores en TreeMap
Para crear un TreeMap, necesitamos crear un objeto de la clase TreeMap. La clase TreeMap consta de varios constructores que permiten la posible creación del TreeMap. Los siguientes son los constructores disponibles en esta clase:
- Mapa de árbol()
- TreeMap (comparador comparador)
- Mapa de árbol (Mapa M)
- Mapa de árbol (Mapa ordenado sm)
Analicémoslos individualmente junto con la implementación de cada constructor de la siguiente manera:
Constructor 1: Mapa de árbol()
Este constructor se utiliza para construir un mapa de árbol vacío que se ordenará utilizando el orden natural de sus claves.
Ejemplo
Java
// Java Program to Demonstrate TreeMap> // using the Default Constructor> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Main class> // TreeMapImplementation> public> class> GFG {> >// Method 1> >// To show TreeMap constructor> >static> void> Example1stConstructor()> >{> >// Creating an empty TreeMap> >TreeMap tree_map> >=>new> TreeMap();> >// Mapping string values to int keys> >// using put() method> >tree_map.put(>10>,>'Geeks'>);> >tree_map.put(>15>,>'4'>);> >tree_map.put(>20>,>'Geeks'>);> >tree_map.put(>25>,>'Welcomes'>);> >tree_map.put(>30>,>'You'>);> >// Printing the elements of TreeMap> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Method 2> >// Main driver method> >public> static> void> main(String[] args)> >{> >System.out.println(>'TreeMap using '> >+>'TreeMap() constructor:
'>);> >// Calling constructor> >Example1stConstructor();> >}> }> |
>
>Producción
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Constructor 2: TreeMap (comparador comparador)
Este constructor se utiliza para construir un objeto TreeMap vacío en el que los elementos necesitarán una especificación externa del orden de clasificación.
Ejemplo
Java
// Java Program to Demonstrate TreeMap> // using Comparator Constructor> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Class 1> // Helper class representing Student> class> Student {> >// Attributes of a student> >int> rollno;> >String name, address;> >// Constructor> >public> Student(>int> rollno, String name, String address)> >{> >// This keyword refers to current object itself> >this>.rollno = rollno;> >this>.name = name;> >this>.address = address;> >}> >// Method of this class> >// To print student details> >public> String toString()> >{> >return> this>.rollno +>' '> +>this>.name +>' '> >+>this>.address;> >}> }> // Class 2> // Helper class - Comparator implementation> class> Sortbyroll>implements> Comparator {> >// Used for sorting in ascending order of> >// roll number> >public> int> compare(Student a, Student b)> >{> >return> a.rollno - b.rollno;> >}> }> // Class 3> // Main class> public> class> GFG {> >// Calling constructor inside main()> >static> void> Example2ndConstructor()> >{> >// Creating an empty TreeMap> >TreeMap tree_map> >=>new> TreeMap(> >new> Sortbyroll());> >// Mapping string values to int keys> >tree_map.put(>new> Student(>111>,>'bbbb'>,>'london'>),>2>);> >tree_map.put(>new> Student(>131>,>'aaaa'>,>'nyc'>),>3>);> >tree_map.put(>new> Student(>121>,>'cccc'>,>'jaipur'>),>1>);> >// Printing the elements of TreeMap> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Main driver method> >public> static> void> main(String[] args)> >{> >System.out.println(>'TreeMap using '> >+>'TreeMap(Comparator)'> >+>' constructor:
'>);> >Example2ndConstructor();> >}> }> |
>
>Producción
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Constructor 3: Mapa de árbol (Mapa M)
Este constructor se utiliza para inicializar un TreeMap con las entradas del mapa dado M que se ordenarán utilizando el orden natural de las claves.
Ejemplo
Java
// Java Program to Demonstrate TreeMap> // using the Default Constructor> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Main class> public> class> TreeMapImplementation {> >// Method 1> >// To illustrate constructor> >static> void> Example3rdConstructor()> >{> >// Creating an empty HashMap> >Map hash_map> >=>new> HashMap();> >// Mapping string values to int keys> >// using put() method> >hash_map.put(>10>,>'Geeks'>);> >hash_map.put(>15>,>'4'>);> >hash_map.put(>20>,>'Geeks'>);> >hash_map.put(>25>,>'Welcomes'>);> >hash_map.put(>30>,>'You'>);> >// Creating the TreeMap using the Map> >TreeMap tree_map> >=>new> TreeMap(hash_map);> >// Printing the elements of TreeMap> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Method 2> >// Main driver method> >public> static> void> main(String[] args)> >{> >System.out.println(>'TreeMap using '> >+>'TreeMap(Map)'> >+>' constructor:
'>);> >Example3rdConstructor();> >}> }> |
>
>Producción
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Constructor 4: Mapa de árbol (Mapa ordenado sm)
Este constructor se utiliza para inicializar un TreeMap con las entradas del mapa ordenado dado que se almacenarán en el mismo orden que el mapa ordenado dado.
Ejemplo
Java
// Java Program to Demonstrate TreeMap> // using the SortedMap Constructor> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Main class> // TreeMapImplementation> public> class> GFG {> >// Method> >// To show TreeMap(SortedMap) constructor> >static> void> Example4thConstructor()> >{> >// Creating a SortedMap> >SortedMap sorted_map> >=>new> ConcurrentSkipListMap();> >// Mapping string values to int keys> >// using put() method> >sorted_map.put(>10>,>'Geeks'>);> >sorted_map.put(>15>,>'4'>);> >sorted_map.put(>20>,>'Geeks'>);> >sorted_map.put(>25>,>'Welcomes'>);> >sorted_map.put(>30>,>'You'>);> >// Creating the TreeMap using the SortedMap> >TreeMap tree_map> >=>new> TreeMap(sorted_map);> >// Printing the elements of TreeMap> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Method 2> >// Main driver method> >public> static> void> main(String[] args)> >{> >System.out.println(>'TreeMap using '> >+>'TreeMap(SortedMap)'> >+>' constructor:
'>);> >Example4thConstructor();> >}> }> |
>
>Producción
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Métodos en la clase TreeMap
| Método | Acción realizada |
|---|---|
| claro() | El método elimina todas las asignaciones de este TreeMap y borra el mapa. |
| clon() | El método devuelve una copia superficial de este TreeMap. |
| contiene clave (clave de objeto) | Devuelve verdadero si este mapa contiene una asignación para la clave especificada. |
| contieneValor(Valor del objeto) | Devuelve verdadero si este mapa asigna una o más claves al valor especificado. |
| conjunto de entrada() | Devuelve una vista establecida de las asignaciones contenidas en este mapa. |
| primera clave() | Devuelve la primera clave (la más baja) actualmente en este mapa ordenado. |
| obtener (clave de objeto) | Devuelve el valor al que este mapa asigna la clave especificada. |
| headMap(Objeto clave_valor) | El método devuelve una vista de la parte del mapa estrictamente menor que el parámetro valor_clave. |
| juego de llaves() | El método devuelve una vista Conjunto de las claves contenidas en el mapa de árbol. |
| última clave() | Devuelve la última clave (la más alta) actualmente en este mapa ordenado. |
| put(Clave del objeto, Valor del objeto) | El método se utiliza para insertar un mapeo en un mapa. |
| putAll(Mapa mapa) | Copia todas las asignaciones del mapa especificado a este mapa. |
| eliminar (clave de objeto) | Elimina la asignación para esta clave de este TreeMap si está presente. |
| tamaño() | Devuelve el número de asignaciones clave-valor en este mapa. |
| subMap((K clave de inicio, K clave de fin) | El método devuelve la parte de este mapa cuyas claves van desde startKey, inclusive, hasta endKey, exclusiva. |
| valores() | Devuelve una vista de colección de los valores contenidos en este mapa. |
Implementación: Los siguientes programas demostrarán mejor cómo crear, insertar y recorrer TreeMap.
Ilustración:
Java
// Java Program to Illustrate Operations in TreeMap> // Such as Creation, insertion> // searching, and traversal> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Main class> // Implementation of TreeMap> public> class> GFG {> >// Declaring a TreeMap> >static> TreeMap tree_map;> >// Method 1> >// To create TreeMap> >static> void> create()> >{> >// Creating an empty TreeMap> >tree_map =>new> TreeMap();> >// Display message only> >System.out.println(>'TreeMap successfully'> >+>' created'>);> >}> >// Method 2> >// To Insert values in the TreeMap> >static> void> insert()> >{> >// Mapping string values to int keys> >// using put() method> >tree_map.put(>10>,>'Geeks'>);> >tree_map.put(>15>,>'4'>);> >tree_map.put(>20>,>'Geeks'>);> >tree_map.put(>25>,>'Welcomes'>);> >tree_map.put(>30>,>'You'>);> >// Display message only> >System.out.println(>'
Elements successfully'> >+>' inserted in the TreeMap'>);> >}> >// Method 3> >// To search a key in TreeMap> >static> void> search(>int> key)> >{> >// Checking for the key> >System.out.println(>'
Is key ''> + key> >+>'' present? '> >+ tree_map.containsKey(key));> >}> >// Method 4> >// To search a value in TreeMap> >static> void> search(String value)> >{> >// Checking for the value> >System.out.println(>'
Is value ''> + value> >+>'' present? '> >+ tree_map.containsValue(value));> >}> >// Method 5> >// To display the elements in TreeMap> >static> void> display()> >{> >// Displaying the TreeMap> >System.out.println(>'
Displaying the TreeMap:'>);> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Method 6> >// To traverse TreeMap> >static> void> traverse()> >{> >// Display message only> >System.out.println(>'
Traversing the TreeMap:'>);> >for> (Map.Entry e :> >tree_map.entrySet())> >System.out.println(e.getKey() +>' '> >+ e.getValue());> >}> >// Method 6> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Calling above defined methods inside main()> >// Creating a TreeMap> >create();> >// Inserting the values in the TreeMap> >insert();> >// Search key '50' in the TreeMap> >search(>50>);> >// Search value 'Geeks' in the TreeMap> >search(>'Geeks'>);> >// Display the elements in TreeMap> >display();> >// Traversing the TreeMap> >traverse();> >}> }> |
>
>Producción
TreeMap successfully created Elements successfully inserted in the TreeMap Is key '50' present? false Is value 'Geeks' present? true Displaying the TreeMap: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You} Traversing the TreeMap: 10 Geeks 15 4 20 Geeks 25 Welcomes 30 You> Realizar varias operaciones en TreeMap
Después de la introducción de genéricos en Java 1.5, es posible restringir el tipo de objeto que se puede almacenar en TreeMap. Ahora, veamos cómo realizar algunas operaciones de uso frecuente en TreeMap.
Operación 1: Agregar elementos
Para agregar un elemento al TreeMap, podemos usar el método put(). Sin embargo, el orden de inserción no se conserva en TreeMap. Internamente, para cada elemento, las claves se comparan y clasifican en orden ascendente.
Ejemplo
Java
// Java Program to Illustrate Addition of Elements> // in TreeMap using put() Method> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Default Initialization of a TreeMap> >TreeMap tm1 =>new> TreeMap();> >// Inserting the elements in TreeMap> >// using put() method> >tm1.put(>3>,>'Geeks'>);> >tm1.put(>2>,>'For'>);> >tm1.put(>1>,>'Geeks'>);> >// Initialization of a TreeMap using Generics> >TreeMap tm2> >=>new> TreeMap();> >// Inserting the elements in TreeMap> >// again using put() method> >tm2.put(>new> Integer(>3>),>'Geeks'>);> >tm2.put(>new> Integer(>2>),>'For'>);> >tm2.put(>new> Integer(>1>),>'Geeks'>);> >// Printing the elements of both TreeMaps> >// Map 1> >System.out.println(tm1);> >// Map 2> >System.out.println(tm2);> >}> }> |
>
>Producción
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operación 2: Cambio de elementos
Después de agregar los elementos, si deseamos cambiar el elemento, podemos hacerlo agregando nuevamente el elemento con el método put(). Dado que los elementos en el mapa de árbol están indexados usando las claves, el valor de la clave se puede cambiar simplemente insertando el valor actualizado de la clave que deseamos cambiar.
Ejemplo
Java
// Java program to Illustrate Updation of Elements> // in TreeMap using put() Method> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Initialization of a TreeMap> >// using Generics> >TreeMap tm> >=>new> TreeMap();> >// Inserting the elements in Map> >// using put() method> >tm.put(>3>,>'Geeks'>);> >tm.put(>2>,>'Geeks'>);> >tm.put(>1>,>'Geeks'>);> >// Print all current elements in map> >System.out.println(tm);> >// Inserting the element at specified> >// corresponding to specified key> >tm.put(>2>,>'For'>);> >// Printing the updated elements of Map> >System.out.println(tm);> >}> }> |
>
>Producción
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operación 3: Eliminando elemento
Para eliminar un elemento del TreeMap, podemos usar el método remove(). Este método toma el valor de la clave y elimina la asignación de la clave de este mapa de árbol si está presente en el mapa.
Ejemplo
Java
subcadena de cadena
// Java program to Illustrate Removal of Elements> // in TreeMap using remove() Method> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Initialization of a TreeMap> >// using Generics> >TreeMap tm> >=>new> TreeMap();> >// Inserting the elements> >// using put() method> >tm.put(>3>,>'Geeks'>);> >tm.put(>2>,>'Geeks'>);> >tm.put(>1>,>'Geeks'>);> >tm.put(>4>,>'For'>);> >// Printing all elements of Map> >System.out.println(tm);> >// Removing the element corresponding to key> >tm.remove(>4>);> >// Printing updated TreeMap> >System.out.println(tm);> >}> }> |
>
>Producción
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Operación 4: Iterando a través del TreeMap
Hay varias formas de recorrer el mapa. La forma más famosa es utilizar un para cada bucle y consigue las llaves. El valor de la clave se encuentra usando el método getValue() .
Ejemplo
Java
// Java Program to Illustrate Iterating over TreeMap> // using> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Initialization of a TreeMap> >// using Generics> >TreeMap tm> >=>new> TreeMap();> >// Inserting the elements> >// using put() method> >tm.put(>3>,>'Geeks'>);> >tm.put(>2>,>'For'>);> >tm.put(>1>,>'Geeks'>);> >// For-each loop for traversal over Map> >// via entrySet() Method> >for> (Map.Entry mapElement : tm.entrySet()) {> >int> key = (>int>)mapElement.getKey();> >// Finding the value> >String value = (String)mapElement.getValue();> >// Printing the key and value> >System.out.println(key +>' : '> + value);> >}> >}> }> |
>
>Producción
1 : Geeks 2 : For 3 : Geeks>
Ventajas de TreeMap:
- Orden ordenado: TreeMap proporciona un orden ordenado de sus elementos, según el orden natural de sus claves o un Comparador personalizado pasado al constructor. Esto lo hace útil en situaciones en las que necesita recuperar elementos en un orden específico.
- Orden de iteración predecible: dado que los elementos de un TreeMap se almacenan en un orden ordenado, puede predecir el orden en el que se devolverán durante la iteración, lo que facilita la escritura de algoritmos que procesen los elementos en un orden específico.
- Rendimiento de búsqueda: TreeMap proporciona una implementación eficiente de la interfaz Map, lo que le permite recuperar elementos en tiempo logarítmico, lo que lo hace útil en algoritmos de búsqueda donde necesita recuperar elementos rápidamente.
- Autoequilibrio: TreeMap se implementa utilizando un árbol Rojo-Negro, que es un tipo de árbol de búsqueda binario autoequilibrado. Esto proporciona un rendimiento eficiente para agregar, eliminar y recuperar elementos, así como para mantener el orden de los elementos.
Desventajas de TreeMap:
- Lento para insertar elementos: insertar elementos en un TreeMap puede ser más lento que insertar elementos en un mapa normal, ya que TreeMap necesita mantener el orden de sus elementos.
- Restricción de clave: las claves en un TreeMap deben implementar la interfaz java.lang.Comparable o se debe proporcionar un comparador personalizado. Esto puede ser una restricción si necesita utilizar claves personalizadas que no implementan esta interfaz.
Libros de referencia:
Colecciones Java de Maurice Naftalin y Philip Wadler. Este libro proporciona una descripción general completa del marco de las colecciones de Java, incluido TreeMap.
Java en pocas palabras de David Flanagan. Este libro proporciona una referencia rápida de las características principales de Java, incluido TreeMap.
Colecciones y genéricos de Java de Maurice Naftalin y Philip Wadler. Este libro proporciona una guía completa sobre genéricos y colecciones en Java, incluido TreeMap.