HashMaps e coleções em Java

Um mapa armazena uma associação de cada chave a um valor. Em um mapa de estoque, o nome de um produto é a chave e sua quantidade é o valor. Dois produtos podem ter a mesma quantidade, mas uma chave de produto não pode ter duas entradas separadas.

Crie o mapa

import java.util.HashMap;

HashMap<String, Integer> stock = new HashMap<>();

O primeiro tipo, String, descreve as chaves. O segundo, Integer, descreve os valores. O diamante <> à direita permite que Java infira esses tipos. Os argumentos de tipo devem ser tipos de referência: use Integer, Double, Character ou Boolean em vez de int, double, char ou boolean. Java empacota um int simples quando o armazena como Integer e desempacota um Integer quando um int é necessário.

Acompanhe cada alteração

stock.put("apple", 12);
stock.put("pear", 7);
Integer previous = stock.put("apple", 15);

A primeira chamada cria apple=12; a segunda adiciona pear=7. A terceira encontra a chave existente "apple" e substitui seu valor. O mapa agora tem duas entradas, e previous contém 12. Um put para uma chave sem associação anterior retorna null.

stock.get("apple") agora retorna 15. stock.remove("pear") retorna 7 e remove essa entrada. Remover "pear" novamente retorna null. size() conta as entradas, isEmpty() verifica se não há nenhuma e clear() remove todas as entradas.

Trate uma chave ausente

stock.get("kiwi") retorna null, e stock.containsKey("kiwi") retorna false. Esta instrução compila, mas falha quando é executada:

int quantity = stock.get("kiwi");

Java tenta desempacotar null em um int, causando uma NullPointerException. Para um mapa de quantidades não nulas, use um valor padrão:

int quantity = stock.getOrDefault("kiwi", 0);

Isso fornece 0 sem adicionar "kiwi" ao mapa. Você também pode verificar containsKey antes da leitura. containsValue(15) verifica se alguma entrada tem esse valor; ele pode percorrer todos os valores, portanto é diferente de encontrar uma chave conhecida.

Um HashMap também permite uma chave null e valores null. Se uma chave estiver explicitamente associada a null, getOrDefault retornará o null armazenado, não o valor padrão. containsKey distingue esse caso de uma chave ausente. Mapas de quantidades são mais simples quando cada quantidade armazenada é um número real.

Faça a correspondência correta de chaves e valores

Chaves do tipo String distinguem maiúsculas de minúsculas: "apple", "Apple" e "apple " são diferentes. Aplique a mesma limpeza antes de armazenar e pesquisar, por exemplo, name.trim().toLowerCase(). Limpar apenas uma chave de pesquisa não corrige chaves armazenadas de forma inconsistente.

Compare valores empacotados pelo conteúdo com equals. Se duas entradas contiverem 1000, suas referências Integer podem ser diferentes, portanto == pode ser falso mesmo que seus conteúdos numéricos correspondam. Depois de verificar que ambos os valores são não nulos, a.equals(b) compara seus conteúdos.

Um mapa pode responder a uma única consulta ou fornecer todos os seus dados a um laço. Escolha a visão que fornece as partes necessárias ao laço. As visões estão vinculadas ao mapa, portanto alterações feitas por meio delas também podem alterar o mapa.

Escolha chaves, valores ou entradas

Use keySet() para visitar as chaves. Uma consulta dentro desse laço pode recuperar cada valor:

for (String name : phoneBook.keySet()) {
    System.out.println(name + ": " + phoneBook.get(name));
}

Use values() quando as chaves não forem relevantes. Para as quantidades em estoque maçã 15, pera 7 e figo 3:

int total = 0;
for (int quantity : stock.values()) {
    total += quantity;
}

O total passa a ser 25. Valores repetidos ainda contribuem separadamente: uma visão de valores não é um conjunto.

Uma entrada contém uma chave e seu valor juntos. Importe java.util.Map e use Map.Entry<K, V> com getKey() e getValue(). Isso evita uma segunda consulta:

String best = null;
int bestScore = Integer.MIN_VALUE;
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    if (best == null || entry.getValue() > bestScore) {
        best = entry.getKey();
        bestScore = entry.getValue();
    }
}

Para Ana 82, Ben 91 e Cai 77, o resultado é Ben com 91. O teste best == null também trata uma primeira pontuação igual ao menor valor possível de int. Um mapa vazio deixa best como null.

Escolha a ordem explicitamente

Um HashMap não garante uma ordem de iteração. Não se pode presumir a ordem de inserção, a ordem classificada ou a ordem exibida hoje. Um LinkedHashMap preserva a ordem de inserção; um TreeMap visita as chaves em ordem classificada. Se duas pontuações empatarem, o laço anterior mantém a primeira visitada. Com um HashMap, qualquer um dos nomes empatados pode vencer. Adicione uma regra explícita de desempate quando o resultado precisar ser previsível.

Remova entradas pelo iterador

Chamar stock.remove(key) dentro de um laço for-each que percorre stock.keySet() altera as chaves usadas pelo laço. Isso pode causar uma ConcurrentModificationException. A detecção não é garantida; uma execução sem exceção não torna esse padrão válido.

Use o próprio método de remoção do iterador:

Iterator<Map.Entry<String, Integer>> it =
    stock.entrySet().iterator();
while (it.hasNext()) {
    if (it.next().getValue() == 0) {
        it.remove();
    }
}

Importe java.util.Iterator. Para maçã 15, pera 0, figo 0 e kiwi 4, isso remove pera e figo. Outra abordagem segura registra as chaves em uma lista, termina o laço e depois as remove.

Substituir um valor existente não adiciona nem remove uma chave. Durante um laço sobre entradas, entry.setValue(entry.getValue() * 2) pode dobrar as quantidades com segurança. Não adicione novas chaves por meio do mapa durante esse laço.

