equals, hashCode e como escolher uma coleção em Java

Um HashMap do Java encontra chaves com hashCode e equals, então um contrato quebrado ou uma chave alterada depois do put faz entradas sumirem. Veja as regras, por que o TreeSet usa compareTo e qual coleção escolher.

Um HashMap ou um HashSet confia em dois métodos de cada chave: hashCode, para decidir onde procurar, e equals, para decidir o que conta como igual. Erre qualquer um dos dois, ou mude uma chave depois de guardá-la, e a coleção para de encontrar, em silêncio, coisas que ainda estão dentro dela. Sem exceção, sem aviso, só null.

Este post trata dos contratos de equals e hashCode, de como um HashMap encontra uma chave, de por que uma chave alterada se perde, de por que o TreeSet usa compareTo no lugar, e de como escolher uma lista, um deque, um map ou uma coleção imutável. Todo programa abaixo rodou no Java 25, e a saída foi colada da execução. Para rodar um deles, salve como Main.java e rode java Main.java.

O contrato de equals, e um bug de simetria

Um método equals precisa se comportar como igualdade de verdade, ou as coleções dão respostas que dependem de qual lado perguntou. A parte sobre valores e referências trata de == versus equals, e a parte sobre records mostra o equals que os records escrevem para você. Esta seção é sobre escrever um à mão.

Aqui está um wrapper que tenta ajudar. Ele compara sem diferenciar maiúsculas de minúsculas com outros wrappers, e com strings comuns também:

final class CaseInsensitive {
    private final String key;

    CaseInsensitive(String text) {
        this.key = text.toLowerCase(Locale.ROOT);
    }

    @Override
    public boolean equals(Object other) {
        if (other instanceof CaseInsensitive c) {
            return key.equals(c.key);
        }
        if (other instanceof String s) {
            return key.equals(s.toLowerCase(Locale.ROOT));
        }
        return false;
    }

    @Override
    public int hashCode() {
        return key.hashCode();
    }
}

void main() {
    var name = new CaseInsensitive("Ana");
    IO.println("name.equals(\"ana\"): " + name.equals("ana"));
    IO.println("\"ana\".equals(name): " + "ana".equals(name));

    var wrappers = new ArrayList<Object>();
    wrappers.add(name);
    IO.println("wrappers contains \"ana\": " + wrappers.contains("ana"));

    var strings = new ArrayList<Object>();
    strings.add("ana");
    IO.println("strings contains name:  " + strings.contains(name));
}

Ele imprime:

name.equals("ana"): true
"ana".equals(name): false
wrappers contains "ana": false
strings contains name:  true

CaseInsensitive conhece String, mas String nunca ouviu falar de CaseInsensitive. Então a.equals(b) e b.equals(a) discordam. ArrayList.contains(x) chama x.equals(element), o que significa que a resposta muda conforme qual objeto está na lista e qual você está procurando.

Isso quebra a regra de simetria. O contrato de equals na documentação de Object tem cinco regras, para quaisquer x, y e z não nulos:

• Reflexiva: x.equals(x) é true.
• Simétrica: x.equals(y) é true exatamente quando y.equals(x) é true.
• Transitiva: se x.equals(y) e y.equals(z), então x.equals(z).
• Consistente: chamar de novo dá a mesma resposta, desde que nenhum dos objetos tenha mudado.
• Null: x.equals(null) é false, não uma exceção.

A correção é comparar só com o seu próprio tipo. Uma classe final importa aqui: se uma subclasse pudesse adicionar campos e ter o próprio equals, o mesmo problema de simetria voltaria entre pai e filho.

final class CaseInsensitive {
    private final String key;

    CaseInsensitive(String text) {
        this.key = text.toLowerCase(Locale.ROOT);
    }

    @Override
    public boolean equals(Object other) {
        return other instanceof CaseInsensitive c && key.equals(c.key);
    }

