HashSet

Konstruktion

HashSet konstruierst du in der Praxis fast immer entweder leer (für Sammlungs-Zwecke im Loop) oder direkt aus einer existierenden Sequenz. Die Konstruktor-Familie spiegelt die von HashMap eins-zu-eins, weil HashSet intern als HashMap mit Unit-Value (()) implementiert ist — alle Mechanik kommt von der HashMap.

use std::collections::HashSet;

fn main() {
    let mut s1: HashSet<i32> = HashSet::new();
    let mut s2: HashSet<i32> = HashSet::with_capacity(100);

    // Aus Iterator
    let s3: HashSet<i32> = [1, 2, 3, 4, 5].into_iter().collect();

    // Aus Array
    let s4 = HashSet::from([1, 2, 3]);
}

Besonders der collect()-Weg ist die idiomatische Form, um ein HashSet aus einer Iterator-Quelle zu bauen — etwa um die eindeutigen Werte einer Liste zu ermitteln. Duplikate werden dabei stillschweigend verworfen; eine Liste [1, 2, 1, 3, 2] ergibt ein Set mit genau drei Einträgen. Das ist eine der häufigsten Anwendungen überhaupt.

with_capacity(n) ist genau dann interessant, wenn du in einem Loop viele insert-Aufrufe machst und die ungefähre Endgröße kennst — die Reallocations beim Wachsen einer HashSet sind genauso teuer wie bei einer HashMap, weil alle bestehenden Elemente neu gehasht werden müssen.

Grundlegende Operations

Die Basis-API von HashSet ist auffällig schmal — es gibt nur eine Handvoll Operationen, weil ein Set semantisch sehr einfach ist: ein Wert ist drin oder draußen. Drei Operationen reichen für 90 % der Anwendungen: hinzufügen, prüfen, entfernen. Bemerkenswert ist, dass alle drei bool als Rückgabewert nutzen, statt eine Option mit dem alten Wert — denn anders als bei HashMap gibt es bei einem Set keinen „alten Wert" außer dem Wert selbst, den du ja schon hattest.

use std::collections::HashSet;

fn main() {
    let mut s: HashSet<&str> = HashSet::new();

    let neu = s.insert("a");      // true — war nicht da
    let nicht_neu = s.insert("a"); // false — schon da
    assert!(neu);
    assert!(!nicht_neu);

    let drin = s.contains("a");     // true
    let nicht = s.contains("z");    // false

    let entfernt = s.remove("a");   // true — war da
    let nochmal = s.remove("a");    // false — jetzt nicht mehr da

    assert_eq!(s.len(), 0);
}

insert(item) ist die zentrale Schreib-Operation und hat ein nützliches Verhalten: sie liefert true, wenn der Wert tatsächlich neu hinzugefügt wurde, und false, wenn der Wert schon im Set war (in diesem Fall passiert nichts — die alte Kopie bleibt). Dieses bool-Ergebnis ist die elegante Grundlage für eine ganze Reihe von Algorithmen wie Deduplizierung („wenn neu, dann auch in die Output-Liste") oder Visited-Tracking in Graph-Traversierung („wenn neu, dann besuchen wir den Knoten zum ersten Mal").

contains(&item) ist der reine Lookup, der nur die Existenz prüft, ohne etwas zu verändern. Er nimmt einen Borrow auf den gesuchten Wert; bei einem HashSet<String> kannst du contains mit einem &str aufrufen, dank der gleichen Borrow-Magie wie bei HashMap. Die Operation ist O(1) im Schnitt.

remove(&item) entfernt den Wert und gibt true zurück, wenn der Wert vorher da war, false sonst. Der Wert selbst wird nicht zurückgegeben — wenn du ihn nach dem Entfernen noch brauchst, musst du ihn vorher selbst behalten haben.

len() und is_empty() sind die üblichen Größen-Abfragen. len ist O(1), weil HashSet die Anzahl als separates Feld speichert und bei jedem insert/remove aktualisiert.

Set-Operationen

