Un guide sur TreeMap en Java

1. Vue d'ensemble

Dans cet article, nous allons explorer l' implémentation TreeMap de l' interface Map de Java Collections Framework (JCF).

TreeMap est une implémentation de carte qui conserve ses entrées triées selon l'ordre naturel de ses clés ou mieux encore à l'aide d'un comparateur s'il est fourni par l'utilisateur au moment de la construction.

Auparavant, nous avons couvert les implémentations HashMap et LinkedHashMap et nous nous rendrons compte qu'il y a pas mal d'informations sur le fonctionnement de ces classes qui sont similaires.

Il est fortement recommandé de lire les articles mentionnés avant de poursuivre celui-ci.

2. Tri par défaut dans TreeMap

Par défaut, TreeMap trie toutes ses entrées selon leur ordre naturel. Pour un entier, cela signifierait l'ordre croissant et pour les chaînes, l'ordre alphabétique.

Voyons l'ordre naturel dans un test:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() { TreeMap map = new TreeMap(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString()); }

Notez que nous avons placé les clés entières de manière non ordonnée, mais lors de la récupération du jeu de clés, nous confirmons qu'elles sont bien conservées dans l'ordre croissant. Il s'agit de l'ordre naturel des entiers.

De même, lorsque nous utilisons des chaînes, elles seront triées dans leur ordre naturel, c'est à dire par ordre alphabétique:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() { TreeMap map = new TreeMap(); map.put("c", "val"); map.put("b", "val"); map.put("a", "val"); map.put("e", "val"); map.put("d", "val"); assertEquals("[a, b, c, d, e]", map.keySet().toString()); }

TreeMap , contrairement à une carte de hachage et à une carte de hachage liée, n'emploie nulle part le principe de hachage car il n'utilise pas de tableau pour stocker ses entrées.

3. Tri personnalisé dans TreeMap

Si nous ne sommes pas satisfaits de l'ordre naturel de TreeMap , nous pouvons également définir notre propre règle de classement au moyen d'un comparateur lors de la construction d'une carte arborescente.

Dans l'exemple ci-dessous, nous voulons que les clés entières soient classées par ordre décroissant:

@Test public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() { TreeMap map = new TreeMap(Comparator.reverseOrder()); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString()); }

Une carte de hachage ne garantit pas l'ordre des clés stockées et ne garantit pas spécifiquement que cet ordre restera le même au fil du temps, mais une carte d'arborescence garantit que les clés seront toujours triées selon l'ordre spécifié.

4. Importance du tri TreeMap

Nous savons maintenant que TreeMap stocke toutes ses entrées dans un ordre trié. En raison de cet attribut d'arborescence, nous pouvons effectuer des requêtes comme; trouver «plus grand», trouver «plus petit», trouver toutes les clés inférieures ou supérieures à une certaine valeur, etc.

Le code ci-dessous ne couvre qu'un petit pourcentage de ces cas:

@Test public void givenTreeMap_whenPerformsQueries_thenCorrect() { TreeMap map = new TreeMap(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); Integer highestKey = map.lastKey(); Integer lowestKey = map.firstKey(); Set keysLessThan3 = map.headMap(3).keySet(); Set keysGreaterThanEqTo3 = map.tailMap(3).keySet(); assertEquals(new Integer(5), highestKey); assertEquals(new Integer(1), lowestKey); assertEquals("[1, 2]", keysLessThan3.toString()); assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString()); }

5. Mise en œuvre interne de TreeMap

TreeMap implémente l' interface NavigableMap et fonde son fonctionnement interne sur les principes des arbres rouge-noir:

public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable

Le principe des arbres rouge-noir dépasse le cadre de cet article, cependant, il y a des éléments clés à retenir pour comprendre comment ils s'intègrent dans TreeMap .

Tout d'abord , un arbre rouge-noir est une structure de données composée de nœuds; imaginez un manguier inversé avec sa racine dans le ciel et les branches poussant vers le bas. La racine contiendra le premier élément ajouté à l'arborescence.

La règle est qu'à partir de la racine, tout élément de la branche gauche de tout nœud est toujours inférieur à l'élément du nœud lui-même. Ceux de droite sont toujours plus grands. Ce qui définit plus ou moins que est déterminé par l'ordre naturel des éléments ou le comparateur défini lors de la construction comme nous l'avons vu précédemment.

Cette règle garantit que les entrées d'un treemap seront toujours dans un ordre trié et prévisible.

Deuxièmement , un arbre rouge-noir est un arbre de recherche binaire auto-équilibré. Cet attribut et ce qui précède garantissent que les opérations de base telles que rechercher, obtenir, placer et supprimer prennent un temps logarithmique O (log n) .

Être auto-équilibré est la clé ici. Au fur et à mesure que nous insérons et supprimons des entrées, imaginez l'arbre de plus en plus long d'un côté ou plus court de l'autre.

Cela signifierait qu'une opération prendrait moins de temps sur la branche la plus courte et plus de temps sur la branche la plus éloignée de la racine, ce que nous ne voudrions pas.

Par conséquent, cela est pris en compte dans la conception des arbres rouge-noir. Pour chaque insertion et suppression, la hauteur maximale de l'arbre sur n'importe quelle arête est maintenue à O (log n) c'est-à-dire que l'arbre s'équilibre en permanence.

Tout comme la mappe de hachage et la mappe de hachage liée, une mappe d'arbre n'est pas synchronisée et, par conséquent, les règles d'utilisation dans un environnement multi-thread sont similaires à celles des deux autres implémentations de mappe.

6. Choisir la bonne carte

Après avoir examiné les implémentations HashMap et LinkedHashMap précédemment et maintenant TreeMap , il est important de faire une brève comparaison entre les trois pour nous guider sur celui qui se situe où.

Une carte de hachage est une bonne implémentation de carte à usage général qui fournit des opérations de stockage et de récupération rapides. Cependant, il échoue en raison de sa disposition chaotique et désordonnée des entrées.

Cela entraîne des performances médiocres dans les scénarios où il y a beaucoup d'itérations, car la capacité totale du tableau sous-jacent affecte le parcours autre que le nombre d'entrées.

Une carte de hachage liée possède les bons attributs des cartes de hachage et ajoute de l'ordre aux entrées. Il fonctionne mieux là où il y a beaucoup d'itérations car seul le nombre d'entrées est pris en compte quelle que soit la capacité.

Une carte arborescente fait passer l'ordre au niveau suivant en fournissant un contrôle complet sur la façon dont les clés doivent être triées. D'un autre côté, il offre des performances générales moins bonnes que les deux autres alternatives.

Nous pourrions dire qu'une carte de hachage liée réduit le chaos dans l'ordre d'une carte de hachage sans encourir la pénalité de performance d'une carte d'arbre .

7. Conclusion

Dans cet article, nous avons exploré la classe Java TreeMap et son implémentation interne. Puisqu'il s'agit de la dernière d'une série d'implémentations d'interface de carte commune, nous avons également discuté brièvement de l'endroit où cela correspond le mieux par rapport aux deux autres.

Le code source complet de tous les exemples utilisés dans cet article se trouve dans le projet GitHub.