El TreeMap a Java s'utilitza per implementar Interfície de mapa i NavigableMap juntament amb la classe AbstractMap. El mapa s'ordena segons l'ordre natural de les seves claus, o per a Comparador proporcionat en el moment de la creació del mapa, depenent del constructor que s'utilitzi. Això demostra ser una manera eficient d'ordenar i emmagatzemar els parells clau-valor. L'ordre d'emmagatzematge que manté el mapa d'arbre ha de ser coherent amb els iguals igual que qualsevol altre mapa ordenat, independentment dels comparadors explícits. La implementació del mapa d'arbre no està sincronitzada en el sentit que si s'accedeix a un mapa mitjançant diversos fils, simultàniament i almenys un dels fils modifica el mapa estructuralment, s'ha de sincronitzar externament.
El TreeMap en Java és una implementació concreta de la interfície java.util.SortedMap. Proporciona una col·lecció ordenada de parells clau-valor, on les claus s'ordenen en funció del seu ordre natural o d'un comparador personalitzat passat al constructor.
Un TreeMap s'implementa mitjançant un arbre vermell-negre, que és un tipus d'arbre de cerca binari d'autoequilibri. Això proporciona un rendiment eficient per a operacions comunes com afegir, eliminar i recuperar elements, amb una complexitat de temps mitjana de O(log n).
Aquí teniu un exemple de com utilitzar la classe 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));> >}> >}> }> |
>
>Sortida
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Característiques d'un TreeMap
Algunes característiques importants del mapa d'arbre són les següents:
- Aquesta classe és membre de la Col·leccions Java Marc.
- La classe implementa Interfícies de mapes incloent NavigableMap , SortedMap i amplia la classe AbstractMap.
- TreeMap a Java no permet claus nul·les (com Map) i per tant es llança una NullPointerException. Tanmateix, es poden associar diversos valors nuls amb claus diferents.
- Els parells d'entrada retornats pels mètodes d'aquesta classe i les seves vistes representen instantànies de mapes en el moment en què es van produir. No admeten el mètode Entry.setValue.
Ara avancem i parlem de Synchronized TreeMap. La implementació d'un TreeMap no està sincronitzada. Això vol dir que si diversos fils accedeixen a un conjunt d'arbres simultàniament i almenys un dels fils modifica el conjunt, s'ha de sincronitzar externament. Això s'aconsegueix normalment utilitzant el mètode Collections.synchronizedSortedMap. Això es fa millor en el moment de la creació, per evitar l'accés accidental no sincronitzat al conjunt. Això es pot fer com:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Frikis, ara us heu de preguntar com funciona el TreeMap internament?
Els mètodes d'un TreeMap mentre obtenen el conjunt de claus i els valors, retornen un iterador que és de naturalesa ràpida. Per tant, qualsevol modificació simultània llançarà ConcurrentModificationException . Un TreeMap es basa en una estructura de dades d'arbre vermell-negre.
Cada node de l'arbre té:
- 3 variables ( Tecla K=Clau, valor V=Valor, color booleà=Color )
- 3 referències ( Entrada esquerra = esquerra, entrada dreta = dreta, entrada pare = pare )
Constructors a TreeMap
Per crear un TreeMap, hem de crear un objecte de la classe TreeMap. La classe TreeMap consta de diversos constructors que permeten la possible creació del TreeMap. Els constructors disponibles en aquesta classe són els següents:
- TreeMap()
- TreeMap (composició del comparador)
- TreeMap (Mapa M)
- TreeMap(SortedMap sm)
Parlem-ne individualment juntament amb la implementació de cada constructor de la manera següent:
Constructor 1: TreeMap()
Aquest constructor s'utilitza per construir un mapa d'arbre buit que s'ordenarà utilitzant l'ordre natural de les seves claus.
Exemple
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();> >}> }> |
>
>Sortida
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Constructor 2: TreeMap (comparador de comparació)
Aquest constructor s'utilitza per construir un objecte TreeMap buit en el qual els elements necessitaran una especificació externa de l'ordre d'ordenació.
Exemple
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();> >}> }> |
>
>Sortida
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Constructor 3: TreeMap (Mapa M)
Aquest constructor s'utilitza per inicialitzar un TreeMap amb les entrades del mapa donat M que s'ordenaran utilitzant l'ordre natural de les claus.
Exemple
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();> >}> }> |
>
>Sortida
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Constructor 4: TreeMap(SortedMap sm)
Aquest constructor s'utilitza per inicialitzar un TreeMap amb les entrades del mapa ordenat donat que s'emmagatzemaran en el mateix ordre que el mapa ordenat donat.
Exemple
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();> >}> }> |
>
>Sortida
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Mètodes de la classe TreeMap
| Mètode | Acció realitzada |
|---|---|
| clar () | El mètode elimina tots els mapes d'aquest TreeMap i esborra el mapa. |
| clonar () | El mètode retorna una còpia superficial d'aquest TreeMap. |
| containsKey (clau d'objecte) | Retorna true si aquest mapa conté una assignació per a la clau especificada. |
| containsValue (Valor de l'objecte) | Retorna true si aquest mapa associa una o més claus al valor especificat. |
| entrySet() | Retorna una vista conjunta dels mapes continguts en aquest mapa. |
| firstKey() | Retorna la primera clau (la més baixa) actualment en aquest mapa ordenat. |
| obtenir (clau d'objecte) | Retorna el valor al qual aquest mapa associa la clau especificada. |
| headMap(valor_clau de l'objecte) | El mètode retorna una vista de la part del mapa estrictament menor que el paràmetre valor_clau. |
| keySet() | El mètode retorna una vista Set de les claus contingudes al mapa d'arbre. |
| lastKey() | Retorna la darrera clau (la més alta) actualment en aquest mapa ordenat. |
| put(clau de l'objecte, valor de l'objecte) | El mètode s'utilitza per inserir un mapa en un mapa. |
| putAll (mapa del mapa) | Copia tots els mapes del mapa especificat a aquest mapa. |
| eliminar (clau d'objecte) | Elimina l'assignació d'aquesta clau d'aquest TreeMap si està present. |
| mida () | Retorna el nombre de mapes de valor-clau en aquest mapa. |
| subMap((K clau inicial, K clau final) | El mètode retorna la part d'aquest mapa les claus van des de startKey, inclòs, fins a endKey, exclusiu. |
| valors () | Retorna una vista de col·lecció dels valors continguts en aquest mapa. |
Implementació: Els programes següents mostraran millor com crear, inserir i recórrer el TreeMap.
Il·lustració:
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();> >}> }> |
>
>Sortida
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> Realització de diverses operacions en TreeMap
Després de la introducció dels genèrics a Java 1.5, és possible restringir el tipus d'objecte que es pot emmagatzemar al TreeMap. Ara, anem a veure com realitzar algunes operacions d'ús freqüent al TreeMap.
Operació 1: Afegir Elements
Per afegir un element al TreeMap, podem utilitzar el mètode put() . Tanmateix, l'ordre d'inserció no es conserva al TreeMap. Internament, per a cada element, les claus es comparen i s'ordenen en ordre ascendent.
Exemple
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);> >}> }> |
>
>Sortida
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operació 2: Canvi d'elements
Després d'afegir els elements si volem canviar l'element, es pot fer afegint de nou l'element amb el mètode put() . Com que els elements del mapa d'arbre s'indexen mitjançant les claus, el valor de la clau es pot canviar simplement inserint el valor actualitzat de la clau per a la qual volem canviar.
Exemple
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);> >}> }> |
>
>Sortida
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operació 3: Eliminació de l'element
Per eliminar un element del TreeMap, podem utilitzar el mètode remove() . Aquest mètode pren el valor de la clau i elimina l'assignació de la clau d'aquest mapa d'arbre si està present al mapa.
Exemple
Java
mida del text de làtex
// 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);> >}> }> |
>
>Sortida
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Operació 4: Iterant a través del TreeMap
Hi ha diverses maneres de recórrer el mapa. La forma més famosa és utilitzar a per a cada bucle i agafa les claus. El valor de la clau es troba utilitzant el mètode getValue(). .
Exemple
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);> >}> >}> }> |
>
>Sortida
1 : Geeks 2 : For 3 : Geeks>
Avantatges de TreeMap:
- Ordre ordenat: el TreeMap proporciona un ordre ordenat dels seus elements, basat en l'ordre natural de les seves claus o en un comparador personalitzat passat al constructor. Això fa que sigui útil en situacions en què necessiteu recuperar elements en un ordre específic.
- Ordre d'iteració previsible: com que els elements d'un TreeMap s'emmagatzemen en un ordre ordenat, podeu predir l'ordre en què es tornaran durant la iteració, facilitant l'escriptura d'algorismes que processin els elements en un ordre específic.
- Rendiment de la cerca: TreeMap proporciona una implementació eficient de la interfície del mapa, que us permet recuperar elements en temps logarítmic, cosa que el fa útil en algorismes de cerca on necessiteu recuperar elements ràpidament.
- Autoequilibri: el TreeMap s'implementa mitjançant un arbre vermell-negre, que és un tipus d'arbre de cerca binari d'autoequilibri. Això proporciona un rendiment eficient per afegir, eliminar i recuperar elements, així com mantenir l'ordre ordenat dels elements.
Desavantatges de TreeMap:
- Lenta per inserir elements: inserir elements en un TreeMap pot ser més lent que inserir elements en un mapa normal, ja que el TreeMap ha de mantenir l'ordre ordenat dels seus elements.
- Restricció de claus: les claus d'un TreeMap han d'implementar la interfície java.lang.Comparable o s'ha de proporcionar un comparador personalitzat. Això pot ser una restricció si necessiteu utilitzar claus personalitzades que no implementin aquesta interfície.
Llibres de referència:
Col·leccions Java de Maurice Naftalin i Philip Wadler. Aquest llibre ofereix una visió general completa del marc de col·leccions de Java, inclòs el TreeMap.
Java en poques paraules de David Flanagan. Aquest llibre proporciona una referència ràpida per a les característiques bàsiques de Java, inclòs el TreeMap.
Java Generics and Collections de Maurice Naftalin i Philip Wadler. Aquest llibre ofereix una guia completa sobre genèrics i col·leccions en Java, inclòs el TreeMap.