    @Override
    public int hashCode() {
        return key.hashCode();
    }
}

void main() {
    var a = new CaseInsensitive("Ana");
    var b = new CaseInsensitive("ANA");
    var c = new CaseInsensitive("ana");
    IO.println("reflexive:  " + a.equals(a));
    IO.println("symmetric:  " + (a.equals(b) == b.equals(a)));
    IO.println("transitive: " + (a.equals(b) && b.equals(c) && a.equals(c)));
    IO.println("null:       " + a.equals(null));
    IO.println("vs String:  " + a.equals("ana") + " " + "ana".equals(a));
}

Ele imprime:

reflexive:  true
symmetric:  true
transitive: true
null:       false
vs String:  false false

Agora um wrapper e uma string nunca são iguais, de nenhum dos lados. É menos esperto, e é correto. instanceof também trata null de graça, porque null instanceof CaseInsensitive é false.

Objetos iguais precisam ter hash codes iguais

O contrato de hashCode tem uma regra que importa mais que as outras: se a.equals(b) é true, a.hashCode() precisa ser igual a b.hashCode(). Objetos diferentes podem ter o mesmo hash code. Objetos iguais não podem ter hash codes diferentes.

O bug clássico é sobrescrever equals e esquecer hashCode. O build que esta série usa, javac -Xlint:all -Werror, pega isso:

class Email {
    private final String address;

    Email(String address) {
        this.address = address;
    }

    @Override
    public boolean equals(Object other) {
        return other instanceof Email e && address.equals(e.address);
    }
}

void main() {
    var subscribers = new HashSet<Email>();
    subscribers.add(new Email("ana@example.com"));
    IO.println(subscribers.contains(new Email("ana@example.com")));
}

O build falha com:

Main.java:1: warning: [overrides] Class Main.Email overrides equals, but neither it nor any superclass overrides hashCode method
error: warnings found and -Werror specified

Isso nos surpreendeu: a verificação existe, mas vem desligada. javac Main.java e java Main.java, sem opções, aceitam esse arquivo sem dizer nada. O lint overrides só roda quando você pede, com -Xlint. A mensagem diz Main.Email porque um arquivo-fonte compacto envolve as suas classes numa classe Main escondida.

Então veja o que acontece quando ninguém pede. @SuppressWarnings("overrides") desliga a verificação, para você ver o bug rodando:

@SuppressWarnings("overrides")
class Email {
    private final String address;

    Email(String address) {
        this.address = address;
    }

    @Override
    public boolean equals(Object other) {
        return other instanceof Email e && address.equals(e.address);
    }
}

void main() {
    var a = new Email("ana@example.com");
    var b = new Email("ana@example.com");
    IO.println("a.equals(b):   " + a.equals(b));
    IO.println("same hashCode: " + (a.hashCode() == b.hashCode()));

    var subscribers = new HashSet<Email>();
    subscribers.add(a);
    IO.println("contains b:    " + subscribers.contains(b));
    subscribers.add(b);
    IO.println("size:          " + subscribers.size());

    var list = new ArrayList<Email>();
    list.add(a);
    IO.println("list has b:    " + list.contains(b));
}

Ele imprime:

a.equals(b):   true
same hashCode: false
contains b:    false
size:          2
list has b:    true

a e b são iguais, mas cada um ainda tem o hash code de Object, que se baseia na identidade do objeto. O HashSet procura b no lugar errado e diz que ele não está lá. Depois adiciona sem problema uma “duplicata”, e o set fica com dois elementos iguais. O ArrayList nunca usa hash codes, então encontra b. É por isso que esse bug se esconde: o código que usa listas funciona, e a mesma classe quebra no momento em que entra num set ou vira chave de um map.

A correção é um hashCode feito com os mesmos campos que equals compara. Objects.hash faz isso numa linha:

class Email {
    private final String user;
    private final String domain;

    Email(String user, String domain) {
        this.user = user;
        this.domain = domain;
    }

