TreeMap în Java este folosit pentru implementare Interfață pentru hartă și NavigableMap împreună cu Clasa AbstractMap. Harta este sortată în funcție de ordinea naturală a cheilor sale, sau după a Comparator furnizate la momentul creării hărții, în funcție de constructorul utilizat. Aceasta se dovedește a fi o modalitate eficientă de sortare și stocare a perechilor cheie-valoare. Ordinea de stocare menținută de harta arborescentă trebuie să fie în concordanță cu egalii la fel ca orice altă hartă sortată, indiferent de comparatorii explici. Implementarea hărții arbore nu este sincronizată în sensul că, dacă o hartă este accesată de mai multe fire de execuție, concomitent și cel puțin unul dintre fire de execuție modifică harta structural, aceasta trebuie să fie sincronizată extern.
TreeMap în Java este o implementare concretă a interfeței java.util.SortedMap. Oferă o colecție ordonată de perechi cheie-valoare, în care cheile sunt ordonate în funcție de ordinea lor naturală sau de un comparator personalizat transmis constructorului.
Un TreeMap este implementat folosind un arbore roșu-negru, care este un tip de arbore de căutare binar cu auto-echilibrare. Acest lucru oferă performanță eficientă pentru operațiuni obișnuite, cum ar fi adăugarea, eliminarea și preluarea elementelor, cu o complexitate de timp medie de O(log n).
Iată un exemplu de utilizare a clasei 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));> >}> >}> }> |
>
>Ieșire
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Caracteristicile unui TreeMap
Câteva caracteristici importante ale hărții arborelui sunt următoarele:
- Această clasă este membră a Colecții Java Cadru.
- Clasa implementează Interfețe pentru hărți inclusiv NavigableMap , SortedMap și extinde clasa AbstractMap.
- TreeMap în Java nu permite chei nule (cum ar fi Map) și astfel se aruncă o excepție NullPointerException. Cu toate acestea, mai multe valori nule pot fi asociate cu chei diferite.
- Perechile de intrare returnate de metodele din această clasă și vederile sale reprezintă instantanee ale mapărilor la momentul în care au fost produse. Ele nu acceptă metoda Entry.setValue.
Acum haideți să mergem mai departe și să discutăm despre Synchronized TreeMap. Implementarea unui TreeMap nu este sincronizată. Aceasta înseamnă că dacă mai multe fire de execuție accesează un set de arbore simultan și cel puțin unul dintre fire de execuție modifică setul, acesta trebuie să fie sincronizat extern. Acest lucru se realizează de obicei prin utilizarea metodei Collections.synchronizedSortedMap. Acest lucru se face cel mai bine în momentul creării, pentru a preveni accesul accidental nesincronizat la set. Acest lucru se poate face ca:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Geeks, acum trebuie să vă întrebați cum funcționează TreeMap intern?
Metodele dintr-un TreeMap în timp ce obțin set de chei și valori, returnează un Iterator care este de natură rapidă la eșec. Astfel, orice modificare concomitentă va arunca ConcurrentModificationException . Un TreeMap se bazează pe o structură de date arbore roșu-negru.
Fiecare nod din arbore are:
- 3 variabile ( Tasta K=Cheie, valoarea V=Valoare, culoare booleană=Culoare )
- 3 Referințe ( Intrare stânga = stânga, intrare dreapta = dreapta, intrare părinte = părinte )
Constructori în TreeMap
Pentru a crea un TreeMap, trebuie să creăm un obiect din clasa TreeMap. Clasa TreeMap constă din diverși constructori care permit crearea posibilă a TreeMap. Următorii sunt constructorii disponibili în această clasă:
- Harta copac()
- Harta arborelui (comparație de comparație)
- Harta arborelui (Harta M)
- Harta copac(Harta Sortată sm)
Să le discutăm individual împreună cu implementarea fiecărui constructor, după cum urmează:
Constructor 1: Harta copac()
Acest constructor este folosit pentru a construi o hartă arborescentă goală care va fi sortată folosind ordinea naturală a cheilor sale.
Exemplu
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();> >}> }> |
>
>Ieșire
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Constructor 2: Harta arborelui (comparație de comparație)
Acest constructor este folosit pentru a construi un obiect TreeMap gol în care elementele vor avea nevoie de o specificație externă a ordinii de sortare.
Exemplu
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();> >}> }> |
>
>Ieșire
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Constructor 3: Harta arborelui (Harta M)
Acest constructor este folosit pentru a inițializa un TreeMap cu intrările din harta dată M care vor fi sortate folosind ordinea naturală a cheilor.
Exemplu
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();> >}> }> |
>
>Ieșire
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Constructor 4: Harta copac(Harta Sortată sm)
Acest constructor este folosit pentru a inițializa un TreeMap cu intrările din harta sortată dată, care va fi stocată în aceeași ordine cu harta sortată dată.
Exemplu
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();> >}> }> |
>
>Ieșire
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Metode din clasa TreeMap
| Metodă | Actiune realizata |
|---|---|
| clar() | Metoda elimină toate mapările din acest TreeMap și șterge harta. |
| clona() | Metoda returnează o copie superficială a acestui TreeMap. |
| containsKey(cheie obiect) | Returnează true dacă această hartă conține o mapare pentru cheia specificată. |
| containsValue(Valoare obiect) | Returnează true dacă această hartă mapează una sau mai multe chei la valoarea specificată. |
| entrySet() | Returnează o vizualizare setată a mapărilor conținute în această hartă. |
| firstKey() | Returnează prima cheie (cea mai joasă) în prezent din această hartă sortată. |
| get(cheie obiect) | Returnează valoarea la care această hartă mapează cheia specificată. |
| headMap(Obiect key_value) | Metoda returnează o vedere a porțiunii hărții strict mai mică decât parametrul key_value. |
| keySet() | Metoda returnează o vizualizare Set a cheilor conținute în harta arborescentă. |
| lastKey() | Returnează ultima cheie (cea mai înaltă) în prezent din această hartă sortată. |
| put(cheia obiectului, valoarea obiectului) | Metoda este folosită pentru a insera o mapare într-o hartă. |
| putAll(hartă pe hartă) | Copiază toate mapările de pe harta specificată pe această hartă. |
| eliminați (cheia obiectului) | Îndepărtează maparea pentru această cheie din acest TreeMap, dacă este prezent. |
| mărimea() | Returnează numărul de mapări cheie-valoare din această hartă. |
| subMap((K cheie start, K cheie final) | Metoda returnează porțiunea acestei hărți ale cărei chei variază de la startKey, inclusiv, la endKey, exclusiv. |
| valori () | Returnează o vizualizare de colecție a valorilor conținute în această hartă. |
Implementare: Următoarele programe de mai jos vor demonstra mai bine cum să creați, să inserați și să traversați Harta Arborilor.
Ilustrare:
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();> >}> }> |
>
>Ieșire
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> Efectuarea diferitelor operații pe TreeMap
După introducerea genericelor în Java 1.5, este posibil să se restricționeze tipul de obiect care poate fi stocat în TreeMap. Acum, să vedem cum să efectuați câteva operațiuni frecvent utilizate pe TreeMap.
Operațiunea 1: Adăugarea de elemente
Pentru a adăuga un element în TreeMap, putem folosi metoda put() . Cu toate acestea, ordinea de inserare nu este reținută în TreeMap. Intern, pentru fiecare element, cheile sunt comparate și sortate în ordine crescătoare.
Exemplu
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);> >}> }> |
>
>Ieșire
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operațiunea 2: Schimbarea elementelor
După adăugarea elementelor dacă dorim să schimbăm elementul, se poate face prin adăugarea din nou a elementului cu metoda put() . Deoarece elementele din harta arborescentă sunt indexate folosind cheile, valoarea cheii poate fi modificată prin simpla inserare a valorii actualizate pentru cheia pentru care dorim să o modificăm.
Exemplu
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);> >}> }> |
>
>Ieșire
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operațiunea 3: Îndepărtarea elementului
Pentru a elimina un element din TreeMap, putem folosi metoda remove() . Această metodă preia valoarea cheii și elimină maparea cheii din această hartă arborescentă dacă este prezentă în hartă.
Exemplu
Java
interfață vs clasă abstractă
// 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);> >}> }> |
>
>Ieșire
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Operațiunea 4: Iterarea prin TreeMap
Există mai multe moduri de a itera prin Hartă. Cel mai faimos mod este de a folosi a pentru-fiecare buclă și ia cheile. Valoarea cheii este găsită folosind metoda getValue(). .
Exemplu
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);> >}> >}> }> |
>
>Ieșire
1 : Geeks 2 : For 3 : Geeks>
Avantajele TreeMap:
- Ordine sortată: TreeMap oferă o ordine sortată a elementelor sale, pe baza ordinii naturale a cheilor sale sau a unui comparator personalizat transmis constructorului. Acest lucru îl face util în situațiile în care trebuie să preluați elemente într-o anumită ordine.
- Ordine previzibilă de iterație: Deoarece elementele dintr-un TreeMap sunt stocate într-o ordine sortată, puteți prezice ordinea în care vor fi returnate în timpul iterației, făcând mai ușor să scrieți algoritmi care procesează elementele într-o anumită ordine.
- Performanța căutării: TreeMap oferă o implementare eficientă a interfeței Map, permițându-vă să preluați elemente în timp logaritmic, făcându-l util în algoritmii de căutare în care trebuie să recuperați elemente rapid.
- Auto-echilibrare: TreeMap este implementat folosind un arbore roșu-negru, care este un tip de arbore de căutare binar cu auto-echilibrare. Acest lucru oferă performanțe eficiente pentru adăugarea, eliminarea și preluarea elementelor, precum și menținerea ordinii sortate a elementelor.
Dezavantajele TreeMap:
- Încet pentru inserarea elementelor: inserarea elementelor într-o hartă arboreală poate fi mai lentă decât inserarea elementelor într-o hartă obișnuită, deoarece Harta arborelui trebuie să mențină ordinea sortată a elementelor sale.
- Restricție cheie: cheile dintr-un TreeMap trebuie să implementeze interfața java.lang.Comparable sau trebuie furnizat un comparator personalizat. Aceasta poate fi o restricție dacă trebuie să utilizați chei personalizate care nu implementează această interfață.
Carti de referinta:
Colecții Java de Maurice Naftalin și Philip Wadler. Această carte oferă o privire de ansamblu cuprinzătoare asupra cadrului Java Collections, inclusiv TreeMap.
Java pe scurt de David Flanagan. Această carte oferă o referință rapidă pentru caracteristicile de bază ale Java, inclusiv TreeMap.
Generice și colecții Java de Maurice Naftalin și Philip Wadler. Această carte oferă un ghid cuprinzător pentru generice și colecții în Java, inclusiv TreeMap.