HashMap résout les problèmes de comptage en Java

1. Vue d’ensemble

Les problèmes de comptage (counting problems) apparaissent partout : compter les fréquences de caractères, trouver l’élément le plus fréquent, compter les paires satisfaisant une condition, regrouper les éléments identiques. HashMap est l’outil pratiquement « par défaut » pour ce groupe de problèmes car la recherche et la mise à jour sont toutes deux en O(1) en moyenne.

Après avoir lu cet article, vous saurez comment utiliser HashMap (et Map.merge, getOrDefault) pour résoudre 4 types courants de problèmes de comptage, comprendre la complexité temporelle/spatiale, et éviter quelques erreurs courantes quand vous utilisez HashMap dans les problèmes de comptage.

2. Pourquoi HashMap convient aux problèmes de comptage

L’idée générale d’un problème de comptage : pour chaque élément, vous devez savoir « combien de fois il a été rencontré » ou « s’il a déjà été rencontré ». HashMap<K, V> vous offre :

La recherche de clés en O(1) en moyenne — pas besoin de trier.
La mise à jour de valeurs (incrémenter le compteur) en O(1) en moyenne.
Conserver l’état « déjà vu » via containsKey ou une valeur de comptage > 0.

Par rapport à un tableau de comptage (counting array) qui ne peut être utilisé que lorsque l’ensemble des valeurs est petit et connu d’avance (par exemple les caractères a-z), HashMap est plus général : la clé peut être une String, un Integer, ou tout objet.

3. Compter la fréquence des éléments

3.1. Utiliser getOrDefault

C’est le moyen classique de compter la fréquence de chaque élément dans une liste.

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) retourne la valeur actuelle si word existe déjà, ou 0 sinon — évite d’écrire if (map.containsKey(...)). Avec la liste ["cam", "xoai", "cam", "cam", "xoai"], le résultat est :

{cam=3, xoai=2}

3.2. Utiliser Map.merge (plus court)

À partir de Java 8, Map.merge fusionne l’étape de vérification et de mise à jour en un seul appel.

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) signifie : si word n’existe pas encore, définissez la valeur à 1 ; s’il existe, prenez l’ancienne valeur plus 1 via la fonction Integer::sum. C’est un peu plus rapide et plus naturel à lire quand la logique d’agrégation est simple.

3.3. Tester avec 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);
    }
}

Note : getOrDefault ne modifie pas la map si la clé n’existe pas encore — elle fait seulement une lecture. À ne pas confondre avec putIfAbsent, qui est utilisé pour affecter une valeur par défaut quand la clé n’existe pas.

4. Trouver l’élément le plus fréquent

Une fois que vous avez un tableau de fréquences, trouver l’élément le plus fréquent ne nécessite qu’une seule itération sur 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() compare les entrées selon leur valeur (nombre d’occurrences), .max(...) prend l’entrée avec la plus grande valeur. S’il y a plusieurs éléments ex-æquo, max ne retourne que l’un d’eux — l’ordre n’est pas garanti car HashMap ne préserve pas l’ordre d’insertion.

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

Note : Si vous avez besoin de préserver l’ordre d’insertion pour obtenir un résultat stable quand plusieurs éléments sont ex-æquo, utilisez LinkedHashMap à la place de HashMap.

5. Compter les paires d’éléments satisfaisant une condition (Two Sum sous forme de comptage)

Une variante courante : compter le nombre de paires (i, j) telles que arr[i] + arr[j] == target. Au lieu de brute-force en O(n²), utilisez HashMap pour réduire à 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;
    }
}

Explication ligne par ligne :

complement = target - number : la valeur à trouver pour s’ajouter à number et égaler target.
count += seen.getOrDefault(complement, 0) : ajouter le nombre de fois que complement a déjà été rencontré — chaque fois crée une paire valide.
seen.merge(number, 1, Integer::sum) : enregistrer le nombre actuel dans le tableau de comptage, de sorte que les éléments suivants puissent former des paires avec celui-ci.

