Classe Java TreeMap | W3Docs Learn Java

O que é um TreeMap

TreeMap<K, V> é o Map que mantém suas chaves ordenadas. Internamente é uma árvore rubro-negra — a mesma árvore de busca binária auto-balanceada que suporta o TreeSet — e toda operação é O(log n): put, get, remove, a primeira chave, a última chave, consultas por intervalo. O custo em log é compensado pela API de navegação em NavigableMap<K, V>: floor, ceiling, lower, higher, sub-map, head-map, tail-map, visões descendentes. Nada disso é possível em uma tabela hash sem uma ordenação completa antes.

Se você alguma vez se pegar fazendo new TreeMap<>(hashMap) no final de uma função para "ordenar as entradas," esse é o sinal de que TreeMap deveria ter sido o tipo desde o início.

Duas formas de definir a ordem das chaves

Um TreeMap precisa comparar chaves de alguma forma. Assim como no TreeSet:

Ordenação natural — o tipo da chave implementa Comparable<K>. Strings, wrappers numéricos, datas e seus próprios tipos record que implementam Comparable são elegíveis.
Um Comparator<K> passado ao construtor — use quando a ordem natural não existe ou não corresponde ao que você quer. (Veja Comparable vs Comparator para entender a diferença entre os dois.)

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

Assim como no TreeSet, a igualdade é determinada pelo compareTo retornando 0, não por equals. Duas chaves que o comparador considera iguais colapsam em uma única entrada — o segundo put sobrescreve o primeiro. Com o chaveamento por String.CASE_INSENSITIVE_ORDER, inserir "Java" e depois "JAVA" resulta em uma única entrada cuja chave é o "Java" original e cujo valor é o valor do segundo put. Isso quase nunca é o que você quer por acidente.

A API NavigableMap

A interface que um TreeMap implementa oferece muitas operações que um Map comum não possui:

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

É por isso que o TreeMap existe. "Encontrar o evento mais próximo antes das 9h" é headMap(9am).lastEntry() — uma única busca em tempo logarítmico. A mesma operação em um HashMap teria que percorrer todas as chaves.

As visões de sub-map são dinâmicas

subMap, headMap e tailMap retornam visões do mapa original — não cópias. Alterações feitas por meio da visão se propagam de volta, e alterações no original que se enquadrem no intervalo da visão aparecem na visão. As visões também impõem o intervalo: tentar inserir uma chave fora do intervalo por meio da visão lança IllegalArgumentException. É assim que a iteração delimitada por intervalo permanece segura mesmo quando você altera durante a varredura.

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 é rejeitado (para chaves)

Você não pode ter uma chave null em um TreeMap pelo mesmo motivo que o TreeSet as rejeita: não há como chamar compareTo em null de forma sensata. O primeiro put(null, ...) lança NullPointerException. Valores null são permitidos.

Quando escolher `TreeMap`

Fluxo de decisão:

Você precisa de iteração ordenada por chave ou consultas por intervalo nas chaves → TreeMap. Única opção.
Você precisa de busca rápida e a ordem não importa → HashMap. O(1) vence.
Você precisa de busca rápida e iteração na ordem de inserção → LinkedHashMap.
O tipo da chave é um enum → EnumMap. Mais rápido que TreeMap e naturalmente ordenado.

Todos os quatro implementam o mesmo contrato Map, então alternar entre eles geralmente é uma mudança de construtor de uma linha.

Um padrão útil: use um HashMap para construir o mapa rapidamente, depois new TreeMap<>(hashMap) uma vez para apresentar uma visão ordenada ao final. Construa rápido, apresente ordenado.

Um exemplo prático: consulta de agenda, consultas por intervalo, chaveamento por comparador

O programa abaixo usa um TreeMap para modelar uma pequena "agenda de eventos" chaveada por minutos-desde-meia-noite. Ele demonstra a API de navegação para "qual é o próximo evento após X" e "tudo antes de Y," mostra a visão dinâmica de sub-map e revela a armadilha da igualdade por comparador com um mapa sem diferenciação de maiúsculas e minúsculas.

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

O que observar na execução:

A agenda é exibida em ordem cronológica sem nenhuma ordenação explícita. Adicionar "coffee" às 11:30 o inseriu automaticamente no lugar correto.
Consultamos às 11:00. ceilingEntry(11*60) retorna a próxima entrada em ou após 11:00, que é o almoço das 13:00 (o design review das 10:30 é antes das 11:00, portanto não se qualifica). lowerEntry(11*60) retorna a entrada mais recente estritamente antes das 11:00, o design review das 10:30. Ambas são O(log n).
O sub-map morning é uma visão dinâmica — coffee apareceu nela após inserirmos no mapa original. Se tivéssemos inserido "midnight snack" às 23:00, a visão teria ignorado (fora do intervalo).
pollFirstEntry repetidamente drenava o próximo evento. Isso é uma fila de prioridade improvisada quando você também quer buscas por chave, o que um PriorityQueue real não pode fornecer.
O mapa sem diferenciação de maiúsculas e minúsculas colapsou "Java" e "JAVA" em uma única entrada — chaveada pelo "Java" original, mas com o valor do segundo put, 2. Igualdade por comparador, não igualdade por equals.

O que vem a seguir

As quatro implementações modernas de map — HashMap, LinkedHashMap, TreeMap e ConcurrentHashMap — são as que você deve usar em código novo. Há mais uma no JDK que as antecede a todas e você ainda a verá ocasionalmente em código legado: Hashtable. Vale a pena saber por que ela existe, por que hoje quase sempre é a escolha errada e como substituí-la.

Prática

Um `TreeMap<Integer, String>` contém as chaves `10, 20, 30, 40`. O que `tree.floorKey(25)` retorna?

`20` — a maior chave que é menor ou igual a 25`30` — a menor chave que é maior ou igual a 25`25` — a chave é inserida com um valor null e retornada`null` — `floorKey` só retorna uma chave quando é uma correspondência exata no mapa