Hier liegt der eigentliche Mehrwert von HashSet gegenüber HashMap mit Dummy-Values: die vier klassischen Mengen-Operationen der Mathematik sind direkt als Methoden verfügbar. Sie sind nicht nur ergonomische Helfer, sondern auch performant implementiert — sie laufen einmal über das kleinere der beiden Sets und nutzen die Hash-Lookup-Eigenschaft des anderen, sodass die Gesamtkomplexität O(n + m) wird, wobei n und m die Set-Größen sind.

use std::collections::HashSet;

fn main() {
    let a: HashSet<i32> = [1, 2, 3, 4].into_iter().collect();
    let b: HashSet<i32> = [3, 4, 5, 6].into_iter().collect();

    // Union — alle aus a UND b
    let union: HashSet<i32> = a.union(&b).copied().collect();
    // {1, 2, 3, 4, 5, 6}

    // Intersection — nur in BEIDEN
    let inter: HashSet<i32> = a.intersection(&b).copied().collect();
    // {3, 4}

    // Difference — in a, nicht in b
    let diff: HashSet<i32> = a.difference(&b).copied().collect();
    // {1, 2}

    // Symmetric Difference — in einem, aber nicht beiden
    let sym: HashSet<i32> = a.symmetric_difference(&b).copied().collect();
    // {1, 2, 5, 6}

    assert_eq!(union.len(), 6);
    assert_eq!(inter.len(), 2);
    assert_eq!(diff.len(), 2);
    assert_eq!(sym.len(), 4);
}

Die vier Operationen entsprechen direkt der mathematischen Definition. union liefert alle Werte, die in mindestens einem der beiden Sets sind. intersection nur die, die in beiden vorkommen. difference die, die im ersten Set sind, aber nicht im zweiten — das ist asymmetrisch, a.difference(&b) und b.difference(&a) sind unterschiedlich. symmetric_difference schließlich liefert die Werte, die in genau einem der Sets sind, also weder das gemeinsame Material noch der Schnitt.

Wichtig ist, dass die Methoden Iteratoren zurückgeben, keine neuen Sets. Das ist eine bewusste Designentscheidung: oft willst du das Ergebnis gar nicht als Set sammeln, sondern direkt durchlaufen (for x in a.intersection(&b)). Wenn du doch ein neues Set brauchst, kommt das .copied().collect() ans Ende. copied() ist hier notwendig, weil der Iterator &T liefert, das Ziel-Set aber T braucht — bei Copy-Typen ist copied die billigere Variante zu cloned.

Eine subtile Eigenheit: bei union ist die Reihenfolge der Argumente egal — das Set ist symmetrisch. Bei intersection ebenfalls. Bei difference und symmetric_difference macht die Reihenfolge dagegen einen großen Unterschied — beachte das beim Aufruf.

Subset-Relation

Neben den vier Set-Operationen gibt es drei boolesche Prüfungen, mit denen du die Beziehung zwischen zwei Sets ohne Materialisierung des Ergebnisses abfragen kannst. Sie sind alle in O(n) und arbeiten so lazy wie möglich — is_disjoint etwa bricht schon nach dem ersten gemeinsamen Element ab.

use std::collections::HashSet;

fn main() {
    let a: HashSet<i32> = [1, 2, 3].into_iter().collect();
    let b: HashSet<i32> = [1, 2, 3, 4, 5].into_iter().collect();
    let c: HashSet<i32> = [10, 20].into_iter().collect();

    assert!(a.is_subset(&b));         // a ⊆ b
    assert!(b.is_superset(&a));        // b ⊇ a
    assert!(a.is_disjoint(&c));        // a ∩ c = ∅
}

Iteration

use std::collections::HashSet;

fn main() {
    let s: HashSet<i32> = [1, 2, 3, 4].into_iter().collect();

    for x in &s {
        print!("{x} ");
    }
    // Reihenfolge ist nicht definiert!
}

