Wie pflege ich eine eindeutige Liste in Java?

104

Wie erstelle ich eine Liste eindeutiger / eindeutiger Objekte (keine Duplikate) in Java?

Im Moment HashMap<String, Integer>mache ich das, da der Schlüssel überschrieben wird und wir am Ende bekommen können, HashMap.getKeySet()was einzigartig wäre. Aber ich bin sicher, es sollte einen besseren Weg geben, dies zu tun, da der Wertteil hier verschwendet wird.

Basil Bourque
quelle

Antworten:

164

Sie können eine Set- Implementierung verwenden:

Einige Infos aus dem JAVADoc:

Eine Sammlung, die keine doppelten Elemente enthält . Formal enthalten Mengen kein Elementpaar e1 und e2, so dass e1.equals (e2) und höchstens ein Nullelement. Wie der Name andeutet, modelliert diese Schnittstelle die Abstraktion mathematischer Mengen.

Hinweis: Wenn veränderbare Objekte als Set-Elemente verwendet werden, ist besondere Vorsicht geboten. Das Verhalten einer Menge wird nicht angegeben, wenn der Wert eines Objekts so geändert wird, dass sich dies auf Vergleiche auswirkt, während das Objekt ein Element in der Menge ist. Ein Sonderfall dieses Verbots ist, dass es nicht zulässig ist, dass sich eine Menge als Element enthält. "

Dies sind die Implementierungen:

  • HashSet

    Diese Klasse bietet eine konstante Zeitleistung für die grundlegenden Operationen (Hinzufügen, Entfernen, Enthalten und Größe), vorausgesetzt, die Hash-Funktion verteilt die Elemente ordnungsgemäß auf die Buckets. Das Durchlaufen dieses Satzes erfordert Zeit, die proportional zur Summe der Größe der HashSet-Instanz (Anzahl der Elemente) plus der "Kapazität" der unterstützenden HashMap-Instanz (Anzahl der Buckets) ist. Daher ist es sehr wichtig, die Anfangskapazität nicht zu hoch (oder den Lastfaktor zu niedrig) einzustellen, wenn die Iterationsleistung wichtig ist.

    Bei der Iteration von a ist HashSetdie Reihenfolge der erhaltenen Elemente undefiniert.

  • LinkedHashSet

    Implementierung der Hash-Tabelle und der verknüpften Liste der Set-Schnittstelle mit vorhersagbarer Iterationsreihenfolge. Diese Implementierung unterscheidet sich von HashSet dadurch, dass eine doppelt verknüpfte Liste geführt wird, die alle Einträge durchläuft. Diese verknüpfte Liste definiert die Iterationsreihenfolge, dh die Reihenfolge, in der Elemente in die Menge eingefügt wurden (Einfügereihenfolge). Beachten Sie, dass die Einfügereihenfolge nicht beeinflusst wird, wenn ein Element erneut in die Menge eingefügt wird. (Ein Element e wird erneut in eine Menge s eingefügt, wenn s.add (e) aufgerufen wird, wenn s.contains (e) unmittelbar vor dem Aufruf true zurückgeben würde.)

    Also, die Ausgabe des obigen Codes ...

     Set<Integer> linkedHashSet = new LinkedHashSet<>();
     linkedHashSet.add(3);
     linkedHashSet.add(1);
     linkedHashSet.add(2);
    
     for (int i : linkedHashSet) {
         System.out.println(i);
     }

    ... wird unbedingt sein

    3
    1
    2
  • TreeSet

    Diese Implementierung bietet garantierte log (n) Zeitkosten für die grundlegenden Vorgänge (Hinzufügen, Entfernen und Enthalten). Standardmäßig werden die bei der Iteration zurückgegebenen Elemente nach ihrer " natürlichen Reihenfolge " sortiert , sodass der obige Code ...

     Set<Integer> treeSet = new TreeSet<>();
     treeSet.add(3);
     treeSet.add(1);
     treeSet.add(2);
    
     for (int i : treeSet) {
         System.out.println(i);
     }

    ... gibt dies aus:

    1
    2
    3

    (Sie können eine ComparatorInstanz auch an einen TreeSetKonstruktor übergeben, damit die Elemente in einer anderen Reihenfolge sortiert werden.)

    Beachten Sie, dass die von einer Menge gepflegte Reihenfolge (unabhängig davon, ob ein expliziter Komparator bereitgestellt wird oder nicht) mit gleich übereinstimmen muss, um die Set-Schnittstelle korrekt zu implementieren. (Eine genaue Definition von konsistent mit gleich finden Sie unter Vergleichbar oder Komparator.) Dies liegt daran, dass die Set-Schnittstelle in Bezug auf die Gleichheitsoperation definiert ist, eine TreeSet-Instanz jedoch alle Elementvergleiche mit ihrer compareTo-Methode (oder compare-Methode) durchführt, also zwei Elemente, die nach dieser Methode als gleich angesehen werden, sind vom Standpunkt der Menge aus gleich. Das Verhalten einer Menge ist genau definiert, auch wenn ihre Reihenfolge nicht mit gleich übereinstimmt. Der allgemeine Vertrag der Set-Schnittstelle wird einfach nicht eingehalten.

