Le TreeMap en Java est utilisé pour implémenter Interface cartographique et NavigableMap avec la classe AbstractMap. La carte est triée selon l'ordre naturel de ses clés, ou par un Comparateur fourni au moment de la création de la carte, en fonction du constructeur utilisé. Cela s'avère être un moyen efficace de trier et de stocker les paires clé-valeur. L'ordre de stockage maintenu par le treemap doit être cohérent avec les égaux, comme n'importe quelle autre carte triée, quels que soient les comparateurs explicites. L'implémentation du treemap n'est pas synchronisée dans le sens où si une carte est accédée par plusieurs threads, simultanément et qu'au moins un des threads modifie structurellement la carte, elle doit être synchronisée en externe.
Le TreeMap en Java est une implémentation concrète de l'interface java.util.SortedMap. Il fournit une collection ordonnée de paires clé-valeur, où les clés sont classées en fonction de leur ordre naturel ou d'un comparateur personnalisé transmis au constructeur.
Un TreeMap est implémenté à l'aide d'un arbre rouge-noir, qui est un type d'arbre de recherche binaire auto-équilibré. Cela offre des performances efficaces pour les opérations courantes telles que l’ajout, la suppression et la récupération d’éléments, avec une complexité temporelle moyenne de O(log n).
Voici un exemple d’utilisation de la classe 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));> >}> >}> }> |
>
>Sortir
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Caractéristiques d'un TreeMap
Certaines fonctionnalités importantes du treemap sont les suivantes :
- Cette classe est membre du Collections Java Cadre.
- La classe implémente Interfaces cartographiques y compris NavigableMap , SortedMap et étend la classe AbstractMap.
- TreeMap en Java n'autorise pas les clés nulles (comme Map) et donc une NullPointerException est levée. Cependant, plusieurs valeurs nulles peuvent être associées à différentes clés.
- Les paires d'entrées renvoyées par les méthodes de cette classe et ses vues représentent des instantanés des mappages au moment où ils ont été produits. Ils ne prennent pas en charge la méthode Entry.setValue.
Maintenant, allons de l'avant et discutons de Synchronized TreeMap. L'implémentation d'un TreeMap n'est pas synchronisée. Cela signifie que si plusieurs threads accèdent simultanément à un ensemble d’arborescences et qu’au moins un des threads modifie l’ensemble, il doit être synchronisé en externe. Ceci est généralement réalisé à l’aide de la méthode Collections.synchronizedSortedMap. Il est préférable de le faire au moment de la création, afin d'éviter tout accès accidentel et non synchronisé à l'ensemble. Cela peut être fait comme :
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Geeks, maintenant vous devez vous demander comment fonctionne le TreeMap en interne ?
Les méthodes d'un TreeMap, tout en obtenant le jeu de clés et les valeurs, renvoient un itérateur de nature à échec rapide. Ainsi, toute modification simultanée lancera ConcurrentModificationException . Un TreeMap est basé sur une structure de données arborescente rouge-noir.
Chaque nœud de l'arborescence possède :
- 3 variables ( Touche K = Clé, valeur V = Valeur, couleur booléenne = Couleur )
- 3 références ( Entrée gauche = Gauche, Entrée droite = Droite, Entrée parent = Parent )
Constructeurs dans TreeMap
Afin de créer un TreeMap, nous devons créer un objet de la classe TreeMap. La classe TreeMap se compose de différents constructeurs qui permettent la création éventuelle du TreeMap. Voici les constructeurs disponibles dans cette classe :
- ArbreMap()
- TreeMap (composition de comparaison)
- ArbreMap(Carte M)
- TreeMap (Map triée sm)
Discutons-en individuellement tout en implémentant chaque constructeur comme suit :
Constructeur 1 : ArbreMap()
Ce constructeur est utilisé pour construire un treemap vide qui sera trié en utilisant l'ordre naturel de ses clés.
Exemple
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();> >}> }> |
>
>Sortir
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Constructeur 2 : TreeMap (composition de comparaison)
Ce constructeur est utilisé pour construire un objet TreeMap vide dans lequel les éléments auront besoin d'une spécification externe de l'ordre de tri.
Exemple
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();> >}> }> |
>
>Sortir
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Constructeur 3 : ArbreMap(Carte M)
Ce constructeur est utilisé pour initialiser un TreeMap avec les entrées de la carte M donnée qui seront triées en utilisant l'ordre naturel des clés.
Exemple
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();> >}> }> |
>
>Sortir
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Constructeur 4 : TreeMap (Map triée sm)
Ce constructeur est utilisé pour initialiser un TreeMap avec les entrées de la carte triée donnée qui seront stockées dans le même ordre que la carte triée donnée.
Exemple
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();> >}> }> |
>
>Sortir
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Méthodes de la classe TreeMap
| Méthode | Action effectuée |
|---|---|
| clair() | La méthode supprime tous les mappages de ce TreeMap et efface la carte. |
| cloner() | La méthode renvoie une copie superficielle de ce TreeMap. |
| contientClé (clé d'objet) | Renvoie vrai si cette carte contient un mappage pour la clé spécifiée. |
| contientValeur(Valeur de l'objet) | Renvoie vrai si cette carte mappe une ou plusieurs clés à la valeur spécifiée. |
| jeu d'entrées() | Renvoie une vue définie des mappages contenus dans cette carte. |
| premièreClé() | Renvoie la première clé (la plus basse) actuellement dans cette carte triée. |
| obtenir (clé d'objet) | Renvoie la valeur à laquelle cette carte mappe la clé spécifiée. |
| headMap (objet clé_valeur) | La méthode renvoie une vue de la partie de la carte strictement inférieure au paramètre key_value. |
| jeu de clés() | La méthode renvoie une vue Set des clés contenues dans le treemap. |
| dernièreClé() | Renvoie la dernière clé (la plus élevée) actuellement dans cette carte triée. |
| put (clé d'objet, valeur d'objet) | La méthode est utilisée pour insérer un mappage dans une carte. |
| putAll (Carte carte) | Copie tous les mappages de la carte spécifiée vers cette carte. |
| supprimer (clé d'objet) | Supprime le mappage de cette clé de ce TreeMap s'il est présent. |
| taille() | Renvoie le nombre de mappages clé-valeur dans cette carte. |
| sous-carte ((K startKey, K endKey) | La méthode renvoie la partie de cette carte dont les clés vont de startKey, inclus, à endKey, exclusif. |
| valeurs() | Renvoie une vue de collection des valeurs contenues dans cette carte. |
Mise en œuvre: Les programmes suivants ci-dessous montreront mieux comment créer, insérer et parcourir 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();> >}> }> |
>
>Sortir
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> Effectuer diverses opérations sur TreeMap
Après l'introduction des génériques dans Java 1.5, il est possible de restreindre le type d'objet pouvant être stocké dans le TreeMap. Voyons maintenant comment effectuer quelques opérations fréquemment utilisées sur le TreeMap.
Opération 1 : Ajout d'éléments
Afin d'ajouter un élément au TreeMap, nous pouvons utiliser la méthode put() . Cependant, l'ordre d'insertion n'est pas conservé dans le TreeMap. En interne, pour chaque élément, les clés sont comparées et triées par ordre croissant.
Exemple
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);> >}> }> |
>
>Sortir
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Opération 2 : Changer les éléments
Après avoir ajouté les éléments, si nous souhaitons modifier l'élément, cela peut être fait en ajoutant à nouveau l'élément avec la méthode put(). Étant donné que les éléments du treemap sont indexés à l'aide des clés, la valeur de la clé peut être modifiée en insérant simplement la valeur mise à jour pour la clé pour laquelle nous souhaitons modifier.
Exemple
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);> >}> }> |
>
>Sortir
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Opération 3 : Suppression d'un élément
Afin de supprimer un élément du TreeMap, nous pouvons utiliser la méthode remove() . Cette méthode prend la valeur de la clé et supprime le mappage de la clé de ce treemap si elle est présente dans la carte.
Exemple
Java
burak ozcivit
// 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);> >}> }> |
>
>Sortir
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Opération 4 : Itérer dans le TreeMap
Il existe plusieurs façons de parcourir la carte. La méthode la plus connue consiste à utiliser un pour chaque boucle et récupérez les clés. La valeur de la clé est trouvée en utilisant le Méthode getValue() .
Exemple
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);> >}> >}> }> |
>
>Sortir
1 : Geeks 2 : For 3 : Geeks>
Avantages de TreeMap :
- Ordre trié : le TreeMap fournit un ordre trié de ses éléments, basé sur l'ordre naturel de ses clés ou un comparateur personnalisé transmis au constructeur. Cela le rend utile dans les situations où vous devez récupérer des éléments dans un ordre spécifique.
- Ordre d'itération prévisible : étant donné que les éléments d'un TreeMap sont stockés dans un ordre trié, vous pouvez prédire l'ordre dans lequel ils seront renvoyés au cours de l'itération, ce qui facilite l'écriture d'algorithmes qui traitent les éléments dans un ordre spécifique.
- Performances de recherche : TreeMap fournit une implémentation efficace de l'interface Map, vous permettant de récupérer des éléments en temps logarithmique, ce qui le rend utile dans les algorithmes de recherche où vous devez récupérer rapidement des éléments.
- Auto-équilibrage : Le TreeMap est implémenté à l’aide d’un arbre rouge-noir, qui est un type d’arbre de recherche binaire auto-équilibré. Cela offre des performances efficaces pour l’ajout, la suppression et la récupération d’éléments, ainsi que pour le maintien de l’ordre de tri des éléments.
Inconvénients de TreeMap :
- Lente pour l'insertion d'éléments : l'insertion d'éléments dans un TreeMap peut être plus lente que l'insertion d'éléments dans une Map classique, car le TreeMap doit conserver l'ordre de tri de ses éléments.
- Restriction de clé : les clés d'un TreeMap doivent implémenter l'interface java.lang.Comparable, ou un comparateur personnalisé doit être fourni. Cela peut constituer une restriction si vous devez utiliser des clés personnalisées qui n'implémentent pas cette interface.
Livres de référence:
Collections Java de Maurice Naftalin et Philip Wadler. Ce livre fournit une présentation complète du framework Java Collections, y compris TreeMap.
Java en bref par David Flanagan. Ce livre fournit une référence rapide sur les fonctionnalités principales de Java, y compris TreeMap.
Génériques et collections Java par Maurice Naftalin et Philip Wadler. Ce livre fournit un guide complet des génériques et des collections en Java, y compris TreeMap.