T: / Corrigés des challenges / Java

HashMap en Java pour structurer les données efficacement

Utilisation et présentation de la classe HashMap en Java : initialisation et méthodes clés.

→ Challenge Correction: Greenoïd #6 - A project to sink

Sixième corrigé des challenges de l’histoire originale Greenoïd, créée à l’occasion de la Battle Dev Thales 2024.

Il était question dans ce challenge d’analyser les flux dans un réseau de vannes pour déterminer la vanne qui recevait le plus d’eau à la fin du réseau. Il y avait 4 niveaux successifs de vannes, de 1 à 4. En partant des débits des vannes 1 et de la définition des différents écoulements, il fallait donc trouver la vanne de niveau 4 qui recevait le plus d’eau.

Plusieurs solutions étaient possibles pour résoudre ce challenge.

Parmi les solutions complexes, on pouvait travailler avec de la récursivité ou créer des objets pour gérer les différents noeuds. Mais… en analysant bien le problème, on pouvait simplifier davantage l’algorithme à mettre en oeuvre.

Pour illustrer cet algorithme, on va résoudre le challenge en Java ! En utilisant la classe HashMap issue de la collection java.util.

Au programme :

Création d’une HashMap en Java

Dans la méthode main, juste après le jeu de données, on peut créer la HashMap : 

// == Création d'une HashMap pour stocker les débits de chaque vanne
HashMap<String, Integer> debitParVanne = new HashMap<>();

Lorsqu’on crée une HashMap, on définit le type de la clé (ici String) et le type des valeurs contenues (ici Integer). Ces types devront être scrupuleusement respectés au risque de déclencher des erreurs.

Ici, une clé représentera le nom de la vanne : « V1A », « V2C », etc.

Et une valeur représentera son débit : 1560, 887, etc.

Initialisation de la HashMap avec flux

Les premières informations utiles du challenge se trouvaient dans la variable flux qui contenait les débits des vannes de niveau 1. On pouvait donc parcourir flux, extraire les données intéressantes avec un peu de parsing et initialiser notre HashMap avec de premières valeurs :

// == Initialisation des débits de départ pour les vannes de niveau 1
for (String fluxVanne : flux) {
    String[] parts = fluxVanne.split(":"); // Divise une seule fois la chaîne
    String vanne = parts[0];               // Extraction du code de la vanne (ex : "V1A")
    int debitInitial = Integer.parseInt(parts[1]); // Extraction du débit initial (ex : 2621)
    debitParVanne.put(vanne, debitInitial);
}

Un peu d’explications :

  • On parcourt flux, et chaque élément de flux se retrouvera dans la chaine de caractères fluxVanne
  • La méthode split nous permet de parser fluxVanne et de stocker chaque morceau dans parts
  • On récupère alors le nom de la vanne et son débit initial qu’on transforme en entier grâce à Integer.parseInt
  • On utilise ensuite la méthode put, disponible avec HashMap qui permet de définir un nouvel élément en indiquant en premier paramètre la clé, et en second la valeur.

Parcours de network et mise à jour de la HashMap en Java

Maintenant il s’agit de parcourir tout le réseau pour suivre les débits de chaque vanne.

// == Répartition des débits dans le réseau
for (String connexion : network) {
    String[] parts = connexion.split(":"); // Divise la chaîne une seule fois
    String vanneParent = parts[0]; // Extraction du code de la vanne parent (ex : "V1A")
    int debitParent = debitParVanne.getOrDefault(vanneParent, 0); // Récupération du débit de la vanne parent

    // Vannes enfants recevant de l'eau de la vanne parent
    String[] vannesEnfants = parts[1].split(","); // Séparation des vannes enfants

    // Distribution équitable du débit du parent vers chaque vanne enfant
    int debitDistribue = debitParent / vannesEnfants.length;

    for (String vanneEnfant : vannesEnfants) {
        // On ajoute le débit distribué à chaque vanne enfant
        debitParVanne.put(
            vanneEnfant,
            debitParVanne.getOrDefault(vanneEnfant, 0) + debitDistribue);
    }
}

