devstory

Le Tutoriel de Java TreeMap

  1. TreeMap
  2. Comment TreeMap stocke-t-il les données?
  3. Examples
  4. TreeMap avec la clef null

1. TreeMap

Dans cet article, nous découvrons la classe TreeMap, qui est une implémentation de l'interface Map et se situe dans Java Collection Framework.
public class TreeMap<K,V> extends AbstractMap<K,V>
                    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
En règle générale, dans cet article, nous allons apprendre les caractéristiques de TreeMap et la manière dont il stocke les mappages. Les concepts de base de Map ne seront pas mentionnés à nouveau, si vous ne connaissez pas le concept de Map, vous devriez l'apprendre avant de continuer avec cet article.
Map<K,V>
SortedMap<K,V>
NavigableMap<K,V>
TreeMap<K,V>
Les clefs dupliquées ne sont pas autorisées.
Autoriser la clef null et les valeurs null.
Autoriser uniquement la clef null si un Comparator approprié est fourni.
L'ordre des clefs n'est pas garanti.
Les clefs sont classées dans l'ordre croissant en fonction de leur ordre naturel ou selon un Comparator fourni.
Hériter des fonctionnalités de l'interface SortedMap. Toutes les clés TreeMap doivent être de type Comparable ou vous devez fournir un Comparator pour TreeMap qui compare les clés. Sinon, ClassCastException sera levée. Comparator est fourni au moment où l'objet TreeMap est créé via l'un de ses constructeurs.
TreeMap​ constructors
TreeMap()

TreeMap​(Map<? extends K,​? extends V> m)    

TreeMap​(Comparator<? super K> comparator)

// Using the same ordering as the specified sortedMap.
TreeMap​(SortedMap<K,​? extends V> m)

2. Comment TreeMap stocke-t-il les données?

TreeMap utilise comparator.compare(key1,key2) pour comparer deux clés si Comparator est fourni. Sinon, il utilise key1.compareTo(key2) pour comparer deux clés. TreeMap est conçu pour garantir que la recherche, la mise à jour ou la suppression d'une carte prend le moins de temps possible en réduisant le nombre de fois que les clés doivent être comparées. Dans cette section, nous allons découvrir comment TreeMap stocke ses données.
Entry<K,V> est une classe utilisée pour stocker un mappage qui consiste en cinq propriétés: key, value, parent, left, right. TreeMap gère une référence à une Entry racine - root, les recherches sur TreeMap commencent à partir de Entry racine et se propage jusqu'à une feuille de l'arbre.
Entry<K,V>
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
Pour faire simple, observer ce qui se passe lorsqu'on ajoute des mappages à un TreeMap<Integer,String>.
TreeMap<Integer, String> map = new TreeMap<>();

// keys = 5, 3, 9, 7, 1, 11.
map.put(5, "Five");
map.put(3,  "Three");
map.put(9,  "Nine");
map.put(7, "Seven");
map.put(1, "One");
map.put(11, "Eleven");
L'image ci-dessus montre la structure de TreeMap. Le premier mappage ajouté à TreeMap sera la racine (root) de l'arbre, le mappage avec la plus petite clef sera placé à gauche, et le mappage avec la plus grande clef sera placé à droite.
get(key)?
map.get(7); // key =  7
L'opération de recherche d'un mappage commence toujours à Entry racine. La clef à rechercher sera comparée à la clé Entry actuelle, si elle est supérieure, elle sera comparée à la prochaine clé Entry sur la droite. Sinon, si elle est plus petite, elle sera comparée à la prochaine touche Entry à gauche, jusqu'à ce qu'elle trouve ou atteigne les feuilles de l'arbre.
remove(key)?
Ensuite, observer ce que TreeMap fait pour supprimer un mappage.
map.remove(5); // Remove the mapping has key = 5.
Pour supprimer un mappage, le TreeMap identifie l'emplacement de Entry à supprimer. Ensuite, il cherche Entry avec la clef la plus petite et plus grande que celle à retirer pour la replacer à la position de Entry à enlever.
put(key,value)?
map.put(2, "Two");

3. Examples

Comme on le sait tous, la classe Integer implémente l'interface Comparable, donc les objets Integer peuvent être comparés l'un à l'autre. TreeMap avec les clef Integer n'ont pas besoin d'un Comparator.
TreeMapEx1.java
package org.o7planning.treemap.ex;

import java.util.Set;
import java.util.TreeMap;