    @Override
    public boolean equals(Object other) {
        return other instanceof Email e && user.equals(e.user) && domain.equals(e.domain);
    }

    @Override
    public int hashCode() {
        return Objects.hash(user, domain);
    }
}

void main() {
    var a = new Email("ana", "example.com");
    var b = new Email("ana", "example.com");
    IO.println("same hashCode: " + (a.hashCode() == b.hashCode()));

    var subscribers = new HashSet<Email>();
    subscribers.add(a);
    subscribers.add(b);
    IO.println("contains b:    " + subscribers.contains(b));
    IO.println("size:          " + subscribers.size());
}

Ele imprime:

same hashCode: true
contains b:    true
size:          1

Use todo campo que equals usa, e nenhum campo que ele ignora. Um record faz tudo isso para você a partir dos componentes, como mostra a parte sobre records. Se Email fosse record Email(String user, String domain) {}, não haveria nada para esquecer.

Como um HashMap encontra uma chave

Um HashMap guarda as entradas num array de buckets, e o hash code de cada chave decide em qual bucket ela fica. Uma busca não percorre o map inteiro. Ela calcula o hash code da chave, vai direto a um bucket e confere com equals só as entradas desse bucket.

Duas chaves podem cair no mesmo bucket, e podem até ter o mesmo hash code. equals separa as duas:

void main() {
    IO.println("\"Aa\".hashCode() = " + "Aa".hashCode());
    IO.println("\"BB\".hashCode() = " + "BB".hashCode());

    var map = new HashMap<String, Integer>();
    map.put("Aa", 1);
    map.put("BB", 2);
    IO.println("get Aa: " + map.get("Aa"));
    IO.println("get BB: " + map.get("BB"));
    IO.println("size:   " + map.size());
}

Ele imprime:

"Aa".hashCode() = 2112
"BB".hashCode() = 2112
get Aa: 1
get BB: 2
size:   2

"Aa" e "BB" colidem exatamente, então dividem um bucket. O map ainda mantém as duas separadas, porque "Aa".equals("BB") é false. Uma colisão custa um pouco de tempo. Nunca custa a correção.

Explicado como se você tivesse dez anos

Um HashMap é uma chapelaria. Quando você entrega o seu casaco, o atendente lê a etiqueta dele e escolhe uma arara a partir da etiqueta. Isso é o hashCode. O atendente pendura o seu casaco nessa arara, junto de alguns outros casacos.

Quando você volta, mostra a mesma etiqueta. O atendente vai até aquela arara e confere as fichas dos casacos pendurados ali, um por um, até um bater. Isso é o equals. Ninguém revira a sala inteira.

Agora imagine que você volta escondido e troca a etiqueta do seu casaco depois de entregá-lo. Quando você pede o casaco, a etiqueta nova manda o atendente para outra arara. O seu casaco não está lá. Ele continua na sala, na arara antiga, mas ninguém vai procurá-lo ali.

A versão precisa

Um HashMap guarda um array de buckets cujo tamanho é uma potência de dois, 16 por padrão depois que a primeira entrada entra. Para escolher um bucket, ele pega o hashCode() da chave, mistura os bits altos nos baixos com h ^ (h >>> 16) e fica com os bits baixos usando (n - 1) & hash, onde n é o número de buckets. Cada entrada guarda o hash com que foi inserida.

get(key) calcula o hash de novo, vai até aquele bucket e, para cada entrada, confere se o hash guardado é igual e se as chaves são == ou equals. A primeira entrada que passar é a resposta. Quando o map passa de 75% de ocupação, o array dobra e as entradas são redistribuídas pelos novos buckets. Se um bucket junta entradas demais (a constante de limite do JDK é 8) e a tabela tem pelo menos 64 buckets, esse bucket vira uma pequena árvore, então nem uma função de hash ruim faz as buscas percorrerem uma cadeia longa.