Die Iteration über HashSet folgt denselben Regeln wie bei HashMap — gleiche Borrow-Modi, gleiche Unbestimmtheit der Reihenfolge. Letzteres ist hier besonders wichtig: anders als bei HashMap, wo du oft einen Lookup nach Key machst und die Iter-Reihenfolge dir gleichgültig ist, kommt bei HashSet die Iteration sehr häufig vor (z. B. „gib mir alle eindeutigen Tags"). Wer auf eine bestimmte Reihenfolge angewiesen ist — alphabetisch sortiert, numerisch aufsteigend —, muss entweder BTreeSet benutzen oder die Werte über into_iter().collect::<Vec<_>>() materialisieren und manuell sortieren.

Praxis: HashSet im echten Code

Die Anwendungsfälle von HashSet teilen sich grob in zwei Kategorien. Erstens Eindeutigkeits-Operationen: Duplikate entfernen, Membership-Tests, Visited-Tracking. Zweitens Mengen-Logik: Diff zwischen Listen, Schnittmengen, Permission-Sets. Die Beispiele unten decken beide Bereiche ab.

Deduplizierung

use std::collections::HashSet;

pub fn entferne_duplikate<T: Eq + std::hash::Hash + Clone>(items: &[T]) -> Vec<T> {
    let mut gesehen: HashSet<T> = HashSet::new();
    let mut result = Vec::new();
    for item in items {
        if gesehen.insert(item.clone()) {
            result.push(item.clone());
        }
    }
    result
}

Eines der häufigsten Anwendungsmuster überhaupt: aus einer Liste die eindeutigen Werte herausziehen und die Reihenfolge des ersten Vorkommens behalten. Eine pure into_iter().collect::<HashSet<_>>() würde dedupezieren, aber die Reihenfolge wäre verloren. Das gezeigte Pattern löst beides: gesehen.insert(item.clone()) liefert true, wenn das Item neu war — genau dann wird es ans Ergebnis angehängt. Bei Duplikaten ist insert false, und das Item wird übersprungen.

Das doppelte clone ist ein Kompromiss: einmal für das Set, einmal für den Result-Vec. Bei Copy-Typen wie i32 ist das kostenlos; bei großen Typen wie String lohnt es sich, mit &T-Borrows zu arbeiten, sofern die Lifetimes passen. Für eine besonders schlanke Implementation könnte man auch .windows(2) oder die itertools::unique-Methode aus dem Crate nutzen — aber für eine eigene Stdlib-Lösung ist der gezeigte Code völlig idiomatisch.

Verfügbare Tags ermitteln

use std::collections::HashSet;

pub fn alle_tags(eintraege: &[Vec<String>]) -> HashSet<String> {
    eintraege.iter()
        .flat_map(|tags| tags.iter().cloned())
        .collect()
}

fn main() {
    let posts = vec![
        vec!["rust".to_string(), "tutorial".into()],
        vec!["rust".into(), "ownership".into()],
        vec!["go".into()],
    ];
    let tags = alle_tags(&posts);
    assert_eq!(tags.len(), 4);
}

Die Kombination flat_map plus collect::<HashSet<_>> ist die schönste Form, eindeutige Werte aus einer Liste-von-Listen zu sammeln. flat_map faltet die innere Struktur auseinander — aus einer Vec<Vec<String>> wird ein flacher Iterator über alle Tags. Das collect::<HashSet<_>> am Ende fasst sie zur eindeutigen Menge zusammen; Duplikate (wie das doppelt auftretende "rust") verschwinden stillschweigend.

Das cloned() zwischen flat_map und collect ist nötig, weil tags.iter() Referenzen liefert (&String), das Ziel-HashSet aber besitzte Werte braucht. Bei einer großen Eingabe sind das viele Allocations — wenn Performance wichtig ist und die Eingabe lange lebt, würde man HashSet<&String> zurückgeben und das Cloning sparen.

Permission-Check

use std::collections::HashSet;

pub struct User { permissions: HashSet<String> }

impl User {
    pub fn hat(&self, perm: &str) -> bool {
        self.permissions.contains(perm)
    }

    pub fn hat_alle(&self, perms: &[&str]) -> bool {
        perms.iter().all(|p| self.permissions.contains(*p))
    }

    pub fn hat_eines(&self, perms: &[&str]) -> bool {
        perms.iter().any(|p| self.permissions.contains(*p))
    }
}

Permission-Modelle sind ein Lehrbuch-Anwendungsfall für HashSet. Jeder User hat eine Menge von Berechtigungen, und die Frage „darf der User X tun?" reduziert sich auf einen Membership-Test. Bei kleinen Permission-Sets (ein paar Dutzend) wäre auch ein Vec mit linearer Suche schnell genug, aber HashSet skaliert ohne Sorgen auf Hunderte oder Tausende von Permissions.

Die hat_alle- und hat_eines-Methoden zeigen die typische Iterator-Logik für Mehrfach-Checks: all läuft, bis das erste fehlende Permission gefunden ist (Short-Circuit auf false); any läuft, bis das erste vorhandene gefunden ist (Short-Circuit auf true). Beide sind so effizient wie es sein kann — sie scannen nur so viele Permissions wie nötig.

Diff zwischen zwei Listen

use std::collections::HashSet;

pub fn neu_hinzugekommen<T: Eq + std::hash::Hash + Clone>(
    alt: &[T],
    neu: &[T],
) -> Vec<T> {
    let alt_set: HashSet<&T> = alt.iter().collect();
    neu.iter()
        .filter(|x| !alt_set.contains(x))
        .cloned()
        .collect()
}

fn main() {
    let alt = vec!["a", "b", "c"];
    let neu = vec!["b", "c", "d", "e"];
    let added = neu_hinzugekommen(&alt, &neu);
    assert_eq!(added, vec!["d", "e"]);
}

Inkrementelle Updates sind ein typischer Fall: vergleiche eine alte und eine neue Liste und finde heraus, was neu dazugekommen ist. Statt das alte Set als Vec mit O(n²)-Suche zu durchsuchen, wird es einmalig in ein HashSet umgewandelt — die anschließende contains-Prüfung ist O(1) pro Element. Über n neue Items kostet das O(n + m), wobei m die Größe der alten Liste ist.

Beachte die saubere Trennung: alt_set wird mit &T-Referenzen gefüllt (kein Cloning), weil das Set nur während der Funktion lebt. Erst beim .cloned() vor dem finalen collect werden die übrigen Werte tatsächlich geklont, damit sie als besitzte Werte im Result-Vec landen können.

Graph: Visited-Tracking

use std::collections::HashSet;

pub fn dfs_pfad_existiert(
    graph: &[(u32, u32)],
    start: u32,
    ziel: u32,
) -> bool {
    let mut visited: HashSet<u32> = HashSet::new();
    let mut stack = vec![start];

    while let Some(node) = stack.pop() {
        if node == ziel { return true; }
        if !visited.insert(node) { continue; }      // schon besucht
        for (a, b) in graph {
            if *a == node { stack.push(*b); }
        }
    }
    false
}

Tiefensuche mit Visited-Tracking ist der Standard-Algorithmus für „gibt es einen Pfad von A nach B?". Der HashSet<u32> hält alle Knoten, die schon mal auf dem Stack waren — ohne diese Markierung würde der Algorithmus in Zyklen feststecken. Der elegante Trick ist die if !visited.insert(node) { continue; }-Zeile: sie fügt den Knoten ins Visited-Set ein und liefert dabei direkt das bool, ob er neu war. Wenn nicht neu, überspringen wir die Verarbeitung. Eine einzige Operation für Insertion und Existenz-Check.

Der Algorithmus arbeitet mit einem Vec als Stack (pop und push am Ende, O(1)) und einem HashSet als Visited-Marker. Beides hat O(1) für die typischen Operationen, also bleibt die Gesamtkomplexität O(V + E) — V Knoten, E Kanten.

Set-Operationen für User-Gruppen

use std::collections::HashSet;

pub fn doppel_mitglieder(
    gruppe_a: &HashSet<u64>,
    gruppe_b: &HashSet<u64>,
) -> Vec<u64> {
    gruppe_a.intersection(gruppe_b).copied().collect()
}

pub fn nur_in_a(
    gruppe_a: &HashSet<u64>,
    gruppe_b: &HashSet<u64>,
) -> Vec<u64> {
    gruppe_a.difference(gruppe_b).copied().collect()
}

Hier siehst du, wie Set-Operationen direkt der Domain-Sprache entsprechen. „Wer ist in beiden Gruppen?" ist exakt intersection. „Wer ist nur in Gruppe A?" ist exakt difference(A, B). Diese Eins-zu-eins-Übersetzung von Geschäftslogik in Code macht solche Funktionen kurz, lesbar und schwer falsch zu schreiben.

Die Funktionen geben Vec<u64> zurück, nicht HashSet<u64> — typische Wahl, wenn das Ergebnis vom Caller wahrscheinlich sequenziell verarbeitet wird. Für ein wiederverwendbares Set, das selbst weitere Set-Operationen erfahren soll, wäre die HashSet-Rückgabe besser. Die Wahl hängt von der weiteren Verwendung ab.

Whitelist-Check

use std::collections::HashSet;
use std::sync::OnceLock;

pub fn ist_erlaubt(host: &str) -> bool {
    static WHITELIST: OnceLock<HashSet<&str>> = OnceLock::new();
    let liste = WHITELIST.get_or_init(|| {
        HashSet::from([
            "example.com",
            "trusted.org",
            "internal.local",
        ])
    });
    liste.contains(host)
}

Whitelists, Allow-Listen und ähnliche statische Mengen sind ein typischer Anwendungsfall, bei dem ein einmal initialisiertes HashSet die richtige Wahl ist. OnceLock<T> ist die thread-sichere Version eines lazy_static! aus den älteren Crate-Tagen — der innere Wert wird genau einmal initialisiert, beim ersten Aufruf von get_or_init. Alle folgenden Aufrufe geben den fertigen Wert zurück, ohne erneute Initialisierung. Damit zahlt der erste Aufrufer den Initialisierungs-Aufwand, alle anderen profitieren von einem reinen Lookup.

Das static macht die Whitelist global — sie lebt für die gesamte Programmlaufzeit. Für eine Dynamik-Whitelist (zur Laufzeit aktualisierbar) wäre statt OnceLock ein RwLock<HashSet<&str>> die richtige Wahl, aber das ist eine andere Diskussion.

Eindeutige Counts pro Day

use std::collections::{HashMap, HashSet};

pub fn dau(events: &[(String, u64)]) -> HashMap<String, usize> {
    let mut tage: HashMap<String, HashSet<u64>> = HashMap::new();
    for (tag, user_id) in events {
        tage.entry(tag.clone()).or_default().insert(*user_id);
    }
    tage.into_iter()
        .map(|(t, set)| (t, set.len()))
        .collect()
}

Das Daily-Active-Users-Pattern ist ein klassisches Analytics-Beispiel und zeigt, wie HashMap und HashSet zusammen eine schöne Datenstruktur ergeben. Pro Tag wird ein HashSet aller User-IDs gesammelt, die an diesem Tag aktiv waren — Duplikate (mehrere Events vom selben User am gleichen Tag) verschwinden automatisch. Am Ende wird pro Tag die Größe des Sets ausgelesen — das ist die DAU-Zahl.

Das or_default() ist eine besonders elegante Variante von or_insert_with: es ruft den Default-Konstruktor des Wert-Typs auf, also HashSet::default() für ein leeres Set. So bleibt der Code knapp und symmetrisch.

Bei großen Datenmengen ist diese Struktur speichersparend: anstatt eine Liste mit Millionen User-Events zu speichern (die meisten redundant pro Tag), behältst du pro Tag nur die eindeutigen User. Im finalen map wird das Set durch seine Größe ersetzt — die User-IDs selbst werden weggeworfen, weil nur der Zähler relevant ist.

Set-Differenz für Garbage-Collection

use std::collections::HashSet;

pub fn finde_verwaiste(
    referenziert: &HashSet<u64>,
    alle: &HashSet<u64>,
) -> Vec<u64> {
    alle.difference(referenziert).copied().collect()
}

Garbage Collection im weitesten Sinn: du hast eine Sammlung „aller IDs", die irgendwo existieren (etwa alle Dateien in einem Storage), und eine Sammlung „referenzierter IDs" (alle, die noch von einem aktiven Objekt zitiert werden). Die Differenz ist genau das, was du löschen kannst — die Waisen, die keinen Owner mehr haben.

Diese eine Zeile löst ein Problem, das ohne Set-Operationen einen Loop mit Membership-Tests brauchen würde. Auf großen Datenmengen (Millionen IDs) ist die Set-Operation auch deutlich schneller, weil sie intern optimiert ist.

Weiterführende Ressourcen

Externe Quellen

• std::collections::HashSet
• The Rust Book – Hash Maps

Verwandte Artikel

• HashMap
• BTreeMap und BTreeSet
• Collections – Übersicht