Fonctionnalités de TreeMap en Java

Si vous lisez cet article, il y a de fortes chances que vous connaissiez l' interface Map et ses utilisations. Sinon, c'est parti. Aujourd'hui, nous allons parler des fonctionnalités d'implémentation de TreeMap, et plus précisément, en quoi il diffère de HashMap et comment l'utiliser correctement.

Comparaison de TreeMap, HashMap et LinkedHashMap

L'implémentation la plus couramment utilisée de l' interface Map est HashMap . Il est facile à utiliser et garantit un accès rapide aux données, ce qui en fait le meilleur candidat pour la plupart des tâches. La plupart, mais pas tous. Parfois, il est nécessaire de stocker les données sous une forme structurée avec la possibilité de les parcourir. Dans ce cas, une autre implémentation de l' interface Map vient à la rescousse - TreeMap . TreeMap implémente l' interface NavigableMap , qui hérite de SortedMap , qui à son tour hérite de l' interface Map . En implémentant les interfaces NavigableMap et SortedMap , TreeMap bénéficie de fonctionnalités supplémentaires que HashMap n'offre pas , mais cela a un prix en termes de performances. Il existe également une classe LinkedHashMap , qui vous permet également de stocker les données dans un certain ordre - dans l'ordre dans lequel elles ont été ajoutées. Pour vous aider à comprendre les différences entre ces trois classes, consultez ce tableau : Comme vous pouvez le constater, ces cours ont de nombreux points communs, mais il existe également quelques différences. Bien que la classe TreeMapsoit la plus multifonctionnelle, elle ne peut pas toujours être stockée nullcomme clé. De plus, le temps d’accès aux éléments TreeMap sera le plus long. Par conséquent, si vous n'avez pas besoin de stocker les données sous forme triée, il est préférable d'utiliser HashMapou LinkedHashMap.

Ébène rouge

Comme vous l'avez probablement remarqué, il utilise sous le capot TreeMapune structure de données appelée arbre rouge-noir. C'est le stockage des données dans cette structure qui garantit l'ordre dans lequel les données sont stockées. Quel est cet arbre ? Voyons cela ! Imaginez que vous ayez besoin de stocker des paires Number-String. Les nombres 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 seront les clés. Si vous stockez des données dans une liste traditionnelle et que vous devez trouver un élément avec la clé 101, vous devrez parcourir les 13 éléments pour le trouver. Pour 13 éléments, ce n'est pas critique : lorsque nous travaillons avec un million, nous aurons de gros problèmes. Pour résoudre de tels problèmes, les programmeurs utilisent des structures de données légèrement plus complexes. Alors rencontrez l’arbre rouge-noir !

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

