Classe Java TreeMap | W3Docs Learn Java

Cos'è una TreeMap

TreeMap<K, V> è la Map che mantiene le proprie chiavi ordinate. Internamente è un albero rosso-nero — lo stesso albero binario di ricerca auto-bilanciante che supporta TreeSet — e ogni operazione è O(log n): put, get, remove, la prima chiave, l'ultima chiave, le query su intervalli. Il vantaggio del costo logaritmico è l'API di navigazione su NavigableMap<K, V>: floor, ceiling, lower, higher, sub-map, head-map, tail-map, viste discendenti. Nessuna di queste operazioni è possibile su una tabella hash senza un ordinamento completo prima.

Se ti ritrovi mai a fare new TreeMap<>(hashMap) alla fine di una funzione per "ordinare le voci," questo è il segnale che TreeMap avrebbe dovuto essere il tipo sin dall'inizio.

Due modi per definire l'ordine delle chiavi

Una TreeMap ha bisogno di confrontare le chiavi in qualche modo. Come con TreeSet:

Ordine naturale — il tipo di chiave implementa Comparable<K>. Stringhe, wrapper numerici, date e i tuoi tipi record personalizzati che implementano Comparable sono tutti idonei.
Un Comparator<K> passato al costruttore — usalo quando l'ordine naturale non esiste o non corrisponde a ciò che vuoi. (Vedi Comparable vs Comparator per le differenze tra i due.)

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());

Come con TreeSet, l'uguaglianza avviene tramite compareTo che restituisce 0, non tramite equals. Due chiavi che il comparatore considera uguali collassano in un'unica voce — il secondo put sovrascrive il primo. Con la chiave String.CASE_INSENSITIVE_ORDER, inserendo "Java" e poi "JAVA" si ottiene un'unica voce la cui chiave è la prima "Java" e il cui valore è il valore del secondo put. Questo non è quasi mai ciò che si vuole per sbaglio.

L'API NavigableMap

L'interfaccia implementata da una TreeMap offre molte operazioni che una semplice Map non ha:

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

Ecco perché esiste TreeMap. "Trova l'evento più vicino prima delle 9:00" è headMap(9am).lastEntry() — una singola ricerca in tempo logaritmico. La stessa operazione su una HashMap dovrebbe scansionare tutte le chiavi.

Le viste di sub-map sono live

subMap, headMap e tailMap restituiscono viste sulla mappa originale — non copie. Le modifiche apportate tramite la vista si propagano all'indietro, e le modifiche all'originale che rientrano nell'intervallo della vista compaiono nella vista. Le viste impongono anche l'intervallo: tentare di inserire una chiave fuori dall'intervallo tramite la vista lancia IllegalArgumentException. Questo è il modo in cui l'iterazione con intervallo delimitato rimane sicura anche durante la mutazione nel corso della traversata.

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 è rifiutato (per le chiavi)

Non puoi avere una chiave null in una TreeMap per la stessa ragione per cui TreeSet le rifiuta: non esiste un modo sensato per chiamare compareTo su null. Il primo put(null, ...) lancia NullPointerException. I valori null sono accettati.

Quando scegliere `TreeMap`

Flusso decisionale:

Hai bisogno di iterazione ordinata per chiave o di query su intervalli di chiavi → TreeMap. È l'unica scelta.
Hai bisogno di ricerca veloce e l'ordine non è importante → HashMap. O(1) vince.
Hai bisogno di ricerca veloce e iterazione nell'ordine di inserimento → LinkedHashMap.
Il tipo di chiave è un enum → EnumMap. Più veloce di TreeMap e naturalmente ordinato.

Tutte e quattro implementano lo stesso contratto Map, quindi passare da una all'altra di solito è una modifica di una riga nel costruttore.

Un pattern utile: usa una HashMap per costruire la mappa velocemente, poi new TreeMap<>(hashMap) una volta sola per presentare una vista ordinata alla fine. Costruisci veloce, presenta ordinato.

Un esempio pratico: ricerca in un calendario, query su intervalli, chiave con comparatore

Il programma seguente usa una TreeMap per modellare un piccolo "calendario eventi" con chiave in minuti-dalla-mezzanotte. Dimostra l'API di navigazione per "qual è il prossimo evento dopo X" e "tutto prima di Y," mostra la vista live della sub-map, e rivela la trappola dell'uguaglianza per comparatore con una mappa case-insensitive.

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);
  }
}

Cosa ricavare dall'esecuzione:

Il calendario stampa in ordine cronologico senza alcun ordinamento esplicito. L'aggiunta di "coffee" alle 11:30 l'ha inserito automaticamente nel posto giusto.
Abbiamo fatto una query alle 11:00. ceilingEntry(11*60) restituisce la voce successiva alle 11:00 o dopo, che è il pranzo delle 13:00 (il design review delle 10:30 è prima delle 11:00, quindi non è idoneo). lowerEntry(11*60) restituisce la voce più recente strettamente prima delle 11:00, il design review delle 10:30. Entrambe sono O(log n).
La sub-map morning è una vista live — coffee è apparsa in essa dopo che l'abbiamo inserita nella mappa originale. Se avessimo inserito "midnight snack" alle 23:00, la vista lo avrebbe ignorato (fuori dall'intervallo).
pollFirstEntry ha svuotato ripetutamente l'evento successivo. È una coda di priorità per poveri quando hai anche bisogno di ricerche per chiave, cosa che una vera PriorityQueue non può darti.
La mappa case-insensitive ha collassato "Java" e "JAVA" in un'unica voce — con chiave "Java" originale ma con il valore del secondo put 2. Uguaglianza per comparatore, non uguaglianza per equals.

Cosa c'è dopo

Le quattro implementazioni di mappa moderne — HashMap, LinkedHashMap, TreeMap e ConcurrentHashMap — sono quelle a cui ricorrere nel nuovo codice. Ce n'è un'altra nel JDK che le precede tutte e che si vede ancora occasionalmente nel vecchio codice: Hashtable. Vale la pena sapere perché esiste, perché è quasi sempre la scelta sbagliata oggi, e come sostituirla.

Esercitati

Pratica

Una `TreeMap<Integer, String>` contiene le chiavi `10, 20, 30, 40`. Cosa restituisce `tree.floorKey(25)`?

`20` — la chiave più grande minore o uguale a 25`30` — la chiave più piccola maggiore o uguale a 25`25` — la chiave viene inserita con valore null e restituita`null` — `floorKey` restituisce una chiave solo quando è una corrispondenza esatta nella mappa