Listas, Conjuntos e Mapas — o Collections Framework

As estruturas de dados prontas da biblioteca padrão, o que cada uma custa e como escolher a certa para cada problema.

Em "Escreva uma Vez para Todo Tipo" você construiu uma Lista<E>: um array que cresce sozinho, escondido atrás de uma interface genérica. Foi o primeiro passo. A biblioteca padrão traz dezenas de estruturas desse tipo, prontas, testadas e otimizadas ao longo de mais de vinte e cinco anos: o Collections Framework. Nesta aula você vai conhecer as três famílias principais, listas, conjuntos e mapas, além das filas, e vai aprender o critério que mais importa na escolha entre elas: quanto custa cada operação.

Um mapa do framework

O framework separa, como recomendou "Contratos sem Implementação", os contratos das implementações:

Collection<E>                      Map<K, V>
├── List<E>                        ├── HashMap
│   ├── ArrayList                  ├── LinkedHashMap
│   └── LinkedList                 └── TreeMap
├── Set<E>
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet
└── Queue<E> / Deque<E>
    ├── ArrayDeque
    └── PriorityQueue

Os nomes da esquerda de cada ramo, como List, Set e Map, são interfaces. Os da direita são classes. O nome de cada classe descreve a técnica usada por dentro: Array para um array que cresce, Hash para uma tabela de espalhamento baseada no hashCode de "Iguais ou o Mesmo?", Tree para uma árvore ordenada, e Linked para elementos encadeados uns aos outros.

A consequência prática: declare as variáveis pelo tipo da interface e escolha a implementação só no new:

List<String> tarefas = new ArrayList<>();

Todo o código que usa tarefas depende só do contrato List. Se amanhã outra implementação for mais adequada, só a linha do new muda. Pela mesma razão, métodos devem receber e devolver interfaces, como List<String>, e não classes concretas.

Listas: sequências com posição

Uma List guarda elementos numa ordem, acessíveis por posição, e aceita repetições. A implementação padrão é o ArrayList, a versão profissional da Lista que você construiu:

void main() {
    List<String> tarefas = new ArrayList<>();
    tarefas.add("estudar genéricos");
    tarefas.add("fazer exercícios");
    tarefas.add(0, "revisar a aula anterior");   // insere na posição 0
    tarefas.add("descansar");

    IO.println(tarefas);
    IO.println(tarefas.size() + " tarefas; a segunda é: " + tarefas.get(1));

    tarefas.set(3, "descansar um pouco");        // substitui
    tarefas.remove("fazer exercícios");          // remove pelo valor
    IO.println(tarefas.contains("estudar genéricos") + " " + tarefas.indexOf("descansar um pouco"));

    IO.println(tarefas.getFirst() + " | " + tarefas.getLast());
    IO.println(tarefas.reversed());

    for (String t : tarefas) {
        IO.println("- " + t);
    }
}

[revisar a aula anterior, estudar genéricos, fazer exercícios, descansar]
4 tarefas; a segunda é: estudar genéricos
true 2
revisar a aula anterior | descansar um pouco
[descansar um pouco, estudar genéricos, revisar a aula anterior]
- revisar a aula anterior
- estudar genéricos
- descansar um pouco

A maioria dos métodos se explica pelo nome. contains e indexOf usam equals, então funcionam com as classes de valor de "Iguais ou o Mesmo?". O for-each de "Muitos Valores sob um Nome" funciona com qualquer coleção. getFirst, getLast e reversed vêm das coleções sequenciadas, uma interface acrescentada no Java 21 a todas as coleções que têm uma ordem definida. Antes dela, pegar o último elemento de uma lista exigia lista.get(lista.size() - 1).

A armadilha do remove

List tem dois métodos remove: remove(int indice) e remove(Object elemento). Numa lista de inteiros, a sobrecarga de "Dividir para Resolver" cria uma armadilha:

List<Integer> numeros = new ArrayList<>(List.of(10, 20, 30, 2));
numeros.remove(2);                    // remove a POSIÇÃO 2 (o 30)
IO.println(numeros);                  // [10, 20, 2]
numeros.remove(Integer.valueOf(2));   // remove o VALOR 2
IO.println(numeros);                  // [10, 20]

Um int literal escolhe a versão por índice, porque ela não exige autoboxing. Para remover pelo valor, é preciso passar um Integer de forma explícita.

ArrayList ou LinkedList?

A biblioteca também tem o LinkedList, em que cada elemento guarda referências para o anterior e o próximo, como as listas encadeadas que os cursos de C constroem à mão. Na teoria, ele insere e remove no meio sem deslocar elementos. Na prática, para chegar ao meio ele precisa percorrer a lista nó por nó, e os nós espalhados pela memória são muito mais lentos de percorrer do que um array contíguo. Em quase todos os casos reais, o ArrayList é mais rápido. Até Joshua Bloch, que escreveu o LinkedList, disse publicamente que não o usa. Use ArrayList como padrão.

Listas imutáveis

Para listas que não devem mudar, existe List.of:

List<String> fixa = List.of("a", "b");
fixa.add("c");      // UnsupportedOperationException

A lista criada por List.of rejeita qualquer alteração, e também rejeita elementos null na criação. List.copyOf(outra) cria uma cópia imutável de uma lista existente, que não muda quando a original muda. É exatamente o que faltava ao record Turma de "Dados sem Cerimônia":

record Turma(String nome, List<String> alunos) {
    Turma {
        alunos = List.copyOf(alunos);   // cópia defensiva e imutável
    }
}

List<String> nomes = new ArrayList<>(List.of("Ana", "Bia"));
Turma t = new Turma("A", nomes);
nomes.set(0, "Zeca");
IO.println(t);                                                  // Turma[nome=A, alunos=[Ana, Bia]]
IO.println(t.equals(new Turma("A", List.of("Ana", "Bia"))));    // true

Os três problemas do exercício 2 daquela aula desaparecem. A turma não muda quando a lista original muda. t.alunos().add(...) lança exceção. E o equals e o toString gerados funcionam, porque listas comparam conteúdo e se imprimem legivelmente, ao contrário dos arrays.

Cuidado com um parente enganoso, o Arrays.asList(array). Ele devolve uma lista que é uma visão do array: alterar um elemento da lista altera o array, e vice-versa, e a lista tem tamanho fixo, então add lança UnsupportedOperationException. Prefira List.of para listas fixas e new ArrayList<>(List.of(...)) para listas que vão crescer, como nos exemplos desta aula.

Removendo durante o percurso

Um erro que todo programador Java comete uma vez:

List<String> nomes = new ArrayList<>(List.of("Ana", "Bruno", "Bia", "Caio"));
for (String n : nomes) {
    if (n.startsWith("B")) {
        nomes.remove(n);        // ConcurrentModificationException
    }
}

O for-each usa por baixo um iterador, um objeto que percorre a coleção. Quando a coleção é alterada por fora do iterador durante o percurso, ele detecta a mudança e lança ConcurrentModificationException, em vez de continuar com posições que não fazem mais sentido. O nome engana: não há nada de "concorrente", no sentido de threads, acontecendo. Para remover durante o percurso, use o próprio iterador:

Iterator<String> it = nomes.iterator();
while (it.hasNext()) {
    if (it.next().startsWith("B")) {
        it.remove();            // remove pelo iterador: seguro
    }
}
IO.println(nomes);              // [Ana, Caio]

Em "Comportamento como Valor" você vai conhecer uma forma de uma linha para isso, removeIf.

Conjuntos: sem repetição

Um Set não aceita elementos repetidos, segundo o equals. As três implementações diferem na ordem em que os elementos aparecem:

String[] visitas = {"Recife", "Olinda", "Recife", "Caruaru", "Olinda", "Arcoverde"};

Set<String> hash = new HashSet<>();
Set<String> linked = new LinkedHashSet<>();
Set<String> tree = new TreeSet<>();
for (String cidade : visitas) {
    hash.add(cidade);
    linked.add(cidade);
    tree.add(cidade);
}