Distinga uma visão de uma cópia

stock.keySet().remove("apple") remove a entrada correspondente do mapa. Uma lista separada criada com new ArrayList<>(stock.keySet()) é uma cópia das chaves atuais. Ordenar essa lista não reordena o mapa, e remover um nome da lista não remove sua associação no mapa.

Um ID de produto armazenado como String já tem regras de igualdade úteis. Uma chave criada a partir de sua própria classe exige uma decisão: dois objetos separados com os mesmos dados representam a mesma chave?

Códigos de dispersão limitam a busca; a igualdade a confirma

Um HashMap usa hashCode() para ajudar a localizar uma chave e equals() para verificar uma correspondência. Chaves iguais devem ter códigos de dispersão iguais. Chaves diferentes podem compartilhar um código de dispersão; a igualdade ainda as distingue. Classes padrão de valores, como String e Integer, já seguem esse contrato.

Sem sobrescritas, uma classe herda de Object a igualdade baseada em identidade. Dois pontos criados separadamente com coordenadas 2 e 3 são chaves diferentes, embora seus campos correspondam:

labels.put(new Point(2, 3), "door");
String label = labels.get(new Point(2, 3));

Com igualdade por identidade, label é null. A consulta criou um segundo objeto, diferente daquele usado na inserção.

Sobrescreva os dois métodos em conjunto

Aqui as coordenadas de um ponto definem seu conteúdo:

import java.util.Objects;

