HashSet und BTreeMap in Rust

Ein HashSet ist eine Sammlung eindeutiger Werte. Fügst du denselben Wert zweimal ein, wird er trotzdem nur einmal gespeichert. Stell dir eine Gästeliste am Eingang vor: Den Türsteher interessiert nur, ob dein Name draufsteht – nicht, wie oft er aufgeschrieben wurde.

Vec und HashMap kennst du schon. Auf dieser Seite kommen die anderen Collections dazu, die du am häufigsten brauchst: HashSet, die sortierten BTreeMap und BTreeSet und VecDeque für Warteschlangen. Am Ende hilft dir eine Tabelle, die richtige auszuwählen.

Ein HashSet erstellen

HashSet liegt in std::collections, du brauchst also eine use-Zeile. Die Methode insert gibt einen bool zurück: true, wenn der Wert neu war, und false, wenn er schon drin war.

use std::collections::HashSet;

fn main() {
    let mut tags = HashSet::new();

    println!("{}", tags.insert("rust"));
    println!("{}", tags.insert("web"));
    println!("{}", tags.insert("rust")); // schon vorhanden

    println!("{} verschiedene Tags", tags.len());
}

Ausgabe:

true
true
false
2 verschiedene Tags

▶ Selbst ausprobieren

Dieser bool ist nützlicher, als er aussieht. Er beantwortet die Frage „Hatte ich das schon?“ im selben Schritt, in dem du den Wert hinzufügst. Eine separate Prüfung brauchst du also nicht.

Werte prüfen und entfernen

contains sagt dir, ob ein Wert im Set ist. remove nimmt ihn heraus und gibt – genau wie insert – einen bool zurück, der dir sagt, ob tatsächlich etwas entfernt wurde.

use std::collections::HashSet;

fn main() {
    let mut online: HashSet<&str> = HashSet::from(["ana", "ben", "chen"]);

    println!("ist ben online? {}", online.contains("ben"));

    println!("ben entfernt: {}", online.remove("ben"));
    println!("ben noch mal entfernt: {}", online.remove("ben"));

    println!("ist ben online? {}", online.contains("ben"));
    println!("{} Leute online", online.len());
}

Ausgabe:

ist ben online? true
ben entfernt: true
ben noch mal entfernt: false
ist ben online? false
2 Leute online

▶ Selbst ausprobieren

Warum hier ein Set statt eines Vec? Bei einem Vec schaut contains jedes Element einzeln an. Ein HashSet springt direkt zur Antwort, egal wie groß es wird. Bei einer Million Benutzern ist das ein riesiger Unterschied.

Achtung

Ein HashSet hat keine feste Reihenfolge. Gibst du es mit {:?} aus oder läufst mit einer Schleife darüber, kann sich die Reihenfolge von einem Durchlauf zum nächsten ändern. Brauchst du beim Ausgeben eine stabile Reihenfolge, kopiere die Werte in einen Vec und sortiere ihn – oder nimm ein BTreeSet (dazu gleich mehr).

Duplikate aus einem Vec entfernen

Eine sehr häufige Aufgabe: Du hast eine Liste mit Wiederholungen und willst jeden Wert nur einmal. Dafür gibt es zwei gute Wege – je nachdem, ob dir die ursprüngliche Reihenfolge wichtig ist.

use std::collections::HashSet;

fn main() {
    let visits = vec![3, 1, 3, 2, 1, 5, 2];

    // Weg 1: in ein Set sammeln, dann für eine stabile Reihenfolge sortieren
    let unique: HashSet<i32> = visits.iter().copied().collect();
    let mut sorted: Vec<i32> = unique.into_iter().collect();
    sorted.sort();
    println!("sortiert, eindeutig: {:?}", sorted);

    // Weg 2: jeden Wert beim ersten Auftreten behalten, in der ursprünglichen Reihenfolge
    let mut seen = HashSet::new();
    let mut in_order = visits.clone();
    in_order.retain(|x| seen.insert(*x));
    println!("in Reihenfolge:      {:?}", in_order);
}

Ausgabe:

sortiert, eindeutig: [1, 2, 3, 5]
in Reihenfolge:      [3, 1, 2, 5]

▶ Selbst ausprobieren

Weg 2 nutzt den bool von insert. retain behält ein Element nur, wenn die Closure true zurückgibt – und insert gibt nur beim ersten Mal true zurück, wenn es einen Wert sieht.

Mengenlehre: Vereinigung, Schnittmenge, Differenz

Sets lassen sich kombinieren wie die Kreise in einem Venn-Diagramm. Jede dieser Methoden gibt einen Iterator zurück. Deshalb sammeln wir die Ergebnisse in einen Vec und sortieren sie vor der Ausgabe – so kommt jedes Mal dasselbe heraus.

use std::collections::HashSet;

