TreeMap i Java bruges til at implementere Kort interface og NavigableMap sammen med AbstractMap Class. Kortet er sorteret efter den naturlige rækkefølge af dets nøgler, eller efter en Komparator leveres på tidspunktet for oprettelse af kort, afhængigt af hvilken konstruktør der bruges. Dette viser sig at være en effektiv måde at sortere og opbevare nøgleværdi-parrene på. Lagringsrækkefølgen, der vedligeholdes af trækortet, skal være i overensstemmelse med ligeværdige, ligesom ethvert andet sorteret kort, uanset de eksplicitte komparatorer. Trækortimplementeringen er ikke synkroniseret i den forstand, at hvis et kort tilgås af flere tråde, samtidig og mindst én af trådene ændrer kortet strukturelt, skal det synkroniseres eksternt.
TreeMap i Java er en konkret implementering af java.util.SortedMap-grænsefladen. Det giver en ordnet samling af nøgleværdi-par, hvor nøglerne er ordnet baseret på deres naturlige rækkefølge eller en tilpasset komparator videregivet til konstruktøren.
Et TreeMap er implementeret ved hjælp af et rød-sort træ, som er en type selvbalancerende binært søgetræ. Dette giver effektiv ydeevne til almindelige operationer såsom tilføjelse, fjernelse og hentning af elementer med en gennemsnitlig tidskompleksitet på O(log n).
Her er et eksempel på, hvordan du bruger TreeMap-klassen:
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));> >}> >}> }> |
>
>Produktion
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Funktioner i et trækort
Nogle vigtige funktioner i trækortet er som følger:
- Denne klasse er medlem af Java samlinger Ramme.
- Klassen implementerer Kortgrænseflader inklusive NavigableMap , SortedMap , og udvider AbstractMap-klassen.
- TreeMap i Java tillader ikke null-nøgler (som Map), og derfor kastes en NullPointerException. Imidlertid kan flere null-værdier associeres med forskellige nøgler.
- Indtastningspar returneret af metoderne i denne klasse og dens visninger repræsenterer øjebliksbilleder af kortlægninger på det tidspunkt, de blev produceret. De understøtter ikke Entry.setValue-metoden.
Lad os nu gå videre og diskutere Synchronized TreeMap. Implementeringen af et TreeMap er ikke synkroniseret. Dette betyder, at hvis flere tråde får adgang til et træsæt samtidigt, og mindst én af trådene ændrer sættet, skal det synkroniseres eksternt. Dette opnås typisk ved at bruge metoden Collections.synchronizedSortedMap. Dette gøres bedst på oprettelsestidspunktet for at forhindre utilsigtet usynkroniseret adgang til sættet. Dette kan gøres som:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Nørder, nu må du undre dig over, hvordan fungerer TreeMap internt?
Metoderne i et TreeMap returnerer en Iterator, der er fejlhurtig i naturen, mens de får keyset og værdier. Således vil enhver samtidig ændring kaste ConcurrentModificationException . Et TreeMap er baseret på en rød-sort trædatastruktur.
Hver knude i træet har:
- 3 variabler ( K-tast=Nøgle, V-værdi=Værdi, boolsk farve=Farve )
- 3 referencer ( Indgang venstre = Venstre, Indgang højre = Højre, Indgang forælder = Forælder )
Konstruktører i TreeMap
For at oprette et TreeMap skal vi oprette et objekt af TreeMap-klassen. TreeMap-klassen består af forskellige konstruktører, der muliggør oprettelse af TreeMap. Følgende er konstruktørerne tilgængelige i denne klasse:
- TreeMap()
- TreeMap (Comparator comp)
- Trækort (kort M)
- TreeMap(Sorteret kort sm)
Lad os diskutere dem individuelt sammen med implementering af hver konstruktør som følger:
Konstruktør 1: TreeMap()
Denne konstruktør bruges til at bygge et tomt trækort, der vil blive sorteret ved at bruge dens naturlige rækkefølge.
Eksempel
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();> >}> }> |
>
>Produktion
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Konstruktør 2: TreeMap (Comparator comp)
Denne konstruktør bruges til at bygge et tomt TreeMap-objekt, hvor elementerne skal have en ekstern specifikation af sorteringsrækkefølgen.
Eksempel
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();> >}> }> |
>
>Produktion
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Konstruktør 3: Trækort (kort M)
Denne konstruktør bruges til at initialisere et TreeMap med indtastningerne fra det givne kort M, som vil blive sorteret ved at bruge den naturlige rækkefølge af nøglerne.
Eksempel
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();> >}> }> |
>
>Produktion
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Konstruktør 4: TreeMap(Sorteret kort sm)
Denne konstruktør bruges til at initialisere et trækort med indtastningerne fra det givne sorterede kort, som vil blive gemt i samme rækkefølge som det givne sorterede kort.
Eksempel
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();> >}> }> |
>
>Produktion
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Metoder i TreeMap-klassen
| Metode | Handling udført |
|---|---|
| klar() | Metoden fjerner alle kortlægninger fra dette TreeMap og rydder kortet. |
| klone() | Metoden returnerer en overfladisk kopi af dette TreeMap. |
| containsKey(Objektnøgle) | Returnerer sand, hvis dette kort indeholder en tilknytning til den angivne nøgle. |
| indeholderVærdi(objektværdi) | Returnerer sand, hvis dette kort knytter en eller flere nøgler til den angivne værdi. |
| entrySet() | Returnerer en fast visning af kortlægningerne på dette kort. |
| firstKey() | Returnerer den første (laveste) nøgle i øjeblikket på dette sorterede kort. |
| get (objektnøgle) | Returnerer den værdi, som dette kort knytter den angivne nøgle til. |
| headMap(Objektnøgleværdi) | Metoden returnerer en visning af den del af kortet, der er strengt mindre end parameteren nøgleværdi. |
| keySet() | Metoden returnerer en Set-visning af nøglerne indeholdt i træoversigten. |
| lastKey() | Returnerer den sidste (højeste) nøgle i øjeblikket på dette sorterede kort. |
| put(Objektnøgle, Objektværdi) | Metoden bruges til at indsætte en kortlægning i et kort. |
| putAll(Kortkort) | Kopierer alle tilknytninger fra det angivne kort til dette kort. |
| fjern (objektnøgle) | Fjerner kortlægningen for denne nøgle fra dette TreeMap, hvis det findes. |
| størrelse() | Returnerer antallet af nøgleværdi-tilknytninger i dette kort. |
| subMap((K startKey, K endKey) | Metoden returnerer den del af dette kort, hvis nøgler spænder fra startKey, inklusive, til endKey, exclusive. |
| værdier() | Returnerer en samlingsvisning af værdierne på dette kort. |
Implementering: De følgende programmer nedenfor vil bedre demonstrere, hvordan man opretter, indsætter og krydser trækortet.
Illustration:
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();> >}> }> |
>
>Produktion
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> Udførelse af forskellige operationer på TreeMap
Efter introduktionen af Generics i Java 1.5, er det muligt at begrænse den type objekt, der kan gemmes i TreeMap. Lad os nu se, hvordan du udfører et par ofte brugte operationer på trækortet.
Operation 1: Tilføjelse af elementer
For at tilføje et element til TreeMap kan vi bruge put() metoden . Indsættelsesrækkefølgen bibeholdes dog ikke i TreeMap. Internt for hvert element sammenlignes nøglerne og sorteres i stigende rækkefølge.
Eksempel
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);> >}> }> |
>
>Produktion
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operation 2: Ændring af elementer
Efter tilføjelse af elementerne, hvis vi ønsker at ændre elementet, kan det gøres ved igen at tilføje elementet med put() metoden . Da elementerne i trækortet er indekseret ved hjælp af nøglerne, kan nøglens værdi ændres ved blot at indsætte den opdaterede værdi for den nøgle, som vi ønsker at ændre.
Eksempel
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);> >}> }> |
>
>Produktion
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operation 3: Fjernelse af element
For at fjerne et element fra TreeMap kan vi bruge metoden remove() . Denne metode tager nøgleværdien og fjerner kortlægningen for nøglen fra dette trækort, hvis det er til stede i kortet.
Eksempel
Java
python konvertere bytes til streng
// 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);> >}> }> |
>
>Produktion
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Operation 4: Iteration gennem TreeMap
Der er flere måder at iterere gennem kortet. Den mest berømte måde er at bruge en for hver sløjfe og få nøglerne. Værdien af nøglen findes ved at bruge getValue() metode .
Eksempel
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);> >}> >}> }> |
>
>Produktion
1 : Geeks 2 : For 3 : Geeks>
Fordele ved TreeMap:
- Sorteret rækkefølge: TreeMap giver en sorteret rækkefølge af dets elementer, baseret på den naturlige rækkefølge af dets nøgler eller en tilpasset komparator videregivet til konstruktøren. Dette gør det nyttigt i situationer, hvor du skal hente elementer i en bestemt rækkefølge.
- Forudsigelig iterationsrækkefølge: Fordi elementerne i et TreeMap er gemt i en sorteret rækkefølge, kan du forudsige den rækkefølge, som de vil blive returneret i under iterationen, hvilket gør det nemmere at skrive algoritmer, der behandler elementerne i en bestemt rækkefølge.
- Søgeydelse: TreeMap giver en effektiv implementering af kortgrænsefladen, så du kan hente elementer i logaritmisk tid, hvilket gør det nyttigt i søgealgoritmer, hvor du skal hente elementer hurtigt.
- Selvbalancering: TreeMap er implementeret ved hjælp af et rød-sort træ, som er en type selvbalancerende binært søgetræ. Dette giver effektiv ydeevne til tilføjelse, fjernelse og hentning af elementer, samt opretholdelse af den sorterede rækkefølge af elementerne.
Ulemper ved TreeMap:
- Langsomt til indsættelse af elementer: Indsættelse af elementer i et TreeMap kan være langsommere end at indsætte elementer i et almindeligt kort, da TreeMap skal opretholde den sorterede rækkefølge af dets elementer.
- Nøglebegrænsning: Nøglerne i et TreeMap skal implementere java.lang.Comparable-grænsefladen, eller der skal leveres en brugerdefineret komparator. Dette kan være en begrænsning, hvis du skal bruge brugerdefinerede nøgler, der ikke implementerer denne grænseflade.
Opslagsbøger:
Java-samlinger af Maurice Naftalin og Philip Wadler. Denne bog giver et omfattende overblik over Java Collections-rammerne, inklusive TreeMap.
Java i en nøddeskal af David Flanagan. Denne bog giver en hurtig reference til kernefunktionerne i Java, herunder TreeMap.
Java Generics and Collections af Maurice Naftalin og Philip Wadler. Denne bog giver en omfattende guide til generiske artikler og samlinger i Java, inklusive TreeMap.