Comment vérifier si une liste contient des éléments dupliqués en Java

Introduction

Dans ce laboratoire, vous apprendrez à vérifier efficacement si une List Java contient des éléments dupliqués. Nous allons explorer une technique courante et efficace utilisant la structure de données HashSet.

Vous allez tout d'abord implémenter une méthode qui exploite la propriété des éléments uniques de HashSet pour détecter les doublons en parcourant la liste et en ajoutant les éléments à l'ensemble. Si un élément est déjà présent dans l'ensemble, un doublon est trouvé. Ensuite, vous apprendrez une approche alternative en comparant la taille de la liste d'origine avec la taille d'un HashSet rempli avec les éléments de la liste. Enfin, vous testerez votre implémentation dans diverses situations, y compris avec des listes nulles et vides, pour garantir sa robustesse.

Skills Graph

Utiliser HashSet pour la détection de doublons

Dans cette étape, nous allons explorer comment utiliser un HashSet en Java pour détecter efficacement les éléments dupliqués dans une collection. HashSet fait partie du Framework de collections Java et est particulièrement utile pour stocker des éléments uniques.

Tout d'abord, créons un nouveau fichier Java nommé DuplicateDetector.java dans votre répertoire ~/project. Vous pouvez le faire en utilisant l'Explorateur de fichiers de l'IDE Web à gauche. Cliquez avec le bouton droit dans la zone ~/project, sélectionnez "Nouveau fichier" et tapez DuplicateDetector.java.

Maintenant, ouvrez le fichier DuplicateDetector.java dans l'Éditeur de code et ajoutez le code suivant :

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DuplicateDetector {

    public static boolean containsDuplicates(List<String> list) {
        // Create a HashSet to store unique elements
        Set<String> uniqueElements = new HashSet<>();

        // Iterate through the list
        for (String element : list) {
            // If the element is already in the HashSet, it's a duplicate
            if (uniqueElements.contains(element)) {
                return true; // Found a duplicate
            }
            // Otherwise, add the element to the HashSet
            uniqueElements.add(element);
        }

        // If the loop finishes without finding duplicates, return false
        return false;
    }

    public static void main(String[] args) {
        // Example usage
        List<String> myListWithDuplicates = new ArrayList<>();
        myListWithDuplicates.add("apple");
        myListWithDuplicates.add("banana");
        myListWithDuplicates.add("apple"); // Duplicate
        myListWithDuplicates.add("orange");

        List<String> myListWithoutDuplicates = new ArrayList<>();
        myListWithoutDuplicates.add("grape");
        myListWithoutDuplicates.add("mango");
        myListWithoutDuplicates.add("kiwi");

        System.out.println("List with duplicates: " + myListWithDuplicates);
        System.out.println("Contains duplicates? " + containsDuplicates(myListWithDuplicates)); // Expected: true

        System.out.println("\nList without duplicates: " + myListWithoutDuplicates);
        System.out.println("Contains duplicates? " + containsDuplicates(myListWithoutDuplicates)); // Expected: false
    }
}

Comprenons les parties clés de ce code :

• import java.util.ArrayList;, import java.util.HashSet;, import java.util.List;, import java.util.Set; : Ces lignes importent les classes nécessaires du Framework de collections Java.
• public static boolean containsDuplicates(List<String> list) : Il s'agit d'une méthode qui prend une List d'objets String en entrée et renvoie true si elle contient des doublons, et false sinon.
• Set<String> uniqueElements = new HashSet<>(); : Cela crée un HashSet vide appelé uniqueElements. HashSet est conçu pour stocker uniquement des éléments uniques.
• for (String element : list) : Cette boucle parcourt chaque element de la list d'entrée.
• if (uniqueElements.contains(element)) : Cela vérifie si l'element actuel est déjà présent dans le HashSet uniqueElements. Si c'est le cas, cela signifie que nous avons trouvé un doublon, et la méthode renvoie true.
• uniqueElements.add(element); : Si l'élément n'est pas déjà dans le HashSet, il est ajouté. Étant donné que HashSet ne stocke que des éléments uniques, l'ajout d'un élément déjà présent n'a aucun effet.
• return false; : Si la boucle se termine sans trouver de doublons, la méthode renvoie false.
• La méthode main montre comment utiliser la méthode containsDuplicates avec des listes d'exemple.

