menge-datenstruktur

Set (Menge)

Kurz: Eine Datenstruktur, die jedes Element höchstens einmal enthält — ein zweiter Einfügeversuch desselben Werts wird einfach ignoriert, anders als bei einer Liste, die Duplikate zulässt.

Genauer: Sets eignen sich, um Eindeutigkeit zu garantieren (z. B. eine Liste bereits vergebener Benutzernamen) oder um schnell zu prüfen, ob ein Wert bereits vorkommt. Je nach Implementierung ist die Reihenfolge der Elemente nicht garantiert (HashSet), sortiert (TreeSet) oder entspricht der Einfügereihenfolge.

Im Detail

Der wichtigste praktische Vorteil eines Sets gegenüber einer Liste zeigt sich bei der Frage “ist Element X schon vorhanden?”: Bei einer Liste muss man im schlimmsten Fall JEDES Element einzeln durchgehen und vergleichen, um das festzustellen. Ein hash-basiertes Set kann diese Frage dagegen fast augenblicklich beantworten, unabhängig davon, wie viele Elemente bereits enthalten sind — das macht Sets zur natürlichen Wahl, wenn man Duplikate ausschließen oder schnell auf Vorhandensein prüfen will:

gesehene_ids = neues Set()
 
fuer id in eingehende_anfragen:
    wenn gesehene_ids.enthaelt(id):
        ueberspringe(id)   // Duplikat, schon bearbeitet
    sonst:
        gesehene_ids.hinzufuegen(id)
        bearbeite(id)

Ein Set unterstützt außerdem die klassischen mathematischen Mengenoperationen, die man aus der Schule kennt:

• Vereinigung: alle Elemente aus beiden Mengen zusammen (jedes nur einmal)
• Schnittmenge: nur die Elemente, die in BEIDEN Mengen vorkommen
• Differenz: Elemente der einen Menge, die NICHT in der anderen vorkommen

Diese Operationen sind über eingebaute Methoden meist direkt verfügbar, statt sie selbst mit Schleifen nachzubauen — z. B. um herauszufinden, welche Berechtigungen zwei Nutzergruppen gemeinsam haben (Schnittmenge) oder welche eine Gruppe exklusiv besitzt (Differenz).

Wichtig zu beachten: Damit ein selbstdefinierter Objekttyp (z. B. eine eigene Person-Klasse) korrekt in einem hash-basierten Set funktioniert, muss die Sprache wissen, wann zwei Objekte als “gleich” gelten — in vielen Sprachen muss man dafür selbst eine Gleichheits- und Hash-Methode für den eigenen Typ definieren, sonst gelten zwei inhaltlich identische, aber unterschiedliche Objektinstanzen fälschlich als verschieden.

Siehe auch: HashSet, TreeSet, Collections