Stufe 5Collections · Lektion 26 von 34

Set: Mengen ohne Duplikate

Aktualisiert am 24. September 20263 Min. LesezeitSchritt 2/4 dieser Stufe

Ein Set enthält jedes Element höchstens einmal und beantwortet die Frage „ist x enthalten?“ blitzschnell. Dazu kommen die Mengenoperationen aus der Mathematik: Vereinigung, Schnittmenge und Differenz.

Sets erzeugen

val farben = Set("rot", "grün", "blau", "rot")
// Set(rot, grün, blau) – das doppelte "rot" fällt weg

val leer = Set.empty[Int]
val ausListe = List(3, 1, 3, 2, 1).toSet   // Set(3, 1, 2)

Ob ein Element doppelt ist, entscheidet ==. Bei case classes vergleicht das den Inhalt, bei gewöhnlichen Klassen die Identität – eigene Klassen, die in Sets landen sollen, sind deshalb meist case classes.

Enthalten oder nicht

farben.contains("grün")   // true
farben("gelb")            // false – Set ist zugleich eine Funktion A => Boolean
farben.size               // 3

Weil ein Set eine Funktion String => Boolean ist, können Sie es direkt als Filter verwenden:

val erlaubt = Set("de", "at", "ch")
List("de", "fr", "ch", "it").filter(erlaubt)   // List(de, ch)

Die Abfrage contains ist bei einem Hash-basierten Set nahezu unabhängig von der Größe schnell. Bei einer List müsste jedes Element einzeln verglichen werden. Wer häufig prüft, ob ein Wert „dabei“ ist, sollte deshalb ein Set verwenden.

Hinzufügen und entfernen

Sets sind standardmäßig unveränderlich. Operationen liefern ein neues Set:

val mehr = farben + "gelb"          // Set(rot, grün, blau, gelb)
val weniger = farben - "rot"        // Set(grün, blau)
val viele = farben ++ Set("lila", "weiß")

Mengenoperationen

val a = Set(1, 2, 3, 4)
val b = Set(3, 4, 5)

a union b        // Set(1, 2, 3, 4, 5)   auch: a | b
a intersect b    // Set(3, 4)            auch: a & b
a diff b         // Set(1, 2)            auch: a &~ b
a.subsetOf(Set(1, 2, 3, 4, 5, 6))   // true

Ein praktisches Beispiel: Welche Kunden haben in beiden Monaten bestellt, welche nur im ersten?

val august    = Set("Ada", "Alan", "Grace", "Edsger")
val september = Set("Grace", "Barbara", "Ada")

val treu     = august & september      // Set(Ada, Grace)
val verloren = august &~ september     // Set(Alan, Edsger)
val neu      = september &~ august     // Set(Barbara)

Reihenfolge: HashSet und TreeSet

Das Standard-Set ist ein HashSet: Die Reihenfolge der Elemente ist nicht festgelegt und kann sich beim Hinzufügen ändern. (Bis vier Elemente verwendet Scala intern spezielle kleine Klassen, die die Einfügereihenfolge zufällig beibehalten – darauf sollten Sie sich nicht verlassen.)

Brauchen Sie eine sortierte Menge, nehmen Sie TreeSet bzw. SortedSet:

import scala.collection.immutable.SortedSet

val sortiert = SortedSet(42, 7, 19, 3)   // TreeSet(3, 7, 19, 42)
sortiert.head                            // 3
sortiert.range(5, 20)                    // TreeSet(7, 19)

Die Sortierung stammt aus einer Ordering-Instanz. Für eigene Typen liefern Sie eine mit given (siehe given und using).

Veränderliche Sets

Für Algorithmen, die eine Menge Schritt für Schritt aufbauen, gibt es scala.collection.mutable.Set:

import scala.collection.mutable

val besucht = mutable.Set.empty[String]
besucht += "Start"
besucht.add("A")        // true: war neu
besucht.add("A")        // false: war schon da

Ein typischer Einsatz ist die Suche in einem Graphen, bei der man sich merkt, welche Knoten bereits besucht wurden. Nach außen gibt man das Ergebnis mit toSet unveränderlich zurück.

Set oder List?

Eine Liste lässt sich jederzeit mit toSet in ein Set umwandeln – zum Beispiel, um Duplikate zu entfernen. Soll die ursprüngliche Reihenfolge erhalten bleiben, ist list.distinct die bessere Wahl.