final class Point {
    private final int x;
    private final int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        if (!(other instanceof Point)) {
            return false;
        }
        Point point = (Point) other;
        return x == point.x && y == point.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

A verificação de identidade trata rapidamente o caso do mesmo objeto. A verificação de tipo rejeita null e objetos de tipos não relacionados. A comparação final verifica as duas coordenadas. Objects.hash(x, y) constrói o código de dispersão a partir desses mesmos campos. Com essa classe, a consulta anterior retorna "door".

Sobrescrever apenas equals mantém o cálculo de hash herdado, que não garante códigos de dispersão iguais para objetos separados com campos iguais. Um mapa pode então deixar de encontrar uma chave igual. Um código de dispersão constante preservaria a correção, mas tornaria a busca lenta. Gerar as duas sobrescritas em um editor ajuda a evitar o uso de campos incompatíveis.

Use a assinatura exata do método

public boolean equals(Point other) faz uma sobrecarga do método; não substitui equals(Object). A consulta no mapa usa equals(Object), portanto a nova sobrecarga não fornece ao mapa igualdade por conteúdo. A anotação @Override faz uma assinatura errada gerar um erro de compilação em vez de um defeito oculto na consulta.

Mantenha estável a identidade da chave

Não altere campos que determinam a igualdade ou o código de dispersão de uma chave enquanto ela estiver armazenada. Se um ponto armazenado mudar de (2, 3) para (5, 3), o mapa pode deixar de encontrá-lo por qualquer um dos valores, embora size() permaneça igual. Remova-o antes de alterá-lo e depois insira-o novamente. Tornar os campos da chave final, como acima, evita esse erro.

Essas regras também determinam a pertinência em um HashSet. Um ArrayList usa equals para buscas por conteúdo, como contains; não precisa de códigos de dispersão para essa busca.

Uma tabela de frequências tem uma chave para cada item distinto e um número que indica quantas vezes ele ocorre. A primeira ocorrência inicia uma contagem; cada ocorrência posterior atualiza essa mesma entrada.

Construa uma contagem, um item de cada vez

HashMap<String, Integer> counts = new HashMap<>();
for (String word : text.split(" ")) {
    int oldCount = counts.getOrDefault(word, 0);
    counts.put(word, oldCount + 1);
}

Para o texto “o gato viu o cão e o gato correu”, a primeira ocorrência de “o”, correspondente a "the" no texto original, ainda não está no mapa, portanto sua contagem anterior é 0 e a nova é 1. Suas duas ocorrências seguintes alteram essa entrada para 2 e depois para 3. A contagem de “gato”, correspondente a "cat", termina em 2; as contagens de “viu”, “cão”, “e” e “correu”, correspondentes a "saw", "dog", "and" e "ran", terminam em 1 cada.

Há 6 palavras distintas, portanto counts.size() é 6. A soma dos valores é 9, o número de ocorrências de palavras. Eles medem coisas diferentes: o tamanho do mapa não é o comprimento da sequência original.

A atualização pode ser escrita em uma linha:

counts.put(word, counts.getOrDefault(word, 0) + 1);

Uma forma equivalente mais longa verifica containsKey, incrementa uma contagem existente e armazena 1 para uma nova chave. Todas as contagens armazenadas nesse padrão são não nulas.

Preserve o resultado anterior

Chamar counts.put(word, 1) para cada palavra sobrescreve repetidamente cada contagem com 1. Isso registra que uma palavra existe, mas perde sua frequência. Chamar counts.get(word) + 1 sem tratar a primeira ocorrência tenta desempacotar null e falha. O valor padrão deve estar na etapa de leitura; a contagem aumentada deve então ser armazenada novamente.

Decida o que conta como o mesmo item

A igualdade de cadeias de caracteres é exata. "The" e "the" são chaves diferentes, assim como "cat" e "cat,". Se a tarefa as tratar como a mesma palavra, limpe cada unidade de entrada antes de contá-la. Converta o texto para minúsculas e remova a pontuação que o programa trata como separadores. Use uma regra consistente para que os resultados não dependam de qual grafia apareceu primeiro.

A chave também pode ser um caractere. Com HashMap<Character, Integer>, um laço sobre "banana".toCharArray() produz a=3, n=2 e b=1 usando o mesmo padrão de ler, aumentar e armazenar.

Acumule quantias em vez de ocorrências

Para totais por categoria, adicione a quantia atual em vez de 1:

HashMap<String, Double> totals = new HashMap<>();
double oldTotal = totals.getOrDefault(category, 0.0);
totals.put(category, oldTotal + amount);

Alimentação 12,50, transporte 3,20 e alimentação 7,25 resultam em alimentação 19,75 e transporte 3,20. O valor padrão é 0.0, correspondente ao tipo de valor Double. O mapa continua tendo uma entrada por categoria, independentemente de quantas quantias contribuíram para ela.

Interprete a tabela concluída

Percorra as entradas para encontrar a maior contagem ou o maior total, guardando a melhor chave e seu valor. Especifique uma regra de desempate, se necessário. Para um relatório em ordem alfabética, new TreeMap<>(counts) copia as associações em ordem classificada de chaves. Os valores das contagens permanecem inalterados; ordenar as chaves não ordena as categorias por seus totais.

Um valor de mapa pode ser uma coleção. Quando vários alunos pertencem a um curso, o curso é uma chave e a lista associada contém todos os seus alunos. A regra de chave única do mapa continua válida: a lista é o único valor daquele curso.

Crie um grupo antes de adicionar itens a ele

HashMap<Character, ArrayList<String>> groups = new HashMap<>();
for (String fruit : fruits) {
    char letter = fruit.charAt(0);
    if (!groups.containsKey(letter)) {
        groups.put(letter, new ArrayList<>());
    }
    groups.get(letter).add(fruit);
}

Para “apple”, “banana”, “avocado”, “cherry” e “blueberry”, a primeira fruta cria a lista de a e adiciona “apple”. “Banana” cria a lista de b. “Avocado” encontra a lista existente de a e é adicionado a ela. O resultado é a → [apple, avocado], b → [banana, blueberry] e c → [cherry]. Cada lista mantém sua própria ordem de inserção, embora o HashMap não ordene suas chaves.

A verificação pode ser abreviada:

groups.putIfAbsent(letter, new ArrayList<>());
groups.get(letter).add(fruit);

putIfAbsent mantém uma lista existente não nula. O get seguinte retorna essa lista, pronta para receber o item.

Mantenha a lista que você já construiu

Um groups.put(letter, new ArrayList<>()) incondicional dentro do laço substitui a lista anterior a cada ocorrência. Apenas a última fruta de cada letra permanece depois do add seguinte. O erro oposto é deixar de criar a lista: groups.get(letter).add(fruit) lança uma NullPointerException para uma nova chave porque ainda não existe uma lista.

Entenda a referência

get retorna a referência à lista armazenada. Adicionar um item a ela altera essa mesma lista, portanto não é necessário inseri-la novamente. Isso também explica um erro de compartilhamento:

ArrayList<String> shared = new ArrayList<>();
courses.put("Art", shared);
courses.put("Music", shared);
courses.get("Art").add("Jin");

Agora ambas as chaves levam a [Jin]. Duas chaves não criaram duas listas. Crie uma nova lista para cada novo grupo quando os grupos precisarem ser independentes.

Escolha listas ou conjuntos dentro dos grupos

Uma lista preserva adições repetidas. Um conjunto impede duplicatas dentro do grupo. Um HashMap<String, HashSet<String>> pode, portanto, reunir as matrículas distintas dos alunos sem contar o mesmo aluno duas vezes em um curso. A regra do conjunto se aplica dentro de cada valor; o mapa externo continua tendo uma entrada por curso.

Para ler um grupo que pode estar ausente, verifique containsKey ou use groups.getOrDefault(letter, new ArrayList<>()). Uma chave ausente então produz uma lista vazia para essa chamada. A lista padrão não é inserida automaticamente; adicionar um item a ela não cria um grupo armazenado.

Remover o último item de um grupo deixa a chave associada a uma coleção vazia. Se o programa não deve mais listar grupos vazios, verifique isEmpty() e remova também essa chave. Conte os grupos pelo tamanho do mapa externo e os itens pelos tamanhos das coleções internas.

Um índice associa uma chave de identificação a um objeto. Uma biblioteca pode encontrar um livro pelo ISBN sem percorrer todos os livros de uma lista. Uma tabela de consulta usa a mesma estrutura para associar um código a um valor simples, como o preço de um produto.

Escolha uma chave de identificação

Um HashMap<String, Book> pode associar um ISBN ao seu livro. Cada consulta precisa apenas da chave. O nome de uma pessoa muitas vezes é uma chave única inadequada: armazenar outra pessoa chamada “Sam Lee” sob essa mesma cadeia de caracteres substitui a pessoa anterior. Use um ID único ou um mapa de agrupamento se um nome deve levar a várias pessoas.

Mantenha um índice dentro da classe responsável pelos dados:

class Library {
    private HashMap<String, Book> byIsbn;

    Library() {
        byIsbn = new HashMap<>();
    }

    void addBook(Book book) {
        byIsbn.put(book.getIsbn(), book);
    }