Avec numbers = [1, 2, 3, 2, 4] et target = 5 : les paires sont (1,4), (2,3), (3,2) → mais puisque nous comptons uniquement selon l’ordre d’apparition antérieur, vérifiez avec le test.

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

Ces trois paires sont : (2,3) quand on rencontre le chiffre 3, (2,3) quand on rencontre le deuxième 2 (appairé avec 3 déjà vu), et (1,4) quand on rencontre 4.

6. Regrouper les éléments identiques (Groupes d’anagrammes)

Un problème de comptage plus avancé : regrouper les mots qui sont des anagrammes les uns des autres (même ensemble de caractères, ordre différent), puis compter le nombre de groupes ou le nombre d’éléments dans chaque groupe.

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

Le point clé réside dans signature : trier les caractères de chaque mot pour créer une « signature » commune à tous les anagrammes. computeIfAbsent(signature, key -> new ArrayList<>()) crée une nouvelle liste si la signature n’a pas encore de clé, puis ajoute le mot actuel.

Avec l’entrée ["eat", "tea", "tan", "ate", "nat", "bat"], le résultat :

{
  "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 est une meilleure solution que containsKey + put manuel, particulièrement quand la valeur est une collection nécessitant une initialisation paresseuse (lazy init).

7. Complexité temporelle et spatiale

Problème	Temps	Espace
Compter les fréquences	O(n)	O(k) — k est le nombre d’éléments distincts
Trouver l’élément le plus fréquent	O(n)	O(k)
Compter les paires avec la somme cible	O(n)	O(n)
Regrouper les anagrammes	O(n · m log m) — m est la longueur du mot le plus long	O(n)

Par rapport à une solution utilisant d’abord le tri puis la traversée (O(n log n)), HashMap est généralement plus rapide en complexité temporelle mais consomme en échange plus d’espace O(n) ou O(k). Si la mémoire est fortement limitée et que l’ensemble des valeurs est petit, un tableau de comptage (counting array) reste un choix plus économe.

8. Erreurs courantes

Utiliser une clé qui est un objet mutable sans surcharger equals/hashCode : si vous comptez selon une classe personnalisée (par exemple Point), oublier de surcharger ces deux méthodes fait que HashMap ne reconnaît pas deux objets « identiques » comme la même clé.

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

Utiliser record génère automatiquement equals/hashCode corrects en fonction de tous les champs — évite complètement cette erreur.

S’attendre à un ordre d’itération stable : HashMap ne garantit pas l’ordre. Si vous avez besoin de l’ordre d’insertion, utilisez LinkedHashMap ; si vous avez besoin d’un ordre croissant par clé, utilisez TreeMap.
Modifier la map lors de l’itération sur entrySet() : provoque une ConcurrentModificationException. Si vous avez besoin de supprimer une entrée pendant la traversée, utilisez Iterator.remove() ou removeIf.
Utiliser Integer boxing sans précaution dans les grandes boucles : chaque fois que getOrDefault + + 1 crée un nouvel objet Integer via auto-boxing. Avec des données très volumineuses (millions d’éléments), envisagez Map<String, int[]> ou une bibliothèque de map primitif (par exemple Eclipse Collections) pour réduire l’overhead.

Note : Si l’ensemble des clés est seulement les 26 caractères a-z ou une petite plage d’entiers fixe, un tableau (int[26]) est toujours plus rapide et consomme moins de mémoire que HashMap. N’utilisez HashMap que quand l’ensemble des clés est grand, inconnu à l’avance, ou non contigu.

9. Conclusion

HashMap transforme les problèmes de comptage — compter les fréquences, trouver les éléments saillants, compter les paires, regrouper les éléments identiques — en simples boucles O(n) grâce aux recherches O(1). Les méthodes getOrDefault, merge, computeIfAbsent aident à rendre le code plus court et plus clair que la vérification manuelle de containsKey. Rappelez-vous : HashMap ne préserve pas l’ordre, a besoin que equals/hashCode soit correct quand la clé est un objet, et pour les petits ensembles de valeurs, un tableau de comptage reste un choix plus léger.