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.
Verwenden Sie 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 eineListvonString-Objekten als Eingabe nimmt undtruezurückgibt, wenn sie Duplikate enthält, undfalsesonst.Set<String> uniqueElements = new HashSet<>();: Dies erstellt ein leeresHashSetnamensuniqueElements.HashSetist so konzipiert, dass es nur einzigartige Elemente speichert.for (String element : list): Diese Schleife durchläuft jedeselementin der Eingabe-list.if (uniqueElements.contains(element)): Dies prüft, ob das aktuelleelementbereits imuniqueElements-HashSetvorhanden ist. Wenn ja, bedeutet dies, dass wir ein Duplikat gefunden haben, und die Methode gibttruezurück.uniqueElements.add(element);: Wenn das Element noch nicht imHashSetist, wird es hinzugefügt. DaHashSetnur 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 Methodefalsezurück.- Die
main-Methode zeigt, wie man diecontainsDuplicates-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.
Vergleichen Sie die Größe der Liste mit der Größe des 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 einHashSetund initialisiert es mit allen Elementen aus der Eingabe-list. DasHashSetbehandelt 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ünglichenlist(list.size()) mit der Anzahl der einzigartigen Elemente imHashSet(uniqueElements.size()). Wenn die Größen unterschiedlich sind (!=), bedeutet dies, dass es Duplikate in der Liste gab, und die Methode gibttruezurück. Wenn die Größen gleich sind, gab es keine Duplikate, und die Methode gibtfalsezurü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.
Testen 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.
