Classe Java TreeMap | W3Docs Learn Java

Ce qu'est un TreeMap

TreeMap<K, V> est la Map qui conserve ses clés triées. Internally it's a red-black tree — le même arbre de recherche binaire auto-équilibré qui sous-tend TreeSet — et chaque opération est en O(log n) : put, get, remove, la première clé, la dernière clé, les requêtes de plage. La contrepartie du coût logarithmique est l'API de navigation sur NavigableMap<K, V> : floor, ceiling, lower, higher, sub-map, head-map, tail-map, vues descendantes. Aucune de ces opérations n'est possible sur une table de hachage sans un tri complet au préalable.

Si vous vous retrouvez à faire new TreeMap<>(hashMap) à la fin d'une fonction pour « trier les entrées », c'est le signal que TreeMap aurait dû être le type dès le départ.

Deux façons de définir l'ordre des clés

Un TreeMap doit d'une façon ou d'une autre comparer les clés. Comme pour TreeSet :

Ordre naturel — le type de clé implémente Comparable<K>. Les chaînes de caractères, les wrappers numériques, les dates, et vos propres types record qui implémentent Comparable sont tous éligibles.
Un Comparator<K> passé au constructeur — utilisez-le lorsque l'ordre naturel n'existe pas ou ne correspond pas à ce que vous souhaitez. (Voir Comparable vs Comparator pour la différence entre les deux.)

Map<String, Integer> byName    = new TreeMap<>();                        // case-sensitive natural
Map<String, Integer> byNameCi  = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
Map<String, Integer> reverse   = new TreeMap<>(Comparator.reverseOrder());

Comme pour TreeSet, l'égalité se détermine par compareTo retournant 0, et non par equals. Deux clés que le comparateur considère comme égales fusionnent en une seule entrée — le second put écrase le premier. Avec un keying par String.CASE_INSENSITIVE_ORDER, mettre "Java" puis "JAVA" vous laisse avec une seule entrée dont la clé est le "Java" original et dont la valeur est celle du second put. Ce n'est presque jamais ce que vous souhaitez par inadvertance.

L'API NavigableMap

L'interface qu'un TreeMap implémente vous offre de nombreuses opérations qu'une Map ordinaire ne propose pas :

TreeMap<Integer, String> t = new TreeMap<>();
t.put(10, "a"); t.put(20, "b"); t.put(30, "c"); t.put(40, "d");

t.firstKey();        // 10
t.lastKey();         // 40
t.firstEntry();      // 10=a
t.pollFirstEntry();  // 10=a, removes
t.lowerKey(30);      // 20 — strictly less
t.floorKey(30);      // 30 — ≤
t.higherKey(30);     // 40 — strictly greater
t.ceilingKey(30);    // 30 — ≥
t.headMap(30);       // {10=a, 20=b}  — keys strictly < 30
t.tailMap(30);       // {30=c, 40=d}  — keys ≥ 30
t.subMap(20, 40);    // {20=b, 30=c}  — [20, 40)
t.descendingMap();   // reverse-order view

C'est pourquoi TreeMap existe. « Trouver l'événement le plus proche avant 9h » se traduit par headMap(9am).lastEntry() — une seule recherche en temps logarithmique. La même opération sur une HashMap devrait parcourir chaque clé.

Les vues de sous-map sont vivantes

subMap, headMap et tailMap retournent des vues dans la map originale — pas des copies. Les modifications apportées via la vue se propagent vers la map originale, et les modifications de l'originale qui tombent dans la plage de la vue apparaissent dans la vue. Les vues appliquent également la plage : essayer d'insérer une clé hors plage via la vue lève une IllegalArgumentException. C'est ainsi que l'itération bornée par une plage reste sûre même lorsque vous modifiez la map pendant le parcours.

TreeMap<Integer, String> t = new TreeMap<>();
t.put(10, "a"); t.put(20, "b"); t.put(30, "c");
NavigableMap<Integer, String> mid = t.subMap(15, true, 25, true);
mid.put(20, "updated");   // OK — 20 is in range
// mid.put(40, "x");       // would throw — 40 is out of range
System.out.println(t);     // {10=a, 20=updated, 30=c}

Null est rejeté (pour les clés)

Vous ne pouvez pas avoir de clé null dans un TreeMap pour la même raison que TreeSet les rejette : il n'y a aucun moyen sensé d'appeler compareTo sur null. Le premier put(null, ...) lève une NullPointerException. Les valeurs null sont acceptées.

Quand choisir `TreeMap`

Arbre de décision :

Vous avez besoin d'une itération triée par clé ou de requêtes de plage sur les clés → TreeMap. Seul choix.
Vous avez besoin de recherches rapides et l'ordre ne compte pas → HashMap. O(1) l'emporte.
Vous avez besoin de recherches rapides et d'une itération dans l'ordre d'insertion → LinkedHashMap.
Le type de clé est une enum → EnumMap. Plus rapide que TreeMap et naturellement ordonné.