HashSet:       [Arcoverde, Recife, Caruaru, Olinda]
LinkedHashSet: [Recife, Olinda, Caruaru, Arcoverde]
TreeSet:       [Arcoverde, Caruaru, Olinda, Recife]

As repetições desapareceram nos três. O HashSet não garante ordem nenhuma: a ordem depende dos hashCode e pode mudar entre versões do Java, então nunca dependa dela. O LinkedHashSet mantém a ordem de inserção. O TreeSet mantém os elementos ordenados, e é assunto da próxima aula.

O add devolve um boolean que diz se o elemento era novo: hash.add("Recife") devolve false. Isso permite detectar duplicatas sem um teste separado. As operações de conjunto da matemática também estão lá:

Set<Integer> a = new TreeSet<>(List.of(1, 2, 3, 4));
Set<Integer> b = Set.of(3, 4, 5);

Set<Integer> uniao = new TreeSet<>(a);    uniao.addAll(b);      // [1, 2, 3, 4, 5]
Set<Integer> inter = new TreeSet<>(a);    inter.retainAll(b);   // [3, 4]
Set<Integer> dif = new TreeSet<>(a);      dif.removeAll(b);     // [1, 2]

Os conjuntos baseados em hash dependem totalmente do contrato de "Iguais ou o Mesmo?": uma classe com equals e sem hashCode quebra o HashSet, e um elemento que muda depois de inserido se perde dentro dele.

Mapas: chaves e valores

Um Map<K, V> associa chaves a valores, como um dicionário associa palavras a definições. Cada chave aparece uma vez só. Contar as palavras de um texto é o exemplo clássico:

String texto = "o rato roeu a roupa do rei de roma e a rainha roeu o resto";
Map<String, Integer> contagem = new TreeMap<>();
for (String palavra : texto.split(" ")) {
    int atual = contagem.getOrDefault(palavra, 0);
    contagem.put(palavra, atual + 1);
}
IO.println(contagem);

{a=2, de=1, do=1, e=1, o=2, rainha=1, rato=1, rei=1, resto=1, roeu=2, roma=1, roupa=1}

split(" ") divide o texto num array de palavras. getOrDefault devolve o valor da chave ou um padrão, se ela não existir. put grava o valor, substituindo o anterior se a chave já existia. Com TreeMap, as chaves ficam em ordem alfabética.

As operações principais:

contagem.get("roeu");            // 2
contagem.get("gato");            // null: a chave não existe
contagem.containsKey("rei");     // true

for (Map.Entry<String, Integer> entrada : contagem.entrySet()) {
    if (entrada.getValue() > 1) {
        IO.println(entrada.getKey() + " aparece " + entrada.getValue() + " vezes");
    }
}

a aparece 2 vezes
o aparece 2 vezes
roeu aparece 2 vezes

O entrySet() devolve os pares chave-valor, e é a forma eficiente de percorrer um mapa quando você precisa dos dois. Também existem keySet(), só com as chaves, e values(), só com os valores.

Atenção a um detalhe: get devolve null quando a chave não existe. Guardar o resultado num int desembrulha o null e causa a NullPointerException de "Escreva uma Vez para Todo Tipo": int n = mapa.get("ausente"); quebra. Use getOrDefault ou teste com containsKey. E o put devolve o valor anterior da chave, ou null se ela era nova.

As implementações seguem o padrão dos conjuntos: HashMap sem ordem, LinkedHashMap na ordem de inserção e TreeMap ordenado pelas chaves. Como os mapas com ordem são sequenciados, eles oferecem firstEntry() e lastEntry(), disponíveis quando a variável é declarada como SequencedMap:

SequencedMap<String, String> capitais = new LinkedHashMap<>();
capitais.put("PE", "Recife");
capitais.put("BA", "Salvador");
capitais.put("CE", "Fortaleza");
IO.println(capitais.firstEntry() + " " + capitais.lastEntry());   // PE=Recife CE=Fortaleza

