Wie man prüft, ob eine Liste in Java doppelte Elemente enthält

Einführung

In diesem Lab werden Sie lernen, wie Sie effizient prüfen können, ob eine Java-List doppelte Elemente enthält. Wir werden eine gängige und effektive Technik mithilfe der HashSet-Datenstruktur untersuchen.

Zunächst werden Sie eine Methode implementieren, die die Eigenschaft von HashSet, einzigartige Elemente zu speichern, nutzt, um Duplikate zu erkennen. Dazu gehen Sie die Liste durch und fügen die Elemente in das Set ein. Wenn ein Element bereits im Set vorhanden ist, wurde ein Duplikat gefunden. Anschließend werden Sie einen alternativen Ansatz kennenlernen, indem Sie die Größe der ursprünglichen Liste mit der Größe eines HashSet vergleichen, das mit den Elementen der Liste befüllt wurde. Abschließend werden Sie Ihre Implementierung in verschiedenen Szenarien testen, einschließlich Null- und leerer Listen, um die Robustheit sicherzustellen.

Skills Graph

Verwendung von HashSet zur Duplikatdetektion

In diesem Schritt werden wir untersuchen, wie man in Java ein HashSet verwendet, um effizient doppelte Elemente in einer Sammlung zu erkennen. HashSet ist Teil des Java Collections Frameworks und besonders nützlich für die Speicherung einzigartiger Elemente.

Zunächst erstellen wir eine neue Java-Datei namens DuplicateDetector.java in Ihrem ~/project-Verzeichnis. Sie können dies über den Dateiexplorer der WebIDE auf der linken Seite tun. Klicken Sie mit der rechten Maustaste im ~/project-Bereich, wählen Sie "Neue Datei" und geben Sie DuplicateDetector.java ein.

Öffnen Sie jetzt die Datei DuplicateDetector.java im Code-Editor und fügen Sie folgenden Code hinzu:

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

Lassen Sie uns die wichtigsten Teile dieses Codes verstehen:

• import java.util.ArrayList;, import java.util.HashSet;, import java.util.List;, import java.util.Set;: Diese Zeilen importieren die erforderlichen Klassen aus dem Java Collections Framework.
• public static boolean containsDuplicates(List<String> list): Dies ist eine Methode, die eine List von String-Objekten als Eingabe nimmt und true zurückgibt, wenn sie Duplikate enthält, und false sonst.
• Set<String> uniqueElements = new HashSet<>();: Dies erstellt ein leeres HashSet namens uniqueElements. HashSet ist so konzipiert, dass es nur einzigartige Elemente speichert.
• for (String element : list): Diese Schleife durchläuft jedes element in der Eingabe-list.
• if (uniqueElements.contains(element)): Dies prüft, ob das aktuelle element bereits im uniqueElements-HashSet vorhanden ist. Wenn ja, bedeutet dies, dass wir ein Duplikat gefunden haben, und die Methode gibt true zurück.
• uniqueElements.add(element);: Wenn das Element noch nicht im HashSet ist, wird es hinzugefügt. Da HashSet nur einzigartige Elemente speichert, hat das Hinzufügen eines bereits vorhandenen Elements keine Auswirkungen.
• return false;: Wenn die Schleife ohne das Finden von Duplikaten abgeschlossen wird, gibt die Methode false zurück.
• Die main-Methode zeigt, wie man die containsDuplicates-Methode mit Beispiel-Listen verwendet.

Speichern Sie die Datei DuplicateDetector.java (Strg+S oder Cmd+S).

Jetzt kompilieren und führen wir dieses Programm im Terminal aus. Stellen Sie sicher, dass Sie sich im ~/project-Verzeichnis befinden.

Kompilieren Sie den Code:

javac DuplicateDetector.java

Wenn es keine Kompilierungsfehler gibt, sehen Sie keine Ausgabe.

Führen Sie jetzt den kompilierten Code aus:

java DuplicateDetector

Sie sollten eine Ausgabe ähnlich der folgenden sehen:

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

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

Diese Ausgabe bestätigt, dass unsere containsDuplicates-Methode die Liste mit Duplikaten korrekt identifiziert hat. Die Verwendung eines HashSet ist eine effiziente Methode, um auf Duplikate zu prüfen, da die Prüfung auf die Anwesenheit eines Elements in einem HashSet (mit contains()) im Durchschnitt sehr schnell ist.

Vergleich der Größe einer Liste mit der Größe eines Sets

Im vorherigen Schritt haben wir ein HashSet verwendet, um Duplikate zu prüfen, indem wir die Liste durchlaufen und die Elemente in das Set hinzufügten. Eine einfachere und oft effizientere Methode, Duplikate zu erkennen, besteht darin, die Größe der ursprünglichen Liste mit der Größe eines aus dieser Liste erstellten HashSet zu vergleichen.

Denken Sie daran, dass ein HashSet nur einzigartige Elemente speichert. Wenn eine Liste Duplikate enthält, wird die Größe eines aus dieser Liste erstellten HashSet kleiner sein als die Größe der ursprünglichen Liste. Wenn es keine Duplikate gibt, sind die Größen gleich.

Lassen Sie uns die Datei DuplicateDetector.java ändern, um diesen Ansatz zu implementieren. Öffnen Sie ~/project/DuplicateDetector.java im Code-Editor.