Les quatre implémentent le même contrat Map, donc passer de l'une à l'autre est généralement un changement d'une ligne dans le constructeur.

Un patron utile : utilisez une HashMap pour construire la map rapidement, puis faites new TreeMap<>(hashMap) une seule fois pour présenter une vue triée à la fin. Construire vite, présenter trié.

Un exemple concret : consultation de planning, requêtes de plage, clés avec comparateur

Le programme ci-dessous utilise un TreeMap pour modéliser un petit « planning d'événements » indexé par des minutes depuis minuit. Il illustre l'API de navigation pour « quel est le prochain événement après X » et « tout ce qui précède Y », montre la vue de sous-map vivante, et révèle le piège de l'égalité par comparateur avec une map insensible à la casse.

java— editable, runs on the server

import java.util.*;

public class TreeMapShowcase {
  public static void main(String[] args) {
    // --- A schedule keyed by minutes-since-midnight ---
    TreeMap<Integer, String> schedule = new TreeMap<>();
    schedule.put( 9 * 60,     "standup");
    schedule.put(10 * 60 + 30, "design review");
    schedule.put(13 * 60,     "lunch with team");
    schedule.put(16 * 60,     "demo");
    schedule.put(18 * 60,     "ship");
    System.out.println("schedule (sorted by key):");
    schedule.forEach((k, v) ->
        System.out.println("  " + (k / 60) + ":" + String.format("%02d", k % 60) + "  " + v));

int now = 11 * 60 + 0;
    System.out.println("\nat 11:00...");
    System.out.println("  next event:           " + schedule.ceilingEntry(now));
    System.out.println("  most recent past:     " + schedule.lowerEntry(now));

// --- Morning slice: live view ---
    NavigableMap<Integer, String> morning = schedule.headMap(12 * 60, false);
    System.out.println("\nmorning (key < 12:00):  " + morning);
    schedule.put(11 * 60 + 30, "coffee");      // falls in the morning range
    System.out.println("after adding coffee at 11:30:");
    System.out.println("  morning view:  " + morning);  // reflects the new entry

// --- pollFirstEntry: priority-queue-like draining ---
    System.out.println("\ndraining in time order:");
    while (!schedule.isEmpty()) {
      Map.Entry<Integer, String> next = schedule.pollFirstEntry();
      System.out.println("  " + (next.getKey() / 60) + ":"
          + String.format("%02d", next.getKey() % 60) + "  " + next.getValue());
    }

// --- The comparator-equality trap ---
    TreeMap<String, Integer> ci = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
    ci.put("Java", 1);
    ci.put("JAVA", 2);     // comparator says equal → overwrites value, keeps original key
    System.out.println("\ncase-insensitive: " + ci);
  }
}

Ce qu'il faut retenir de l'exécution :

Le planning s'affiche dans l'ordre chronologique sans aucun tri explicite. L'ajout de "coffee" à 11h30 l'a automatiquement inséré au bon endroit.
Nous avons interrogé la map à 11h00. ceilingEntry(11*60) retourne l'entrée suivante à partir de 11h00 ou après, soit le déjeuner à 13h00 (la revue de conception à 10h30 est avant 11h00, donc elle ne compte pas). lowerEntry(11*60) retourne l'entrée la plus récente strictement avant 11h00, la revue de conception à 10h30. Les deux sont en O(log n).
La sous-map morning est une vue vivante — coffee y est apparu après l'avoir ajouté dans la map originale. Si nous avions ajouté "midnight snack" à 23h00, la vue l'aurait ignoré (hors plage).
pollFirstEntry a vidé répétitivement l'événement le plus proche. C'est une file de priorité de fortune lorsque vous souhaitez également des recherches par clé, ce qu'une vraie PriorityQueue ne peut pas vous offrir.
La map insensible à la casse a fusionné "Java" et "JAVA" en une seule entrée — indexée par le "Java" original mais avec la valeur 2 du second put. Égalité par comparateur, pas par equals.

La suite

Les quatre implémentations de map modernes — HashMap, LinkedHashMap, TreeMap, et ConcurrentHashMap — sont celles à utiliser dans le nouveau code. Il en existe une autre dans le JDK qui les précède toutes et que vous rencontrerez encore occasionnellement dans l'ancien code : Hashtable. Il vaut la peine de savoir pourquoi elle existe, pourquoi c'est presque toujours le mauvais choix aujourd'hui, et comment la remplacer.

Pratique

Un `TreeMap<Integer, String>` contient les clés `10, 20, 30, 40`. Que retourne `tree.floorKey(25)` ?

`20` — la plus grande clé inférieure ou égale à 25`30` — la plus petite clé supérieure ou égale à 25`25` — la clé est insérée avec une valeur null et retournée`null` — `floorKey` ne retourne une clé que lorsqu'elle correspond exactement à une clé de la map