HashMap resolvendo problemas de contagem em Java

1. Visão geral

Problemas de contagem (counting problem) aparecem por toda parte: contar frequências de caracteres, encontrar o elemento que mais aparece, contar pares que satisfazem uma condição, agrupar elementos iguais. HashMap é a ferramenta quase “padrão” para esse tipo de problema porque consulta e atualização são O(1) em média.

Após ler este artigo, você saberá como usar HashMap (e Map.merge, getOrDefault) para resolver 4 tipos comuns de problemas de contagem, entender a complexidade de tempo/espaço e evitar alguns erros frequentes ao usar HashMap em problemas de contagem.

2. Por que HashMap é adequado para problemas de contagem

A ideia geral de um problema de contagem: para cada elemento, você precisa saber “quantas vezes já apareceu” ou “se já apareceu”. HashMap<K, V> oferece:

• Busca da chave em O(1) em média — sem necessidade de ordenação.
• Atualização do valor (incrementar contador) em O(1) em média.
• Armazenar o estado “já visto” usando containsKey ou valor de contagem > 0.

Comparado com um array de contagem (counting array) que só funciona quando o intervalo de valores é pequeno e conhecido de antemão (por exemplo, caracteres a-z), HashMap é mais genérico: a chave pode ser String, Integer, qualquer objeto.

3. Contar frequência de elementos

3.1. Usando getOrDefault

Esta é a forma clássica de contar a frequência de cada elemento em uma lista.

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FrequencyCounter {

    public static Map<String, Integer> countFrequency(List<String> words) {
        Map<String, Integer> freq = new HashMap<>();
        for (String word : words) {
            freq.put(word, freq.getOrDefault(word, 0) + 1);
        }
        return freq;
    }
}

freq.getOrDefault(word, 0) retorna o valor atual se word já existe, ou 0 se não existe — evitando ter que escrever if (map.containsKey(...)). Com a lista ["cam", "xoai", "cam", "cam", "xoai"], o resultado é:

{cam=3, xoai=2}

3.2. Usando Map.merge (mais conciso)

A partir do Java 8, Map.merge combina as etapas de verificação e atualização em uma única chamada.

public static Map<String, Integer> countFrequencyMerge(List<String> words) {
    Map<String, Integer> freq = new HashMap<>();
    words.forEach(word -> freq.merge(word, 1, Integer::sum));
    return freq;
}

freq.merge(word, 1, Integer::sum) significa: se word ainda não existe, defina o valor 1; se já existe, pegue o valor antigo e some com 1 através da função Integer::sum. Essa abordagem é um pouco mais rápida e mais legível quando a lógica de acumulação é simples.

3.3. Testando com JUnit 5 + AssertJ

import org.junit.jupiter.api.Test;
import java.util.List;
import java.util.Map;
import static org.assertj.core.api.Assertions.assertThat;

class FrequencyCounterTest {

    @Test
    void shouldCountFrequencyCorrectly() {
        Map<String, Integer> result = FrequencyCounter.countFrequency(
                List.of("cam", "xoai", "cam", "cam", "xoai"));

        assertThat(result)
                .containsEntry("cam", 3)
                .containsEntry("xoai", 2);
    }
}

Observação: getOrDefault não modifica o map se a chave não existe — ele apenas lê. Não confunda com putIfAbsent, que é usado para atribuir um valor padrão quando a chave não existe.

4. Encontrar o elemento mais frequente

Depois de ter a tabela de frequências, encontrar o elemento que mais aparece é apenas uma passada por entrySet().

import java.util.Map;
import java.util.Optional;

public class MostFrequentFinder {

    public static Optional<String> findMostFrequent(Map<String, Integer> freq) {
        return freq.entrySet().stream()
                .max(Map.Entry.comparingByValue())
                .map(Map.Entry::getKey);
    }
}

Map.Entry.comparingByValue() compara as entradas pelo valor (número de ocorrências), .max(...) pega a entrada com o maior valor. Se há múltiplos elementos empatados no primeiro lugar, max retorna apenas um deles — a ordem não é garantida porque HashMap não mantém a ordem de inserção.

Entrada:  {cam=3, xoai=2}
Saída: Optional[cam]

Observação: Se você precisa manter a ordem de inserção para um resultado estável quando há múltiplos elementos empatados, use LinkedHashMap no lugar de HashMap.

5. Contar pares que satisfazem uma condição (Two Sum de contagem)

Uma variante comum: contar o número de pares (i, j) de modo que arr[i] + arr[j] == target. Em vez de usar força bruta O(n²), use HashMap para reduzir a O(n).

import java.util.HashMap;
import java.util.Map;

public class PairCounter {

    public static int countPairsWithSum(int[] numbers, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        int count = 0;

        for (int number : numbers) {
            int complement = target - number;
            count += seen.getOrDefault(complement, 0);
            seen.merge(number, 1, Integer::sum);
        }
        return count;
    }
}

Explicação linha a linha:

• complement = target - number: o valor que precisamos encontrar para somar com number e obter target.
• count += seen.getOrDefault(complement, 0): adicione o número de vezes que complement já apareceu antes — cada vez assim cria um par válido.
• seen.merge(number, 1, Integer::sum): registre o número atual na tabela de contagem, para que elementos posteriores possam formar pares com ele.