Ersetzen Sie die containsDuplicates-Methode durch folgenden Code:

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

Hier ist, was im neuen Code passiert:

• Set<String> uniqueElements = new HashSet<>(list);: Diese Zeile erstellt direkt ein HashSet und initialisiert es mit allen Elementen aus der Eingabe-list. Das HashSet behandelt automatisch die Eindeutigkeit, sodass alle doppelten Elemente aus der Liste nicht in das Set hinzugefügt werden.
• return list.size() != uniqueElements.size();: Diese Zeile vergleicht die Anzahl der Elemente in der ursprünglichen list (list.size()) mit der Anzahl der einzigartigen Elemente im HashSet (uniqueElements.size()). Wenn die Größen unterschiedlich sind (!=), bedeutet dies, dass es Duplikate in der Liste gab, und die Methode gibt true zurück. Wenn die Größen gleich sind, gab es keine Duplikate, und die Methode gibt false zurück.

Die main-Methode kann gleich bleiben, da sie bereits die containsDuplicates-Methode aufruft.

Speichern Sie die Datei DuplicateDetector.java (Strg+S oder Cmd+S).

Jetzt kompilieren und führen wir das geänderte Programm aus. Stellen Sie sicher, dass Sie sich im ~/project-Verzeichnis im Terminal befinden.

Kompilieren Sie den Code:

javac DuplicateDetector.java

Führen Sie den kompilierten Code aus:

java DuplicateDetector

Sie sollten die gleiche Ausgabe wie zuvor sehen:

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

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

Dies bestätigt, dass unsere neue, einfachere Methode zur Duplikatdetektion mithilfe des Größenvergleichs korrekt funktioniert. Dieser Ansatz ist im Allgemeinen kompakter und oft effizienter als das Durchlaufen und die einzelne Prüfung auf Enthaltensein, insbesondere für größere Listen.

Test mit Null- und leeren Listen

In der Praxis der Programmierung ist es wichtig, Randfälle zu berücksichtigen, wie beispielsweise wenn eine Liste leer oder sogar null sein kann. Unsere aktuelle containsDuplicates-Methode funktioniert gut für Listen mit Elementen, aber was passiert, wenn wir eine leere Liste oder eine null-Liste übergeben?

Lassen Sie uns dies testen, indem wir weitere Beispiele in unsere main-Methode in ~/project/DuplicateDetector.java hinzufügen. Öffnen Sie die Datei im Code-Editor und fügen Sie die folgenden Zeilen nach dem bestehenden Code in die main-Methode ein:

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

Speichern Sie die Datei (Strg+S oder Cmd+S).

Jetzt kompilieren und führen Sie das Programm erneut aus.

Kompilieren:

javac DuplicateDetector.java

Ausführen:

java DuplicateDetector

Sie sollten die Ausgabe für die leere Liste sehen:

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

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

Empty list: []
Contains duplicates? false

Die Ausgabe für die leere Liste ist korrekt; eine leere Liste enthält keine Duplikate.

Wenn Sie jedoch die Zeile System.out.println("Contains duplicates? " + containsDuplicates(nullList)); einkommentieren und versuchen, zu kompilieren und auszuführen, erhalten Sie eine NullPointerException. Dies geschieht, weil wir versuchen, ein HashSet aus einer null-Liste zu erstellen, was nicht erlaubt ist.

Um unsere containsDuplicates-Methode robuster zu machen, sollten wir den Fall behandeln, dass die Eingabeliste null ist. Wir können einen Check am Anfang der Methode hinzufügen.

Ändern Sie die containsDuplicates-Methode in ~/project/DuplicateDetector.java, um einen Null-Check einzubeziehen:

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

Jetzt einkommentieren Sie die Zeile, die die null-Liste testet, in der main-Methode:

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

Speichern Sie die Datei (Strg+S oder Cmd+S).

Kompilieren und führen Sie das Programm ein letztes Mal aus.

Kompilieren:

javac DuplicateDetector.java

Ausführen:

java DuplicateDetector

Die Ausgabe sollte nun das Ergebnis für die null-Liste enthalten, ohne dass das Programm abstürzt:

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

Durch das Hinzufügen des Null-Checks ist unsere containsDuplicates-Methode nun robuster und kann null-Eingaben gracefully handhaben. Dies ist eine wichtige Praxis in der Programmierung, um unerwartete Fehler zu vermeiden.

Zusammenfassung

In diesem Lab haben wir gelernt, wie man prüft, ob eine Java-List doppelte Elemente enthält. Wir haben die Verwendung eines HashSet für eine effiziente Duplikatdetektion untersucht. Indem wir die Liste durchlaufen und versuchen, jedes Element einem HashSet hinzuzufügen, können wir schnell feststellen, ob ein Element bereits vorhanden ist, was auf ein Duplikat hinweist.

Wir haben auch eine alternative Methode gelernt, indem wir die Größe der ursprünglichen Liste mit der Größe eines aus der Liste erstellten HashSet verglichen haben. Wenn die Größen unterschiedlich sind, bedeutet dies das Vorhandensein von Duplikaten. Schließlich haben wir Randfälle berücksichtigt, indem wir die Methoden mit Null- und leeren Listen getestet haben, um die Robustheit sicherzustellen.