Ausführbare Go-Docs: Sets

Q: Sollte ich für ein Set in Go map[T]bool oder map[T]struct{} nehmen?

map[T]struct{} macht die Absicht explizit, und seine Werte belegen null Bytes. map[T]bool liest sich natürlicher (if seen[x]), weil ein fehlender Schlüssel false liefert. Beides ist korrekt; der Speicherunterschied zählt nur bei sehr großen Sets. Entscheide dich für eins und bleib dabei.

Das Idiom: eine Map mit leeren Werten

Go hat kein set-Schlüsselwort und kein Set in der Standardbibliothek. Eine Map, deren Schlüssel die Elemente sind und deren Werte nichts tragen, erledigt die Aufgabe.

package main

import "fmt"

func main() {
	tags := map[string]struct{}{}

	// add
	tags["go"] = struct{}{}
	tags["backend"] = struct{}{}
	tags["go"] = struct{}{} // adding again changes nothing

	// has
	_, ok := tags["go"]
	fmt.Println("has go:", ok)

	// remove
	delete(tags, "backend")

	// size
	fmt.Println("size:", len(tags))

	for t := range tags {
		fmt.Println("member:", t)
	}
}

struct{} ist der leere Struct-Typ und struct{}{} sein einziger Wert. Er belegt null Bytes, also speichert die Map nur die Schlüssel.

Alle Map-Regeln gelten: Schlüssel müssen vergleichbar sein, die Iterationsreihenfolge ist zufällig, eine nil-Map löst beim Schreiben eine Panic aus, und nebenläufige Schreibzugriffe brauchen ein Lock. Die Seite zu Maps behandelt jeden Punkt.

map[T]struct{} oder map[T]bool

Die andere verbreitete Schreibweise ist map[T]bool. Sie liest sich besser, weil ein fehlender Schlüssel false liefert:

seen := map[string]bool{}
seen["a"] = true
if seen["a"] { ... }

Die Abwägungen:

	`map[T]struct{}`	`map[T]bool`
Größe des Werts	0 Bytes	1 Byte (plus Alignment)
Mitgliedschaftstest	`_, ok := s[k]`	`s[k]`
Mehrdeutigkeit	keine	`s[k] = false` ist ein dritter Zustand

Die dritte Zeile ist der eigentliche Grund, warum viele Codebasen den leeren Struct bevorzugen: Mit bool schreibt irgendwann jemand s[k] = false, und len(s) ist nicht mehr die Anzahl der Elemente. Bei kleinen Sets spielt der Speicherunterschied keine Rolle.

Duplikate aus einem Slice entfernen

Der häufigste Einsatz eines Sets ist Deduplizierung. Das hier behält das erste Vorkommen jedes Werts und erhält die Reihenfolge:

package main

import (
	"fmt"
	"slices"
)

func unique[T comparable](in []T) []T {
	seen := make(map[T]struct{}, len(in))
	out := make([]T, 0, len(in))
	for _, v := range in {
		if _, ok := seen[v]; ok {
			continue
		}
		seen[v] = struct{}{}
		out = append(out, v)
	}
	return out
}

func main() {
	fmt.Println(unique([]string{"b", "a", "b", "c", "a"}))
	fmt.Println(unique([]int{3, 1, 3, 3, 2}))

	// If order does not matter: sort, then drop adjacent duplicates.
	s := []int{3, 1, 3, 3, 2}
	slices.Sort(s)
	fmt.Println(slices.Compact(s))
}

Ausgabe:

[b a c]
[3 1 2]
[1 2 3]

Vereinigung, Schnittmenge, Differenz

Mengenalgebra sind ein paar Schleifen. Durchlaufe beim Mitgliedschaftstest die kleinere Menge, da jeder Lookup im Mittel konstante Zeit braucht.

package main

import (
	"fmt"
	"maps"
	"slices"
)

type set map[string]struct{}

func of(items ...string) set {
	s := make(set, len(items))
	for _, it := range items {
		s[it] = struct{}{}
	}
	return s
}

func union(a, b set) set {
	out := maps.Clone(a)
	for k := range b {
		out[k] = struct{}{}
	}
	return out
}

func intersect(a, b set) set {
	if len(a) > len(b) {
		a, b = b, a
	}
	out := set{}
	for k := range a {
		if _, ok := b[k]; ok {
			out[k] = struct{}{}
		}
	}
	return out
}

func difference(a, b set) set {
	out := set{}
	for k := range a {
		if _, ok := b[k]; !ok {
			out[k] = struct{}{}
		}
	}
	return out
}

func sorted(s set) []string {
	return slices.Sorted(maps.Keys(s))
}

func main() {
	backend := of("go", "sql", "docker", "linux")
	devops := of("docker", "linux", "terraform")

	fmt.Println("union:     ", sorted(union(backend, devops)))
	fmt.Println("intersect: ", sorted(intersect(backend, devops)))
	fmt.Println("backend-only:", sorted(difference(backend, devops)))
}