    Book findByIsbn(String isbn) {
        return byIsbn.get(isbn);
    }
}

Aqui Book fornece um método getIsbn(). Quem chama a classe usa addBook e findByIsbn; não precisa saber qual implementação de mapa está armazenada. O campo privado também dá à classe um único lugar para manter suas regras de adição e substituição de livros.

Verifique um resultado ausente

Se findByIsbn retornar null, nenhum livro foi encontrado. Teste o resultado antes de chamar um método nele:

Book found = library.findByIsbn("978-0-00-000000-2");
if (found != null) {
    found.setOnLoan(true);
}

Chamar setOnLoan diretamente em um resultado ausente lançaria uma NullPointerException. Um método como hasBook(isbn) é outra forma de permitir que quem chama o método verifique a existência de uma chave.

Acompanhe objetos compartilhados entre índices

Um mapa armazena uma referência a um objeto, não uma nova cópia desse objeto. Se o mesmo livro estiver em uma lista de todos os livros, em um mapa por ISBN e em um agrupamento por autor, setOnLoan(true) alterará o único livro ao qual os três se referem. Isso evita que três objetos de livro separados se tornem inconsistentes.

As próprias estruturas de coleção ainda precisam ser mantidas. Remover um livro do mapa por ISBN não remove sua referência da lista de um autor. Se uma biblioteca mantiver os dois índices, seus métodos de adição e remoção deverão atualizar ambos. Centralizar essas alterações em métodos como addBook e removeBook ajuda a manter as buscas consistentes.

Use uma tabela em um cálculo

Suponha que uma tabela de preços tenha café 2,50, chá 2,00 e muffin 3,25. Para dois cafés e um muffin:

double cost = 2 * prices.get("coffee") + prices.get("muffin");

O subtotal dos cafés é 5,00; somar 3,25 resulta em 8,25. As chaves identificam produtos, e os valores fornecem as quantias. Um produto ausente exige uma decisão explícita antes do cálculo: um valor padrão zero o trataria como gratuito sem aviso. A mesma técnica de consulta pode, portanto, precisar de uma regra para chaves ausentes diferente daquela de uma tabela de frequências.

Um conjunto contém cada valor no máximo uma vez. Ele é adequado para perguntas como “Esse valor já apareceu antes?” ou “Quantos valores diferentes aparecem?”. Um HashSet oferece verificações de pertinência rápidas em média, sem garantir uma ordem de exibição.

Adicione e verifique valores

import java.util.HashSet;

HashSet<String> visited = new HashSet<>();
boolean first = visited.add("Oslo");
boolean second = visited.add("Lima");
boolean third = visited.add("Oslo");
visited.add("Pune");

Os três valores booleanos armazenados são true, true e false. O segundo “Oslo” corresponde a um elemento existente, portanto não é adicionado. O tamanho do conjunto é 3. Uma adição duplicada não substitui uma posição numerada, pois um conjunto não tem índice.

visited.contains("Lima") retorna true. visited.remove("Lima") remove o valor e retorna true; repetir essa remoção retorna false. Use um laço for-each para visitar os valores. Não existe get(0) para o primeiro valor de um HashSet.

Remova duplicatas de uma lista

ArrayList<Integer> values = new ArrayList<>();
values.add(3);
values.add(1);
values.add(3);
values.add(2);
values.add(1);
HashSet<Integer> distinct = new HashSet<>(values);

O conjunto tem três valores: {1, 2, 3}. Sua ordem real de iteração não é especificada. A lista original ainda tem cinco elementos porque o construtor cria uma coleção separada.

Use new LinkedHashSet<>(values) para manter a ordem das primeiras ocorrências, obtendo 3, 1, 2. Use new TreeSet<>(values) para obter valores ordenados, 1, 2, 3. Os conjuntos são escritos entre chaves aqui para destacar a pertinência; o toString() padrão de conjuntos em Java usa colchetes.

Detecte a primeira repetição

O resultado de add pode realizar o teste de pertinência e a inserção juntos:

HashSet<Integer> seen = new HashSet<>();
for (int number : numbers) {
    if (!seen.add(number)) {
        System.out.println(number);
        break;
    }
}

Para [4, 7, 2, 7, 4], o laço exibe 7. Esse é o primeiro valor encontrado uma segunda vez, embora 4 tenha aparecido antes na sequência. Antes de 7 se repetir, o conjunto contém 4, 7 e 2. A inserção que falha provoca a interrupção.

Saiba o que um conjunto não pode informar

Verificar contains antes de cada add é desnecessário porque add já trata duplicatas. Uma lista com uma verificação contains também pode manter valores únicos, mas cada busca na lista pode percorrer todos os elementos armazenados. Um HashSet expressa a regra diretamente.

A igualdade importa para seus próprios objetos. Um HashSet<Point> precisa de equals baseado no conteúdo e de um hashCode compatível para reunir pontos criados separadamente com coordenadas iguais. Sem essas sobrescritas, instâncias separadas permanecem como elementos separados.

Por fim, size() mede valores distintos, não ocorrências. As nove palavras de “o gato viu o cão e o gato correu” produzem seis palavras distintas. Um conjunto não informa mais que “o” ocorreu três vezes; use um mapa de frequências quando essas contagens importarem.

Conjuntos podem descrever grupos e comparar seus membros. Se duas listas de eventos contiverem a mesma pessoa várias vezes, um conjunto primeiro reduz cada lista às pessoas que participaram. As operações de conjuntos então respondem a perguntas sobre qualquer um dos eventos, ambos ou apenas um deles.

Combine dois grupos

Considere que segunda-feira seja {Ana, Ben, Cai, Dee} e terça-feira seja {Ben, Dee, Eva}.

Essas operações são união, interseção e diferença. Elas alteram o conjunto receptor e retornam um valor booleano que indica se ele foi alterado. Elas não retornam um novo conjunto como resultado.

Preserve o original

Faça uma cópia antes de alterar os membros se segunda-feira ainda for necessária:

HashSet<String> both = new HashSet<>(monday);
both.retainAll(tuesday);

both começa com os quatro nomes de segunda-feira. retainAll remove Ana e Cai porque eles não estão em terça-feira. O próprio conjunto de segunda-feira permanece inalterado. Para encontrar quem participou somente na terça-feira, comece com uma cópia de terça-feira e remova os nomes de segunda-feira, obtendo {Eva}. A diferença tem uma direção; invertê-la muda a pergunta.

Verifique subconjuntos e igualdade

monday.containsAll(group) verifica se todos os valores de group estão presentes em segunda-feira. Para {Ben, Dee}, retorna true: esse grupo é um subconjunto de segunda-feira. Isso não exige que segunda-feira contenha apenas essas duas pessoas.

Dois conjuntos são iguais quando seus elementos correspondem, independentemente da ordem de inserção ou da implementação. Um HashSet que contém “x” e “y” é igual a um TreeSet que contém “y” e “x”. A pertinência determina a igualdade de conjuntos, portanto a ordem por si só não pode torná-los diferentes.

Escolha uma ordem para o percurso

Os três evitam duplicatas. Use LinkedHashSet quando a primeira ocorrência de cada nome for importante. Use TreeSet quando cada percurso já precisar estar ordenado. Para cadeias de caracteres, a ordenação natural segue os códigos dos caracteres: formas minúsculas e maiúsculas não se comportam como um único alfabeto sem distinção entre elas.

Um TreeSet com seu construtor padrão precisa de elementos que tenham uma comparação natural, como cadeias de caracteres, números ou objetos que implementem Comparable. Nesse conjunto, um resultado de comparação igual a zero indica uma duplicata. Uma classe que não fornece comparação natural causa uma ClassCastException quando um de seus objetos é inserido. Fornecer um comparador explícito é outra forma de definir a ordem de uma coleção em árvore; os exemplos com construtor padrão usam a ordem natural.

Uma interface descreve operações fornecidas por uma classe que a implementa. Ela permite que uma variável descreva o que o código precisa, deixando a escolha do armazenamento para uma classe concreta. List, Set e Map são interfaces relacionadas a coleções em java.util.

Interprete os dois lados de uma declaração

List<String> names = new ArrayList<>();
Set<String> tags = new HashSet<>();
Map<String, Integer> counts = new HashMap<>();

O lado esquerdo declara o tipo da variável. O lado direito cria um objeto de uma classe que implementa esse tipo. Importe ambos os tipos, como java.util.List e java.util.ArrayList. Você não pode escrever new List<>() ou new Map<>(): uma interface não é um objeto concreto que possa ser construído.

O código que usa counts pode chamar put, get e entrySet porque Map os declara. Se chaves em ordem alfabética se tornarem úteis, altere a construção para new TreeMap<>(). As chamadas existentes continuam compilando. Sua ordem pode mudar porque as implementações podem oferecer garantias diferentes de ordem; a interface não as torna idênticas em todos os comportamentos.

Aceite a capacidade de que um método precisa

Um método que apenas conta palavras longas pode receber uma Collection:

static int countLong(Collection<String> words, int min) {
    int count = 0;
    for (String word : words) {
        if (word.length() >= min) {
            count++;
        }
    }
    return count;
}

Para [“a”, “tree”, “house”] e um mínimo de 4, ele retorna 2. O mesmo método pode receber um ArrayList, um LinkedList, um HashSet ou List.of(...) porque apenas lê os elementos. Um conjunto pode já ter removido duplicatas, portanto pode fornecer dados de entrada diferentes dos de uma lista.

Usar um parâmetro de tipo de interface evita exigir uma classe específica de armazenamento quando o método não precisa dela. Se posições forem necessárias, aceite List. Se consultas por chave forem necessárias, aceite Map.

Conheça os limites do tipo declarado

List<String> names = new ArrayList<>();
names.ensureCapacity(100);  // does not compile

O objeto é um ArrayList, mas List não declara ensureCapacity. O compilador verifica o tipo declarado da variável. Use um tipo de classe concreta quando sua operação especial for realmente necessária; não altere parâmetros de listas comuns apenas para corresponder à classe usada por quem chama o método.

Posicione Map ao lado de Collection

List e Set estendem Collection, que descreve um grupo de elementos. Ela declara métodos como add, remove, contains, size, isEmpty, addAll e clear. A possibilidade de fazer uma alteração depende da coleção concreta.

Map não estende Collection. Ele armazena associações e fornece visões que são coleções: keySet() é um Set, values() é uma Collection e entrySet() é um Set de entradas. Passe counts.values() a um método que precise de uma coleção de valores, não o próprio counts.

Uma classe pode implementar várias interfaces. LinkedList implementa tanto List quanto Deque, uma interface de fila de duas extremidades. Sua própria classe indica as interfaces que se compromete a implementar depois de implements, como em class Member implements Comparable<Member>.

Escolha uma interface pelas regras de que seus dados precisam. Conteúdos de aparência semelhante não tornam uma lista, um conjunto e um mapa intercambiáveis: cada um atribui um significado diferente a posições, repetições e igualdade.

Compare as garantias

ArrayList e LinkedList implementam List. HashSet, LinkedHashSet e TreeSet implementam Set. HashMap, LinkedHashMap e TreeMap implementam Map. As versões baseadas em hash não garantem ordem de percurso; as versões vinculadas preservam a ordem de inserção; as versões em árvore mantêm elementos ou chaves ordenados. Inserir novamente uma chave existente em um LinkedHashMap comum, ordenado por inserção, mantém a posição dessa chave.

Examine com cuidado a remoção em listas de inteiros

Uma List<Integer> tem duas sobrecargas relevantes:

List<Integer> numbers = new ArrayList<>(List.of(1, 5, 7));
numbers.remove(1);

O argumento 1 é um int, portanto Java remove o índice 1: o valor 5. O resultado é [1, 7]. Começando novamente com [1, 5, 7], numbers.remove(Integer.valueOf(1)) seleciona a remoção por valor e deixa [5, 7]. O objeto empacotador deixa clara a sobrecarga pretendida.

Compare conteúdos com a regra correta

Duas listas são iguais quando os mesmos elementos aparecem na mesma ordem. Um ArrayList [1, 2] é igual a um LinkedList [1, 2], mas não a uma lista [2, 1]. Dois conjuntos comparam a pertinência, ignorando a ordem. Dois mapas comparam suas associações, portanto a ordem de inserção não afeta a igualdade dos mapas. Suas classes concretas podem ser diferentes enquanto seus conteúdos são iguais segundo a regra da interface.

Reconheça coleções não modificáveis

List<String> labels = List.of("a", "b");
Set<Integer> levels = Set.of(1, 2, 3);
Map<String, Double> prices = Map.of("tea", 2.0, "coffee", 2.5);

Essas fábricas retornam coleções não modificáveis. Tentativas de adicionar, remover, substituir ou ordenar seu conteúdo lançam UnsupportedOperationException. Map.of aceita até dez pares chave–valor.

As três rejeitam elementos, chaves ou valores null com NullPointerException. Set.of rejeita elementos duplicados e Map.of rejeita chaves duplicadas com IllegalArgumentException. List.of permite duplicatas porque uma lista pode repetir um elemento. Os conjuntos e mapas produzidos pelas fábricas têm ordem de iteração não especificada.

Copie quando alterações forem necessárias

new ArrayList<>(labels) cria uma lista modificável com os mesmos elementos. new HashSet<>(someList) e new HashMap<>(someMap) também criam estruturas de coleção separadas.

Essas cópias são superficiais: elas contêm as mesmas referências aos elementos. Remover um elemento de uma cópia deixa a estrutura original intacta, mas alterar um objeto mutável por meio de qualquer uma das coleções altera o objeto compartilhado. Uma coleção não modificável impede alterações em sua estrutura; ela não congela todos os objetos armazenados nela.

Uma lista mantém uma ordem, mas essa ordem pode apenas refletir como os valores chegaram. A ordenação reorganiza a lista usando uma regra de comparação. Java já fornece uma ordem natural para números e cadeias de caracteres.

Ordene uma lista modificável na própria lista

List<Double> values = new ArrayList<>(List.of(3.5, -1.0, 2.25));
Collections.sort(values);

Importe java.util.Collections. A mesma lista agora contém [-1,0; 2,25; 3,5]. A ordenação retorna void, portanto values = Collections.sort(values) não compila. values.sort(null) também ordena em ordem natural. Para um vetor, use Arrays.sort(array); um vetor contendo 5, 2 e 8 passa a conter 2, 5, 8.

Preveja a ordem de cadeias caractere por caractere

A comparação de cadeias examina o primeiro caractere diferente. Se uma cadeia for prefixo de outra, a mais curta vem primeiro. Assim, “apple” vem antes de “apples”.

A lista [“pear”, “Banana”, “apple”, “10”, “9”] é ordenada como [“10”, “9”, “Banana”, “apple”, “pear”]. Para esses caracteres, algarismos precedem letras maiúsculas, e maiúsculas precedem minúsculas. “10” vem antes de “9” porque “1” vem antes de “9”; a ordem de cadeias não interpreta cadeias de algarismos como números inteiros. Armazene dados numéricos como números quando a ordem numérica for necessária.

Use ordens alternativas prontas

names.sort(String.CASE_INSENSITIVE_ORDER);
values.sort(Collections.reverseOrder());

A primeira chamada ordena [“pear”, “Banana”, “apple”] como [“apple”, “Banana”, “pear”] sem alterar as letras maiúsculas e minúsculas armazenadas. A segunda usa a ordem natural decrescente. Os números 4, 9 e 1 tornam-se 9, 4 e 1. Esses argumentos são comparadores, objetos que fornecem uma ordem alternativa.

Collections.reverse(list) apenas inverte a sequência atual. Ele produz ordem decrescente se essa sequência já estava ordenada de forma crescente; sozinho, não ordena uma lista arbitrária.

Mantenha os empates estáveis

A ordenação de listas é estável: elementos considerados iguais na comparação mantêm sua ordem relativa anterior. Se uma comparação apenas por pontuação empatar duas pessoas, a ordem anterior delas na lista permanece. A estabilidade preserva essa ordem de entrada; ela não cria um critério de desempate alfabético.

Reconheça falhas e atalhos

Uma lista criada com List.of(...) não pode ser ordenada na própria lista. Primeiro copie-a para um ArrayList. Para uma classe sem Comparable, Collections.sort(list) falha na verificação de tipos durante a compilação. Chamar list.sort(null) em objetos desse tipo falha em tempo de execução com ClassCastException quando a comparação é necessária.

Collections.max(collection) e Collections.min(collection) encontram o maior e o menor elemento em ordem natural sem reorganizar a coleção. Eles lançam NoSuchElementException para uma coleção vazia.

Para obter chaves de mapa ordenadas, copie map.keySet() para um ArrayList e ordene a cópia, ou use um TreeMap. Ordenar uma lista copiada de chaves deixa inalterada a ordem de iteração do próprio mapa.

Java não consegue adivinhar se um membro deve vir primeiro pelo nome, pela altura ou por outro campo. Implemente Comparable para dar à classe uma ordem natural. O código de ordenação pode então pedir que cada objeto se compare a outro objeto dessa classe.

Escreva o método de comparação

class Member implements Comparable<Member> {
    private String name;
    private int height;

