TreeMap i Java används för att implementera Kartgränssnitt och NavigableMap tillsammans med AbstractMap Class. Kartan är sorterad enligt den naturliga ordningen för dess nycklar, eller efter en Komparator tillhandahålls när kartan skapas, beroende på vilken konstruktor som används. Detta visar sig vara ett effektivt sätt att sortera och lagra nyckel-värdeparen. Lagringsordningen som upprätthålls av trädkartan måste överensstämma med likadana precis som alla andra sorterade kartor, oberoende av de explicita komparatorerna. Trädkartans implementering är inte synkroniserad i den meningen att om en karta nås av flera trådar samtidigt och åtminstone en av trådarna modifierar kartan strukturellt, måste den synkroniseras externt.
TreeMap i Java är en konkret implementering av java.util.SortedMap-gränssnittet. Den tillhandahåller en ordnad samling nyckel-värdepar, där nycklarna ordnas baserat på deras naturliga ordning eller en anpassad komparator som skickas till konstruktören.
En TreeMap implementeras med hjälp av ett röd-svart träd, som är en typ av självbalanserande binärt sökträd. Detta ger effektiv prestanda för vanliga operationer som att lägga till, ta bort och hämta element, med en genomsnittlig tidskomplexitet på O(log n).
Här är ett exempel på hur du använder klassen 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));> >}> >}> }> |
>
>Produktion
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Funktioner i en TreeMap
Några viktiga funktioner i trädkartan är följande:
- Denna klass är medlem i Java-samlingar Ramverk.
- Klassen implementerar Kartgränssnitt inklusive NavigableMap , SortedMap och utökar klassen AbstractMap.
- TreeMap i Java tillåter inte null-nycklar (som Map) och därför kastas ett NullPointerException. Däremot kan flera nollvärden associeras med olika nycklar.
- Ingångspar som returneras av metoderna i den här klassen och dess vyer representerar ögonblicksbilder av mappningar vid den tidpunkt då de producerades. De stöder inte metoden Entry.setValue.
Låt oss nu gå vidare och diskutera Synchronized TreeMap. Implementeringen av en TreeMap är inte synkroniserad. Detta betyder att om flera trådar får åtkomst till en träduppsättning samtidigt, och minst en av trådarna modifierar uppsättningen, måste den synkroniseras externt. Detta görs vanligtvis genom att använda metoden Collections.synchronizedSortedMap. Detta görs bäst vid skapandet, för att förhindra osynkroniserad åtkomst till setet. Detta kan göras som:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Nördar, nu måste ni undra hur fungerar TreeMap internt?
Metoderna i en TreeMap, samtidigt som man får nyckeluppsättning och värden, returnerar en Iterator som är felsnabb till sin natur. Således kommer varje samtidig modifiering att kasta ConcurrentModificationException . En TreeMap är baserad på en röd-svart träddatastruktur.
Varje nod i trädet har:
- 3 variabler ( K-nyckel=Nyckel, V-värde=Värde, boolesk färg=Färg )
- 3 referenser ( Entry left = Left, Entry right = Right, Entry parent = Parent )
Konstruktörer i TreeMap
För att skapa en TreeMap måste vi skapa ett objekt av klassen TreeMap. TreeMap-klassen består av olika konstruktörer som möjliggör skapandet av TreeMap. Följande är de konstruktörer som finns tillgängliga i den här klassen:
- TreeMap()
- TreeMap(Comparator comp)
- Trädkarta (karta M)
- TreeMap(Sorterad karta sm)
Låt oss diskutera dem individuellt tillsammans med att implementera varje konstruktör enligt följande:
Konstruktör 1: TreeMap()
Denna konstruktor används för att bygga en tom trädkarta som kommer att sorteras med hjälp av den naturliga ordningen för dess nycklar.
Exempel
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)
Denna konstruktor används för att bygga ett tomt TreeMap-objekt där elementen behöver en extern specifikation av sorteringsordningen.
Exempel
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ädkarta (karta M)
Denna konstruktor används för att initiera en TreeMap med posterna från den givna kartan M som kommer att sorteras med hjälp av nycklarnas naturliga ordning.
Exempel
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(Sorterad karta sm)
Denna konstruktor används för att initiera en TreeMap med posterna från den givna sorterade kartan som kommer att lagras i samma ordning som den givna sorterade kartan.
Exempel
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 klassen TreeMap
| Metod | Åtgärd utförd |
|---|---|
| klar() | Metoden tar bort alla mappningar från denna TreeMap och rensar kartan. |
| klona() | Metoden returnerar en ytlig kopia av denna TreeMap. |
| containsKey(Objektnyckel) | Returnerar sant om denna karta innehåller en mappning för den angivna nyckeln. |
| innehållerValue(Objektvärde) | Returnerar sant om denna karta mappar en eller flera nycklar till det angivna värdet. |
| entrySet() | Returnerar en uppsättningsvy av mappningarna som finns i denna karta. |
| firstKey() | Returnerar den första (lägsta) nyckeln för närvarande i den här sorterade kartan. |
| get (objektnyckel) | Returnerar värdet som denna karta mappar den angivna nyckeln till. |
| headMap(Objektnyckelvärde) | Metoden returnerar en vy av den del av kartan som är strikt mindre än parametern nyckelvärde. |
| keySet() | Metoden returnerar en Set-vy av nycklarna som finns i trädkartan. |
| lastKey() | Returnerar den sista (högsta) nyckeln för närvarande i den här sorterade kartan. |
| put(Objektnyckel, Objektvärde) | Metoden används för att infoga en mappning i en karta. |
| putAll(Map map) | Kopierar alla mappningar från den angivna kartan till den här kartan. |
| ta bort (objektnyckel) | Tar bort mappningen för denna nyckel från denna TreeMap om den finns. |
| storlek() | Returnerar antalet nyckel-värde-mappningar i den här kartan. |
| subMap((K startKey, K endKey) | Metoden returnerar den del av denna karta vars nycklar sträcker sig från startKey, inklusive, till endKey, exklusiv. |
| värden() | Returnerar en samlingsvy av värdena som finns i denna karta. |
Genomförande: Följande program nedan kommer att visa bättre hur man skapar, infogar och går igenom TreeMap.
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> Utföra olika operationer på TreeMap
Efter introduktionen av Generics i Java 1.5 är det möjligt att begränsa vilken typ av objekt som kan lagras i TreeMap. Låt oss nu se hur man utför några ofta använda operationer på TreeMap.
Operation 1: Lägga till element
För att lägga till ett element till TreeMap kan vi använda put()-metoden . Insättningsordningen behålls dock inte i TreeMap. Internt, för varje element, jämförs nycklarna och sorteras i stigande ordning.
Exempel
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: Ändra element
Efter att ha lagt till elementen om vi vill ändra elementet, kan det göras genom att återigen lägga till elementet med put()-metoden . Eftersom elementen i trädkartan indexeras med hjälp av nycklarna, kan nyckelns värde ändras genom att helt enkelt infoga det uppdaterade värdet för nyckeln som vi vill ändra.
Exempel
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: Ta bort element
För att ta bort ett element från TreeMap kan vi använda metoden remove() . Denna metod tar nyckelvärdet och tar bort mappningen för nyckeln från denna trädkarta om den finns i kartan.
Exempel
Java
uppsåt uppsåt
// 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: Itererar genom trädkartan
Det finns flera sätt att iterera genom kartan. Det mest kända sättet är att använda en för varje slinga och hämta nycklarna. Nyckelns värde hittas genom att använda getValue() metod .
Exempel
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>
Fördelar med TreeMap:
- Sorterad ordning: TreeMap tillhandahåller en sorterad ordning av dess element, baserat på den naturliga ordningen för dess nycklar eller en anpassad komparator som skickas till konstruktorn. Detta gör det användbart i situationer där du behöver hämta element i en specifik ordning.
- Förutsägbar iterationsordning: Eftersom elementen i en TreeMap lagras i en sorterad ordning, kan du förutsäga i vilken ordning de kommer att returneras under iterationen, vilket gör det lättare att skriva algoritmer som bearbetar elementen i en specifik ordning.
- Sökprestanda: TreeMap ger en effektiv implementering av kartgränssnittet, vilket gör att du kan hämta element i logaritmisk tid, vilket gör den användbar i sökalgoritmer där du behöver hämta element snabbt.
- Självbalansering: Trädkartan implementeras med hjälp av ett röd-svart träd, som är en typ av självbalanserande binärt sökträd. Detta ger effektiv prestanda för att lägga till, ta bort och hämta element, samt bibehålla den sorterade ordningen för elementen.
Nackdelar med TreeMap:
- Långsamt för att infoga element: Att infoga element i en TreeMap kan vara långsammare än att infoga element i en vanlig karta, eftersom TreeMap behöver bibehålla den sorterade ordningen för dess element.
- Nyckelbegränsning: Nycklarna i en TreeMap måste implementera java.lang.Comparable-gränssnittet, eller så måste en anpassad Comparator tillhandahållas. Detta kan vara en begränsning om du behöver använda anpassade nycklar som inte implementerar detta gränssnitt.
Uppslagsverk:
Java-samlingar av Maurice Naftalin och Philip Wadler. Den här boken ger en omfattande översikt över Java Collections-ramverket, inklusive TreeMap.
Java i ett nötskal av David Flanagan. Den här boken ger en snabbreferens för Javas kärnfunktioner, inklusive TreeMap.
Java Generics and Collections av Maurice Naftalin och Philip Wadler. Den här boken ger en omfattande guide till generika och samlingar i Java, inklusive TreeMap.