Onde a analogia falha: um atendente de verdade notaria a etiqueta nova e procuraria. O HashMap nunca relê uma chave depois do put. Ele confia no hash que guardou, então uma chave alterada não é movida, marcada nem recalculada. Além disso, a arara não é escolhida pela etiqueta inteira. Só os bits baixos do hash misturado escolhem o bucket, e é por isso que dois hash codes bem diferentes podem dividir um.

Mudar uma chave depois do put perde a entrada

Uma chave que muda depois de guardada é o jeito mais comum de um HashMap “perder” dados. A entrada continua no map. Você só não consegue mais chegar até ela.

class Coat {
    String tag;

    Coat(String tag) {
        this.tag = tag;
    }

    @Override
    public boolean equals(Object other) {
        return other instanceof Coat c && tag.equals(c.tag);
    }

    @Override
    public int hashCode() {
        return tag.hashCode();
    }
}

void main() {
    var owners = new HashMap<Coat, String>();
    var coat = new Coat("blue-17");
    owners.put(coat, "Ana");
    IO.println("before: " + owners.get(coat));

    coat.tag = "red-42";
    IO.println("after, same object: " + owners.get(coat));
    IO.println("after, old tag:     " + owners.get(new Coat("blue-17")));
    IO.println("containsKey:        " + owners.containsKey(coat));
    IO.println("remove:             " + owners.remove(coat));
    IO.println("size:               " + owners.size());
    IO.println("values:             " + owners.values());

    coat.tag = "blue-17";
    IO.println("tag put back:       " + owners.get(coat));
}

Ele imprime:

before: Ana
after, same object: null
after, old tag:     null
containsKey:        false
remove:             null
size:               1
values:             [Ana]
tag put back:       Ana

Coat tem equals e hashCode corretos. O bug é que os dois dependem de tag, e tag mudou enquanto o casaco era uma chave. Leia os resultados em pares:

• O mesmo objeto, depois da mudança: o hash novo manda o get para outro bucket, então ele não encontra nada. containsKey e remove falham do mesmo jeito.
• Um Coat("blue-17") novo: o hash dele bate com o guardado, então o get chega ao bucket certo. Aí o equals compara com a chave guardada, cuja tag agora diz red-42, e elas não batem.
• size e values: a Ana continua lá. Iterar sobre o map encontra ela. Só as buscas não encontram.

Colocar a tag antiga de volta torna a entrada alcançável de novo, o que prova que nada foi apagado. Em código real ninguém lembra o valor antigo, então a entrada fica presa, e um map que vive muito tempo vaza memória desse jeito.

A correção é usar chaves que não mudam: records com componentes imutáveis, String, Integer ou classes com campos final. Se uma chave realmente precisa mudar, remova primeiro, mude, e depois coloque de volta.

Vendo uma busca, e depois uma chave perdida

A animação é uma imagem simplificada, com números inventados: 8 buckets e hash codes de mentira. Ela mostra owners.get(coat) encontrando a Ana, e depois a mesma chamada após a tag mudar:

Um HashMap simplificado com 8 buckets e hash codes inventados. O hash da chave escolhe o bucket 3, equals rejeita a primeira entrada e aceita a segunda, e get devolve Ana. Depois que a tag muda, o novo hash escolhe o bucket 6, vazio, então get devolve null enquanto a entrada continua no bucket 3.

Aqui estão esses passos em palavras, caso a animação não rode para você:

1. owners.get(coat) começa com um casaco cuja tag é blue-17.
2. get chama coat.hashCode(). Nesta imagem, isso dá 1283, e 1283 escolhe o bucket 3 de 8.
3. O bucket 3 tem duas entradas. get chama equals com a chave da primeira, pear-05, e dá false, então ele segue em frente.
4. equals com a chave da segunda entrada, blue-17, dá true. Essa é a entrada.
5. get devolve o valor guardado com ela, "Ana".
6. Agora a tag do casaco muda para red-42. A entrada não se move: fica no bucket 3, com o hash guardado de 1283. O próximo get(coat) calcula um hash novo, 5078, que escolhe o bucket 6. O bucket 6 está vazio, então get devolve null.