Com numbers = [1, 2, 3, 2, 4] e target = 5: os pares são (1,4), (2,3), (3,2) → mas como contamos pela ordem de aparição anterior, verifique com o teste.

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class PairCounterTest {

    @Test
    void shouldCountPairsWithGivenSum() {
        int[] numbers = {1, 2, 3, 2, 4};

        int result = PairCounter.countPairsWithSum(numbers, 5);

        assertThat(result).isEqualTo(3);
    }
}

Os três pares são: (2,3) ao encontrar o número 3, (2,3) ao encontrar o segundo 2 (emparelhando com o 3 já visto), e (1,4) ao encontrar o 4.

6. Agrupar elementos iguais (Anagrama)

Um problema de contagem mais avançado: agrupar palavras que são anagramas umas das outras (mesmo conjunto de caracteres, ordem diferente), depois contar o número de grupos ou o número de elementos em cada grupo.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AnagramGrouper {

    public static Map<String, List<String>> groupAnagrams(List<String> words) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String word : words) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String signature = new String(chars);

            groups.computeIfAbsent(signature, key -> new ArrayList<>())
                  .add(word);
        }
        return groups;
    }
}

O ponto-chave está em signature: ordenar os caracteres de cada palavra para criar uma “assinatura” comum para todos os anagramas. computeIfAbsent(signature, key -> new ArrayList<>()) cria uma nova lista se a assinatura ainda não existe como chave, depois adiciona a palavra atual a ela.

Com a entrada ["eat", "tea", "tan", "ate", "nat", "bat"], o resultado:

{
  "aet"=[eat, tea, ate],
  "ant"=[tan, nat],
  "abt"=[bat]
}

import org.junit.jupiter.api.Test;
import java.util.List;
import java.util.Map;
import static org.assertj.core.api.Assertions.assertThat;

class AnagramGrouperTest {

    @Test
    void shouldGroupAnagramsTogether() {
        Map<String, List<String>> groups = AnagramGrouper.groupAnagrams(
                List.of("eat", "tea", "tan", "ate", "nat", "bat"));

        assertThat(groups.values())
                .anySatisfy(group -> assertThat(group).containsExactlyInAnyOrder("eat", "tea", "ate"));
    }
}

computeIfAbsent é uma solução mais limpa que containsKey + put manual, especialmente quando o valor é uma coleção que precisa de inicialização preguiçosa (lazy init).

7. Complexidade de tempo e espaço

Problema	Tempo	Espaço
Contar frequências	O(n)	O(k) — k é o número de elementos distintos
Encontrar elemento mais frequente	O(n)	O(k)
Contar pares com soma alvo	O(n)	O(n)
Agrupar anagramas	O(n · m log m) — m é o comprimento da palavra mais longa	O(n)

Comparado com a solução que ordena primeiro e depois itera (O(n log n)), HashMap geralmente é mais rápido em complexidade de tempo, mas em troca usa mais espaço O(n) ou O(k). Se a memória é uma restrição rígida e o intervalo de valores é pequeno, um array de contagem (counting array) ainda é a escolha mais econômica.

8. Erros comuns

• Usar um objeto mutável como chave sem sobrescrever equals/hashCode: se você conta por uma classe customizada (por exemplo, Point), esquecer de sobrescrever esses dois métodos faz com que HashMap não reconheça dois objetos “iguais” como a mesma chave.

public record Point(int x, int y) {}

Usar record ajuda a gerar automaticamente equals/hashCode corretos baseados em todos os fields — evitando esse erro completamente.

• Esperar que a ordem de iteração seja estável: HashMap não garante ordem. Se você precisa de ordem de inserção, use LinkedHashMap; se precisa de ordem crescente pelas chaves, use TreeMap.

• Modificar o map enquanto itera sobre entrySet(): causa ConcurrentModificationException. Se você precisa remover entradas durante a iteração, use Iterator.remove() ou removeIf.

• Usar Integer boxing descuidadamente em loops grandes: cada vez que getOrDefault + + 1 cria um novo objeto Integer devido ao auto-boxing. Com dados muito grandes (milhões de elementos), considere Map<String, int[]> ou uma biblioteca de map primitivo (por exemplo, Eclipse Collections) para reduzir overhead.

Observação: Se o domínio de chaves for apenas 26 caracteres a-z ou um intervalo pequeno e fixo de inteiros, um array (int[26]) é sempre mais rápido e economiza mais memória que HashMap. Use HashMap apenas quando o domínio de chaves for grande, não for conhecido de antemão ou for descontínuo.

9. Conclusão

HashMap transforma problemas de contagem — contar frequências, encontrar elementos destacados, contar pares, agrupar elementos iguais — em simples loops O(n) graças à consulta O(1). Os métodos getOrDefault, merge, computeIfAbsent fazem o código ser mais curto e legível comparado com verificação manual de containsKey. Lembre-se: HashMap não mantém ordem, precisa de equals/hashCode corretos se a chave for um objeto, e com um domínio de valores pequeno, um array de contagem ainda é a escolha mais compacta.