Un peu d’explications :

  • On commence par du parsing car chaque élément de network contient à la fois la vanne parent et les vannes enfant. On a besoin de passer de « V1A:V2B,V2C » à « V1A » d’un côté et « V2B,V2C » de l’autre
  • La vanne parent est la première partie
  • Pour récupérer le débit, on va chercher la valeur dans la HashMap grâce à la méthode getOrDefault() qui prend en paramètre une clé de la HashMap et une valeur par défaut si jamais la vanne n’existe pas (encore). Si on utilise simplement la méthode get(), on peut avoir des erreurs lorsqu’une vanne présentée n’existe pas encore dans la HashMap (cela peut arriver à partir du niveau 2).
  • Ensuite, on parse (à nouveau) pour séparer les vannes enfant. On a besoin de passer de « V2B,V2C » à « V2B » et « V2C »
  • On calcule le débit distribué aux enfants en divisant le débit du parent par le nombre d’enfants. Pour cela on compte le nombre d’éléments contenus dans vannesEnfants.
  • Enfin, on parcourt chaque vanneEnfant pour mettre à jour la HashMap :
    • Au niveau de la clé correspondant à la dénomination de la vanne enfant
    • La somme du débit du parent + la valeur déjà présente sur la clé, ou zéro si celle-ci n’existait pas encore. Cela est rendu possible à nouveau par la méthode getOrDefault().

Recherche de la vanne 4 maximale

Pour cela, on met en place un algorithme classique de recherche de maximum :

// == Recherche des vannes de niveau 4 avec le débit maximal
int debitMax = 0;
String vannesMax = "";

for (Map.Entry<String, Integer> entree : debitParVanne.entrySet()) {
    String vanne = entree.getKey();
    int debit = entree.getValue();

    // Filtrer pour ne garder que les vannes de niveau 4
    if (vanne.charAt(1) == '4') {
        if (debit > debitMax) {
            // Mise à jour du débit maximal et réinitialisation de la chaîne des vannes avec ce débit
            debitMax = debit;
            vannesMax = vanne;
        } else if (debit == debitMax) {
            // Ajout de la vanne en cas d'égalité de débit
            vannesMax += vanne;
        }
    }
}

Un peu d’explications :

  • On initialise les variables qui vont permettre de stocker le maximum et la vanne correspondante
  • On parcourt chaque élément de notre HashMap grâce à la méthode entrySet() qui permet de récupérer chaque paire « clé/valeur » qu’on stocke dans une Map.
  • On vérifie qu’on est bien sur une vanne de niveau 4 en regardant le caractère 1 (on commence à zéro, donc 1 est le deuxième caractère)
  • Et on gère le maximum, avec la gestion d’une potentielle égalité (et donc plusieurs vannes à stocker)

Il ne reste plus qu’à afficher le résultat : 

System.out.println(debitMax + "_" + vannesMax);

Récapitulatif de la HashMap en Java

Initialisation d’une HashMap

HashMap<K, V> map = new HashMap<>();

K est le type de la clé. V est le type de la valeur.

Ajout d’un élément dans une HashMap

debitParVanne.put("V1A", 1245);

On utilise la méthode put(), la clé en premier, la valeur ensuite. Si la clé existe déjà, la valeur est mise à jour.

Accès à un élément dans une HashMap

int debit = debitParVanne.get("V1A");

On utilise la méthode get(). Si la clé n’existe pas, get retourne null.

Comme vu dans le corrigé, il y a aussi la méthode getOrDefault() qui permet de retourner une valeur définie si la clé n’existe pas.

Supprimer un élément dans une HashMap

debitParVanne.remove("V1A");

On utilise la méthode remove(). Si la clé n’existe pas, rien ne se passe, aucune erreur n’est générée.

Vérifier la présence d’un élément dans une HashMap

if (debitParVanne.containsKey("V1A")) {} // Vérification de l'existence d'une clé
if (debitParVanne.containsValue(1245)) {} // Vérification de l'existence d'une valeur

2 méthodes containsKey ou containsValue selon ce qu’on cherche à vérifier.

Parcourir les éléments d’une HashMap

