TreeMap en Java

Si vous lisez cet article, vous êtes probablement familiarisé avec l'interface de la carte et où elle peut être appliquée de manière appropriée. Si non, alors viens ici . Aujourd'hui, nous allons parler des fonctionnalités de l'implémentation de Java TreeMap, et plus précisément de la façon dont il diffère de HashMap et comment l'utiliser correctement.

Comparaison de TreeMap, HashMap et LinkedHashMap

L'implémentation la plus utilisée de l'interface Map est HashMap. Il est facile à utiliser et garantit un accès rapide aux données, c'est donc le meilleur candidat pour résoudre la plupart des problèmes. La plupart, mais pas tous. Parfois, vous avez besoin de stocker des données de manière structurée et de pouvoir les parcourir. Dans ce cas, une autre implémentation de l'interface Map (TreeMap) vient à la rescousse. 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 reçoit des fonctionnalités supplémentaires qui ne sont pas disponibles dans HashMap, mais cela paie un prix en termes de performances. Il y a aussi le LinkedHashMapclass , qui vous permet également de stocker des données dans un ordre spécifique (l'ordre dans lequel vous les ajoutez à la carte). Pour comprendre les différences entre ces trois classes, regardez ce tableau : Comme vous pouvez le voir, ces classes ont beaucoup en commun, mais il y a aussi plusieurs différences. Bien que la classe TreeMap soit la plus polyvalente, elle ne peut pas toujours stocker null en tant que clé. De plus, l'accès aux éléments d'un TreeMap prend le plus de temps. Donc, si vous n'avez pas besoin de stocker les données dans un ordre trié, il est préférable d'utiliser HashMap ou LinkedHashMap .

Arbre rouge-noir

Vous avez probablement remarqué que, sous le capot, TreeMap utilise une structure de données appelée arbre rouge-noir. Le stockage des données dans cette structure est précisément ce qui fournit l'ordre des données. Alors, quel genre d'arbre est-ce? Découvrons-le ! 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 et ​​101 seront des clés. Si vous stockez des données dans une liste traditionnelle et que vous devez trouver l'élément avec la clé 101, vous devrez parcourir les 13 éléments pour le trouver. Pour 13 éléments, ce n'est pas grave, mais quand on travaille avec un million, on va avoir de gros problèmes. Pour résoudre ces problèmes, les programmeurs utilisent des structures de données légèrement plus complexes. C'est là que l'arbre rouge-noir entre en scène !La recherche d'un élément commence à la racine de l'arbre, qui dans notre cas est 61. Ensuite, nous comparons les valeurs des nœuds avec la valeur que nous recherchons. Si notre valeur est inférieure, alors nous allons vers la gauche ; s'il est plus grand, alors nous allons vers la droite. Ce processus se répète jusqu'à ce que nous trouvions la valeur souhaitée ou rencontrions un élément dont la valeur est nulle (une feuille de l'arbre). Les couleurs rouge et noir sont utilisées pour simplifier la navigation et l'équilibrage 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 noire.
• 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 des nœuds enfants de n'importe quelle couleur.
• Un chemin d'un nœud à ses feuilles doit contenir le même nombre de nœuds noirs.
• De nouveaux nœuds sont ajoutés aux feuilles.

Si vous considérez les règles 3, 4 et 5 ensemble, vous pouvez comprendre comment la couleur des nœuds nous permet de naviguer plus rapidement dans l'arbre : un chemin passant par des nœuds noirs est toujours plus court qu'un chemin passant par des nœuds rouges. En conséquence, la taille totale de l'arbre est déterminée par le nombre de nœuds noirs, appelé "hauteur noire". La structure de données arborescente rouge-noire est implémentée dans divers langages de programmation. Il existe de nombreuses implémentations Java sur Internet, nous ne nous attarderons donc pas ici. Au lieu de cela, continuons à connaître les fonctionnalités de TreeMap.

Méthodes issues des interfaces SortedMap et NavigableMap

Comme HashMap, TreeMap implémente l'interface Map, ce qui signifie que TreeMap possède toutes les méthodes qui existent dans HashMap. Mais TreeMap implémente également les interfaces SortedMap et NavigableMap , et en tire ainsi des fonctionnalités supplémentaires. SortedMap est une interface qui étend Map et ajoute des méthodes pertinentes à 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) : retourne une carte qui contient tous les éléments de la carte courante, du début à l'élément avec la clé end
• tailMap(K start) : retourne une carte qui contient tous les éléments de la carte courante, de l'élément de début à la fin
• subMap(K start, K ​​end) : retourne une carte qui contient tous les éléments de la carte courante, de l'élément start à l'élément avec la clé end.

NavigableMap est une interface qui étend SortedMap et ajoute des méthodes pour naviguer entre les éléments d'une 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'y a pas une telle clé, retourne null
• floorKey(K obj) : renvoie la plus grande clé k inférieure ou égale à la clé obj. S'il n'y a pas une telle clé, retourne null
• lowerKey(K obj) : renvoie la plus grande clé k qui est inférieure à la clé obj. S'il n'y a pas une telle clé, retourne null
• upperKey(K obj) : retourne la plus petite clé k qui est plus grande que la clé obj. S'il n'y a pas une telle clé, retourne null
• ceilingEntry(K obj) : similaire à la méthode ceilingKey(K obj), ne renvoie qu'une paire clé-valeur (ou null)
• floorEntry(K obj) : similaire à la méthode floorKey(K obj), ne retourne qu'une paire clé-valeur (ou null)
• lowerEntry(K obj) : similaire à la méthode lowerKey(K obj), ne renvoie qu'une paire clé-valeur (ou null)
• upperEntry(K obj) : similaire à la méthode upperKey(K obj), ne renvoie qu'une paire clé-valeur (ou null)
• descendantKeySet() : renvoie un NavigableSet contenant toutes les clés triées dans l'ordre inverse
• descendantMap() : renvoie une NavigableMap contenant toutes les paires triées dans l'ordre inverse
• navigableKeySet() : renvoie un objet NavigableSet contenant toutes les clés dans l'ordre dans lequel elles sont stockées
• headMap(K upperBound, boolean incl) : renvoie une carte contenant des paires du début à l'élément upperBound. Le paramètre incl indique s'il faut inclure l'élément upperBound dans la carte renvoyée
• tailMap(K lowerBound, boolean incl) : fonctionnalité similaire à la méthode précédente, renvoie uniquement les paires de lowerBound à la fin
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl) : comme pour les méthodes précédentes, renvoie les paires de lowerBound à upperBound ; les arguments lowIncl et highIncl indiquent s'il faut inclure les éléments de frontière dans la nouvelle carte.

En plus des constructeurs habituels, TreeMap a un autre constructeur qui accepte une instance d'un comparateur. Ce comparateur est responsable de l'ordre dans lequel les éléments sont stockés.

Exemples de TreeMap

Cette abondance de méthodes supplémentaires peut sembler inutile, mais elles s'avèrent beaucoup plus utiles que vous ne le pensez à première vue. Explorons ensemble l'exemple suivant. Imaginons 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 des publicités. Il y a deux détails à garder à l'esprit :

• Nous devons garder une trace du nombre d'impressions pour chaque personne
• L'algorithme d'affichage des publicités aux mineurs est différent.

Créons une classe Person , qui stockera toutes les informations pertinentes sur chaque 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("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 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 Main, créez un TreeMap, dans lequel chaque clé représente une personne spécifique, et chaque valeur est le nombre d'impressions d'annonces ce mois-ci. On passe au constructeur un comparateur qui trie les gens par âge. Nous remplissons la carte avec des valeurs arbitraires. Maintenant, nous voulons obtenir une référence au premier adulte dans notre petit référentiel de données. Nous faisons cela en utilisant l'API Stream. Ensuite, nous obtenons deux cartes distinctes, que nous transmettons aux méthodes qui affichent des publicités. Nous aurions pu accomplir cette tâche de très nombreuses façons. L'arsenal de méthodes de la classe TreeMap nous permet de créer des solutions personnalisées pour chaque besoin. Vous n'avez pas besoin de tous les mémoriser, car vous pouvez toujours utiliser la documentation ou les astuces de votre IDE. Pour renforcer ce que vous avez appris, nous vous suggérons de regarder une leçon vidéo de notre cours Java

C'est tout pour le moment! J'espère que la classe TreeMap est claire pour vous maintenant et que vous l'appliquerez correctement pour résoudre des tâches de codage pratiques.