TreeSet e TreeMap usam compareTo, não equals

Um TreeSet ou um TreeMap mantém as chaves ordenadas, e decide se duas chaves são a mesma comparando as duas, não chamando equals. Se compare devolve 0, a árvore trata as duas como uma chave só. Um comparator que devolve 0 para coisas que não são iguais faz o set descartá-las:

void main() {
    var byLength = new TreeSet<String>(Comparator.comparingInt(String::length));
    for (var fruit : List.of("fig", "kiwi", "pear", "plum", "apple")) {
        IO.println("add " + fruit + ": " + byLength.add(fruit));
    }
    IO.println(byLength);
    IO.println("contains pear: " + byLength.contains("pear"));
    IO.println("contains lime: " + byLength.contains("lime"));

    var prices = List.of(new BigDecimal("1.0"), new BigDecimal("1.00"));
    IO.println("equals:    " + prices.get(0).equals(prices.get(1)));
    IO.println("compareTo: " + prices.get(0).compareTo(prices.get(1)));
    IO.println("HashSet size: " + new HashSet<>(prices).size());
    IO.println("TreeSet size: " + new TreeSet<>(prices).size());
}

Ele imprime:

add fig: true
add kiwi: true
add pear: false
add plum: false
add apple: true
[fig, kiwi, apple]
contains pear: true
contains lime: true
equals:    false
compareTo: 0
HashSet size: 2
TreeSet size: 1

pear e plum têm quatro letras, como kiwi, então o set recusou as duas. Pior: contains("lime") diz true para uma palavra que nunca foi adicionada. Ter quatro letras basta.

BigDecimal mostra a mesma coisa no próprio JDK. 1.0 e 1.00 têm escalas diferentes, então equals diz que são diferentes e um HashSet guarda os dois. O compareTo deles é 0, então um TreeSet guarda um só. Quando a ordem natural de uma classe concorda com equals, a documentação chama isso de consistent with equals (consistente com equals), e é o que você quer para chaves.

Uma classe ganha uma ordem natural implementando Comparable. Um Comparator dá uma ordem de fora da classe. Comparator.comparing(...).thenComparing(...) monta um campo por campo, e os critérios de desempate são o que o mantêm consistente com equals:

record Version(int major, int minor) implements Comparable<Version> {
    private static final Comparator<Version> ORDER =
        Comparator.comparingInt(Version::major).thenComparingInt(Version::minor);

    @Override
    public int compareTo(Version other) {
        return ORDER.compare(this, other);
    }
}

record Person(String last, String first, int age) {}

void main() {
    var versions = new TreeSet<>(
        List.of(new Version(21, 0), new Version(8, 2), new Version(17, 1)));
    IO.println(versions);

    var people = new ArrayList<>(List.of(
        new Person("Silva", "Rui", 41),
        new Person("Okafor", "Ada", 29),
        new Person("Silva", "Ana", 35),
        new Person("Okafor", "Ada", 52)));
    people.sort(Comparator.comparing(Person::last)
        .thenComparing(Person::first)
        .thenComparing(Comparator.comparingInt(Person::age).reversed()));
    people.forEach(IO::println);
}

Ele imprime:

[Version[major=8, minor=2], Version[major=17, minor=1], Version[major=21, minor=0]]
Person[last=Okafor, first=Ada, age=52]
Person[last=Okafor, first=Ada, age=29]
Person[last=Silva, first=Ana, age=35]
Person[last=Silva, first=Rui, age=41]

A Version 8.2 vem antes da 17.1 porque a comparação é numérica. Como strings, "17" viria primeiro. people é ordenado pelo sobrenome, depois pelo nome e depois do mais velho para o mais novo. As duas Ada Okafor só diferem na idade, e o último thenComparing as coloca em ordem. Sem ele, um TreeSet com esse comparator guardaria só uma delas.