A regra das chaves é a mesma dos elementos de conjunto: use chaves imutáveis, com equals e hashCode corretos. String, números, enums e records são as chaves ideais.

Filas e pilhas

Uma fila (queue) atende na ordem de chegada: o primeiro a entrar é o primeiro a sair. Uma pilha (stack) funciona ao contrário, como uma pilha de pratos: o último a entrar é o primeiro a sair. A interface Deque (double-ended queue, fila de duas pontas) serve para as duas, e a implementação padrão é o ArrayDeque:

Deque<String> pilha = new ArrayDeque<>();
pilha.push("página 1");
pilha.push("página 2");
pilha.push("página 3");
IO.println("voltar para: " + pilha.pop() + ", depois " + pilha.peek());
// voltar para: página 3, depois página 2

Queue<String> fila = new ArrayDeque<>();
fila.offer("cliente A");
fila.offer("cliente B");
fila.offer("cliente C");
IO.println("atendendo: " + fila.poll() + "; restam " + fila);
// atendendo: cliente A; restam [cliente B, cliente C]

O botão "voltar" de um navegador é uma pilha. Uma fila de atendimento ou de impressão é uma fila. A biblioteca ainda tem uma classe antiga chamada Stack, dos tempos do Java 1.0, que não deve ser usada em código novo: ArrayDeque a substitui com vantagens. Uma fila em que o próximo a sair é o mais prioritário, e não o mais antigo, é a PriorityQueue, que aparece na próxima aula.

O que cada operação custa

A diferença entre as coleções não está no que elas fazem, e sim em quanto custa fazer. Um teste: procurar 10 mil valores numa lista e num conjunto, cada um com 100 mil números.

List<Integer> lista = new ArrayList<>();
Set<Integer> conjunto = new HashSet<>();
for (int i = 0; i < 100_000; i++) {
    lista.add(i);
    conjunto.add(i);
}
// 10.000 buscas com contains em cada um...

Na máquina em que este artigo foi testado (JDK 27), a lista levou cerca de 420 milissegundos, e o conjunto, menos de 2 milissegundos. Uma diferença de mais de duzentas vezes, para a mesma operação. O contains da lista compara elemento por elemento, como a busca linear de "Muitos Valores sob um Nome". O do HashSet calcula o hashCode e vai direto à posição certa.

Programadores descrevem esses custos com a notação O grande, que diz como o tempo de uma operação cresce com o número de elementos, n:

• O(1), tempo constante: o custo não depende do tamanho. Acessar uma posição de ArrayList, buscar num HashSet ou HashMap.
• O(log n), tempo logarítmico: dobrar o tamanho acrescenta um passo. Buscar num TreeSet ou TreeMap. Com um milhão de elementos, são cerca de 20 passos.
• O(n), tempo linear: dobrar o tamanho dobra o tempo. contains numa lista, inserir no início de um ArrayList.

\* Em média: de vez em quando o array interno precisa dobrar de tamanho, como na sua Lista, mas o custo das cópias, distribuído entre todas as inserções, é constante.

Como escolher

Um roteiro que resolve quase todos os casos:

• Precisa de uma sequência, com posição e repetições? ArrayList.
• Precisa saber rapidamente se algo já existe, sem repetições? HashSet. Se a ordem de inserção importa, LinkedHashSet. Se precisa de ordem de valor, TreeSet.
• Precisa encontrar um valor a partir de uma chave? HashMap, ou LinkedHashMap e TreeMap pelos mesmos critérios de ordem.
• Precisa processar na ordem de chegada, ou na ordem inversa? ArrayDeque.
• A coleção não vai mudar? List.of, Set.of, Map.of.

O erro mais comum não é escolher entre implementações parecidas: é usar uma lista onde o problema pede um conjunto ou um mapa, e pagar O(n) em cada busca. Um sistema que verifica se um e-mail já está cadastrado percorrendo uma lista funciona perfeitamente com 100 usuários e trava com 100 mil.

