Présentation de la collection TreeMap

Un jour à l'université, j'ai eu besoin d'écrire du code pour trier les noms de famille de mes camarades de classe, qui servaient de clés à leurs données personnelles, par ordre croissant. J'ai passé beaucoup de temps là-dessus. Mais si j'avais connu la classe TreeMap à l'époque, j'aurais terminé la tâche beaucoup plus rapidement.

Qu'est-ce qu'un TreeMap ? Il s'agit d'une structure de données semblable à un dictionnaire qui stocke les éléments sous forme de paires clé-valeur, en les triant par clé.

Où et comment peut-il être utilisé ? Eh bien, cela aurait été idéal pour le même devoir avec les noms de famille de mes camarades de classe. Si j'ai besoin de stocker des valeurs dans l'ordre croissant, au lieu d'écrire mon propre algorithme de tri, tout ce que j'ai à faire est de créer un TreeMap et d'y mettre les valeurs.

Il trie les types tels que Integer et String dans l'ordre croissant. Mais si vous souhaitez mettre votre propre type personnalisé dans un TreeMap , votre classe doit implémenter l' interface Comparable , afin qu'elle implémente la méthode compareTo() , qui indique comment trier les instances de votre classe.

public class Person implements Comparable<Person> {
 
    private String firstName;
    private String lastName;
 
    public Person(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }
 
    public String getFirstName() {
        return firstName;
    }
 
    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }
 
  …
 
    @Override
    public int compareTo(Person person) {
        return person.getFirstName().compareTo(firstName);
    }
 
    @Override
    public String toString() {
        return "Person{" +
                "firstName='" + firstName + '\'' +
                ", lastName='" + lastName + '\'' +
                '}';
    }
}

Remplaçons la méthode compareTo() afin qu'elle trie les valeurs par prénom dans l'ordre alphabétique inverse :

TreeMap map = new TreeMap<Person, String>();
 
map.put(new Person("AA","BB"), "aa");
map.put(new Person("BB","BB"), "aa");
map.put(new Person("DD","BB"), "aa");
map.put(new Person("CC","BB"), "aa");

Les valeurs seront stockées dans l'ordre suivant :

Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}

La classe TreeMap implémente l' interface NavigableMap , qui à son tour étend l' interface SortedMap . Cela permet à la classe TreeMap d'utiliser des arbres pour stocker les valeurs dans un ordre trié.

Pour le dire en termes simples, un arbre rouge-noir est une structure de données qui stocke des valeurs dans le sous-arbre de droite si elles sont supérieures à la racine, et dans le sous-arbre de gauche si elles sont inférieures. Cette implémentation peut rechercher très rapidement des valeurs dans la structure.

Un arbre rouge-noir est auto-équilibré, il change donc de structure à chaque nouvelle valeur insérée. La valeur ajoutée en premier est initialement considérée comme la racine, mais une autre valeur peut devenir la racine au cours du processus d'équilibrage.

Eh bien, maintenant vous savez ce qu'est TreeMap et comment cela fonctionne.

N'oubliez pas que TreeMap ne peut stocker que des objets dont la classe implémente l' interface Comparable et remplace la méthode compareTo() .

Mais que se passe-t-il si nous utilisons des classes tierces chargées à partir de diverses bibliothèques et que nous ne pouvons pas y implémenter Comparable ? Il existe une solution à cela : écrivez votre propre Comparator .

Comparator est une interface qui a une méthode compare(). Nous pouvons l'utiliser pour comparer des objets et les stocker dans un TreeMap .

Comparator<Person> comparator = new Comparator<Person>() {
 
    @Override
    public int compare(Person person1, Person person2) {
        return person1.getFirstName().compareTo(person2.getFirstName());
    }
};
 
 
TreeMap map = new TreeMap<Person, String>(comparator);

Dans cet exemple, nous avons créé un comparateur personnalisé et transmis un TreeMap à la classe.

À partir de Java 8, nous pouvons écrire ceci en utilisant une expression lambda :

TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));

En d'autres termes, pour stocker des valeurs dans un TreeMap , vous devez spécifier comment les trier. Il existe deux façons de procéder : implémentez Comparable ou implémentez votre propre Comparator .

Mais que se passe-t-il si nous devons mettre null dans un TreeMap comme clé ? HashMap vous permet de le faire. Oui, mais comment TreeMap gère-t-il cela ?

TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");

L'exécution de ce code nous donne une erreur :

Le problème est qu'en interne la classe TreeMap compare les valeurs à l'aide de la méthode compareTo() . Vous pouvez certainement passer une valeur nulle dans et le code se compilera. Mais au moment de l'exécution, vous obtiendrez une erreur, car la méthode sera appelée sur une valeur nulle , provoquant la levée d' une NullPointerException .

Comparaison de HashMap et TreeMap

Contrairement à TreeMap , HashMap vous permet de stocker null en tant que clé. La structure a un emplacement spécifique pour toutes les clés nulles . HashMap est capable de stocker des clés nulles car il détermine où elles vont en fonction de leur valeur de hachage, et le calcul de la valeur de hachage ne nécessite pas de comparaisons. Ainsi, toutes les clés nulles ont leur place.

Voilà, vous savez maintenant quoi utiliser lorsque vous devez stocker des valeurs dans un ordre trié et comment définir les règles de tri.