HashMap para resolver problemas de conteo en Java

1. Tổng quan

Los problemas de conteo (counting problem) aparecen en todas partes: contar frecuencias de caracteres, encontrar el elemento que aparece más, contar pares que cumplen una condición, agrupar elementos similares. HashMap es la herramienta casi «predeterminada» para este grupo de problemas porque tanto la búsqueda como la actualización son O(1) en promedio.

Después de leer este artículo, sabrás cómo usar HashMap (y Map.merge, getOrDefault) para resolver 4 tipos comunes de problemas de conteo, entenderás la complejidad temporal y espacial, y evitarás algunos errores comunes al usar HashMap en problemas de conteo.

2. ¿Por qué HashMap es adecuado para problemas de conteo?

La idea general detrás de los problemas de conteo es: para cada elemento, necesitas saber «cuántas veces lo has visto» o «si lo has visto». HashMap<K, V> te proporciona:

• Búsqueda de clave en O(1) en promedio — sin necesidad de ordenar.
• Actualización de valor (incrementar contador) en O(1) en promedio.
• Almacenar el estado «ya visto» usando containsKey o un valor de conteo > 0.

En comparación con una matriz de conteo (counting array), que solo funciona cuando el rango de valores es pequeño y conocido de antemano (por ejemplo, caracteres a-z), HashMap es más general: la clave puede ser String, Integer, o cualquier objeto.

3. Contar frecuencias de elementos

3.1. Usar getOrDefault

Esta es la forma clásica de contar la frecuencia de cada elemento en una 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) devuelve el valor actual si la palabra ya existe, o 0 si no — evita tener que escribir if (map.containsKey(...)). Con la lista ["cam", "xoai", "cam", "cam", "xoai"], el resultado es:

{cam=3, xoai=2}

3.2. Usar Map.merge (más breve)

A partir de Java 8, Map.merge combina el paso de verificación y actualización en una sola llamada.

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: si la palabra no existe, establece el valor en 1; si ya existe, suma el valor anterior más 1 usando la función Integer::sum. Este enfoque es un poco más rápido y se lee de forma más natural cuando la lógica de acumulación es simple.

3.3. Pruebas con 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);
    }
}

Nota: getOrDefault no modifica el mapa si la clave no existe — solo lee. No lo confundas con putIfAbsent, que se usa para asignar un valor predeterminado cuando la clave no existe.

4. Encontrar el elemento más frecuente

Una vez que tienes la tabla de frecuencias, encontrar el elemento que aparece más veces es solo un recorrido 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 las entradas por su valor (número de apariciones), .max(...) obtiene la entrada con el valor más alto. Si hay varios elementos empatados en el primer lugar, max solo devuelve uno de ellos — el orden no está garantizado porque HashMap no mantiene el orden de inserción.

Input:  {cam=3, xoai=2}
Output: Optional[cam]

Nota: Si necesitas mantener el orden de inserción para resultados estables cuando hay varios elementos empatados, usa LinkedHashMap en lugar de HashMap.

5. Contar pares de elementos que cumplen una condición (Two Sum como conteo)

Una variante común: contar el número de pares (i, j) tales que arr[i] + arr[j] == target. En lugar de usar fuerza bruta O(n²), usa HashMap para reducirlo 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;
    }
}

Explicación línea por línea:

• complement = target - number: el valor que necesitas encontrar para que al sumarlo con number obtengas target.
• count += seen.getOrDefault(complement, 0): suma el número de veces que complement ha aparecido antes — cada vez crea un par válido.
• seen.merge(number, 1, Integer::sum): registra el number actual en la tabla de conteo, para que elementos posteriores puedan formar pares con él.

Con numbers = [1, 2, 3, 2, 4] y target = 5: los pares son (1,4), (2,3), (3,2) → pero como solo contamos en el orden de aparición anterior, verifica con la prueba.

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);
    }
}

Los tres pares son: (2,3) cuando encuentras el 3, (2,3) cuando encuentras el segundo 2 (emparejado con el 3 ya visto), y (1,4) cuando encuentras el 4.

6. Agrupar elementos iguales (Grupos de Anagramas)

Un problema de conteo más avanzado: agrupar palabras que son anagramas entre sí (mismo conjunto de caracteres, diferente orden), y luego contar el número de grupos o el número de elementos en 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;
    }
}

El punto clave está en signature: ordenar los caracteres de cada palabra para crear una «firma» común para todos los anagramas. computeIfAbsent(signature, key -> new ArrayList<>()) crea una nueva lista si la firma aún no tiene una clave, y luego añade la palabra actual.

Con la entrada ["eat", "tea", "tan", "ate", "nat", "bat"], el resultado es:

{
  "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 es una solución más limpia que containsKey + put manual, especialmente cuando el valor es una colección que necesita inicialización perezosa (lazy init).

7. Complejidad temporal y espacial

Problema	Tiempo	Espacio
Contar frecuencias	O(n)	O(k) — k es el número de elementos distintos
Encontrar elemento más frecuente	O(n)	O(k)
Contar pares con suma objetivo	O(n)	O(n)
Agrupar anagramas	O(n · m log m) — m es la longitud de la palabra más larga	O(n)

En comparación con la solución de ordenar primero y luego recorrer (O(n log n)), HashMap generalmente es más rápido en complejidad temporal, pero requiere más espacio O(n) u O(k). Si la memoria es muy ajustada y el rango de valores es pequeño, una matriz de conteo (counting array) sigue siendo la opción más eficiente.

8. Errores comunes

• Usar objetos mutables como clave sin sobrescribir equals/hashCode: si cuentas según una clase personalizada (por ejemplo, Point), olvidar sobrescribir estos dos métodos hace que HashMap no reconozca dos objetos «iguales» como la misma clave.

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

Usar record te ayuda a tener automáticamente equals/hashCode correctos basados en todos los campos — evitando completamente este error.

• Esperar un orden de iteración estable: HashMap no garantiza el orden. Si necesitas orden de inserción, usa LinkedHashMap; si necesitas orden ascendente por clave, usa TreeMap.

• Modificar el mapa mientras lo recorres con entrySet(): causa ConcurrentModificationException. Si necesitas eliminar entradas mientras recorres, usa Iterator.remove() o removeIf.

• Usar boxing de Integer sin cuidado en bucles grandes: cada vez que usas getOrDefault + + 1, se crea un nuevo objeto Integer por auto-boxing. Con datos muy grandes (millones de elementos), considera Map<String, int[]> o una librería de mapa primitivo (por ejemplo, Eclipse Collections) para reducir el overhead.

Nota: Si el dominio de claves es solo 26 caracteres a-z o un pequeño rango fijo de números enteros, un array (int[26]) siempre es más rápido y consume menos memoria que HashMap. Solo usa HashMap cuando el dominio de claves es grande, desconocido, o no es contiguo.

9. Conclusión

HashMap convierte los problemas de conteo — contar frecuencias, encontrar elementos destacados, contar pares, agrupar elementos similares — en simples bucles O(n) gracias a la búsqueda O(1). Los métodos getOrDefault, merge y computeIfAbsent ayudan a que el código sea más breve y claro que la verificación manual con containsKey. Recuerda: HashMap no mantiene el orden, necesitas equals/hashCode correctos cuando la clave es un objeto, y con un rango de valores pequeño, una matriz de conteo sigue siendo la opción más ligera.