Enregistrez le fichier DuplicateDetector.java (Ctrl+S ou Cmd+S).

Maintenant, compilons et exécutons ce programme dans le Terminal. Assurez-vous d'être dans le répertoire ~/project.

Compilez le code :

javac DuplicateDetector.java

S'il n'y a pas d'erreurs de compilation, vous ne verrez aucun résultat.

Maintenant, exécutez le code compilé :

java DuplicateDetector

Vous devriez voir un résultat similaire à ceci :

List with duplicates: [apple, banana, apple, orange]
Contains duplicates? true

List without duplicates: [grape, mango, kiwi]
Contains duplicates? false

Ce résultat confirme que notre méthode containsDuplicates a correctement identifié la liste avec des doublons. L'utilisation d'un HashSet est un moyen efficace de vérifier les doublons car la vérification de la présence d'un élément dans un HashSet (en utilisant contains()) est très rapide, en moyenne.

Comparer la taille de la liste avec la taille de l'ensemble

Dans l'étape précédente, nous avons utilisé un HashSet pour vérifier les doublons en parcourant la liste et en ajoutant les éléments à l'ensemble. Une méthode plus simple et souvent plus efficace pour détecter les doublons consiste à comparer la taille de la liste d'origine avec la taille d'un HashSet créé à partir de cette liste.

Rappelez-vous qu'un HashSet ne stocke que des éléments uniques. Si une liste contient des doublons, la taille d'un HashSet créé à partir de cette liste sera inférieure à la taille de la liste d'origine. S'il n'y a pas de doublons, les tailles seront les mêmes.

Modifions notre fichier DuplicateDetector.java pour implémenter cette approche. Ouvrez ~/project/DuplicateDetector.java dans l'Éditeur de code.

Remplacez la méthode containsDuplicates par le code suivant :

    public static boolean containsDuplicates(List<String> list) {
        // Create a HashSet from the list
        Set<String> uniqueElements = new HashSet<>(list);

        // Compare the size of the list with the size of the HashSet
        return list.size() != uniqueElements.size();
    }

Voici ce qui se passe dans le nouveau code :

• Set<String> uniqueElements = new HashSet<>(list); : Cette ligne crée directement un HashSet et l'initialise avec tous les éléments de la list d'entrée. Le HashSet gère automatiquement l'unicité, donc tous les éléments dupliqués de la liste ne seront pas ajoutés à l'ensemble.
• return list.size() != uniqueElements.size(); : Cette ligne compare le nombre d'éléments dans la list d'origine (list.size()) avec le nombre d'éléments uniques dans le HashSet (uniqueElements.size()). Si les tailles sont différentes (!=), cela signifie qu'il y avait des doublons dans la liste, et la méthode renvoie true. Si les tailles sont les mêmes, il n'y avait pas de doublons, et la méthode renvoie false.

La méthode main peut rester la même car elle appelle déjà la méthode containsDuplicates.

Enregistrez le fichier DuplicateDetector.java (Ctrl+S ou Cmd+S).

Maintenant, compilons et exécutons le programme modifié. Assurez-vous d'être dans le répertoire ~/project dans le Terminal.

Compilez le code :

javac DuplicateDetector.java

Exécutez le code compilé :

java DuplicateDetector

Vous devriez voir le même résultat que précédemment :

List with duplicates: [apple, banana, apple, orange]
Contains duplicates? true

List without duplicates: [grape, mango, kiwi]
Contains duplicates? false

Cela confirme que notre nouvelle méthode plus simple pour détecter les doublons en utilisant la comparaison des tailles fonctionne correctement. Cette approche est généralement plus concise et souvent plus efficace que de parcourir la liste et de vérifier l'appartenance un par un, en particulier pour les listes plus grandes.

Tester avec des listes nulles et vides