Frank
quelle
Jetzt bin ich verwirrt, welches soll ich verwenden? Ich muss nur eine Liste eindeutiger Zeichenfolgen führen. Selbst wenn eine vorhandene Zeichenfolge hinzugefügt wird, sollte sie tatsächlich hinzugefügt werden.
1
Sie haben die Wahl ... HashSet ist universell und schnell, TreeSet ist bestellt, LinkedHashset behält die Einfügereihenfolge bei ...
Frank
6
Dies ist keine LISTE. Daher sind nicht alle LIST-Schnittstellenmethoden verfügbar.
marcolopes
2
Eine Menge ist keine Liste, ich kann Elemente in einer Menge in O (1) -Zeit (Direktzugriff) nicht nach Index suchen.
Wilmol
13

Ich möchte hier einige Dinge für das Originalplakat klarstellen, auf die andere angespielt, aber nicht wirklich explizit angegeben haben. Wenn Sie sagen, dass Sie eine eindeutige Liste möchten, ist dies genau die Definition eines geordneten Satzes. Einige andere wichtige Unterschiede zwischen der Set-Schnittstelle und der List-Schnittstelle bestehen darin, dass Sie mit List den Einfügeindex angeben können. Die Frage ist also, ob Sie die Listenschnittstelle wirklich benötigen (dh für die Kompatibilität mit einer Bibliothek eines Drittanbieters usw.), oder ob Sie Ihre Software für die Verwendung der Set-Schnittstelle neu gestalten können. Sie müssen auch überlegen, was Sie mit der Schnittstelle tun. Ist es wichtig, Elemente anhand ihres Index zu finden? Wie viele Elemente erwarten Sie in Ihrem Set? Wenn Sie viele Elemente haben möchten, ist die Bestellung wichtig?

Wenn Sie wirklich eine Liste benötigen, die nur eine eindeutige Einschränkung hat, gibt es die Apache Common Utils-Klasse org.apache.commons.collections.list.SetUniqueList, die Ihnen die List-Schnittstelle und die eindeutige Einschränkung bereitstellt. Wohlgemerkt, dies bricht jedoch die List-Oberfläche. Sie erhalten jedoch eine bessere Leistung, wenn Sie die Liste nach Index durchsuchen müssen. Wenn Sie mit der Set-Schnittstelle umgehen können und einen kleineren Datensatz haben, ist LinkedHashSet möglicherweise ein guter Weg. Es hängt nur vom Design und der Absicht Ihrer Software ab.

Auch hier hat jede Sammlung bestimmte Vor- und Nachteile. Einige schnelle Einfügungen, aber langsame Lesevorgänge, andere schnelle Lesevorgänge, aber langsame Einfügungen usw. Es ist sinnvoll, viel Zeit mit der Sammlungsdokumentation zu verbringen, um die feineren Details jeder Klasse und Schnittstelle vollständig kennenzulernen.

