O framework de coleções do Java: listas, sets, maps e filas

Todo programa Java que lida com mais de uma coisa ao mesmo tempo usa java.util. O framework é pequeno o bastante para ser aprendido por inteiro — um punhado de interfaces e uma dúzia de implementações que você vai realmente usar —, mas detalhado o bastante para que escolher LinkedList onde cabia ArrayList, ou HashMap onde era preciso TreeMap, custe silenciosamente desempenho ou correção. Este guia apresenta a hierarquia, o modelo de custos, as regras de hashing e de ordem e as operações que desenvolvedores experientes usam no dia a dia. O código tem como alvo o Java 21.

A hierarquia de interfaces

O framework separa o que uma coleção promete (as interfaces) de como ela armazena os dados (as implementações). Programe contra a interface e escolha a implementação no momento da construção.

Iterable
└── Collection
    ├── List          ordered, indexed, duplicates allowed
    ├── Set           no duplicates
    │   └── SortedSet → NavigableSet   sorted by natural order or Comparator
    └── Queue         head-first access
        └── Deque     both ends

Map (not a Collection)   key → value, unique keys
└── SortedMap → NavigableMap

Map fica fora de Collection de propósito: um map é um conjunto de associações, não um saco de elementos, e seus métodos keySet(), values() e entrySet() são as views pelas quais você o trata como uma coleção.

O Java 21 adicionou as coleções sequenciadas (JEP 431): SequencedCollection, SequencedSet e SequencedMap dão a List, Deque, LinkedHashSet, LinkedHashMap e aos tipos ordenados métodos uniformes getFirst(), getLast(), addFirst(), removeLast() e reversed(). Antes do 21, era preciso escrever list.get(list.size() - 1) ou percorrer um ListIterator de trás para frente.

Listas

Uma List é uma sequência ordenada com acesso por posição. Duas implementações importam.

ArrayList guarda os elementos num array que cresce (cerca de metade do tamanho) quando fica cheio. O acesso por índice é de tempo constante, adicionar no fim é de tempo constante amortizado, e inserir ou remover no meio custa deslocar a parte final na memória — rápido na prática, porque System.arraycopy é um laço nativo bem enxuto. A iteração aproveita bem o cache. É a lista padrão.

LinkedList é uma cadeia de nós duplamente encadeados. O acesso por posição caminha a partir de uma das pontas, então get(i) é linear; cada nó é um objeto separado com dois ponteiros, de modo que a memória ocupada é de três a quatro vezes a de um ArrayList para elementos pequenos, e a iteração fica pulando pelo heap. Ela só ganha na remoção num cursor já posicionado por um ListIterator. Também implementa Deque, mas a ArrayDeque faz esse trabalho melhor.

List<String> hosts = new ArrayList<>(List.of("db1", "db2", "cache"));
hosts.add("queue");
hosts.set(0, "db-primary");
hosts.remove("cache");               // remove by value (first match)
hosts.remove(0);                      // remove by index — beware with List<Integer>
String last = hosts.getLast();        // Java 21
hosts.sort(Comparator.naturalOrder());

A armadilha da sobrecarga de remove é real: List<Integer> tem tanto remove(int index) quanto remove(Object o), e list.remove(3) escolhe a versão por índice. Escreva list.remove(Integer.valueOf(3)) para remover por valor.

Sets e o contrato de hashing

Um Set rejeita duplicatas, sendo "duplicata" um elemento para o qual equals retorna true. Como ele as detecta depende da implementação.

HashSet guarda os elementos numa tabela hash. add, contains e remove são de tempo constante em média; a ordem de iteração não é especificada e pode mudar quando o set é redimensionado. Ele depende do contrato de Object: elementos iguais segundo equals precisam ter o mesmo hashCode. Quebre esse contrato (sobrescrevendo um sem o outro) e o set passa a guardar "duplicatas" ou deixa de encontrar elementos que contém. Desde o Java 8, um bucket com muitas chaves em colisão vira uma árvore balanceada em vez de uma lista encadeada, então funções de hash patológicas fazem menos estrago, mas um bom hashCode continua importando.

LinkedHashSet é um HashSet que também mantém uma lista encadeada com a ordem de inserção. Mesmo custo, iteração previsível, um pouco mais de memória. Use quando testes, logs ou usuários forem ver a ordem.