Escolhendo uma lista, uma pilha ou uma fila

ArrayList é a lista certa quase sempre, e o motivo é o jeito como as duas listas guardam os elementos. Um ArrayList guarda referências num único array. get(i) vai direto à posição i. Adicionar no fim escreve na próxima posição livre e, de vez em quando, copia tudo para um array maior.

Um LinkedList embrulha cada elemento num objeto nó próprio, com ligações para os vizinhos. get(i) precisa andar a partir de uma das pontas, nó por nó, e cada elemento custa um objeto a mais. Inserir no meio só é barato quando um iterator já andou até lá, o que raramente compensa o resto.

Para uma pilha ou uma fila, use ArrayDeque. A classe antiga Stack estende Vector, trava em toda chamada, e a própria documentação dela recomenda um Deque no lugar.

void main() {
    var stack = new ArrayDeque<String>();
    stack.push("open file");
    stack.push("read line");
    stack.push("parse number");
    IO.println("stack pop:  " + stack.pop());
    IO.println("stack peek: " + stack.peek());

    var queue = new ArrayDeque<String>();
    queue.offer("Ana");
    queue.offer("Ben");
    queue.offer("Cy");
    IO.println("queue poll: " + queue.poll());
    IO.println("queue now:  " + queue);
    IO.println("empty poll: " + new ArrayDeque<String>().poll());
}

Ele imprime:

stack pop:  parse number
stack peek: read line
queue poll: Ana
queue now:  [Ben, Cy]
empty poll: null

push e pop trabalham na frente, então o último item empilhado sai primeiro. offer adiciona no fim e poll tira da frente, então a fila é first in, first out: o primeiro a entrar é o primeiro a sair. poll num deque vazio devolve null em vez de lançar exceção. ArrayDeque não aceita elementos null, então um null vindo de poll sempre significa que o deque estava vazio.

Escolhendo um map

Os três maps de uso geral diferem numa coisa que dá para ver: a ordem em que os itens voltam quando você itera. Escolha pelo que você precisa:

Você precisa de	Use	Ordem de iteração
Busca rápida, e a ordem não importa	HashMap	Nenhuma em que você deva confiar
Busca rápida, na ordem em que as chaves foram adicionadas	LinkedHashMap	Ordem de inserção
Chaves ordenadas, ou intervalos como “todas as chaves antes de Lagos”	TreeMap	Ordenada por compareTo ou por um comparator

HashMap e LinkedHashMap buscam chaves em tempo constante na média, supondo hash codes razoáveis. TreeMap garante tempo log(n). As mesmas três opções existem para sets: HashSet, LinkedHashSet e TreeSet.

void main() {
    var cities = List.of("Porto", "Lagos", "Delhi", "Accra");
    var inserted = new LinkedHashMap<String, Integer>();
    var sorted = new TreeMap<String, Integer>();
    for (var i = 0; i < cities.size(); i++) {
        inserted.put(cities.get(i), i + 1);
        sorted.put(cities.get(i), i + 1);
    }
    IO.println("LinkedHashMap: " + inserted);
    IO.println("TreeMap:       " + sorted);
    IO.println("first key:     " + sorted.firstKey());
    IO.println("before Lagos:  " + sorted.headMap("Lagos"));
}

Ele imprime:

LinkedHashMap: {Porto=1, Lagos=2, Delhi=3, Accra=4}
TreeMap:       {Accra=4, Delhi=3, Lagos=2, Porto=1}
first key:     Accra
before Lagos:  {Accra=4, Delhi=3}

Nenhum HashMap é impresso aqui, de propósito. A ordem dele vem dos buckets, então pode mudar quando o map cresce ou quando você roda outro JDK. Se a ordem da saída importa, escolha um dos outros dois. Quando as chaves são um enum, EnumMap é a melhor escolha: ele guarda os valores num array indexado pelo ordinal do enum, e itera na ordem da declaração.