Resta uma pergunta que esta aula deixou de lado: como o TreeSet e o TreeMap sabem em que ordem colocar os elementos? Com textos e números, eles usam a ordem natural. Mas e com um Aluno? Por nome, por nota ou por idade? E se a ordem natural dos textos, com maiúsculas antes de minúsculas e acentos no fim, não for a que uma pessoa espera?

Fontes e leituras recomendadas

• Oracle, The Java Tutorials, "Collections": https://docs.oracle.com/javase/tutorial/collections/index.html. A trilha completa, com cada interface e as implementações comparadas.
• JEP 431, "Sequenced Collections": https://openjdk.org/jeps/431. A proposta do Java 21 que acrescentou getFirst, getLast, reversed e as interfaces sequenciadas, com a motivação.
• Documentação do pacote java.util (Java SE 25): https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/package-summary.html. A lista completa de coleções e utilitários. As páginas de cada classe informam o custo das operações.
• Joshua Bloch, Effective Java, 3ª edição, item 64: "Refer to objects by their interfaces", o argumento completo para declarar List em vez de ArrayList.
• Robert Sedgewick e Kevin Wayne, Algorithms, 4ª edição (Addison-Wesley), capítulo 1.4 e capítulo 3: https://algs4.cs.princeton.edu/home/. A análise de desempenho de algoritmos e as estruturas de busca (tabelas de hash e árvores balanceadas), com código em Java.

Exercícios

Exercício 1

Sem rodar, diga o conteúdo final da lista:

List<Integer> v = new ArrayList<>(List.of(5, 1, 4, 1, 3));
v.remove(1);
v.remove(Integer.valueOf(1));
v.add(0, 9);
v.set(v.size() - 1, 7);

Exercício 2

Escolha a coleção mais adequada para cada caso e justifique: (a) os e-mails já cadastrados num sistema, para recusar duplicatas; (b) o histórico de comandos digitados num terminal, para navegar com a seta para cima; (c) os produtos de uma loja, a serem encontrados pelo código de barras; (d) as músicas de uma playlist, na ordem escolhida pelo usuário, podendo repetir; (e) os países com medalhas numa olimpíada, exibidos em ordem alfabética, cada um com o número de medalhas.

Exercício 3

Escreva um programa que leia uma frase e mostre quantas vezes cada letra aparece, em ordem alfabética, ignorando espaços e maiúsculas. Por exemplo, "Ana ama" deve mostrar a=4, m=1, n=1.

void main() {
    String frase = IO.readln("Frase: ").toLowerCase();
    Map<Character, Integer> frequencia = new TreeMap<>();
    for (int i = 0; i < frase.length(); i++) {
        char c = frase.charAt(i);
        if (c == ' ') {
            continue;
        }
        frequencia.put(c, frequencia.getOrDefault(c, 0) + 1);
    }
    IO.println(frequencia);
}

Exercício 4

O trecho abaixo lança ConcurrentModificationException. Explique por quê e corrija-o de modo que remova todos os números negativos.

List<Integer> valores = new ArrayList<>(List.of(3, -1, 4, -5, 9));
for (Integer v : valores) {
    if (v < 0) {
        valores.remove(v);
    }
}

Iterator<Integer> it = valores.iterator();
while (it.hasNext()) {
    if (it.next() < 0) {
        it.remove();
    }
}

Exercício 5

Uma agenda guarda vários telefones por pessoa. Declare a estrutura adequada e escreva um método adicionarTelefone(String nome, String telefone) e um método que devolva os telefones de uma pessoa, ou uma lista vazia se ela não estiver na agenda.

Map<String, List<String>> agenda = new TreeMap<>();

void adicionarTelefone(String nome, String telefone) {
    List<String> telefones = agenda.get(nome);
    if (telefones == null) {
        telefones = new ArrayList<>();
        agenda.put(nome, telefones);
    }
    telefones.add(telefone);
}

List<String> telefonesDe(String nome) {
    return List.copyOf(agenda.getOrDefault(nome, List.of()));
}