La recherche de l'élément requis commence à partir de la racine de l'arbre, dans notre cas il s'agit de 61. Ensuite, une comparaison est faite avec la valeur requise. Si notre valeur est inférieure, nous allons à gauche, si elle est supérieure, nous allons à droite. Cela se produit jusqu'à ce que nous trouvions la valeur requise ou que nous frappions un élément avec une valeur null(une feuille d'arbre). Les couleurs rouge et noire sont utilisées pour faciliter la navigation et l'équilibre de l'arbre. Il y a des règles qui doivent toujours être respectées lors de la construction d'un arbre rouge-noir :

• La racine doit être colorée en noir.
• Les feuilles de l'arbre doivent être noires.
• Un nœud rouge doit avoir deux nœuds enfants noirs.
• Un nœud noir peut avoir n’importe quel nœud enfant.
• Le chemin d'un nœud à ses feuilles doit contenir le même nombre de nœuds noirs.
• De nouveaux nœuds sont ajoutés à la place des feuilles.

Si vous regardez les règles 3, 4 et 5 ensemble, vous pouvez comprendre comment la coloration des nœuds accélère la navigation dans l'arborescence : le chemin passant par les nœuds noirs est toujours plus court que par les nœuds rouges. Par conséquent, la taille totale de l’arbre est déterminée par le nombre de nœuds noirs, et cette taille est appelée « hauteur noire ». L'arbre rouge-noir est implémenté dans différents langages de programmation. Il existe de nombreuses implémentations de Java sur Internet, nous ne nous y attarderons donc pas longtemps, mais nous continuerons à nous familiariser avec les fonctionnalités TreeMap.

Méthodes dérivées des interfaces SortedMap et NavigableMap

Par exemple HashMap, TreeMapil implémente l'interface Map, ce qui signifie qu'il TreeMappossède toutes les méthodes qui HashMap. Mais en plus, TreeMapil implémente des interfaces SortedMapet NavigableMap, en obtenant des fonctionnalités supplémentaires. SortedMap— une interface qui étend Mapet ajoute des méthodes pertinentes pour un ensemble de données triées :

• firstKey(): renvoie la clé du premier élément de la carte ;
• lastKey(): renvoie la clé du dernier élément ;
• headMap(K end): renvoie une carte qui contient tous les éléments de la carte actuelle, du début jusqu'à l'élément avec la clé end;
• tailMap(K start): renvoie une carte qui contient tous les éléments de la carte actuelle, en commençant par l'élément startet en terminant par la fin ;
• subMap(K start, K end): renvoie une carte qui contient tous les éléments de la carte actuelle, en commençant par l'élément startet en terminant par l'élément avec la clé end.

NavigableMap— une interface qui étend SortedMapet ajoute des méthodes de navigation entre les éléments de la carte :

• firstEntry(): renvoie la première paire clé-valeur ;
• lastEntry(): renvoie la dernière paire clé-valeur ;
• pollFirstEntry(): renvoie et supprime la première paire ;
• pollLastEntry(): renvoie et supprime la dernière paire ;
• ceilingKey(K obj): Renvoie la plus petite clé k supérieure ou égale à la clé obj. S'il n'existe pas de clé de ce type, renvoie null ;
• floorKey(K obj): Renvoie la plus grande clé k inférieure ou égale à la clé obj. S'il n'existe pas de clé de ce type, renvoie null ;
• lowerKey(K obj): Renvoie la plus grande clé k qui est plus petite que la clé obj. S'il n'existe pas de clé de ce type, renvoie null ;
• higherKey(K obj): Renvoie la plus petite clé k supérieure à la clé obj. S'il n'existe pas de clé de ce type, renvoie null ;
• ceilingEntry(K obj): similaire à la méthode plafondKey(K obj), mais renvoie une paire clé-valeur (ou null) ;
• floorEntry(K obj): similaire à la méthode floorKey(K obj), mais renvoie une paire clé-valeur (ou null) ;
• lowerEntry(K obj): similaire à la méthode lowerKey(K obj), mais renvoie une paire clé-valeur (ou null) ;
• higherEntry(K obj): similaire à la méthode upperKey(K obj), mais renvoie une paire clé-valeur (ou null) ;
• descendingKeySet(): renvoie un NavigableSet contenant toutes les clés triées dans l'ordre inverse ;
• descendingMap(): renvoie un NavigableMap contenant toutes les paires triées dans l'ordre inverse ;
• navigableKeySet(): renvoie un objet NavigableSet contenant toutes les clés dans l'ordre de stockage ;
• headMap(K upperBound, boolean incl): renvoie une carte qui contient des paires du début jusqu'à l'élément upperBound. L'argument incl spécifie si l'élément upperBound doit être inclus dans la carte renvoyée ;
• tailMap(K lowerBound, boolean incl): la fonctionnalité est similaire à la méthode précédente, seules les paires de lowerBound jusqu'à la fin sont renvoyées ;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Comme dans les méthodes précédentes, les paires de lowerBound à upperBound sont renvoyées, les arguments lowIncl et highIncl indiquant s'il faut inclure les éléments de limite dans la nouvelle carte.

Dans l'implémentation elle-même TreeMap, en plus des constructeurs que nous connaissons, un autre est ajouté, qui accepte une instance du comparateur. Ce comparateur sera responsable de l'ordre dans lequel les éléments sont stockés.

Exemples d'utilisation de TreeMap

Une telle abondance de méthodes supplémentaires peut sembler inutile, mais très souvent elles s'avèrent bien plus utiles qu'il n'y paraissait initialement. Regardons cet exemple avec vous. Imaginez que nous travaillions dans le service marketing d'une grande entreprise et que nous disposions d'une base de données de personnes à qui nous souhaitons montrer de la publicité. Il y a deux nuances à cela :

• nous devons garder une trace du nombre d'impressions pour chaque personne ;
• L'algorithme d'affichage de la publicité auprès des mineurs est différent.

Créons une classe Personqui stockera toutes les informations dont nous disposons sur une personne :

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

Nous implémentons la logique dans la classe Main:

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map){}
   public static void showAdvertisementToAdult(Map map){}
}

Dans la classe Mainque nous créons TreeMap, où keyse trouve une personne spécifique et valuele nombre d'impressions publicitaires ce mois-ci. Dans le constructeur, nous passons par un comparateur qui triera les personnes par âge. Remplissez avec mapdes valeurs aléatoires. Nous devons maintenant obtenir une référence au premier adulte de notre mini magasin de données. Nous faisons cela en utilisant l'API Stream. Après cela, nous obtenons deux cartes indépendantes que nous transmettons aux méthodes qui affichent de la publicité. Il existe de très nombreuses façons de résoudre ce problème. L'arsenal de méthodes du cours TreeMappermet d'inventer des solutions pour tous les goûts. Il n'est pas nécessaire de tous les mémoriser, car vous pouvez toujours utiliser la documentation ou les astuces de l'environnement de développement. C'est tout! J'espère que le cours est maintenant TreeMapclair pour vous et que vous y trouverez une application précise pour résoudre des problèmes pratiques.