public class TreeMapEx1 {

    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        //  
        map.put(5, "Five");
        map.put(3, "Three");
        map.put(9, "Nine");
        map.put(7, "Seven");
        map.put(1, "One");
        map.put(11, "Eleven");
        
        Set<Integer> keys = map.keySet();
        
        System.out.println(keys);
        
        for(Integer key: keys)  {
            System.out.println(key + " --> " + map.get(key));
        }
    }
}
Output:
[1, 3, 5, 7, 9, 11]
1 --> One
3 --> Three
5 --> Five
7 --> Seven
9 --> Nine
11 --> Eleven
Par exemple: Utiliser Comparator personnalisé pour renverser l'ordre des clefs.
TreeMap_reverseOrder_ex1.java
package org.o7planning.treemap.ex;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeMap;

public class TreeMap_reverseOrder_ex1 {

    public static void main(String[] args) {
        Comparator<Integer> reverseOrderComparator = Comparator.reverseOrder();
        
        TreeMap<Integer, String> map = new TreeMap<>(reverseOrderComparator);
        //  
        map.put(5, "Five");
        map.put(3, "Three");
        map.put(9, "Nine");
        map.put(7, "Seven");
        map.put(1, "One");
        map.put(11, "Eleven");
        
        Set<Integer> keys = map.keySet();
        
        System.out.println(keys);
        
        for(Integer key: keys)  {
            System.out.println(key + " --> " + map.get(key));
        }
    }
}
Output:
[11, 9, 7, 5, 3, 1]
11 --> Eleven
9 --> Nine
7 --> Seven
5 --> Five
3 --> Three
1 --> One
Voir plus d'exemple sur l'utilisation de Comparator personnalisé et la manière de naviguer et chercher la clef ou le mappage:

4. TreeMap avec la clef null

TreeMap autorise la clef null uniquement s'il est fourni d'un Comparator lequel prend en charge la comparaison de la clef null avec les autres.
TreeMap_nullKey_ex1.java
package org.o7planning.treemap.ex;

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

public class TreeMap_nullKey_ex1 {

    public static void main(String[] args) {
        // Comparator.nullsFirst
        // Comparator.nullsLast
        Comparator<String> comparator = Comparator.nullsFirst(Comparator.naturalOrder());

         // Create a SortedSet object.
        SortedMap<String, Integer> map = new TreeMap<String, Integer>(comparator);
 
        map.put(null, 0);
        map.put("B", 100);
        map.put("A", 200);
        map.put("F", 400);
        map.put("D", 500);
        map.put("E", 100);

        System.out.println("--- keySet ---");
        Set<String> keys = map.keySet();

        for (String key : keys) {
            System.out.println(key + " --> " + map.get(key));
        }
        
        System.out.println("--- entrySet ---");
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        
        for (Map.Entry<String,Integer> entry: entrySet) {
            System.out.println(entry.getKey() + " --> " + entry.getValue());
        }
    }
}
Output:
--- keySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
--- entrySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
Par exemple: Ecrire un Comparator personnalisé qui prend en charge la comparaison entre une clef null avec les autres:
TreeMap_nullKey_ex2.java
package org.o7planning.treemap.ex;

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

public class TreeMap_nullKey_ex2 {

    public static void main(String[] args) {  
        Comparator<String> comparator = new StringNullComparator();

         // Create a SortedSet object.
        SortedMap<String, Integer> map = new TreeMap<String, Integer>(comparator);
 
        map.put(null, 0);
        map.put("B", 100);
        map.put("A", 200);
        map.put("F", 400);
        map.put("D", 500);
        map.put("E", 100);

        System.out.println("--- keySet ---");
        Set<String> keys = map.keySet();

        for (String key : keys) {
            System.out.println(key + " --> " + map.get(key));
        }
        
        System.out.println("--- entrySet ---");
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        
        for (Map.Entry<String,Integer> entry: entrySet) {
            System.out.println(entry.getKey() + " --> " + entry.getValue());
        }
    }
}
// The comparator supports null comparison.
class StringNullComparator implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        if(o1 == o2) {
            return 0; // o1 = o2
        }
        if(o1 == null)  {
            return -1; // o1 < o2
        }
        if(o2 == null)  {
            return 1; // o1 > o2
        }
        return o1.compareTo(o2);
    }
}
Output:
--- keySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
--- entrySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400

Tutoriels de Java Collections Framework

Show More

Articles les plus récents

Show More