Paul Connolly
quelle
3
Dies gibt keine Antwort auf die Frage. Um einen Autor zu kritisieren oder um Klärung zu bitten, hinterlassen Sie einen Kommentar unter seinem Beitrag. Sie können jederzeit Ihre eigenen Beiträge kommentieren. Sobald Sie einen ausreichenden Ruf haben, können Sie jeden Beitrag kommentieren .
Zach Saucier
1
Es gibt tatsächlich eine Antwort. Wenn er nur eine Liste haben möchte, die sich wie ein Set verhält, verwenden Sie org.apache.commons.collections.list.SetUniqueList. Als Programmierer sollte er / wir jedoch vorsichtiger sein und mehr über das Problem nachdenken. Wenn dies meine Antwort verbessert: "Wie erstelle ich eine eindeutige Liste in Java?" List uniqueList = new SetUniqueList ();, so ...
Paul Connolly
3
Und Zach, ich versuche nicht, ein Idiot zu sein, aber hast du meine Antwort vor deinem Kommentar überhaupt gelesen? Oder verstehst du es einfach nicht? Wenn Sie es nicht verstehen, ist das in Ordnung - lassen Sie es mich wissen und ich werde das Thema erweitern. Ich denke nicht, dass ich eine Abhandlung über Datenstrukturen schreiben muss, um eine freundliche Antwort auf die Frage von jemandem zu geben. Es ist mir auch nicht wichtig, einen sanften Weg zu finden, um meinen Kommentar-Ruf aufzubauen, wenn ich die Antwort kenne und niemand anderes sie wirklich zur Verfügung gestellt hat.
Paul Connolly
1
Übrigens habe ich den Autor weder kritisiert noch um Klärung gebeten. Ich habe nur gesagt, dass er entweder A) die Klasse, die ich ihm gegeben habe, schnell verwenden kann oder B) sich die Zeit nehmen kann, die Unterschiede zwischen diesen Klassen wirklich zu verstehen und sich darauf zu beziehen sie zu seinen Bedürfnissen. B dauert offensichtlich länger, führt aber langfristig zu besserem Code.
Paul Connolly
8

Verwenden Sie new HashSet<String> ein Beispiel:

import java.util.HashSet;
import java.util.Set;

public class MainClass {
  public static void main(String args[]) {
    String[] name1 = { "Amy", "Jose", "Jeremy", "Alice", "Patrick" };

    String[] name2 = { "Alan", "Amy", "Jeremy", "Helen", "Alexi" };

    String[] name3 = { "Adel", "Aaron", "Amy", "James", "Alice" };

    Set<String> letter = new HashSet<String>();

    for (int i = 0; i < name1.length; i++)
      letter.add(name1[i]);

    for (int j = 0; j < name2.length; j++)
      letter.add(name2[j]);

    for (int k = 0; k < name3.length; k++)
      letter.add(name3[k]);

    System.out.println(letter.size() + " letters must be sent to: " + letter);

  }
}
tim_a
quelle
2
Nur das oben genannte Programm hinzufügen -> 11 Briefe müssen gesendet werden an: [Aaron, Alice, James, Adel, Jose, Jeremy, Amy, Alan, Patrick, Helen, Alexi]
Ammad
4

Sie können einfach eine verwenden HashSet<String>, um eine Sammlung eindeutiger Objekte zu verwalten. Wenn die IntegerWerte in Ihrer Karte wichtig sind, können Sie stattdessen mithilfe der containsKeyKartenmethode testen, ob sich Ihr Schlüssel bereits in der Karte befindet.

Ted Hopp
quelle
3

HashSet<String>(oder) jede SetImplementierung kann die Arbeit für Sie erledigen. SetDuplikate nicht zulassen.

Hier ist Javadoc für HashSet.

kosa
quelle
2

Ich weiß nicht, wie effizient dies ist, aber für mich in einem einfachen Kontext gearbeitet.

List<int> uniqueNumbers = new ArrayList<>();

   public void AddNumberToList(int num)
    {
        if(!uniqueNumbers .contains(num)) {
            uniqueNumbers .add(num);
        }
    }
Zapnologica
quelle
1

Möglicherweise möchten Sie eine der implementierenden java.util.Set<E>Schnittstellenklassen verwenden, z java.util.HashSet<String> . B. die Auflistungsklasse.

Eine Sammlung, die keine doppelten Elemente enthält. Formal enthalten Mengen kein Elementpaar e1 und e2, so dass e1.equals (e2) und höchstens ein Nullelement. Wie der Name andeutet, modelliert diese Schnittstelle die Abstraktion mathematischer Mengen.

Yogendra Singh
quelle