Coleções imutáveis e views não modificáveis

List.of, Set.of e Map.of criam coleções que não mudam de jeito nenhum, e List.copyOf faz uma cópia imutável de uma coleção existente. Collections.unmodifiableList é diferente. É uma janela só de leitura para uma lista que ainda pode mudar por baixo:

void main() {
    var names = new ArrayList<String>(List.of("Ana", "Ben"));
    List<String> view = Collections.unmodifiableList(names);
    List<String> copy = List.copyOf(names);

    names.add("Cy");
    IO.println("names: " + names);
    IO.println("view:  " + view);
    IO.println("copy:  " + copy);

    try {
        view.add("Dee");
    } catch (UnsupportedOperationException e) {
        IO.println("view.add threw " + e.getClass().getSimpleName());
    }
    try {
        Map.of("Ana", 31, "Ben", null);
    } catch (NullPointerException e) {
        IO.println("Map.of with a null value threw " + e.getClass().getSimpleName());
    }
}

Ele imprime:

names: [Ana, Ben, Cy]
view:  [Ana, Ben, Cy]
copy:  [Ana, Ben]
view.add threw UnsupportedOperationException
Map.of with a null value threw NullPointerException

Cy foi adicionado a names, e a view mostra, porque a view não tem elementos próprios. A cópia foi feita antes, então não mostra. Você não consegue mudar uma lista pela view, mas quem tem names consegue. Entregue um List.copyOf quando quiser que quem chama veja uma lista fixa.

Os métodos of e copyOf rejeitam null em qualquer lugar. Map.of também rejeita a mesma chave duas vezes, o que pega um erro de copiar e colar no momento em que o map é criado:

void main() {
    var ok = Map.of("Ana", 31, "Ben", 27);
    IO.println("size: " + ok.size());
    IO.println("Ana:  " + ok.get("Ana"));
    var typo = Map.of("Ana", 31, "Ben", 27, "Ana", 40);
    IO.println(typo.size());
}

Ele imprime e para:

size: 2
Ana:  31
Exception in thread "main" java.lang.IllegalArgumentException: duplicate key: Ana

Um HashMap teria guardado o segundo valor sem reclamar. Set.of lança a mesma exceção para um elemento duplicado.

Removendo elementos enquanto itera

Um loop for-each sobre um ArrayList usa um iterator, e esse iterator falha se a lista muda pelas costas dele. Remova um elemento dentro do loop e o passo seguinte lança exceção:

void main() {
    var names = new ArrayList<>(List.of("Ana", "Ben", "Cy", "Dee"));
    for (var name : names) {
        IO.println("checking " + name);
        if (name.startsWith("B")) {
            names.remove(name);
        }
    }
    IO.println(names);
}

Ele imprime e para:

checking Ana
checking Ben
Exception in thread "main" java.util.ConcurrentModificationException

O nome engana: só existe uma thread. “Concurrent” significa que a lista foi alterada enquanto um iterator estava no meio do caminho.

A exceção não é garantida, e esse é o caso pior. Aqui está o mesmo loop numa lista de três elementos:

void main() {
    var names = new ArrayList<>(List.of("Ana", "Ben", "Cy"));
    for (var name : names) {
        IO.println("checking " + name);
        if (name.startsWith("B")) {
            names.remove(name);
        }
    }
    IO.println(names);
}

Ele imprime:

checking Ana
checking Ben
[Ana, Cy]

Nenhuma exceção, e Cy nunca foi conferido. Remover Ben encolheu a lista para dois, o iterator já tinha entregado dois elementos, então concluiu que tinha terminado antes de verificar se houve mudanças. Se Cy começasse com “B”, continuaria na lista. A documentação chama essa verificação de “best-effort” (melhor esforço), e é isso que isso quer dizer.

