Java Language
TreeMap et TreeSet

Introduction

TreeMap d'un type Java simple

Tout d'abord, nous créons une carte vide et y insérons des éléments:

TreeMap<Integer, String> treeMap = new TreeMap<>();

TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();

treeMap.put(10, "ten");
treeMap.put(4, "four");
treeMap.put(1, "one");
treeSet.put(12, "twelve");

Une fois que nous avons quelques éléments dans la carte, nous pouvons effectuer certaines opérations:

System.out.println(treeMap.firstEntry()); // Prints 1=one
System.out.println(treeMap.lastEntry()); // Prints 12=twelve
System.out.println(treeMap.size()); // Prints 4, since there are 4 elemens in the map
System.out.println(treeMap.get(12)); // Prints twelve
System.out.println(treeMap.get(15)); // Prints null, since the key is not found in the map

Nous pouvons également parcourir les éléments de la carte en utilisant soit un itérateur, soit une boucle foreach. Notez que les entrées sont imprimées en fonction de leur ordre naturel et non de l'ordre d'insertion:

for (Entry<Integer, String> entry : treeMap.entrySet()) {
    System.out.print(entry + " "); //prints 1=one 4=four 10=ten 12=twelve 
}

Iterator<Entry<Integer, String>> iter = treeMap.entrySet().iterator();
while (iter.hasNext()) {
    System.out.print(iter.next() + " "); //prints 1=one 4=four 10=ten 12=twelve 
}

TreeSet d'un type Java simple

Tout d'abord, nous créons un ensemble vide et y insérons des éléments:

TreeSet<Integer> treeSet = new TreeSet<>();

TreeSet<Integer> treeSet = new TreeSet<Integer>();

treeSet.add(10);
treeSet.add(4);
treeSet.add(1);
treeSet.add(12);

Une fois que nous avons quelques éléments dans l'ensemble, nous pouvons effectuer certaines opérations:

System.out.println(treeSet.first()); // Prints 1
System.out.println(treeSet.last()); // Prints 12
System.out.println(treeSet.size()); // Prints 4, since there are 4 elemens in the set
System.out.println(treeSet.contains(12)); // Prints true
System.out.println(treeSet.contains(15)); // Prints false

Nous pouvons également parcourir les éléments de la carte en utilisant soit un itérateur, soit une boucle foreach. Notez que les entrées sont imprimées en fonction de leur ordre naturel et non de l'ordre d'insertion:

for (Integer i : treeSet) {
    System.out.print(i + " "); //prints 1 4 10 12
}

Iterator<Integer> iter = treeSet.iterator();
while (iter.hasNext()) {
    System.out.print(iter.next() + " "); //prints 1 4 10 12
}

TreeMap / TreeSet d'un type Java personnalisé

Depuis que TreeMap s et TreeSet conservent les clés / éléments en fonction de leur ordre naturel . Les clés TreeMap et les éléments TreeSet doivent donc être comparables.

Disons que nous avons une classe Person :

public class Person  {

    private int id;
    private String firstName, lastName;
    private Date birthday;

    //... Constuctors, getters, setters and various methods
}

Si nous le stockons tel quel dans un TreeSet (ou une clé dans un TreeMap):

TreeSet<Person2> set = ...      
set.add(new Person(1,"first","last",Date.from(Instant.now())));

Ensuite, nous avons rencontré une exception telle que celle-ci:

Exception in thread "main" java.lang.ClassCastException: Person cannot be cast to java.lang.Comparable
    at java.util.TreeMap.compare(TreeMap.java:1294)
    at java.util.TreeMap.put(TreeMap.java:538)
    at java.util.TreeSet.add(TreeSet.java:255)

Pour corriger cela, supposons que nous voulions ordonner les instances de Person fonction de l'ordre de leurs identifiants ( private int id ). Nous pourrions le faire de deux manières:

1. Une solution consiste à modifier la Person afin qu'elle implémente l' interface Comparable :

   public class Person implements Comparable<Person> {
       private int id;
       private String firstName, lastName;
       private Date birthday;
   
       //... Constuctors, getters, setters and various methods
   
       @Override
       public int compareTo(Person o) {
           return Integer.compare(this.id, o.id); //Compare by id
       }
   }
   

2. Une autre solution consiste à fournir à TreeSet un comparateur :

TreeSet<Person> treeSet = new TreeSet<>((personA, personB) -> Integer.compare(personA.getId(), personB.getId()));

TreeSet<Person> treeSet = new TreeSet<>(new Comparator<Person>(){
    @Override
    public int compare(Person personA, Person personB) {
        return Integer.compare(personA.getId(), personB.getId());
    }
});

Cependant, il y a deux mises en garde pour les deux approches:

1. Il est très important de ne modifier aucun champ utilisé pour la commande une fois qu'une instance a été insérée dans un TreeSet / TreeMap . Dans l'exemple ci-dessus, si nous modifions l' id d'une personne déjà insérée dans la collection, nous pourrions rencontrer un comportement inattendu.

2. Il est important de mettre en œuvre la comparaison correctement et de manière cohérente. Selon le Javadoc :

Le réalisateur doit assurer sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) pour tous les x et y. (Cela implique que x.compareTo(y) doit lancer une exception ssi y.compareTo(x) lance une exception)

L’implémenteur doit également s’assurer que la relation est transitive: (x.compareTo(y)>0 && y.compareTo(z)>0) implique x.compareTo(z)>0 .

Enfin, l'implémenteur doit s'assurer que x.compareTo(y)==0 implique que sgn(x.compareTo(z)) == sgn(y.compareTo(z)) , pour tout z.

TreeMap et TreeSet Thread Safety

TreeMap et TreeSet ne sont pas des collections thread-safe, il convient donc de veiller à ce qu'ils soient utilisés dans des programmes multithread.

TreeMap et TreeSet sont tous deux sûrs lorsqu'ils sont lus, même simultanément, par plusieurs threads. Donc, si elles ont été créées et remplies par un seul thread (par exemple, au début du programme), et seulement après avoir lu, mais pas modifié par plusieurs threads, il n'y a aucune raison de synchroniser ou de verrouiller.

Toutefois, si elle est lue et modifiée simultanément ou modifiée simultanément par plusieurs threads, la collection peut générer une exception ConcurrentModificationException ou se comporter de manière inattendue. Dans ces cas, il est impératif de synchroniser / verrouiller l’accès à la collection en utilisant l’une des méthodes suivantes:

1. Utilisation de Collections.synchronizedSorted.. :

   SortedSet<Integer> set = Collections.synchronizedSortedSet(new TreeSet<Integer>());
   SortedMap<Integer,String> map = Collections.synchronizedSortedMap(new TreeMap<Integer,String>());
   

   Cela fournira une SortedSet / SortedMap mise en œuvre soutenue par la collecte effective et synchronisée sur un objet mutex. Notez que cela synchronisera tous les accès en lecture et en écriture à la collection sur un seul verrou, de sorte que même les lectures simultanées ne seraient pas possibles.

2. En synchronisant manuellement certains objets, comme la collection elle-même:

    TreeSet<Integer> set = new TreeSet<>(); 
   

   ...

   //Thread 1
   synchronized (set) {
       set.add(4);
   }
   

   ...

   //Thread 2
   synchronized (set) {
       set.remove(5);
   }        
   

3. En utilisant un verrou, tel qu'un ReentrantReadWriteLock :

    TreeSet<Integer> set = new TreeSet<>(); 
    ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
   

   ...

    //Thread 1
    lock.writeLock().lock();
    set.add(4);
    lock.writeLock().unlock();
   

   ...

    //Thread 2
    lock.readLock().lock();
    set.contains(5);
    lock.readLock().unlock();
   

Contrairement aux méthodes de synchronisation précédentes, l'utilisation d'un ReadWriteLock permet à plusieurs threads de lire simultanément sur la carte.