TreeMap i Java brukes til å implementere Kartgrensesnitt og NavigableMap sammen med AbstractMap Class. Kartet er sortert i henhold til den naturlige rekkefølgen av nøklene, eller etter en Komparator gitt på tidspunktet for kartoppretting, avhengig av hvilken konstruktør som brukes. Dette viser seg å være en effektiv måte å sortere og lagre nøkkelverdi-parene på. Lagringsrekkefølgen som opprettholdes av trekartet må være konsistent med like, akkurat som alle andre sorterte kart, uavhengig av de eksplisitte komparatorene. Trekartimplementeringen er ikke synkronisert i den forstand at hvis et kart får tilgang til flere tråder, samtidig og minst én av trådene endrer kartet strukturelt, må det synkroniseres eksternt.
TreeMap i Java er en konkret implementering av java.util.SortedMap-grensesnittet. Det gir en ordnet samling av nøkkelverdi-par, der nøklene er ordnet basert på deres naturlige rekkefølge eller en tilpasset komparator sendt til konstruktøren.
Et TreeMap er implementert ved hjelp av et rød-svart tre, som er en type selvbalanserende binært søketre. Dette gir effektiv ytelse for vanlige operasjoner som å legge til, fjerne og hente elementer, med en gjennomsnittlig tidskompleksitet på O(log n).
Her er et eksempel på hvordan du bruker 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));> >}> >}> }> |
>
>Produksjon
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Funksjoner til et trekart
Noen viktige funksjoner i trekartet er som følger:
- Denne klassen er medlem av Java-samlinger Rammeverk.
- Klassen gjennomfører Kartgrensesnitt inkludert NavigableMap , SortedMap , og utvider AbstractMap-klassen.
- TreeMap i Java tillater ikke nullnøkler (som Map) og dermed kastes et NullPointerException. Imidlertid kan flere nullverdier assosieres med forskjellige nøkler.
- Oppføringsparene returnert av metodene i denne klassen og dens visninger representerer øyeblikksbilder av tilordninger på tidspunktet de ble produsert. De støtter ikke Entry.setValue-metoden.
La oss nå gå videre og diskutere Synchronized TreeMap. Implementeringen av et TreeMap er ikke synkronisert. Dette betyr at hvis flere tråder får tilgang til et tresett samtidig, og minst én av trådene endrer settet, må det synkroniseres eksternt. Dette oppnås vanligvis ved å bruke Collections.synchronizedSortedMap-metoden. Dette gjøres best ved opprettelsestidspunktet for å forhindre utilsiktet usynkronisert tilgang til settet. Dette kan gjøres som:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Geeks, nå må du lure på hvordan TreeMap fungerer internt?
Metodene i et TreeMap, mens de får nøkkelsett og verdier, returnerer en Iterator som er feil-rask i naturen. Dermed vil enhver samtidig modifikasjon kaste ConcurrentModificationException . Et TreeMap er basert på en rød-svart tredatastruktur.
Hver node i treet har:
- 3 variabler ( K-tast=Nøkkel, V-verdi=Verdi, boolsk farge=Farge )
- 3 referanser ( Entry left = Venstre, Entry right = Right, Entry parent = Parent )
Konstruktører i TreeMap
For å lage et TreeMap, må vi lage et objekt av TreeMap-klassen. TreeMap-klassen består av forskjellige konstruktører som muliggjør mulig opprettelse av TreeMap. Følgende er konstruktørene som er tilgjengelige i denne klassen:
- Trekart()
- TreeMap (Comparator comp)
- Trekart (Kart M)
- Trekart(Sortert kart sm)
La oss diskutere dem individuelt ved siden av å implementere hver konstruktør som følger:
Konstruktør 1: Trekart()
Denne konstruktøren brukes til å bygge et tomt trekart som vil bli sortert ved å bruke den naturlige rekkefølgen til nøklene.
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();> >}> }> |
>
>Produksjon
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Konstruktør 2: TreeMap (Comparator comp)
Denne konstruktøren brukes til å bygge et tomt TreeMap-objekt der elementene trenger en ekstern spesifikasjon av sorteringsrekkefø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();> >}> }> |
>
>Produksjon
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Konstruktør 3: Trekart (Kart M)
Denne konstruktøren brukes til å initialisere et TreeMap med oppføringene fra det gitte kartet M som vil bli sortert ved å bruke den naturlige rekkefølgen til nøklene.
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();> >}> }> |
>
>Produksjon
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Konstruktør 4: Trekart(Sortert kart sm)
Denne konstruktøren brukes til å initialisere et TreeMap med oppføringene fra det gitte sorterte kartet som vil bli lagret i samme rekkefølge som det gitte sorterte kartet.
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();> >}> }> |
>
>Produksjon
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Metoder i TreeMap-klassen
| Metode | Handling utført |
|---|---|
| klar() | Metoden fjerner alle tilordninger fra dette trekartet og sletter kartet. |
| klone() | Metoden returnerer en grunn kopi av dette trekartet. |
| containsKey(Objektnøkkel) | Returnerer sann hvis dette kartet inneholder en tilordning for den angitte nøkkelen. |
| containsValue(Objektverdi) | Returnerer sann hvis dette kartet tilordner én eller flere nøkler til den angitte verdien. |
| entrySet() | Returnerer en sett visning av tilordningene i dette kartet. |
| firstKey() | Returnerer den første (laveste) nøkkelen i dette sorterte kartet. |
| get (objektnøkkel) | Returnerer verdien som dette kartet tilordner den angitte nøkkelen til. |
| headMap(Objektnøkkelverdi) | Metoden returnerer en visning av delen av kartet som er strengt mindre enn parameteren nøkkelverdi. |
| keySet() | Metoden returnerer en Set-visning av nøklene i trekartet. |
| lastKey() | Returnerer den siste (høyeste) nøkkelen for øyeblikket i dette sorterte kartet. |
| put(Objektnøkkel, Objektverdi) | Metoden brukes til å sette inn en kartlegging i et kart. |
| putAll(Kart kart) | Kopierer alle tilordningene fra det angitte kartet til dette kartet. |
| fjern (objektnøkkel) | Fjerner tilordningen for denne nøkkelen fra dette trekartet hvis det finnes. |
| størrelse() | Returnerer antall nøkkelverdi-tilordninger i dette kartet. |
| subMap((K startKey, K endKey) | Metoden returnerer den delen av dette kartet hvis nøkler spenner fra startKey, inklusive, til endKey, exclusive. |
| verdier() | Returnerer en samlingsvisning av verdiene i dette kartet. |
Gjennomføring: Følgende programmer nedenfor vil demonstrere bedre hvordan du oppretter, setter inn og går gjennom TreeMap.
Illustrasjon:
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();> >}> }> |
>
>Produksjon
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> Utføre forskjellige operasjoner på TreeMap
Etter introduksjonen av Generics i Java 1.5 er det mulig å begrense hvilken type objekt som kan lagres i TreeMap. La oss nå se hvordan du utfører noen få ofte brukte operasjoner på TreeMap.
Operasjon 1: Legge til elementer
For å legge til et element til TreeMap, kan vi bruke put()-metoden . Innsettingsrekkefølgen beholdes imidlertid ikke i TreeMap. Internt, for hvert element, blir nøklene sammenlignet og sortert i stigende rekkefø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);> >}> }> |
>
>Produksjon
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operasjon 2: Bytte elementer
Etter å ha lagt til elementene hvis vi ønsker å endre elementet, kan det gjøres ved å legge til elementet igjen med put()-metoden . Siden elementene i trekartet er indeksert ved hjelp av nøklene, kan verdien til nøkkelen endres ved ganske enkelt å sette inn den oppdaterte verdien for nøkkelen vi ønsker å endre.
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);> >}> }> |
>
>Produksjon
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operasjon 3: Fjerner element
For å fjerne et element fra TreeMap, kan vi bruke remove()-metoden . Denne metoden tar nøkkelverdien og fjerner tilordningen for nøkkelen fra dette trekartet hvis det finnes i kartet.
Eksempel
Java
python konvertere byte 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);> >}> }> |
>
>Produksjon
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Operasjon 4: Iterering gjennom TreeMap
Det er flere måter å iterere gjennom kartet på. Den mest kjente måten er å bruke en for hver løkke og hente nøklene. Verdien av nøkkelen finner du ved å bruke getValue()-metoden .
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);> >}> >}> }> |
>
>Produksjon
1 : Geeks 2 : For 3 : Geeks>
Fordeler med TreeMap:
- Sortert rekkefølge: TreeMap gir en sortert rekkefølge av elementene, basert på den naturlige rekkefølgen til nøklene eller en tilpasset komparator sendt til konstruktøren. Dette gjør det nyttig i situasjoner der du trenger å hente elementer i en bestemt rekkefølge.
- Forutsigbar iterasjonsrekkefølge: Fordi elementene i et TreeMap er lagret i en sortert rekkefølge, kan du forutsi rekkefølgen de vil bli returnert i under iterasjonen, noe som gjør det lettere å skrive algoritmer som behandler elementene i en bestemt rekkefølge.
- Søkeytelse: TreeMap gir en effektiv implementering av kartgrensesnittet, slik at du kan hente elementer i logaritmisk tid, noe som gjør det nyttig i søkealgoritmer der du trenger å hente elementer raskt.
- Selvbalansering: TreeMap er implementert ved hjelp av et rød-svart tre, som er en type selvbalanserende binært søketre. Dette gir effektiv ytelse for å legge til, fjerne og hente elementer, samt opprettholde den sorterte rekkefølgen av elementene.
Ulemper med TreeMap:
- Sakte for å sette inn elementer: Å sette inn elementer i et TreeMap kan være tregere enn å sette inn elementer i et vanlig kart, ettersom TreeMap trenger å opprettholde den sorterte rekkefølgen av elementene.
- Nøkkelbegrensning: Nøklene i et TreeMap må implementere java.lang.Comparable-grensesnittet, eller en tilpasset komparator må leveres. Dette kan være en begrensning hvis du trenger å bruke egendefinerte nøkler som ikke implementerer dette grensesnittet.
Referanse bøker:
Java-samlinger av Maurice Naftalin og Philip Wadler. Denne boken gir en omfattende oversikt over Java Collections-rammeverket, inkludert TreeMap.
Java i et nøtteskall av David Flanagan. Denne boken gir en rask referanse for kjernefunksjonene til Java, inkludert TreeMap.
Java Generics and Collections av Maurice Naftalin og Philip Wadler. Denne boken gir en omfattende guide til generikk og samlinger i Java, inkludert TreeMap.