wake-up-neo.net

Sie sollten vor dem Einfügen in ein Set nach einem Duplikat suchen

Ich lerne Sätze zu benutzen. Meine Frage ist: Sets enthalten keine Duplikate. Wenn wir versuchen, Duplikate einzufügen, wird kein Fehler ausgegeben und Duplikate werden automatisch entfernt. Ist es eine gute Praxis, jeden Wert vor dem Einfügen in set zu überprüfen, ob er existiert oder nicht? Oder ist es in Ordnung, etwas wie den folgenden Code zu tun? Ich denke, Java würde intern die Überprüfung mit .contains(value) durchführen. Was denkst du?

Was wäre die Big O-Komplexität in beiden Fällen, wenn man bedenkt, dass n Elemente in den Satz gehen?

import Java.util.HashSet;
import Java.util.Set;

public class DuplicateTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
         Set<Integer> mySet = new HashSet<Integer>();

         mySet.add(10);
         mySet.add(20);
         mySet.add(30);
         mySet.add(40);
         mySet.add(50);
         mySet.add(50);
         mySet.add(50);
         mySet.add(50);
         mySet.add(50);
         mySet.add(50);

         System.out.println("Contents of the Hash Set :"+mySet);
    }

}
20
Zack

Wie in den docs :

public boolean add(E e)

Fügt dem Satz das angegebene Element hinzu, wenn es noch nicht vorhanden ist. Fügt formal das angegebene Element e zu dieser Gruppe hinzu, wenn diese Gruppe kein Element e2 enthält, also (e == null? E2 == null: e.equals (e2)). Wenn dieser Satz das Element bereits enthält, lässt der Aufruf den Satz unverändert und gibt false zurück.

Die add()-Methode gibt also bereits ein wahres oder ein falsches Ergebnis zurück. Sie müssen also die zusätzliche Prüfung nicht durchführen.

21
Atri

Vergleichen Sie mit der API-Dokumentation von Set.add(E)

Die add-Methode prüft, ob sich das Element bereits in der Set befindet. Wenn das Element bereits vorhanden ist, wird das neue Element nicht hinzugefügt, und die Variable Set bleibt unverändert. In den meisten Situationen müssen Sie nichts überprüfen.

Die Komplexität der Methode hängt von der konkreten Implementierung von Set ab, die Sie verwenden.

9
Alejandro Goñi

Es ist in Ordnung, nicht zu überprüfen. Dies ist der Hauptvorteil gegenüber Listen, da Duplikate automatisch herausgefiltert werden.

HashSet hat eine konstante Zeitleistung ( http://docs.Oracle.com/javase/8/docs/api/Java/util/HashSet.html )

Diese Klasse bietet eine konstante Zeitleistung für die grundlegenden Vorgänge (Hinzufügen, Entfernen, Enthalten und Größe), vorausgesetzt, die Hash-Funktion verteilt die Elemente ordnungsgemäß zwischen den Buckets

4
DMozzy

Die Add-Funktion gibt einen Booleschen Wert zurück, den Sie überprüfen können, um festzustellen, ob sich der Artikel bereits im Set befindet. Dies hängt natürlich von Ihren Bedürfnissen ab und ist keine bewährte Methode. Es ist gut zu wissen, dass ein bereits vorhandenes Element nicht entfernt wird. Es kann also nicht davon abhängen, den vorhandenen Wert mit neuen Informationen zu aktualisieren, wenn Sie Gleichheitszeichen auf der Grundlage von Ersatzschlüsseln aus Ihrer Datenbank definieren. Dies ist im Gegensatz zur Funktionsweise von Maps, da eine Karte jeden vorhandenen Wert zurückgibt und durch den neuen Wert ersetzt.

2
Greg L.

Hier finden Sie Antworten auf Ihre Fragen:

Wenn wir versuchen, Duplikate einzufügen, wird kein Fehler ausgegeben, und Entfernt Duplikate automatisch.

Ihr Verständnis ist nicht korrekt. Der Aufruf von Set.add() fügt kein neues Element hinzu, wenn es bereits im Set enthalten ist. Diese Anweisung gilt für alle Implementierungen von Set, einschließlich HashSet und TreeSet.

Ist es eine gute Praxis, jeden Wert vor dem Einfügen in Set Zu überprüfen, ob er existiert oder nicht? oder ist es in Ordnung, etwas wie den folgenden Code zu tun? Ich denke, Java würde intern die Überprüfung mit .Contains (value) durchführen. Was denkst du?

Da Ihr Verständnis von Anfang an falsch war, müssen Sie vor dem Einfügen in den Satz nicht jeden Wert überprüfen, um festzustellen, ob er bereits vorhanden ist. Ja, intern macht es etwas wie contains().

Was wäre die Komplexität von Big Oh in beiden Fällen, wenn man bedenkt, dass "N" Elemente in den Satz gehen?

Für HashSet ist die Zeitkomplexität O(1) für jede add(). Für TreeSet() - die Sie nicht verwendet haben - ist die zeitliche Komplexität O(lg N) für jede add().