    Member(String name, int height) {
        this.name = name;
        this.height = height;
    }

    @Override
    public int compareTo(Member other) {
        return Integer.compare(this.height, other.height);
    }
}

A altura é medida em centímetros. Comparable<Member> especifica que o outro objeto é um Member; nenhuma conversão explícita é necessária. public int compareTo(Member other) é o método exigido. A interface padrão Comparable está em java.lang, portanto não precisa ser importada.

Para a.compareTo(b), um resultado negativo coloca a antes de b, zero os coloca na mesma posição de comparação e um resultado positivo coloca a depois de b. Apenas o sinal importa: -35 é um resultado negativo tão válido quanto -1.

Acompanhe a ordem

Com a comparação por altura, Ana 172, Ben 165 e Cai 180 são ordenados como Ben 165, Ana 172 e Cai 180. Para colocar os membros mais altos primeiro, inverta os argumentos:

return Integer.compare(other.height, this.height);

Altere a regra de forma deliberada. Inverter os argumentos inverte o sentido desse campo; isso não muda o significado da altura nem altera os dados de qualquer membro.

Compare valores numéricos inteiros com segurança

A subtração parece conveniente, mas pode retornar o sinal errado quando ocorre estouro de um int. Para -2.000.000.000 e 2.000.000.000, subtrair o segundo do primeiro produz, por estouro, 294.967.296, um resultado positivo. Integer.compare retorna corretamente um resultado negativo.

Para campos decimais, use Double.compare(this.price, other.price). Converter explicitamente uma diferença para int perde informação: (int) (1.8 - 1.5) é 0, portanto preços diferentes tornam-se um empate na comparação. Um método auxiliar de comparação preserva a ordem sem truncar a diferença.

Compare texto e reutilize a regra

Para ordenar por nome, retorne this.name.compareTo(other.name). Ele segue a ordem dos caracteres da cadeia. compareToIgnoreCase fornece comparação de texto sem distinção entre maiúsculas e minúsculas quando essa é a regra pretendida para o campo.

Depois que uma classe define uma ordem natural, operações como Collections.sort, Collections.max e as comparações padrão de TreeSet ou TreeMap podem usá-la. Uma classe também pode implementar outras interfaces, separadas por vírgulas depois de implements.

Há uma ordem natural para a classe, não um compareTo diferente selecionado para cada lista. Use objetos comparadores separados quando um contexto precisar de ordem por nome e outro de ordem por altura. Uma comparação apenas por altura também empata todas as alturas iguais; decidir se esse empate é aceitável torna-se especialmente importante em conjuntos ordenados.

Uma comparação principal muitas vezes deixa empates. Dois filmes podem ter o mesmo ano ou dois jogadores podem ter a mesma pontuação. Um critério de desempate dá vez ao campo seguinte somente quando os campos anteriores são considerados iguais na comparação.

Compare os campos em ordem de prioridade

@Override
public int compareTo(Film other) {
    int byYear = Integer.compare(this.year, other.year);
    if (byYear != 0) {
        return byYear;
    }
    return this.title.compareTo(other.title);
}

O ano é a regra principal. O título só importa quando os anos empatam. Up (2009), Avatar (2009) e Alien (1979) são ordenados como Alien (1979), Avatar (2009), Up (2009). Comparar os títulos primeiro daria a eles prioridade sobre o ano e atenderia a uma tarefa de ordenação diferente.

Os sentidos podem ser diferentes para cada campo. Para colocar as maiores pontuações primeiro e os nomes de A a Z, comece com Integer.compare(other.points, this.points). Se o resultado for zero, retorne this.name.compareTo(other.name). Inverter toda a lista final também inverteria os nomes dentro das pontuações empatadas.

Entenda a regra de duplicatas de um conjunto ordenado

Um TreeSet<Member> padrão usa a comparação natural tanto para ordenar elementos quanto para decidir quando um elemento já está presente. Se Member.compareTo usar apenas a altura, Ana 172 e Dee 172 terão comparação igual a zero. Adicionar Ana retorna true; adicionar Dee retorna false. Ana permanece como elemento armazenado mesmo que equals considere as duas integrantes diferentes.

Uma lista pode manter os dois objetos empatados; um conjunto em árvore dá a eles uma única posição de comparação. Adicione o critério de desempate necessário se eles precisarem ser distintos no conjunto.

Alinhe a comparação à igualdade

Uma ordem é consistente com equals quando a comparação retorna zero se, e somente se, equals retorna verdadeiro. Para uma classe cuja igualdade usa altura e nome, comparar primeiro a altura e depois o nome pode atender a essa regra. Se a igualdade usar outra identidade, como um ID de membro, adicionar apenas o nome como critério de desempate não estabelece a consistência.

A comparação também deve se comportar como uma ordem válida. Se a vem antes de b, a comparação inversa deve colocar b depois de a. Se a está antes de b e b antes de c, a deve estar antes de c. Usar métodos auxiliares de comparação de campos completos em uma ordem fixa de prioridade ajuda a cumprir essas regras. Um método inconsistente pode ordenar resultados incorretamente ou fazer uma ordenação lançar IllegalArgumentException.

Mantenha as chaves do mapa ordenadas também

Um TreeMap ordena chaves, não valores. Para as contagens de palavras de “o gato viu o cão e o gato correu”, a primeira chave é “cão” e a última é “viu”. firstKey() e lastKey() fornecem esses extremos. Declare um TreeMap ou uma interface apropriada de mapa ordenado ao chamar métodos que o Map comum não declara.

A comparação de chaves também define quais chaves correspondem. Uma segunda chave cuja comparação resulta em zero atualiza a associação existente, mesmo quando equals distingue os objetos. Coleções em árvore com comportamento padrão exigem elementos ou chaves comparáveis naturalmente; inserir um objeto sem comparação adequada lança ClassCastException. Um comparador fornecido explicitamente pode definir outra ordem.

O custo de uma operação descreve como seu trabalho cresce com o número de elementos armazenados. Ele ajuda a identificar código que é rápido para um exemplo pequeno, mas lento quando a coleção se torna grande.

Compare o crescimento, não os segundos

O tempo constante, O(1), permanece aproximadamente independente do tamanho da coleção. O tempo linear, O(n), pode crescer em proporção ao número de elementos. O tempo logarítmico, O(log n), cresce lentamente à medida que o tamanho aumenta. Essas designações descrevem o crescimento, não tempos exatos de execução em um computador específico.

Uma busca em ArrayList pode verificar todos os elementos; alterações no início deslocam os elementos seguintes. Um LinkedList precisa percorrer a lista até uma posição, portanto o acesso repetido por índice pode ser custoso. ArrayList é uma escolha padrão útil para o trabalho comum com listas.

Identifique o percurso repetido

Suponha que um programa verifique 10.000 nomes em uma lista que contém 100.000 nomes. Chamar list.contains(name) para cada nome pode exigir até 1.000.000.000 de verificações de igualdade. Uma chamada de método que parece rápida ainda é uma busca completa quando usada dessa forma.

Construa um conjunto para verificar a pertinência uma única vez:

Set<String> allowed = new HashSet<>(allowedNames);
int matches = 0;
for (String name : incomingNames) {
    if (allowed.contains(name)) {
        matches++;
    }
}

Há trabalho para construir o conjunto de 100.000 elementos, seguido de 10.000 verificações de pertinência em tempo constante em média. Contando as duas etapas, o total cresce aproximadamente com a soma dos tamanhos das duas entradas, em vez de seu produto. Reconstruir o conjunto dentro do laço repetiria o trabalho de preparação e eliminaria esse benefício.

Interprete corretamente as garantias médias

Operações baseadas em hash dependem de chaves cujos códigos de dispersão distribuam bem os valores. Retornar um código de dispersão constante para todos os objetos ainda pode satisfazer as regras de igualdade, mas torna a consulta lenta. Isso não é uma maneira sem custo de evitar escrever um método de hash útil.

Coleções em árvore mantêm a ordem classificada com operações básicas logarítmicas. Dobrar o número de elementos acrescenta apenas uma pequena quantidade de trabalho à busca. Para 100.000 elementos, um logaritmo de base dois é aproximadamente 16,6; isso indica a escala da busca, não uma garantia exata de 17 comparações em toda consulta em árvore de Java.

Considere a tarefa inteira

Construir um conjunto adicional custa tempo e memória. Para poucos elementos ou uma única consulta, a lista original pode ser suficiente. Para verificações repetidas de pertinência, um conjunto reutilizável frequentemente elimina o principal custo. Comece pelo comportamento necessário e depois examine as operações repetidas com mais frequência.

A coleção adequada mantém as informações de que o programa precisa e facilita a expressão de suas principais perguntas. Decida as regras dos dados antes de escolher o nome de uma classe conhecida.

Pergunte o que identifica um item

Um double[12] pode armazenar a precipitação em milímetros quando cada posição corresponde a um mês conhecido. Um mapa cujas chaves são apenas as posições 0, 1, 2 e assim por diante acrescenta uma camada que uma lista ou um vetor já fornece.

Escolha a ordem necessária

Para mapas e conjuntos, use HashMap ou HashSet quando nenhuma ordem for necessária, LinkedHashMap ou LinkedHashSet para ordem de inserção e TreeMap ou TreeSet para chaves ou elementos ordenados. Para uma lista de uso geral, comece com ArrayList.

Contagens de palavras exibidas em ordem alfabética combinam com um TreeMap<String, Integer>. Uma lista de marcadores distintos na ordem em que foram vistos pela primeira vez combina com LinkedHashSet<String>. Músicas repetidas exigem uma lista, mesmo que também estejam armazenadas em outro lugar em um conjunto: descartar repetições alteraria a playlist.

Combine coleções quando os dados tiverem camadas

Alunos por curso podem ser representados por Map<String, List<String>>; cada valor é uma lista ordenada de matrículas. Marcadores por artigo podem ser representados por Map<String, Set<String>>; cada artigo recebe marcadores distintos. Uma tabela de classificação pode ser uma List<Player> ordenada pela comparação natural do jogador.

As escolhas externas e internas respondem a perguntas diferentes. Se os cursos devem ser listados em ordem alfabética e os alunos mantidos em ordem de matrícula, use um TreeMap por fora e uma lista por dentro. Ordenar as chaves não ordena as listas. Se registros de matrícula duplicados devem ser ignorados, use um conjunto para os grupos internos.

Mantenha dados relacionados juntos

Duas listas paralelas, uma de nomes e outra de números de telefone, dependem de posições correspondentes. Remover um nome sem seu número desfaz todos os pares seguintes. Se os nomes identificarem pessoas de forma única, um mapa pode guardar a associação. Se nomes se repetirem ou vários campos pertencerem a uma pessoa, mantenha objetos de pessoas em uma lista ou indexe-os por um ID único.

Pesquisar uma lista repetidamente por um campo é outro sinal de que vale considerar um mapa como índice. Mantenha também a lista se a ordem de exibição e as entradas repetidas importarem, mas atualize as duas estruturas em conjunto quando dados forem adicionados ou removidos.

Verifique as regras dos elementos e o tipo declarado

Use uma declaração com interface, como Map<String, Double> prices = new HashMap<>();, para que quem usa o mapa dependa das operações necessárias. Coleções baseadas em hash precisam de uma igualdade adequada e de códigos de dispersão compatíveis para chaves ou elementos personalizados. Coleções em árvore com comportamento padrão precisam de uma comparação natural que distinga exatamente os valores que a coleção deve manter. Essas regras fazem parte de garantir que a coleção escolhida represente os dados pretendidos.