TreeSet mantém os elementos ordenados numa árvore rubro-negra, pela ordem natural (Comparable) ou por um Comparator que você fornece. As operações são logarítmicas e você ganha consultas por intervalo: headSet, tailSet, subSet, ceiling, floor. Um TreeSet decide a igualdade com compareTo ou compare, não com equals, então um comparator que retorna 0 para elementos distintos vai descartar um deles.

EnumSet é um vetor de bits especializado em elementos de enum: minúsculo, extremamente rápido e a escolha certa sempre que o tipo dos elementos for um enum.

record Tag(String name) implements Comparable<Tag> {
    @Override public int compareTo(Tag o) { return name.compareToIgnoreCase(o.name); }
}

Set<Tag> tags = new TreeSet<>();
tags.add(new Tag("Java"));
tags.add(new Tag("java"));           // compareTo says equal → not added
System.out.println(tags.size());     // 1, even though the records are not equals()

Maps

Um Map associa chaves únicas a valores. As mesmas três estratégias de armazenamento se aplicam.

A interface Map ganhou no Java 8 um conjunto de métodos que substituem a velha dança de "verificar e depois dar put":

Map<String, List<String>> byDept = new HashMap<>();

// Before Java 8
List<String> names = byDept.get("eng");
if (names == null) { names = new ArrayList<>(); byDept.put("eng", names); }
names.add("Ada");

// Now
byDept.computeIfAbsent("eng", k -> new ArrayList<>()).add("Ada");

Map<String, Integer> counts = new HashMap<>();
counts.merge("java", 1, Integer::sum);            // increment or initialise
int hits = counts.getOrDefault("kotlin", 0);
counts.putIfAbsent("scala", 0);
counts.replaceAll((k, v) -> v * 2);

computeIfAbsent, merge e getOrDefault são os três para guardar de cor. Percorra um map por entrySet() quando precisar das duas metades; percorrer keySet() e chamar get para cada chave faz duas buscas por entrada.

O LinkedHashMap tem uma flag no construtor para ordem de acesso e um hook removeEldestEntry que, juntos, permitem montar um cache LRU limitado em umas dez linhas — pergunta clássica de entrevista e, de vez em quando, uma ferramenta útil em produção.

As chaves precisam ser estáveis. Uma chave cujo hashCode muda depois da inserção (um objeto mutável com hash baseado nos seus campos) se perde: o map procura no bucket do novo hash e nunca a encontra. Use chaves imutáveis — strings, números, enums, records.

Filas, deques e pilhas

Queue oferece acesso pela cabeça com duas famílias de métodos: add/remove/element lançam exceção quando não conseguem prosseguir, enquanto offer/poll/peek retornam false ou null. Deque estende isso às duas pontas.

ArrayDeque é um array circular redimensionável e a implementação certa tanto para uma fila FIFO quanto para uma pilha LIFO. É mais rápida que LinkedList nos dois casos e mais rápida que a classe legada Stack, que é sincronizada e estende Vector — não use Stack em código novo.

PriorityQueue é um heap binário que sempre devolve o menor elemento pela ordem natural ou pelo comparator. Inserção e remoção são logarítmicas; percorrer a fila não devolve os elementos em ordem, só poll() garante isso.

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop());   // second

Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
pq.addAll(List.of(3, 9, 1));
System.out.println(pq.poll());     // 9

As variantes bloqueantes — ArrayBlockingQueue, LinkedBlockingQueue — adicionam put e take, que esperam, e fazem parte da caixa de ferramentas de concorrência.

Iteração, ordem e modificação

O laço for-each é compilado para um Iterator: hasNext(), next(), e repete. A maioria das coleções não concorrentes é fail-fast: se a coleção sofrer uma modificação estrutural durante a iteração por qualquer coisa que não seja o próprio remove do iterator, o next() seguinte lança ConcurrentModificationException. É uma detecção de bug feita com o melhor esforço possível, não uma garantia de thread safety.

List<Order> orders = ...;

// Wrong: throws ConcurrentModificationException
for (Order o : orders) if (o.isCancelled()) orders.remove(o);

// Right, and shortest
orders.removeIf(Order::isCancelled);

// Also right, when you need the iterator anyway
for (Iterator<Order> it = orders.iterator(); it.hasNext(); ) {
    if (it.next().isCancelled()) it.remove();
}

