Per implementare viene utilizzata la TreeMap in Java Interfaccia della mappa e NavigableMap insieme alla classe AbstractMap. La mappa è ordinata secondo l'ordine naturale delle sue chiavi, oppure per a Comparatore fornito al momento della creazione della mappa, a seconda del costruttore utilizzato. Questo si rivela un modo efficiente per ordinare e archiviare le coppie chiave-valore. L'ordine di memorizzazione mantenuto dalla mappa ad albero deve essere coerente con gli uguali proprio come qualsiasi altra mappa ordinata, indipendentemente dai comparatori espliciti. L'implementazione della mappa ad albero non è sincronizzata nel senso che se a una mappa accedono più thread contemporaneamente e almeno uno dei thread modifica strutturalmente la mappa, deve essere sincronizzata esternamente.
TreeMap in Java è un'implementazione concreta dell'interfaccia java.util.SortedMap. Fornisce una raccolta ordinata di coppie chiave-valore, in cui le chiavi vengono ordinate in base al loro ordine naturale o a un comparatore personalizzato passato al costruttore.
Una TreeMap viene implementata utilizzando un albero Rosso-Nero, che è un tipo di albero di ricerca binario autobilanciante. Ciò fornisce prestazioni efficienti per operazioni comuni come l'aggiunta, la rimozione e il recupero di elementi, con una complessità temporale media di O(log n).
Ecco un esempio di come utilizzare la classe TreeMap:
Giava
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));> >}> >}> }> |
>
>Produzione
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Caratteristiche di una mappa ad albero
Alcune caratteristiche importanti della mappa ad albero sono le seguenti:
- Questa classe è un membro del Collezioni Java Struttura.
- La classe implementa Interfacce della mappa inclusi NavigableMap , SortedMap ed estende la classe AbstractMap.
- TreeMap in Java non consente chiavi null (come Map) e quindi viene generata una NullPointerException. Tuttavia, più valori null possono essere associati a chiavi diverse.
- Le coppie di voci restituite dai metodi in questa classe e le relative visualizzazioni rappresentano istantanee delle mappature nel momento in cui sono state prodotte. Non supportano il metodo Entry.setValue.
Ora andiamo avanti e parliamo di Synchronized TreeMap. L'implementazione di una TreeMap non è sincronizzata. Ciò significa che se più thread accedono contemporaneamente a un set di alberi e almeno uno dei thread modifica il set, deve essere sincronizzato esternamente. Questa operazione viene in genere eseguita utilizzando il metodo Collections.synchronizedSortedMap. È meglio farlo al momento della creazione, per impedire l'accesso accidentale e non sincronizzato al set. Questo può essere fatto come:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Geek, ora ti starai chiedendo come funziona internamente TreeMap?
I metodi in una TreeMap mentre ottengono set di chiavi e valori, restituiscono un Iterator di natura fail-fast. Pertanto, qualsiasi modifica simultanea genererà ConcurrentModificationException . Una TreeMap è basata su una struttura dati ad albero rosso-nero.
Ogni nodo dell'albero ha:
- 3 variabili ( Chiave K=Chiave, valore V=Valore, colore booleano=Colore )
- 3 Riferimenti ( Entrata a sinistra = Sinistra, Entrata a destra = Destra, Entrata genitore = Genitore )
Costruttori in TreeMap
Per creare una TreeMap, dobbiamo creare un oggetto della classe TreeMap. La classe TreeMap è composta da vari costruttori che permettono l'eventuale creazione della TreeMap. Di seguito sono riportati i costruttori disponibili in questa classe:
- MappaAlbero()
- TreeMap (comparatore comp)
- MappaAlbero(Mappa M)
- MappaAlbero(MappaOrdinata sm)
Discutiamoli individualmente insieme all'implementazione di ogni costruttore come segue:
Costruttore 1: MappaAlbero()
Questo costruttore viene utilizzato per creare una mappa ad albero vuota che verrà ordinata utilizzando l'ordine naturale delle relative chiavi.
Esempio
Giava
// 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();> >}> }> |
>
>Produzione
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Costruttore 2: TreeMap (comparatore comp)
Questo costruttore viene utilizzato per creare un oggetto TreeMap vuoto in cui gli elementi avranno bisogno di una specifica esterna dell'ordinamento.
Esempio
Giava
// 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();> >}> }> |
>
>Produzione
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Costruttore 3: MappaAlbero(Mappa M)
Questo costruttore viene utilizzato per inizializzare una TreeMap con le voci della mappa M specificata che verranno ordinate utilizzando l'ordine naturale delle chiavi.
Esempio
Giava
// 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();> >}> }> |
>
>Produzione
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Costruttore 4: MappaAlbero(MappaOrdinata sm)
Questo costruttore viene utilizzato per inizializzare una TreeMap con le voci della mappa ordinata data che verranno archiviate nello stesso ordine della mappa ordinata data.
Esempio
Giava
// 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();> >}> }> |
>
>Produzione
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Metodi nella classe TreeMap
| Metodo | Azione eseguita |
|---|---|
| chiaro() | Il metodo rimuove tutte le mappature da questa TreeMap e cancella la mappa. |
| clone() | Il metodo restituisce una copia superficiale di questa TreeMap. |
| contieneChiave(Chiave oggetto) | Restituisce vero se questa mappa contiene una mappatura per la chiave specificata. |
| contieneValore(Valore oggetto) | Restituisce vero se questa mappa mappa una o più chiavi al valore specificato. |
| set di voci() | Restituisce una vista impostata delle mappature contenute in questa mappa. |
| primachiave() | Restituisce la prima chiave (la più bassa) attualmente in questa mappa ordinata. |
| get(Chiave oggetto) | Restituisce il valore a cui questa mappa mappa la chiave specificata. |
| headMap(valore_chiave oggetto) | Il metodo restituisce una visualizzazione della porzione di mappa strettamente inferiore al parametro key_value. |
| mazzo di chiavi() | Il metodo restituisce una vista Set delle chiavi contenute nella mappa ad albero. |
| ultimachiave() | Restituisce l'ultima chiave (la più alta) attualmente in questa mappa ordinata. |
| put(Chiave oggetto, Valore oggetto) | Il metodo viene utilizzato per inserire una mappatura in una mappa. |
| putAll(Mappa mappa) | Copia tutte le mappature dalla mappa specificata a questa mappa. |
| rimuovi(chiave oggetto) | Rimuove la mappatura per questa chiave da questa TreeMap, se presente. |
| misurare() | Restituisce il numero di mappature di valori-chiave in questa mappa. |
| subMap((K startKey, K endKey) | Il metodo restituisce la porzione di questa mappa le cui chiavi vanno da startKey, inclusivo, a endKey, esclusivo. |
| valori() | Restituisce una visualizzazione della raccolta dei valori contenuti in questa mappa. |
Implementazione: I seguenti programmi dimostreranno meglio come creare, inserire e attraversare la TreeMap.
Illustrazione:
Giava
// 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();> >}> }> |
>
>Produzione
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> Esecuzione di varie operazioni su TreeMap
Dopo l'introduzione dei Generics in Java 1.5, è possibile limitare il tipo di oggetto che può essere memorizzato nella TreeMap. Ora vediamo come eseguire alcune operazioni utilizzate di frequente sulla TreeMap.
Operazione 1: Aggiunta di elementi
Per aggiungere un elemento alla TreeMap possiamo utilizzare il metodo put() . Tuttavia, l'ordine di inserimento non viene mantenuto nella TreeMap. Internamente, per ogni elemento, le chiavi vengono confrontate e ordinate in ordine crescente.
Esempio
Giava
// 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);> >}> }> |
>
>Produzione
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operazione 2: Modifica degli elementi
Dopo aver aggiunto gli elementi, se desideriamo modificare l'elemento, è possibile farlo aggiungendo nuovamente l'elemento con il metodo put() . Poiché gli elementi nella mappa ad albero vengono indicizzati utilizzando le chiavi, il valore della chiave può essere modificato semplicemente inserendo il valore aggiornato per la chiave per la quale si desidera modificare.
Esempio
Giava
// 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);> >}> }> |
>
>Produzione
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operazione 3: Rimozione dell'elemento
Per rimuovere un elemento dalla TreeMap possiamo utilizzare il metodoremove() . Questo metodo accetta il valore della chiave e rimuove la mappatura della chiave da questa mappa ad albero se è presente nella mappa.
Esempio
Giava
algoritmo knn
// 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);> >}> }> |
>
>Produzione
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Operazione 4: Iterazione attraverso la TreeMap
Esistono diversi modi per scorrere la mappa. Il modo più famoso è usare a per ogni ciclo e prendi le chiavi. Il valore della chiave si trova utilizzando il file metodo getValue() .
Esempio
Giava
// 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);> >}> >}> }> |
>
>Produzione
1 : Geeks 2 : For 3 : Geeks>
Vantaggi di TreeMap:
- Ordine ordinato: TreeMap fornisce un ordine ordinato dei suoi elementi, in base all'ordine naturale delle sue chiavi o a un comparatore personalizzato passato al costruttore. Ciò lo rende utile in situazioni in cui è necessario recuperare elementi in un ordine specifico.
- Ordine di iterazione prevedibile: poiché gli elementi in una TreeMap sono archiviati in un ordine ordinato, è possibile prevedere l'ordine in cui verranno restituiti durante l'iterazione, semplificando la scrittura di algoritmi che elaborano gli elementi in un ordine specifico.
- Prestazioni di ricerca: TreeMap fornisce un'implementazione efficiente dell'interfaccia Map, consentendo di recuperare elementi in tempo logaritmico, rendendolo utile negli algoritmi di ricerca in cui è necessario recuperare rapidamente gli elementi.
- Autobilanciamento: TreeMap è implementato utilizzando un albero Rosso-Nero, che è un tipo di albero di ricerca binario autobilanciante. Ciò fornisce prestazioni efficienti per l'aggiunta, la rimozione e il recupero di elementi, nonché per il mantenimento dell'ordinamento degli elementi.
Svantaggi di TreeMap:
- Lento per l'inserimento di elementi: l'inserimento di elementi in una TreeMap può essere più lento rispetto all'inserimento di elementi in una mappa normale, poiché la TreeMap deve mantenere l'ordine ordinato dei suoi elementi.
- Restrizione chiave: le chiavi in una TreeMap devono implementare l'interfaccia java.lang.Comparable oppure deve essere fornito un comparatore personalizzato. Questa può essere una limitazione se è necessario utilizzare chiavi personalizzate che non implementano questa interfaccia.
Libri di riferimento:
Collezioni Java di Maurice Naftalin e Philip Wadler. Questo libro fornisce una panoramica completa del framework Java Collections, inclusa TreeMap.
Java in poche parole di David Flanagan. Questo libro fornisce un rapido riferimento per le funzionalità principali di Java, inclusa TreeMap.
Java Generics e raccolte di Maurice Naftalin e Philip Wadler. Questo libro fornisce una guida completa ai generici e alle raccolte in Java, inclusa TreeMap.