Existem dois jeitos corretos. removeIf faz o trabalho todo numa chamada. Um Iterator explícito deixa você remover o elemento atual com it.remove(), e o iterator fica sabendo disso:

void main() {
    var names = new ArrayList<>(List.of("Ana", "Ben", "Cy", "Bea", "Dee"));
    names.removeIf(name -> name.startsWith("B"));
    IO.println("removeIf: " + names);

    var guests = new ArrayList<>(List.of("Ana", "Ben", "Cy", "Bea", "Dee"));
    var it = guests.iterator();
    while (it.hasNext()) {
        var name = it.next();
        if (name.startsWith("B")) {
            it.remove();
            IO.println("removed " + name);
        }
    }
    IO.println("iterator: " + guests);
}

Ele imprime:

removeIf: [Ana, Cy, Dee]
removed Ben
removed Bea
iterator: [Ana, Cy, Dee]

Use removeIf, a não ser que você precise fazer algo com cada elemento removido, como o loop com iterator faz aqui.

getOrDefault, merge e computeIfAbsent

Três métodos de Map substituem a maior parte do código “confere, depois faz put” que se escrevia antes. getOrDefault devolve um valor padrão para uma chave que não existe. merge combina um valor novo com um que já existe. computeIfAbsent cria um valor na primeira vez que uma chave aparece.

void main() {
    var text = "the quick fox saw the lazy dog and the dog saw the fox";

    var counts = new TreeMap<String, Integer>();
    for (var word : text.split(" ")) {
        counts.merge(word, 1, Integer::sum);
    }
    IO.println(counts);
    IO.println("the: " + counts.getOrDefault("the", 0));
    IO.println("cat: " + counts.getOrDefault("cat", 0));

    var byLength = new TreeMap<Integer, List<String>>();
    for (var word : counts.keySet()) {
        byLength.computeIfAbsent(word.length(), k -> new ArrayList<>()).add(word);
    }
    IO.println(byLength);
}

Ele imprime:

{and=1, dog=2, fox=2, lazy=1, quick=1, saw=2, the=4}
the: 4
cat: 0
{3=[and, dog, fox, saw, the], 4=[lazy], 5=[quick]}

counts.merge(word, 1, Integer::sum) coloca 1 para uma palavra nova e soma 1 a uma palavra que já está lá. computeIfAbsent cria uma lista vazia na primeira vez que vê um tamanho, devolve a lista do map nos dois casos, e add coloca a palavra nela. Os dois maps são TreeMaps, então a ordem impressa é ordenada e igual em toda execução.

O que lembrar

• equals precisa ser reflexivo, simétrico, transitivo, consistente, e dar false para null. Compare só com o seu próprio tipo, ou a resposta depende de qual lado pergunta.
• Objetos iguais precisam ter hash codes iguais. Sobrescreva hashCode junto com equals, usando os mesmos campos, por exemplo com Objects.hash. -Xlint avisa quando você esquece, mas só se você ligar. Records fazem os dois por você.
• Um HashMap usa hashCode para escolher um bucket e depois equals dentro dele. Nunca mude um campo que hashCode usa enquanto o objeto é uma chave, ou a entrada fica inalcançável.
• TreeSet e TreeMap tratam compare(a, b) == 0 como a mesma chave. Adicione critérios de desempate com thenComparing para a ordem concordar com equals.
• Use ArrayList para listas, ArrayDeque para pilhas e filas, e escolha HashMap, LinkedHashMap ou TreeMap pela ordem de iteração que você precisa.
• List.of e List.copyOf não mudam. Collections.unmodifiableList é uma view que mostra as mudanças na lista por trás dela.
• Não remova itens de uma lista dentro de um loop for-each. Use removeIf ou Iterator.remove.

Uma coleção baseada em hash só funciona se o equals e o hashCode de uma chave concordam e não mudam enquanto ela está lá dentro.