A ordenação pode ser feita na própria lista — list.sort(comparator) ou Collections.sort(list) — ou em uma nova coleção com um stream. Comparator se compõe bem: Comparator.comparing(Person::lastName).thenComparing(Person::firstName).reversed(), com nullsFirst/nullsLast para campos opcionais. A ordenação é um merge sort estável (TimSort), então elementos iguais mantêm a ordem relativa, o que importa quando você ordena por uma chave e depois por outra.

Coleções imutáveis e views

O Java 9 introduziu factories práticas: List.of(...), Set.of(...), Map.of(k1, v1, ...), Map.ofEntries(...), e o Java 10 adicionou List.copyOf, Set.copyOf e Map.copyOf. Elas devolvem coleções não modificáveis: qualquer método mutador lança UnsupportedOperationException, elementos null são rejeitados e Set.of/Map.of lançam exceção com chaves duplicadas. A ordem de iteração delas é propositalmente aleatória a cada execução da JVM, para que ninguém dependa dela por acidente.

Diferencie três coisas que parecem iguais:

• Coleção imutável (List.of): não pode mudar, nunca.
• View não modificável (Collections.unmodifiableList(inner)): você não consegue alterá-la pela view, mas, se a original mudar, a view reflete a mudança. Boa para expor estado interno sem copiar.
• Cópia defensiva (new ArrayList<>(inner) ou List.copyOf(inner)): um snapshot que nenhum dos lados consegue afetar.

As views estão por todo o framework: map.keySet(), list.subList(a, b) e Arrays.asList(array) são janelas vivas para outros dados. Remover de keySet() remove do map; limpar uma subList remove aquele intervalo da lista. Poderoso quando é intencional, surpreendente quando não é.

Collections também oferece synchronizedList e companhia, que envolvem cada método num lock. Eles tornam seguras as chamadas individuais, mas não sequências de chamadas (verificar e depois agir) nem a iteração, e foram em grande parte substituídos pelas coleções de java.util.concurrent.

Escolhendo uma implementação

Informe uma capacidade inicial quando souber o tamanho: new ArrayList<>(10_000) ou HashMap.newHashMap(expected) (Java 19) evitam uma série de redimensionamentos. E dimensione a coleção que você devolve: devolver List.of() ou Collections.emptyList() não custa nada, enquanto alocar um ArrayList vazio a cada chamada vai somando.

Erros comuns

Chaves de hash mutáveis. Um Set<Point> em que Point tem setters, ou um map cuja chave é uma lista à qual você depois adiciona itens, perde elementos silenciosamente. Chaves precisam ser imutáveis.

Depender da ordem do HashMap. Ela não é especificada e muda com redimensionamentos e com a versão do JDK. Testes que passam por sorte quebram depois de um refactoring.

Arrays.asList em um array de primitivos. Arrays.asList(new int[]{1, 2}) gera uma List<int[]> com um único elemento. Use IntStream.of(...).boxed().toList() ou um Integer[].

Tratar subList como cópia. É uma view; mudanças estruturais na lista pai a invalidam, e mudanças feitas por meio dela alteram a lista pai.

Usar LinkedList como fila ou Stack como pilha. ArrayDeque é mais rápida e mais leve nos dois casos.

Null nas coleções modernas. List.of, Map.of e ConcurrentHashMap rejeitam null. Decida de antemão se null tem significado nos seus dados; em geral não tem, e Optional ou um valor sentinela explícito é mais claro.

Percorrer keySet() e depois chamar get. Duas buscas por entrada; percorra entrySet().

Um comparator de TreeSet inconsistente com equals. Elementos que o comparator considera iguais são deduplicados mesmo que equals discorde. Torne-os consistentes ou documente a diferença.

Principais pontos

• Declare variáveis pela interface (List, Set, Map, Deque) e escolha a implementação na construção.
• ArrayList, HashSet, HashMap e ArrayDeque são as escolhas padrão; recorra a Linked* quando a ordem de iteração importar e a Tree* quando precisar de ordenação ou de consultas por intervalo.
• Coleções baseadas em hash dependem de um par equals/hashCode consistente e de chaves que nunca mudam; as baseadas em árvore dependem apenas do comparator.
• Durante a iteração, modifique a coleção só por removeIf ou pelo iterator; qualquer outra coisa lança ConcurrentModificationException.
• List.of e companhia são imutáveis e avessos a null; Collections.unmodifiable* e subList são views vivas; copyOf e os construtores de cópia são snapshots.
• Use computeIfAbsent, merge e getOrDefault em vez de verificar e depois dar put, e entrySet() para iterar.