Voor de implementatie wordt de TreeMap in Java gebruikt Kaartinterface en NavigableMap samen met de AbstractMap-klasse. De kaart is gesorteerd op basis van de natuurlijke volgorde van de sleutels, of op basis van a Comparator verstrekt tijdens het maken van de kaart, afhankelijk van welke constructor wordt gebruikt. Dit blijkt een efficiënte manier te zijn om de sleutel-waardeparen te sorteren en op te slaan. De opslagvolgorde die door de boomkaart wordt aangehouden, moet consistent zijn met gelijken, net als elke andere gesorteerde kaart, ongeacht de expliciete vergelijkers. De implementatie van de treemap is niet gesynchroniseerd in de zin dat als een kaart tegelijkertijd door meerdere threads wordt benaderd en ten minste één van de threads de kaart structureel wijzigt, deze extern moet worden gesynchroniseerd.
De TreeMap in Java is een concrete implementatie van de java.util.SortedMap-interface. Het biedt een geordende verzameling sleutel-waardeparen, waarbij de sleutels worden geordend op basis van hun natuurlijke volgorde of een aangepaste comparator die aan de constructor wordt doorgegeven.
Een TreeMap wordt geïmplementeerd met behulp van een rood-zwarte boom, een soort zelfbalancerende binaire zoekboom. Dit biedt efficiënte prestaties voor algemene bewerkingen zoals het toevoegen, verwijderen en ophalen van elementen, met een gemiddelde tijdscomplexiteit van O(log n).
Hier is een voorbeeld van hoe u de TreeMap-klasse gebruikt:
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));> >}> >}> }> |
>
>Uitvoer
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Kenmerken van een Boomkaart
Enkele belangrijke kenmerken van de boomkaart zijn als volgt:
- Deze klasse is lid van de Java-collecties Kader.
- De klas implementeert Kaartinterfaces inclusief NavigableMap , SortedMap en breidt de AbstractMap-klasse uit.
- TreeMap in Java staat geen nulsleutels toe (zoals Map) en daarom wordt er een NullPointerException gegenereerd. Er kunnen echter meerdere nulwaarden aan verschillende sleutels worden gekoppeld.
- Ingangsparen die door de methoden in deze klasse en de views ervan worden geretourneerd, vertegenwoordigen momentopnamen van toewijzingen op het moment dat ze werden geproduceerd. Ze ondersteunen de Entry.setValue-methode niet.
Laten we nu verder gaan en Synchronized TreeMap bespreken. De implementatie van een TreeMap is niet gesynchroniseerd. Dit betekent dat als meerdere threads tegelijkertijd toegang hebben tot een boomset en ten minste één van de threads de set wijzigt, deze extern moet worden gesynchroniseerd. Dit wordt doorgaans bereikt met behulp van de Collections.synchronizedSortedMap-methode. Dit kunt u het beste doen tijdens het maken van de set, om onbedoelde, niet-gesynchroniseerde toegang tot de set te voorkomen. Dit kan gedaan worden als:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Geeks, nu vragen jullie je waarschijnlijk af hoe de TreeMap intern werkt?
De methoden in een TreeMap retourneren bij het ophalen van sleutelsets en waarden een Iterator die snel van aard is. Elke gelijktijdige wijziging zal dus ConcurrentModificationException genereren. Een TreeMap is gebaseerd op een rood-zwarte boomdatastructuur.
Elk knooppunt in de boom heeft:
- 3 variabelen ( K-toets=Sleutel, V-waarde=Waarde, Booleaanse kleur=Kleur )
- 3 Referenties ( Ingang links = Links, Ingang rechts = Rechts, Ingang ouder = Ouder )
Constructeurs in TreeMap
Om een TreeMap te maken, moeten we een object van de TreeMap-klasse maken. De klasse TreeMap bestaat uit verschillende constructors die de mogelijke creatie van de TreeMap mogelijk maken. De volgende constructors zijn beschikbaar in deze klasse:
- Boomkaart()
- TreeMap(vergelijkingsvergelijking)
- Boomkaart (kaart M)
- Boomkaart(Gesorteerde kaart sm)
Laten we ze afzonderlijk bespreken, naast het implementeren van elke constructor, als volgt:
Constructeur 1: Boomkaart()
Deze constructor wordt gebruikt om een lege boomkaart te bouwen die wordt gesorteerd op basis van de natuurlijke volgorde van de sleutels.
Voorbeeld
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();> >}> }> |
>
>Uitvoer
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Constructeur 2: TreeMap (vergelijkingsvergelijking)
Deze constructor wordt gebruikt om een leeg TreeMap-object te bouwen waarin de elementen een externe specificatie van de sorteervolgorde nodig hebben.
Voorbeeld
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();> >}> }> |
>
>Uitvoer
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Constructeur 3: Boomkaart (kaart M)
Deze constructor wordt gebruikt om een TreeMap te initialiseren met de gegevens van de gegeven kaart M, die zal worden gesorteerd met behulp van de natuurlijke volgorde van de sleutels.
Voorbeeld
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();> >}> }> |
>
>Uitvoer
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Constructeur 4: Boomkaart(Gesorteerde kaart sm)
Deze constructor wordt gebruikt om een TreeMap te initialiseren met de gegevens van de gegeven gesorteerde kaart, die in dezelfde volgorde zullen worden opgeslagen als de gegeven gesorteerde kaart.
Voorbeeld
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();> >}> }> |
>
>Uitvoer
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Methoden in de TreeMap-klasse
| Methode | Actie uitgevoerd |
|---|---|
| duidelijk() | De methode verwijdert alle toewijzingen uit deze TreeMap en wist de kaart. |
| kloon() | De methode retourneert een ondiepe kopie van deze TreeMap. |
| bevatsleutel(Objectsleutel) | Retourneert waar als deze toewijzing een toewijzing voor de opgegeven sleutel bevat. |
| bevatWaarde(Objectwaarde) | Retourneert waar als deze kaart een of meer sleutels toewijst aan de opgegeven waarde. |
| entrySet() | Retourneert een vaste weergave van de toewijzingen op deze kaart. |
| eerstesleutel() | Retourneert de eerste (laagste) sleutel die momenteel in deze gesorteerde kaart staat. |
| get(Objectsleutel) | Retourneert de waarde waaraan deze kaart de opgegeven sleutel toewijst. |
| headMap(Objectsleutel_waarde) | De methode retourneert een weergave van het gedeelte van de kaart dat strikt kleiner is dan de parameter key_value. |
| sleutelbos() | De methode retourneert een Set-weergave van de sleutels in de boomstructuurkaart. |
| laatstesleutel() | Retourneert de laatste (hoogste) sleutel die momenteel in deze gesorteerde kaart staat. |
| put(Objectsleutel, Objectwaarde) | De methode wordt gebruikt om een mapping in een kaart in te voegen. |
| putAll(kaart) | Kopieert alle toewijzingen van de opgegeven kaart naar deze kaart. |
| verwijderen(Objectsleutel) | Verwijdert de toewijzing voor deze sleutel uit deze TreeMap, indien aanwezig. |
| maat() | Retourneert het aantal sleutel/waarde-toewijzingen in deze kaart. |
| subMap((K startsleutel, K eindsleutel) | De methode retourneert het gedeelte van deze kaart waarvan de sleutels variëren van startKey, inclusief, tot endKey, exclusief. |
| waarden() | Retourneert een verzamelingsweergave van de waarden in deze kaart. |
Implementatie: De volgende programma's hieronder laten beter zien hoe u de TreeMap kunt maken, invoegen en doorlopen.
Illustratie:
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();> >}> }> |
>
>Uitvoer
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> Verschillende bewerkingen uitvoeren op TreeMap
Na de introductie van Generics in Java 1.5 is het mogelijk om het type object dat in de TreeMap kan worden opgeslagen te beperken. Laten we nu eens kijken hoe we een paar veelgebruikte bewerkingen op de TreeMap kunnen uitvoeren.
Operatie 1: Elementen toevoegen
Om een element aan de TreeMap toe te voegen, kunnen we de put() methode gebruiken. De invoegopdracht blijft echter niet behouden in de TreeMap. Intern worden voor ieder element de sleutels vergeleken en oplopend gesorteerd.
Voorbeeld
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);> >}> }> |
>
>Uitvoer
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operatie 2: Elementen veranderen
Als we na het toevoegen van de elementen het element willen wijzigen, kan dit worden gedaan door het element opnieuw toe te voegen met de put() methode . Omdat de elementen in de boomkaart worden geïndexeerd met behulp van de sleutels, kan de waarde van de sleutel worden gewijzigd door eenvoudigweg de bijgewerkte waarde in te voegen voor de sleutel waarvoor we deze willen wijzigen.
Voorbeeld
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);> >}> }> |
>
>Uitvoer
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operatie 3: Element verwijderen
Om een element uit de TreeMap te verwijderen, kunnen we de remove() methode gebruiken. Deze methode neemt de sleutelwaarde en verwijdert de toewijzing voor de sleutel uit deze boomkaart als deze aanwezig is in de kaart.
Voorbeeld
Java
wat is winterslaap
// 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);> >}> }> |
>
>Uitvoer
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Operatie 4: Itereren door de TreeMap
Er zijn meerdere manieren om door de kaart te bladeren. De meest bekende manier is om een voor elke lus en de sleutels halen. De waarde van de sleutel wordt gevonden met behulp van de getValue()-methode .
Voorbeeld
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);> >}> >}> }> |
>
>Uitvoer
1 : Geeks 2 : For 3 : Geeks>
Voordelen van TreeMap:
- Gesorteerde volgorde: De TreeMap biedt een gesorteerde volgorde van de elementen, gebaseerd op de natuurlijke volgorde van de sleutels of een aangepaste comparator die aan de constructor wordt doorgegeven. Dit maakt het handig in situaties waarin u elementen in een specifieke volgorde moet ophalen.
- Voorspelbare iteratievolgorde: Omdat de elementen in een TreeMap in een gesorteerde volgorde worden opgeslagen, kunt u de volgorde voorspellen waarin ze tijdens de iteratie worden geretourneerd, waardoor het gemakkelijker wordt om algoritmen te schrijven die de elementen in een specifieke volgorde verwerken.
- Zoekprestaties: De TreeMap biedt een efficiënte implementatie van de kaartinterface, waardoor u elementen in logaritmische tijd kunt ophalen, waardoor het nuttig is in zoekalgoritmen waarbij u elementen snel moet ophalen.
- Zelfbalancerend: De TreeMap wordt geïmplementeerd met behulp van een rood-zwarte boom, een soort zelfbalancerende binaire zoekboom. Dit biedt efficiënte prestaties bij het toevoegen, verwijderen en ophalen van elementen, evenals het handhaven van de gesorteerde volgorde van de elementen.
Nadelen van TreeMap:
- Langzaam voor het invoegen van elementen: Het invoegen van elementen in een TreeMap kan langzamer zijn dan het invoegen van elementen in een gewone kaart, omdat de TreeMap de gesorteerde volgorde van zijn elementen moet behouden.
- Sleutelbeperking: De sleutels in een TreeMap moeten de interface java.lang.Comparable implementeren, anders moet er een aangepaste Comparator worden geleverd. Dit kan een beperking zijn als u aangepaste sleutels moet gebruiken die deze interface niet implementeren.
Naslagwerken:
Java-collecties van Maurice Naftalin en Philip Wadler. Dit boek biedt een uitgebreid overzicht van het Java Collections-framework, inclusief de TreeMap.
Java in een notendop door David Flanagan. Dit boek biedt een snel naslagwerk voor de kernfuncties van Java, inclusief de TreeMap.
Java-generieken en collecties door Maurice Naftalin en Philip Wadler. Dit boek biedt een uitgebreide gids voor generieke geneesmiddelen en collecties in Java, inclusief de TreeMap.