TD4 Les HashMap et ArrayList

Cours : Les ArrayList en Java

Introduction

Nous avons vu précédemment l'usage des tableaux pour le stockage de données. Bien que très efficaces et économes en mémoire, leur utilisation est limitée aux trois opérations principales suivantes :

Ces limitations rendent les tableaux peu adaptés à certaines situations où la taille ou le contenu des données évoluent dynamiquement.

Avantages des tableaux

Les tableaux restent extrêmement efficaces en termes de performances et d'économie de mémoire. Voici une comparaison entre tableaux et ArrayList :

Exemple de performance

import java.util.ArrayList;
import java.lang.Math;

public class Comparaison {

    public static void main(String... args) {

        for (int sizePower = 1; sizePower < 10; sizePower++) {
            int SIZE = (int) Math.pow(10, sizePower);

            long time = System.currentTimeMillis();
            {
                int[] tableau = new int[SIZE];
                for (int i = 0; i < tableau.length; i++) {
                    tableau[i] = i;
                }
                long sum = 0;
                for (int i = tableau.length - 1; i >= 0; i--) {
                    sum += tableau[i];
                }
            }
            long t1 = System.currentTimeMillis() - time;

            time = System.currentTimeMillis();
            {
                ArrayList<Integer> arrayList = new ArrayList<>();
                for (int i = 0; i < SIZE; i++) {
                    arrayList.add(i);
                }
                long sum = 0;
                for (int i = arrayList.size() - 1; i >= 0; i--) {
                    sum += arrayList.get(i);
                }
            }
            long t2 = System.currentTimeMillis() - time;

            System.out.println(SIZE + ";" + t1 + ";" + t2);
        }
    }
}

Comparaison

Avantages des ArrayList

Contrairement aux tableaux, les ArrayList offrent de nombreuses fonctionnalités supplémentaires, notamment :

  1. Redimensionnement dynamique :

    • La taille d’une ArrayList s'ajuste automatiquement en fonction des éléments ajoutés ou supprimés.
    • Plus besoin de définir une taille fixe.

  2. Manipulation des données simplifiée :

    • Ajout (add), suppression (remove), insertion (add(index, element)).
    • Les éléments se décalent automatiquement pour maintenir l’ordre.

  3. Richesse des méthodes :

    • Les ArrayList incluent un ensemble de méthodes prêtes à l’emploi pour travailler sur les données.

Méthodes principales des ArrayList

Voici les méthodes les plus fréquemment utilisées avec des exemples :

Ajout d'éléments

ArrayList<String> liste = new ArrayList<>();
liste.add("A");
liste.add("B");
System.out.println(liste); // Affiche [A, B]

Insertion à un indice spécifique

liste.add(1, "C");
System.out.println(liste); // Affiche [A, C, B]

Suppression d'éléments

liste.remove(1); // Supprime l'élément à l'indice 1
System.out.println(liste); // Affiche [A, B]

Récupération d'un élément

String element = liste.get(0);
System.out.println(element); // Affiche A

Vérification de la présence d'un élément

if (liste.contains("A")) {
    System.out.println("A est présent !");
}

Taille de la liste

System.out.println(liste.size()); // Affiche 2

Parcours de la liste

for (String s : liste) {
    System.out.println(s);
}

Points communs entre tableaux et ArrayList

Iterabilité

Les deux sont itérables : ils peuvent être utilisés dans un for amélioré :

Typage fort

Les ArrayList comme les tableaux nécessitent l'utilisation d'un typage fort, donc on doit préciser le type du contenu.

Mais les ArrayList ne peuvent contenir que des objets

Donc nous sommes obligés de passer par des types enveloppe.

Exercice d'application types enveloppe

Exercices pratiques

Exercice 1 : Manipulation des ArrayList

Exercice 2 : Comparaison des performances

Exercice 3 : Conversion ArrayList -> Tableau

Cours : Les HashMap en Java

Introduction

Les tableaux et les ArrayList permettent de stocker et de manipuler des collections de données. Cependant, ils ont une limitation importante : l'accès aux données est basé sur leur indice.

Les HashMap, quant à elles, permettent d'associer des clés à des valeurs, offrant une flexibilité considérable pour les recherches et les manipulations de données.

Avantages des HashMap

Les HashMap offrent plusieurs avantages par rapport aux structures de données précédentes :

  1. Accès rapide aux données :

    • Une HashMap utilise une table de hachage, permettant un accès très rapide aux éléments via leurs clés.

  2. Association clé-valeur :

    • Contrairement aux tableaux, chaque élément stocké dans une HashMap est une paire clé-valeur.

  3. Manipulation flexible :

    • Ajout (put), récupération (get), suppression (remove), et vérifications (containsKey, containsValue).

  4. Taille dynamique :

    • La HashMap ajuste automatiquement sa capacité au besoin, sans intervention manuelle.

Méthodes principales des HashMap

Voici les méthodes les plus fréquemment utilisées, avec des exemples :

Ajout d'une paire clé-valeur

HashMap<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
map.put("Bob", 30);
System.out.println(map);

Récupération d'une valeur

int age = map.get("Alice");
System.out.println(age);

Suppression d'une paire clé-valeur

map.remove("Bob");
System.out.println(map);

Vérification de l'existence d'une clé ou d'une valeur

if (map.containsKey("Alice")) {
    System.out.println("Alice est dans la map !");
}
if (map.containsValue(25)) {
    System.out.println("Une valeur 25 existe dans la map !");
}

Parcours d'une HashMap

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

Comparaison des performances

Les HashMap sont très performantes pour l'accès et la manipulation des données par clé. Voici une démonstration simple :

import java.util.HashMap;

public class PerformanceTest {

    public static void main(String[] args) {
        int size = 1000000;
        HashMap<Integer, Integer> map = new HashMap<>();

        // Insertion
        long start = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            map.put(i, i);
        }
        long insertionTime = System.currentTimeMillis() - start;

        // Recherche
        start = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            map.get(i);
        }
        long searchTime = System.currentTimeMillis() - start;

        System.out.println("Temps d'insertion : " + insertionTime + " ms");
        System.out.println("Temps de recherche : " + searchTime + " ms");
    }
}

Exemples pratiques

Exercice 1 : Manipulation des HashMap

Exercice 2 : Utilisation des méthodes principales

Exercice 3 : Parcours et manipulation des données