sorted gibt es nur, damit die Ausgabe stabil ist. Gibst du ein Set per range aus, kommt bei jedem Lauf eine andere Reihenfolge heraus. maps.Keys und slices.Sorted brauchen Go 1.23.

Ein benannter Typ wie type set map[string]struct{} bleibt eine Map: Du indizierst ihn, durchläufst ihn mit range und löschst mit delete genauso, und du kannst Methoden daran hängen.

Ein kleines generisches Set

Mit Generics (Go 1.18) deckt ein Typ jeden vergleichbaren Elementtyp ab. Für die meisten Programme reicht das:

package main

import (
	"cmp"
	"fmt"
	"maps"
	"slices"
)

type Set[T comparable] struct {
	m map[T]struct{}
}

func NewSet[T comparable](items ...T) *Set[T] {
	s := &Set[T]{m: make(map[T]struct{}, len(items))}
	for _, it := range items {
		s.Add(it)
	}
	return s
}

func (s *Set[T]) Add(v T)    { s.m[v] = struct{}{} }
func (s *Set[T]) Remove(v T) { delete(s.m, v) }
func (s *Set[T]) Len() int   { return len(s.m) }
func (s *Set[T]) Has(v T) bool {
	_, ok := s.m[v]
	return ok
}

func (s *Set[T]) Union(o *Set[T]) *Set[T] {
	out := &Set[T]{m: maps.Clone(s.m)}
	for v := range o.m {
		out.Add(v)
	}
	return out
}

// Sorted is a free function because it needs a stricter constraint than the type.
func Sorted[T cmp.Ordered](s *Set[T]) []T {
	return slices.Sorted(maps.Keys(s.m))
}

func main() {
	a := NewSet(1, 2, 3)
	b := NewSet(3, 4)
	a.Add(2)
	fmt.Println(a.Len(), a.Has(2), a.Has(9))

	u := a.Union(b)
	fmt.Println(Sorted(u))

	words := NewSet("go", "rust")
	words.Remove("rust")
	fmt.Println(Sorted(words))
}

Die Map in einem Struct zu verpacken versteckt das Rauschen von struct{}{} und garantiert, dass die Map vom Konstruktor erzeugt wird. Damit fällt die Panic bei einer nil-Map weg. Sorted kann keine Methode sein: Eine Methode kann keine eigenen Typparameter deklarieren und die comparable-Constraint des Typs nicht verschärfen, und Sortieren braucht cmp.Ordered. Constraints erklärt die Seite zu Generics.

Brauchst du ein Set mit vollem Funktionsumfang (threadsichere Varianten, viele Operationen), gibt es Pakete von Drittanbietern wie github.com/deckarep/golang-set. In den meisten Fällen nutzen Go-Programmierer das Map-Idiom oder einen Typ mit 30 Zeilen wie diesen.

Sets aus Structs

Jeder vergleichbare Typ kann ein Element sein, auch Structs mit vergleichbaren Feldern. Damit werden Prüfungen wie „habe ich dieses Paar schon gesehen“ direkt:

type edge struct{ from, to string }
visited := map[edge]struct{}{}
visited[edge{"a", "b"}] = struct{}{}

Slices und Maps können keine Set-Elemente sein. Um eindeutige Slices zu verfolgen, wandle jeden vorher in einen vergleichbaren Schlüssel um, zum Beispiel ein Array fester Größe oder einen mit fmt.Sprint gebauten String.

Häufige Fehler

Das Initialisieren vergessen. var s map[string]struct{} ist nil; das erste Hinzufügen löst eine Panic aus.
Ein Set ausgeben und eine stabile Ausgabe erwarten. Sortier die Elemente vorher.
map[T]bool verwenden und false speichern. Dann zählt len nicht mehr die Elemente. Entferne mit delete.

Häufig gestellte Fragen

Hat Go einen Set-Typ?

Nein. Die Standardbibliothek hat kein Set. Das Idiom ist eine Map, deren Werte keine Information tragen: map[string]struct{}. Hinzufügen ist s[k] = struct{}{}, die Mitgliedschaft prüfst du mit _, ok := s[k], Entfernen ist delete(s, k), und die Größe ist len(s).

Sollte ich für ein Set in Go map[T]bool oder map[T]struct{} nehmen?

map[T]struct{} macht die Absicht explizit, und seine Werte belegen null Bytes. map[T]bool liest sich natürlicher (if seen[x]), weil ein fehlender Schlüssel false liefert. Beides ist korrekt; der Speicherunterschied zählt nur bei sehr großen Sets. Entscheide dich für eins und bleib dabei.

Wie entferne ich Duplikate aus einem Slice in Go?

Um jeweils das erste Vorkommen in der Reihenfolge zu behalten, durchläufst du den Slice, merkst dir gesehene Werte in einer map[T]struct{} und hängst nur ungesehene an. Ist die Reihenfolge egal, sortier und entferne benachbarte Duplikate: slices.Sort(s); s = slices.Compact(s).

Verwandte Konzepte