fn main() {
    let alice: HashSet<&str> = HashSet::from(["rust", "python", "go"]);
    let bob: HashSet<&str> = HashSet::from(["go", "java", "rust"]);

    let mut both: Vec<_> = alice.intersection(&bob).collect();
    both.sort();
    println!("beide kennen:     {:?}", both);

    let mut either: Vec<_> = alice.union(&bob).collect();
    either.sort();
    println!("mindestens einer: {:?}", either);

    let mut only_alice: Vec<_> = alice.difference(&bob).collect();
    only_alice.sort();
    println!("nur Alice:        {:?}", only_alice);

    let mut only_one: Vec<_> = alice.symmetric_difference(&bob).collect();
    only_one.sort();
    println!("nur einer kennt:  {:?}", only_one);
}

Ausgabe:

beide kennen:     ["go", "rust"]
mindestens einer: ["go", "java", "python", "rust"]
nur Alice:        ["python"]
nur einer kennt:  ["java", "python"]

▶ Selbst ausprobieren

difference geht nur in eine Richtung: alice.difference(&bob) heißt „was Alice kennt, Bob aber nicht“. Vertauschst du die beiden, bekommst du stattdessen Bobs Liste. symmetric_difference nimmt beide Seiten auf einmal: alles, was nur einer von beiden kennt.

BTreeMap und BTreeSet: immer sortiert

BTreeMap funktioniert genau wie HashMap, und BTreeSet genau wie HashSet. Der Unterschied: Sie halten ihre Schlüssel sortiert. Läufst du mit einer Schleife darüber, bekommst du die Schlüssel jedes Mal in der richtigen Reihenfolge.

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let text = "the cat sat on the mat the end";

    let mut counts: BTreeMap<&str, u32> = BTreeMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    for (word, count) in &counts {
        println!("{word}: {count}");
    }

    let scores: BTreeSet<u32> = BTreeSet::from([72, 95, 58, 88]);
    println!("niedrigster: {:?}", scores.first());
    println!("höchster: {:?}", scores.last());
    println!("alle: {:?}", scores);
}

Ausgabe:

cat: 1
end: 1
mat: 1
on: 1
sat: 1
the: 3
niedrigster: Some(58)
höchster: Some(95)
alle: {58, 72, 88, 95}

▶ Selbst ausprobieren

Der englische Beispielsatz bleibt absichtlich stehen: BTreeMap sortiert Zeichenketten Byte für Byte. Umlaute wie „ä“ oder „ü“ würden dabei hinter „z“ landen – das wäre hier nur verwirrend.

Die entry-API kennst du schon von der Seite HashMap. Weil die Map hier eine BTreeMap ist, kommen die Wörter ohne zusätzliches Sortieren in alphabetischer Reihenfolge heraus.

Was solltest du wählen?

• Nimm standardmäßig HashMap / HashSet. Das Nachschlagen ist meist schneller.
• Nimm BTreeMap / BTreeSet, wenn du die Daten geordnet brauchst: für einen sortierten Bericht, um den kleinsten oder größten Schlüssel zu finden oder um einen Bereich von Schlüsseln abzufragen.

VecDeque: eine Warteschlange

Eine VecDeque (gesprochen „Vec Deck“) ist eine Liste, an deren beiden Enden du schnell Elemente hinzufügen und entfernen kannst. Damit ist sie die natürliche Wahl für eine Warteschlange (Queue): Wer zuerst kommt, ist zuerst dran – wie Leute, die in einer Schlange warten.

use std::collections::VecDeque;

fn main() {
    let mut line: VecDeque<&str> = VecDeque::new();
    line.push_back("ana");
    line.push_back("ben");
    line.push_back("chen");

    while let Some(person) = line.pop_front() {
        println!("bediene {person}, {} warten noch", line.len());
    }
}

Ausgabe:

bediene ana, 2 warten noch
bediene ben, 1 warten noch
bediene chen, 0 warten noch

▶ Selbst ausprobieren

Du könntest dafür auch Vec::remove(0) benutzen. Dann rückt aber jedes andere Element um eine Stelle nach. pop_front auf einer VecDeque macht das nicht und bleibt deshalb auch bei einer langen Schlange schnell.

Welche Collection soll ich nehmen?

Collection	Nimm sie, wenn du … brauchst	Beispiel
Vec<T>	eine geordnete Liste mit Zugriff per Position	Zeilen einer Datei, eine Liste von Punktzahlen
HashMap<K, V>	schnelles Nachschlagen eines Werts per Schlüssel	Benutzername → Benutzerprofil
HashSet<T>	eindeutige Werte und schnelle „Ist das drin?“-Prüfungen	besuchte Seiten, verbotene Wörter
BTreeMap<K, V>	Schlüssel → Wert, mit sortierten Schlüsseln	eine alphabetisch ausgegebene Wortzählung
VecDeque<T>	Hinzufügen/Entfernen an beiden Enden	eine Warteschlange für Aufgaben oder Nachrichten

Im Zweifel fang mit einem Vec an. Wechsle, wenn du merkst, dass du ihn immer wieder durchsuchst (dann nimm ein Set oder eine Map), oder wenn du oft vorne Elemente entfernst (dann nimm eine VecDeque).

Häufige Fehler

Ein eigenes Struct ohne die passenden Derives in ein HashSet stecken. Ein HashSet muss seine Werte hashen und auf Gleichheit vergleichen können. Dein Struct kann das nicht automatisch:

use std::collections::HashSet;

struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
}

error[E0277]: the trait bound `Point: Eq` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Eq` is not implemented for `Point`

error[E0277]: the trait bound `Point: Hash` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Hash` is not implemented for `Point`

Der Compiler sagt dir hier (auf Englisch): Point implementiert die Traits Eq und Hash nicht. Die Lösung ist eine einzige Zeile über dem Struct: #[derive(PartialEq, Eq, Hash)]. Für ein BTreeSet bräuchtest du zusätzlich PartialOrd und Ord, damit es weiß, wie sortiert wird. Was diese Traits jeweils bedeuten, erfährst du unter Wichtige Traits.

use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
    visited.insert(Point { x: 1, y: 0 });
    visited.insert(Point { x: 0, y: 0 }); // Duplikat, wird ignoriert
    println!("{} Felder besucht", visited.len());
}

Ausgabe:

2 Felder besucht

▶ Selbst ausprobieren

Übungen

1. Die erste Wiederholung

Du hast die Wörter ["rot", "blau", "grün", "blau", "rot"]. Gib das erste Wort aus, das zum zweiten Mal auftaucht. Tipp: insert gibt false zurück, wenn der Wert schon im Set ist, und break beendet die Schleife.

Lösung anzeigen

use std::collections::HashSet;

fn main() {
    let words = ["rot", "blau", "grün", "blau", "rot"];
    let mut seen = HashSet::new();

    for word in words {
        if !seen.insert(word) {
            println!("Erste Wiederholung: {word}");
            break;
        }
    }
}

Ausgabe:

Erste Wiederholung: blau

▶ Selbst ausprobieren

!seen.insert(word) liest sich wie „Einfügen hat nicht geklappt“ – also „das hatte ich schon“. "blau" ist das erste Wort, das sich wiederholt. "rot" wiederholt sich auch, aber erst später.

2. Buchstaben der Reihe nach

Zähle, wie oft jeder Buchstabe in "mississippi" vorkommt, und gib die Zählungen in alphabetischer Reihenfolge aus. Tipp: Nimm eine BTreeMap mit demselben Trick entry(...).or_insert(0) aus dem Abschnitt über BTreeMap und lauf mit einer Schleife über word.chars().

Lösung anzeigen

use std::collections::BTreeMap;

fn main() {
    let word = "mississippi";
    let mut counts = BTreeMap::new();

    for letter in word.chars() {
        *counts.entry(letter).or_insert(0) += 1;
    }

    for (letter, count) in &counts {
        println!("{letter}: {count}");
    }
}

Ausgabe:

i: 4
m: 1
p: 2
s: 4

▶ Selbst ausprobieren

Mit einer HashMap könnten diese vier Zeilen in beliebiger Reihenfolge herauskommen. Die BTreeMap hält ihre Schlüssel sortiert. Deshalb erscheinen i, m, p, s jedes Mal alphabetisch.

Zusammenfassung

• HashSet speichert eindeutige Werte. insert und remove geben einen bool zurück, der dir sagt, ob sich etwas geändert hat.
• contains ist bei einem Set schnell, selbst bei riesigen Sets. Bei einem Vec wird jedes Element geprüft.
• union, intersection, difference und symmetric_difference erledigen die Mengenlehre. Sortiere die Ergebnisse vor der Ausgabe.
• BTreeMap und BTreeSet halten ihre Schlüssel sortiert. Nimm sie, wenn die Reihenfolge wichtig ist.
• VecDeque ist die Standard-Warteschlange: push_back zum Anstellen, pop_front zum Drankommen.

Kurzer Check

Kurzer Check

1. Was gibt set.insert(x) zurück, wenn x schon im Set ist?

true Einen Fehler false Den alten Wert

2. Du willst eine Wortzählung alphabetisch ausgeben, ohne selbst zu sortieren. Welche Map passt am besten?

HashMap BTreeMap Vec VecDeque

3. Warum kann die Ausgabe eines HashSet mit {:?} bei verschiedenen Durchläufen unterschiedlich aussehen?

Ein HashSet hat keine feste Reihenfolge {:?} ist zufällig Sets verlieren mit der Zeit Werte Das passiert nur im Debug-Modus

4. Welche Collection eignet sich am besten für eine Warteschlange nach dem Prinzip „wer zuerst kommt, ist zuerst dran“?

HashSet BTreeSet HashMap VecDeque

Punkte: 0 / 4

Weiterlesen

• Überblick über std::collections – Standardbibliothek (auf Englisch): eine ausführlichere Anleitung zur Wahl der richtigen Collection, mit der Geschwindigkeit jeder Operation.
• HashSet – Rust by Example (auf Englisch): ein ausführbares Beispiel zu union, intersection und difference.
• HashSet – Standardbibliothek (auf Englisch): alle Methoden für Sets, auch is_subset und retain.
• BTreeMap – Standardbibliothek (auf Englisch): sortierte Maps, inklusive range, um einen Ausschnitt der Schlüssel zu bekommen.
• VecDeque – Standardbibliothek (auf Englisch): alle Methoden für Warteschlangen, etwa push_front, pop_back und front.