En programmation réelle, il est important de prendre en compte les cas limites, comme lorsque une liste peut être vide ou même null. Notre méthode containsDuplicates actuelle fonctionne bien pour les listes avec des éléments, mais que se passe-t-il si nous passons une liste vide ou une liste null ?

Testons cela en ajoutant plus d'exemples à notre méthode main dans ~/project/DuplicateDetector.java. Ouvrez le fichier dans l'Éditeur de code et ajoutez les lignes suivantes à la méthode main, après le code existant :

        System.out.println("\nEmpty list: " + new ArrayList<>());
        System.out.println("Contains duplicates? " + containsDuplicates(new ArrayList<>())); // Expected: false

        List<String> nullList = null;
        System.out.println("\nNull list: " + nullList);
        // The following line will cause a NullPointerException if not handled
        // System.out.println("Contains duplicates? " + containsDuplicates(nullList));

Enregistrez le fichier (Ctrl+S ou Cmd+S).

Maintenant, compilez et exécutez le programme à nouveau.

Compilez :

javac DuplicateDetector.java

Exécutez :

java DuplicateDetector

Vous devriez voir le résultat pour la liste vide :

List with duplicates: [apple, banana, apple, orange]
Contains duplicates? true

List without duplicates: [grape, mango, kiwi]
Contains duplicates? false

Empty list: []
Contains duplicates? false

Le résultat pour la liste vide est correct ; une liste vide ne contient pas de doublons.

Cependant, si vous décommentez la ligne System.out.println("Contains duplicates? " + containsDuplicates(nullList)); et que vous essayez de compiler et d'exécuter, vous obtiendrez une NullPointerException. Cela se produit car nous essayons de créer un HashSet à partir d'une liste null, ce qui n'est pas autorisé.

Pour rendre notre méthode containsDuplicates plus robuste, nous devrions gérer le cas où la liste d'entrée est null. Nous pouvons ajouter une vérification au début de la méthode.

Modifiez la méthode containsDuplicates dans ~/project/DuplicateDetector.java pour inclure une vérification de nullité :

    public static boolean containsDuplicates(List<String> list) {
        // Handle null input
        if (list == null) {
            return false; // A null list does not contain duplicates
        }

        // Create a HashSet from the list
        Set<String> uniqueElements = new HashSet<>(list);

        // Compare the size of the list with the size of the HashSet
        return list.size() != uniqueElements.size();
    }

Maintenant, décommentez la ligne qui teste la liste null dans la méthode main :

        List<String> nullList = null;
        System.out.println("\nNull list: " + nullList);
        System.out.println("Contains duplicates? " + containsDuplicates(nullList)); // Expected: false

Enregistrez le fichier (Ctrl+S ou Cmd+S).

Compilez et exécutez le programme une dernière fois.

Compilez :

javac DuplicateDetector.java

Exécutez :

java DuplicateDetector

Le résultat devrait maintenant inclure le résultat pour la liste null sans planter :

List with duplicates: [apple, banana, apple, orange]
Contains duplicates? true

List without duplicates: [grape, mango, kiwi]
Contains duplicates? false

Empty list: []
Contains duplicates? false

Null list: null
Contains duplicates? false

En ajoutant la vérification de nullité, notre méthode containsDuplicates est maintenant plus robuste et peut gérer les entrées null de manière gracieuse. C'est une pratique importante en programmation pour éviter les erreurs inattendues.

Résumé

Dans ce laboratoire (lab), nous avons appris à vérifier si une List Java contient des éléments dupliqués. Nous avons exploré l'utilisation d'un HashSet pour une détection efficace des doublons. En parcourant la liste et en essayant d'ajouter chaque élément à un HashSet, nous pouvons rapidement déterminer si un élément est déjà présent, ce qui indique un doublon.

Nous avons également appris une méthode alternative en comparant la taille de la liste d'origine avec la taille d'un HashSet créé à partir de cette liste. Si les tailles sont différentes, cela signifie qu'il y a des doublons. Enfin, nous avons pris en compte les cas limites en testant les méthodes avec des listes nulles et vides pour garantir la robustesse.