Le fonctionnement interne de TreeMap en Java

TreeMap est une classe de Java Collection Framework qui implémente l'interface NavigableMap. Elle stocke les éléments de la carte dans une structure arborescente et fournit une alternative efficace pour stocker les paires clé-valeur dans un ordre trié. En interne, TreeMap utilise une arborescence rouge-noir. , qui est un arbre de recherche binaire auto-équilibré. Un TreeMap doit implémenter l'interface Comparable ou un comparateur personnalisé afin de pouvoir maintenir l'ordre de tri de ses éléments, sinon nous rencontrerons une exception java.lang.ClassCastException. comment TreeMap fonctionne en interne dans Java.

Le fonctionnement interne de TreeMap en Java

Pour comprendre le fonctionnement interne de TreeMap, il est nécessaire d'avoir une vue d'ensemble de l'algorithme de l'arbre rouge-noir, car TreeMap l'utilise pour stocker des éléments.

Relation entre l'arbre rouge noir et TreeMap

Un arbre rouge-noir est un arbre de recherche binaire auto-équilibré avec les propriétés suivantes :

• Chaque nœud contient un bit supplémentaire, représenté en rouge ou en noir. Ces couleurs sont utilisées pour garantir que l'arbre reste équilibré.

• La couleur du nœud racine est toujours noire.

• Un nœud rouge ne peut pas avoir un autre nœud de la même couleur que son voisin

• Du nœud racine au nœud vide, le nombre de nœuds noirs sur tous les chemins doit être le même

Voyons maintenant la structure de TreeMap :

Si nous ajoutons un élément au TreeMap, il ajoutera la première entrée en premier lieu, à partir du deuxième élément, il vérifiera si la clé de l'entrée actuelle est supérieure ou inférieure à l'entrée précédente. seront ajoutés à gauche et ceux avec la plus grande valeur seront ajoutés à droite de l’entrée Parent.

Constructeur de TreeMap

Pour utiliser la collection TreeMap dans notre programme, nous devons d'abord créer une instance de la classe TreeMap. Pour cela, Java fournit les constructeurs suivants :

• TreeMap() : cela créera une collection TreeMap vide

• TreeMap(Map mapInstance) : Nous pouvons créer une arborescence en utilisant les entrées d'une autre carte

• TreeMap(Comparator comparatorInstance) : Il nous permet de créer une carte arborescente vide, triée à l'aide d'un comparateur.

• TreeMap(SortedMap sortedmapInstance) : Nous pouvons également créer une arborescence avec les entrées d'une carte triée.

Discutons de quelques exemples pour mieux comprendre les points discutés ci-dessus.

Exemple

Dans l'exemple suivant, nous allons créer un TreeMap vide, puis y stocker certains éléments à l'aide de la méthode 'put()'. Nous imprimerons ses détails en utilisant la boucle for-each. Les résultats seront affichés par ordre trié.

import java.util.*;
public class Example1 {
   public static void main(String[] args) {
      // creating a TreeMap
      TreeMap<String, Integer> TrMap = new TreeMap<>();
      // Adding elements in the map
      TrMap.put("Kurti", 4000);
      TrMap.put("Shirt", 3000);
      TrMap.put("TShirt", 1500);
      TrMap.put("Watch", 2000);
      TrMap.put("Perfume", 2500);
      // printing the details of map 
      System.out.println("Elements of the map: ");
      // iterating through the map
      for (String unKey : TrMap.keySet()) {
         // printing details of each node
         System.out.println("Item: " + unKey + ", Price: " + 
TrMap.get(unKey));
      }
      String frstKey = TrMap.firstKey(); // accessing first key
      String lstKey = TrMap.lastKey(); // accessing last key
      System.out.println("Accessing name of first key in Map: " + 
frstKey);
      System.out.println("Accessing name of last key in Map: " + 
lstKey);
   }
}

Sortie

Elements of the map: 
Item: Kurti, Price: 4000
Item: Perfume, Price: 2500
Item: Shirt, Price: 3000
Item: TShirt, Price: 1500
Item: Watch, Price: 2000
Accessing name of first key in Map: Kurti
Accessing name of last key in Map: Watch

Conclusion

Nous avons commencé cet article en définissant un TreeMap et avons discuté de son fonctionnement interne dans la section suivante. TreeMap utilise un arbre rouge-noir pour stocker ses éléments, qui est un arbre de recherche binaire auto-équilibré. De plus, nous avons également discuté d'un exemple pour illustrer le fonctionnement de TreeMap.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!