for (String key : debitParVanne.keySet()) {} // On parcourt seulement les clés
for (Integer value : debitParVanne.values()) {} // On parcourt seulement les valeurs
for (Map.Entry<String, Integer> entry : debitParVanne.entrySet()) { // On parcourt les deux à la fois

On a vu dans le corrigé la dernière méthode permettant de tout parcourir à la fois mais on peut aussi parcourir seulement les valeurs ou seulement les clés !

Récupérer la taille d’une HashMap

int nbVannes = debitParVanne.size();

Il en existe encore d’autres mais pour une premier tour d’horizon c’est pas mal !

Code complet

Et voici le code complet de résolution du challenge, en java, en mettant bout à bout toutes les portions de code décrites jusqu’ici : (avec un jeu de données aléatoire)

import java.util.*;
import java.io.*;
import java.math.*;

public class Challenge
{
    public static void main(String[] args)
    {
        //== NE PAS TOUCHER
        String[] flux = {"V1A:2226", "V1B:2975", "V1C:2382"};
		String[] network = {"V1A:V2A,V2C,V2D", "V1B:V2A,V2D", "V1C:V2B,V2C,V2A", "V2A:V3G,V3D,V3E", "V2B:V3C,V3E,V3D,V3G,V3B", "V2C:V3F,V3G,V3E,V3D,V3A", "V2D:V3F,V3C,V3D,V3A,V3G", "V3A:V4I,V4K,V4L,V4E", "V3B:V4F,V4E,V4A,V4I,V4J", "V3C:V4I,V4L,V4B,V4C", "V3D:V4F,V4H,V4G,V4D,V4I", "V3E:V4E,V4A,V4H,V4K", "V3F:V4G,V4E,V4B,V4H,V4D", "V3G:V4K,V4J,V4I,V4G,V4C,V4H"};
        //== NE PAS TOUCHER
        
        // == Création d'une HashMap pour stocker les débits de chaque vanne
        HashMap<String, Integer> debitParVanne = new HashMap<>();

        // == Initialisation des débits de départ pour les vannes de niveau 1
        for (String fluxVanne : flux) {
            String[] parts = fluxVanne.split(":"); // Divise une seule fois la chaîne
            String vanne = parts[0];               // Extraction du code de la vanne (ex : "V1A")
            int debitInitial = Integer.parseInt(parts[1]); // Extraction du débit initial (ex : 2621)
            debitParVanne.put(vanne, debitInitial);
        }
        
        // == Répartition des débits dans le réseau
        for (String connexion : network) {
            String[] parts = connexion.split(":"); // Divise la chaîne une seule fois
            String vanneParent = parts[0]; // Extraction du code de la vanne parent (ex : "V1A")
            int debitParent = debitParVanne.getOrDefault(vanneParent, 0); // Récupération du débit de la vanne parent
        
            // Vannes enfants recevant de l'eau de la vanne parent
            String[] vannesEnfants = parts[1].split(","); // Séparation des vannes enfants
        
            // Distribution équitable du débit du parent vers chaque vanne enfant
            int debitDistribue = debitParent / vannesEnfants.length;
        
            for (String vanneEnfant : vannesEnfants) {
                // On ajoute le débit distribué à chaque vanne enfant
                debitParVanne.put(
                    vanneEnfant,
                    debitParVanne.getOrDefault(vanneEnfant, 0) + debitDistribue
                );
            }
        }
        
        // == Recherche des vannes de niveau 4 avec le débit maximal
        int debitMax = 0;
        String vannesMax = "";
        
        for (Map.Entry<String, Integer> entree : debitParVanne.entrySet()) {
            String vanne = entree.getKey();
            int debit = entree.getValue();
        
            // Filtrer pour ne garder que les vannes de niveau 4
            if (vanne.charAt(1) == '4') {
                if (debit > debitMax) {
                    // Mise à jour du débit maximal et réinitialisation de la chaîne des vannes avec ce débit
                    debitMax = debit;
                    vannesMax = vanne;
                } else if (debit == debitMax) {
                    // Ajout de la vanne en cas d'égalité de débit
                    vannesMax += vanne;
                }
            }
        }
        
        System.out.println(debitMax + "_" + vannesMax);
    }
}

Qui a codé ce superbe contenu ?

Keep learning

Other content to discover