HashMap

Konstruktion

Eine HashMap lebt im Modul std::collections und muss explizit importiert werden — anders als Vec oder String, die im Prelude liegen. Diese kleine Reibung sorgt dafür, dass HashMap nicht versehentlich für Aufgaben gewählt wird, bei denen ein anderer Container besser passen würde. Die Konstruktion bietet vier idiomatische Wege, die sich nach der Quelle der Daten richten: aus dem Nichts beginnen (new), mit Vorrat (with_capacity), aus einem Iterator von Tupeln (collect) oder aus einem Array von Tupeln (from).

use std::collections::HashMap;

fn main() {
    // Leer
    let mut m1: HashMap<String, i32> = HashMap::new();

    // Mit Kapazität
    let mut m2: HashMap<String, i32> = HashMap::with_capacity(100);

    // Aus Iterator von Tupeln
    let m3: HashMap<&str, i32> = [("a", 1), ("b", 2), ("c", 3)]
        .into_iter()
        .collect();

    // Aus Arrays
    let m4 = HashMap::from([
        ("eins", 1),
        ("zwei", 2),
    ]);
}

HashMap::new() legt eine leere Map an, die noch keinen Heap-Speicher reserviert hat — die erste Allocation passiert beim ersten insert. Bei with_capacity(n) wird sofort Platz für mindestens n Einträge reserviert; der tatsächliche Wert ist oft etwas größer, weil HashMap intern auf Power-of-Two-Größen aufrundet und einen Load-Factor (typisch 7/8) berücksichtigt, damit Kollisionen selten bleiben.

collect und from sind die zwei Wege, eine Map direkt aus Daten zu bauen. Beide produzieren funktional identische Ergebnisse — der Unterschied ist syntaktisch. from([...]) ist die kürzeste Form bei Literalen, weil das Array direkt aus dem Code kommt; collect ist universell und funktioniert mit jedem Iterator-Quelltyp (Vec, Range, Filter-Pipeline). In beiden Fällen liest die HashMap aus der size_hint des Iterators einen passenden Initial-Capacity-Wert und vermeidet so Rehashes während des Aufbaus.

Wichtige Detail: bei Duplikaten in der Eingabe-Sequenz gewinnt der letzte Eintrag — wenn [("a", 1), ("a", 2)] collectet wird, steht am Ende a -> 2 in der Map. Das ist konsistent mit dem Verhalten von wiederholten insert-Aufrufen.

Voraussetzung: Key muss Hash + Eq sein

Damit HashMap einen Wert nach einem Key zuordnen kann, braucht der Key zwei Trait-Implementierungen. Sie greifen ineinander: zuerst wird Hash benutzt, um aus dem Key eine Zahl (den Hash-Wert) zu berechnen — diese Zahl bestimmt, in welchem Bucket des internen Arrays der Eintrag landet. Wenn zwei verschiedene Keys den gleichen Hash haben (eine Kollision), liegen sie im selben Bucket, und HashMap muss sie über Eq auseinanderhalten — dafür wird die exakte Gleichheit abgefragt. Ohne Eq wäre kein zuverlässiger Lookup möglich.

Hash — produziert eine 64-Bit-Hash aus den Bytes/Feldern des Keys. Bei Strings die UTF-8-Bytes, bei Structs die Hashes aller Felder kombiniert.

Eq — strikte Gleichheit (==). Implementiert wird PartialEq, und Eq ist ein Marker-Trait, der ausdrückt: „diese Gleichheit ist reflexiv" (x == x ist immer true). Das schließt z. B. Floats aus, bei denen NaN != NaN.

use std::collections::HashMap;

#[derive(Debug, PartialEq, Eq, Hash)]
pub struct UserId(u64);

fn main() {
    let mut map: HashMap<UserId, String> = HashMap::new();
    map.insert(UserId(42), "Anna".into());
    assert_eq!(map.get(&UserId(42)), Some(&"Anna".to_string()));
}

Das gezeigte Pattern ist der Standard: ein eigener Newtype-Wrapper (hier UserId(u64)) bekommt die drei Traits über #[derive(...)] und kann sofort als HashMap-Key dienen. Das derive generiert automatisch korrekte Implementierungen, die auf der Gleichheit und dem Hash des inneren Wertes basieren. Für die meisten eigenen Key-Typen ist das die richtige Wahl — du musst nicht selbst hashen.

Float-Keys (f32, f64) funktionieren nicht direkt, weil das IEEE-754-Verhalten von Floats die Eq-Bedingung der Reflexivität bricht: NaN == NaN liefert false. Wenn du trotzdem Floats als Keys brauchst, gibt es zwei Wege: die ordered_float-Crate liefert einen Wrapper NotNan<f64>, der NaN verbietet und damit Eq erfüllen kann; alternativ kannst du die Float-Bits selbst als u64 interpretieren (f64::to_bits()) und diese als Key nutzen, wenn dir die exakte Bit-Identität reicht.

Grundlegende Operations

Insert / Update

insert ist die zentrale Schreib-Operation und hat ein bemerkenswertes Detail: sie unterscheidet zwischen neuer Einfügung und Überschreibung über den Rückgabewert. Das Konzept ist anders als in den meisten Sprachen, in denen map[key] = value keine Information zurückgibt — Rust will, dass du bewusst weißt, ob du gerade etwas verloren hast.

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    let alt = map.insert("a", 1);     // None — neu
    let alt2 = map.insert("a", 99);    // Some(1) — überschrieben
    assert_eq!(alt, None);
    assert_eq!(alt2, Some(1));
}

Im ersten Aufruf war der Key "a" noch nicht vorhanden — Rückgabewert ist None, der neue Eintrag wird angelegt. Im zweiten Aufruf existiert "a" bereits mit Wert 1 — der neue Wert 99 überschreibt ihn, und der vorherige Wert wird als Some(1) zurückgegeben. Damit kannst du in einer Zeile feststellen, ob du etwas Bestehendes ersetzt hast, was bei Caches und Counter-Strukturen wichtig sein kann: „wenn ich gerade einen alten Wert weggeworfen habe, sollte ich vielleicht eine Warnung loggen".

Wichtig zu wissen ist, dass insert den Key moved — bei String als Key wird der String in die HashMap übernommen, du kannst ihn danach nicht mehr verwenden. Wenn du den Key weiter benutzen willst, klonst du ihn vorher oder nutzt die Entry-API, die nur einmal den Key braucht.

Lookup

Der Lookup-Stil in Rust unterscheidet sich von vielen anderen Sprachen, weil das Fehlen eines Keys nicht in einer Exception endet, sondern in einem expliziten Option-Rückgabewert. Du bekommst keinen Default-Wert, keinen Panic — sondern eine None-Variante, die du im Pattern-Match behandelst. Das ist anders, aber sehr sicher: du kannst nicht versehentlich auf einem fehlenden Key arbeiten.

use std::collections::HashMap;

fn main() {
    let mut m = HashMap::from([("a", 1), ("b", 2)]);

    let a: Option<&i32> = m.get("a");                 // Some(&1)
    let z: Option<&i32> = m.get("z");                 // None
    let hat_a: bool = m.contains_key("a");            // true
    let n: usize = m.len();                            // 2

    // Mutable get
    if let Some(wert) = m.get_mut("a") {
        *wert += 100;        // a ist jetzt 101
    }
}

get gibt eine Option<&V> zurück — bei Treffer eine geliehene Referenz auf den gespeicherten Wert, sonst None. get_mut ist die mutable Variante mit Option<&mut V> und erlaubt In-Place-Änderung. contains_key ist ein billiger Existenz-Check, der nichts zurückgibt außer dem booleschen Treffer-Status; intern macht er denselben Lookup wie get, ist aber semantisch klarer, wenn du nur die Frage „ist der Key drin?" beantworten willst.

Bemerkenswert ist die Borrow-Magie bei m.get("a"). Obwohl die Map mit &str (im Beispiel) typisiert ist, kannst du den Key in vielen Formen übergeben — ein &str, ein &String, ein &[u8] (bei einigen Implementierungen). Möglich wird das durch den Borrow-Trait: die HashMap-Methode get erwartet einen Q: ?Sized mit K: Borrow<Q>, und der Compiler findet automatisch die passende Trait-Implementierung. In der Praxis bedeutet das: wenn deine Map HashMap<String, V> ist, kannst du map.get("foo") mit einem &str-Literal aufrufen, ohne einen String aus "foo" allozieren zu müssen. Diese kleine Eleganz spart in Hot-Paths viele unnötige Allocations.

Remove

use std::collections::HashMap;

fn main() {
    let mut m = HashMap::from([("a", 1), ("b", 2)]);

    let alt = m.remove("a");          // Some(1)
    let nicht_da = m.remove("z");     // None
    assert_eq!(alt, Some(1));
    assert_eq!(nicht_da, None);
}

remove löscht den Eintrag und gibt den entfernten Wert zurück, sofern es einen gab. Das ist wieder das Rust-typische Muster: keine schweigende Erfolgs-/Misserfolgs-Logik, sondern eine Option, die dich zwingt zu entscheiden, wie du mit beiden Fällen umgehst. Dieser Rückgabewert ist besonders nützlich, wenn du den Wert „herauspflücken" willst — etwa in einer Move-Out-Operation, bei der du den Eintrag aus der Map entfernst und gleichzeitig weiterverarbeitest.

Im Speicher passiert beim remove nicht viel Spektakuläres: der Slot im Bucket-Array wird als „gelöscht" markiert (technisch über einen sogenannten Tombstone oder durch Verschiebung benachbarter Einträge, je nach Implementation), und die len wird dekrementiert. Die Kapazität bleibt unverändert — wer nach vielen Removes Speicher zurückgewinnen will, ruft shrink_to_fit auf.

Die Entry-API — der wichtigste Trick

Die Entry-API ist eine der elegantesten Designentscheidungen in der Rust-Stdlib, und gleichzeitig die, die viele Anfänger erst spät entdecken — meist nach mehreren Bug-Sessions mit der naiven Variante. Das gelöste Problem ist allgegenwärtig: du willst einen Eintrag in der Map manipulieren, weißt aber nicht, ob er schon existiert oder nicht. Die naive Lösung über contains_key und insert/get_mut macht zwei Lookups und führt schnell zu Borrow-Checker-Problemen. Die Entry-API löst beides in einem einzigen, atomaren Aufruf.

Die naive Form mit contains_key + insert:

use std::collections::HashMap;

fn main() {
    let mut zaehler: HashMap<&str, u32> = HashMap::new();
    let key = "rot";

    // Schlecht — zwei Lookups
    if zaehler.contains_key(key) {
        *zaehler.get_mut(key).unwrap() += 1;
    } else {
        zaehler.insert(key, 1);
    }
}

Im naiven Code passiert mehr, als es aussieht. contains_key(key) macht einen Hash und einen Lookup. Wenn der Treffer da ist, ruft get_mut(key) denselben Hash und Lookup nochmal auf — dann unwrap, weil wir ja gerade festgestellt haben, dass der Key existiert. Das sind also zwei vollständige Hash-Berechnungen plus zwei Bucket-Walks. Bei kleinen Maps egal, bei großen oder Hot-Path-Maps spürbar.

Der idiomatische Weg führt über entry:

use std::collections::HashMap;

fn main() {
    let mut zaehler: HashMap<&str, u32> = HashMap::new();
    *zaehler.entry("rot").or_insert(0) += 1;
    *zaehler.entry("rot").or_insert(0) += 1;
    *zaehler.entry("blau").or_insert(0) += 1;
    assert_eq!(zaehler.get("rot"), Some(&2));
    assert_eq!(zaehler.get("blau"), Some(&1));
}

Das entry(key)-Verfahren funktioniert in zwei Schritten. Im ersten Schritt liefert die Methode einen Entry-Wert zurück — ein Enum mit zwei Varianten: Occupied(...), wenn der Key existiert, oder Vacant(...), wenn nicht. Das interessante: Rust hat dabei den Lookup schon erledigt, und der Entry hält intern die Position im Bucket fest. Im zweiten Schritt rufst du eine Methode auf dem Entry auf — or_insert(default), or_insert_with(...), and_modify(...) — und Rust kann die Operation ohne weiteren Lookup ausführen.

or_insert(default) ist die häufigste Folge-Methode. Wenn der Key existiert, gibt sie eine &mut V auf den vorhandenen Wert zurück. Wenn nicht, fügt sie den Default-Wert ein und gibt eine &mut V auf den neu eingefügten Eintrag zurück. In beiden Fällen bekommst du also eine mutable Referenz, mit der du den Wert direkt verändern kannst — wie im Beispiel mit *=-Operatoren. Das gesamte „insert-if-missing-then-update"-Pattern wird damit zu einer einzigen Zeile.

or_insert_with für teure Defaults

or_insert(default) hat ein Performance-Detail, das schnell zur Bug-Quelle wird: der Default-Wert wird immer berechnet, auch wenn der Key schon existiert und der Default gar nicht eingefügt wird. Das ist okay bei or_insert(0) (eine i32-Konstante), katastrophal bei or_insert(teure_berechnung(...)). Genau dafür gibt es die Lazy-Variante.

use std::collections::HashMap;

let mut cache: HashMap<String, Vec<u8>> = HashMap::new();
let daten = cache.entry("foo".into())
    .or_insert_with(|| teure_berechnung("foo"));
# fn teure_berechnung(_: &str) -> Vec<u8> { vec![] }

or_insert_with(closure) nimmt eine Closure statt eines Wertes, und die Closure wird nur dann aufgerufen, wenn der Key noch nicht in der Map ist. Bei einem Cache-Hit (Key existiert) passiert nichts außer dem normalen Lookup — die Closure und ihre potentiell teure Berechnung werden komplett übersprungen. Das ist die idiomatische Form für Memoization, Lazy-Loading und Caches: nur dann allozieren, wenn der Eintrag wirklich neu gebaut werden muss.

Das gleiche Pattern existiert mit or_insert_with_key(closure), wenn die Default-Berechnung den Key kennt — die Closure bekommt den Key als Parameter. Praktisch, wenn der Default vom Key abhängt.

Entry-Pattern für komplexere Logik

Manchmal brauchst du nicht nur „insert wenn fehlt", sondern „update wenn da, sonst insert" mit unterschiedlicher Logik für beide Fälle. Genau dafür gibt es and_modify, das vor or_insert in der Entry-Kette platziert wird.

use std::collections::HashMap;

fn main() {
    let mut m: HashMap<&str, i32> = HashMap::from([("a", 10)]);

    // Wenn da: verdoppeln. Sonst: 1 einsetzen.
    m.entry("a")
        .and_modify(|v| *v *= 2)
        .or_insert(1);

    m.entry("b")
        .and_modify(|v| *v *= 2)
        .or_insert(1);

    assert_eq!(m.get("a"), Some(&20));
    assert_eq!(m.get("b"), Some(&1));
}

and_modify(closure) bekommt eine Closure, die auf einer mutable Referenz auf den bestehenden Wert läuft — aber nur dann, wenn der Eintrag existiert. Wenn der Key nicht da ist, passiert and_modify einfach nichts und reicht den Entry unverändert weiter. Das anschließende or_insert(1) greift dann mit dem Default-Wert. Im Beispiel sieht man die saubere Trennung: für Key "a" (existiert mit Wert 10) wird and_modify aktiv und verdoppelt auf 20; or_insert(1) ist hier wirkungslos. Für Key "b" (existiert nicht) macht and_modify nichts, und or_insert(1) fügt den Default ein.

Die Kette entry().and_modify().or_insert() ist die idiomatische Form für sogenannte „upsert"-Operationen mit unterschiedlicher Logik. Es gibt keinen redundanten Lookup — entry hat die Position schon ermittelt, alle weiteren Operationen wissen, wo der Eintrag liegt (oder eben nicht).

Iteration

HashMap-Iteration bietet die gleiche Borrow-Logik wie Vec (iter, iter_mut, into_iter), aber zusätzlich eigene Iteratoren für die beiden Komponenten Key und Value. Praktisch, weil oft nur eine Seite des Paares interessiert.

use std::collections::HashMap;

fn main() {
    let m = HashMap::from([("a", 1), ("b", 2), ("c", 3)]);

    // Über Paare (&K, &V):
    for (key, wert) in &m {
        println!("{key} → {wert}");
    }

    // Nur Keys:
    for k in m.keys() { print!("{k} "); }

    // Nur Values:
    for v in m.values() { print!("{v} "); }

    // Mutable Values:
    let mut m2 = m.clone();
    for v in m2.values_mut() {
        *v *= 10;
    }
}

Vier Iterations-Wege, die du in der Praxis immer wieder brauchst: das Paar-Loop (for (k, v) in &m) ist die häufigste Form für klassische „mach was mit jedem Eintrag"-Operationen. keys() und values() geben dir nur die jeweilige Seite als Iterator zurück — billig, weil sie auf demselben internen Storage arbeiten wie die volle Iteration, nur die andere Komponente ignorieren. values_mut() erlaubt In-Place-Update aller Werte, während die Keys unangetastet bleiben (was zwingend ist — Keys ändern würde den Hash invalidieren).

Eine wichtige Eigenschaft, die viele Anfänger überrascht: die Iterations-Reihenfolge ist nicht definiert und kann sich von Lauf zu Lauf unterscheiden. Das ist kein Bug, sondern Absicht — HashMap nutzt einen zufallsinitialisierten Hash-Seed (DoS-Schutz), und die interne Bucket-Anordnung hängt davon ab. Wer auf reproduzierbare Reihenfolge angewiesen ist, hat zwei Optionen: BTreeMap (sortiert nach Key) oder die Keys in einen Vec extrahieren, sortieren und dann manuell iterieren. Beides ist legitim, aber bewusster zu wählen, als sich auf HashMap-Reihenfolge zu verlassen.

Default-Hasher und Custom-Hasher

Eine HashMap-Eigenschaft, die in Performance-Debatten oft auftaucht, ist die Wahl des Hash-Algorithmus. Rust verwendet standardmäßig SipHash 1-3 — eine kryptographisch motivierte Wahl. Der Grund ist eine spezifische Angriffsklasse: Hash-Collision-Attacks. Wenn ein Angreifer weiß, welche Hash-Funktion deine Server-HashMap nutzt, kann er gezielt Keys konstruieren, die alle im selben Bucket landen. Damit degeneriert HashMap-Lookup von O(1) auf O(n), und der Server lässt sich mit wenigen Einträgen lahmlegen. SipHash ist gegen diese Angriffe gehärtet, indem es einen pro Prozess-zufälligen Seed nutzt — der Angreifer kann die Kollisionen nicht vorausberechnen.

Der Preis: SipHash ist messbar langsamer als nicht-kryptographische Hashes. Für interne Datenstrukturen mit vertrauenswürdigen Keys (z. B. ein Compiler-internes Symbol-Mapping, ein Spiel-Engine-Cache) ist dieser Schutz unnötig — und schnellere Alternativen können den Hash-Schritt 2-3× beschleunigen.

# // Erfordert Cargo.toml: ahash = "0.8"
use ahash::AHashMap;

fn main() {
    let mut schnell: AHashMap<String, i32> = AHashMap::new();
    schnell.insert("a".into(), 1);
}

Die zwei meistgenutzten Alternativen sind ahash (sehr schnell, mit etwas Schutz vor Kollisions-Angriffen über einen Seed) und rustc-hash (extrem schnell, dafür gar nicht angriffsresistent — der Rust-Compiler selbst nutzt das für seine internen Tables). Die API ist identisch zu HashMap, du tauschst nur den Konstruktor aus.

In der Praxis gilt: Standard ist die richtige Wahl für 99 % der Fälle. Erst wenn Profiling tatsächlich zeigt, dass HashMap-Operationen ein messbarer Bottleneck sind, lohnt sich der Wechsel — und auch dann nur, wenn die Keys vertrauenswürdig sind. Bei Server-HashMaps mit user-supplied Keys (HTTP-Header, URL-Parameter, Form-Daten) solltest du beim Default bleiben, weil die DoS-Resistenz dort genau das ist, was du brauchst.

Praxis: HashMap im echten Code

Die folgenden Beispiele sind Patterns, die du in realem Rust-Code immer wieder findest — von kleinen CLI-Tools bis zu großen Webservern. Sie zeigen, dass HashMap selten allein steht, sondern fast immer in Verbindung mit anderen Mechanismen (Entry-API, Iterator-Chains, Tuple-Lookups) eingesetzt wird.

Frequenz-Zähler

use std::collections::HashMap;

pub fn wort_frequenz(text: &str) -> HashMap<&str, u32> {
    let mut counts = HashMap::new();
    for wort in text.split_whitespace() {
        *counts.entry(wort).or_insert(0) += 1;
    }
    counts
}

fn main() {
    let h = wort_frequenz("der schnelle braune fuchs der schnelle hase");
    assert_eq!(h.get("der"), Some(&2));
    assert_eq!(h.get("hase"), Some(&1));
}

Das ist die kanonische Demonstration der Entry-API: Wörter zählen. Bei jedem Wort wird entry(wort) aufgerufen, das eine Entry zurückgibt. or_insert(0) produziert eine mutable Referenz auf den Wert — entweder den existierenden Zähler oder eine frisch eingefügte 0. Auf diese Referenz wird mit *= ... += 1 dann inkrementiert. Insgesamt ist das eine einzige Zeile pro Wort, mit einem einzigen Hash-Lookup. Die naive Variante mit contains_key plus insert/get_mut wäre fünf Zeilen und doppelter Aufwand pro Wort.

Die Funktion gibt die Map zurück; der Aufrufer kann dann mit get, iter oder anderen Methoden weiterarbeiten. Beachte den Lifetime-Trick im Rückgabe-Typ: HashMap<&str, u32> — die Keys sind Borrows aus dem Eingabe-Text, kein neuer String-Allocation-Aufwand. Das funktioniert, solange der zurückgegebene Wert nicht länger lebt als der Input.

Cache mit Lazy-Computation

use std::collections::HashMap;

pub struct Cache<K: std::hash::Hash + Eq, V: Clone> {
    eintraege: HashMap<K, V>,
}

impl<K: std::hash::Hash + Eq, V: Clone> Cache<K, V> {
    pub fn neu() -> Self {
        Cache { eintraege: HashMap::new() }
    }

    pub fn hole_oder_berechne<F: FnOnce() -> V>(&mut self, key: K, f: F) -> V {
        self.eintraege.entry(key).or_insert_with(f).clone()
    }
}

Ein generischer Cache mit Lazy-Initialisierung. Der Aufruf hole_oder_berechne(key, f) macht zwei Dinge: gibt es den Eintrag schon, wird er gecloned und zurückgegeben; gibt es ihn nicht, wird f() aufgerufen, das Ergebnis eingefügt und ebenfalls gecloned zurückgegeben. Die Trait-Bounds zeigen die typischen Anforderungen: K: Hash + Eq für den Map-Key, V: Clone weil wir den Wert herausgeben (statt eine Referenz, die durch den &mut self-Borrow blockiert wäre).

Das Clone ist hier ein bewusster Kompromiss. Eine Variante ohne Clone würde &V zurückgeben, ist aber komplizierter im Borrow-Verhalten — der Caller hätte einen Borrow auf den Cache, der weitere Aufrufe verhindert. Mit Clone ist die API leichter zu konsumieren, der Preis ist eine Kopie des Werts. Für teuer-zu-erstellende, aber billig-zu-klonende Werte (z. B. Arc<T>) ist das ein sehr guter Trade-off.

Index-Map für Detail-Lookup

use std::collections::HashMap;

pub struct UserIndex {
    by_id: HashMap<u64, String>,
    by_email: HashMap<String, u64>,
}

impl UserIndex {
    pub fn neu() -> Self {
        UserIndex { by_id: HashMap::new(), by_email: HashMap::new() }
    }

    pub fn hinzufuegen(&mut self, id: u64, email: String, name: String) {
        self.by_email.insert(email.clone(), id);
        self.by_id.insert(id, name);
    }

    pub fn name_von_email(&self, email: &str) -> Option<&String> {
        let id = self.by_email.get(email)?;
        self.by_id.get(id)
    }
}

Wenn du dieselben Daten über zwei verschiedene Keys finden willst, brauchst du zwei HashMaps mit gegenseitiger Verknüpfung. Im Beispiel speichert by_id die User-Namen, by_email mappt E-Mails auf die ID — die ID dient als Bindeglied. Bei einem name_von_email-Lookup wird zuerst aus der E-Mail die ID geholt (? propagiert ein eventuelles None), dann aus der ID der Name. Zwei Lookups, beide O(1).

Das Pattern ist die manuelle Umsetzung eines Datenbank-Sekundär-Index. Der Nachteil: bei Updates musst du beide Maps konsistent halten, sonst entstehen Inkonsistenzen. Bibliotheken wie multimap oder bimap lösen das eleganter, sind aber für einfache Fälle Overkill. Die email.clone() in hinzufuegen ist notwendig, weil email einmal in by_email und der zugehörige Wert auch noch in der ID-Map referenziert wird — Rust kann nicht zwei mutable Borrows auf denselben String haben, deshalb der Clone.

Configuration-Wrapper

use std::collections::HashMap;

pub struct Config(HashMap<String, String>);

impl Config {
    pub fn aus_env() -> Self {
        let m = std::env::vars().collect();
        Config(m)
    }

    pub fn get(&self, key: &str) -> Option<&str> {
        self.0.get(key).map(|s| s.as_str())
    }

    pub fn get_oder(&self, key: &str, default: &str) -> String {
        self.get(key).map(|s| s.to_string()).unwrap_or_else(|| default.to_string())
    }
}

HashMap als Konfigurations-Backend ist ein klassisches Pattern für CLI-Tools und Services. std::env::vars() gibt einen Iterator von (String, String)-Tupeln zurück, der direkt zu einer HashMap collectet wird. Die Config-Struct ist ein Newtype-Wrapper — sie versteckt die HashMap-Implementation und exponiert nur die API, die für Konfiguration sinnvoll ist (get, get_oder). Wer später vom HashMap-Backend auf TOML, ENV oder einen Service-Discovery-Lookup umstellen will, kann das tun, ohne die Aufrufer anzupassen.

Die get_oder-Methode mit Default ist eine kleine, aber wichtige Bequemlichkeit. unwrap_or macht den Option-Pattern-Match unsichtbar und sorgt dafür, dass der Caller niemals mit einem None umgehen muss — der Default greift transparent.

Aggregation nach Kategorie

use std::collections::HashMap;

struct Order { kategorie: String, betrag: i64 }

pub fn umsatz_pro_kategorie(orders: &[Order]) -> HashMap<String, i64> {
    let mut summen: HashMap<String, i64> = HashMap::new();
    for o in orders {
        *summen.entry(o.kategorie.clone()).or_insert(0) += o.betrag;
    }
    summen
}

Das Group-By-Pattern in seiner direktesten Form. Für jede Bestellung wird der Kategorie-Schlüssel geklont (weil die HashMap einen besitzten String als Key braucht und wir nur einen Borrow auf o.kategorie haben). or_insert(0) liefert die Referenz auf den Summen-Akkumulator, += o.betrag aktualisiert sie. Am Ende enthält die Map für jede Kategorie genau eine Summe.

Bei sehr vielen Bestellungen mit wenigen verschiedenen Kategorien wird kategorie.clone() zum spürbaren Kostenfaktor — jeder Insert klont den String, auch wenn der Key schon in der Map ist. Eine Optimierung wäre, statt clone die entry-Variante mit or_insert_with_key zu nutzen, oder den Key-Typ auf &str mit Lifetime-Bindung zu ändern, sodass die HashMap nur Referenzen in den Eingabe-String hält.

Doppelten-Erkennung

use std::collections::HashMap;

pub fn erste_doppelte(zahlen: &[i32]) -> Option<i32> {
    let mut gesehen: HashMap<i32, u32> = HashMap::new();
    for &n in zahlen {
        let count = gesehen.entry(n).or_insert(0);
        *count += 1;
        if *count == 2 {
            return Some(n);
        }
    }
    None
}

Duplikate-Erkennung in linearer Zeit. Statt jedes Element gegen alle bisherigen zu vergleichen (was O(n²) wäre), nutzt der Algorithmus eine HashMap, um jede gesehene Zahl auf einen Counter zu mappen. Sobald ein Counter auf 2 springt, ist das erste Duplikat gefunden, und die Funktion kehrt sofort zurück. Die Gesamtkomplexität ist O(n) mit O(n) Speicher — ein klassischer Time-vs-Space-Trade-off.

Für den reinen Duplikate-Test ohne Counter-Bedarf wäre ein HashSet semantisch passender: if !gesehen.insert(n) { return Some(n); } ist eine kürzere Variante, weil insert auf HashSet true bei neuem Element und false bei Duplikat liefert.

Two-Sum-Algorithmus

use std::collections::HashMap;

pub fn two_sum(nums: &[i32], ziel: i32) -> Option<(usize, usize)> {
    let mut gesehen: HashMap<i32, usize> = HashMap::new();
    for (i, &n) in nums.iter().enumerate() {
        let komplement = ziel - n;
        if let Some(&j) = gesehen.get(&komplement) {
            return Some((j, i));
        }
        gesehen.insert(n, i);
    }
    None
}

fn main() {
    assert_eq!(two_sum(&[2, 7, 11, 15], 9), Some((0, 1)));
}

Der bekannte Two-Sum-Algorithmus ist ein Lehrbuch-Beispiel für die Macht der HashMap. Die naive Lösung wäre eine doppelte Schleife (für jedes Element gegen alle anderen prüfen) — O(n²). Die HashMap-Lösung speichert während des einmaligen Durchgangs jeden gesehenen Wert auf seinen Index. Für jedes neue Element wird das Komplement (ziel - n) berechnet und in der Map gesucht. Findet sich es, sind die zwei Indizes gefunden — O(n) gesamt, mit O(n) zusätzlichem Speicher.

Der Trick ist, dass das Komplement schon vor dem Insert gesucht wird — sonst würde das Element sich selbst als Komplement finden, wenn n + n == ziel. Diese Reihenfolge ist subtil und kommt bei vielen Hash-basierten Algorithmen wieder.

Session-Store

use std::collections::HashMap;
use std::time::Instant;

pub struct SessionStore {
    sessions: HashMap<String, (u64, Instant)>,        // token -> (user_id, expiry)
}

impl SessionStore {
    pub fn neu() -> Self {
        SessionStore { sessions: HashMap::new() }
    }

    pub fn registrieren(&mut self, token: String, user_id: u64, exp: Instant) {
        self.sessions.insert(token, (user_id, exp));
    }

    pub fn validieren(&self, token: &str) -> Option<u64> {
        let (uid, exp) = self.sessions.get(token)?;
        if Instant::now() < *exp { Some(*uid) } else { None }
    }

    pub fn aufraeumen(&mut self) {
        let jetzt = Instant::now();
        self.sessions.retain(|_, (_, exp)| jetzt < *exp);
    }
}

Ein Mini-Session-Store, wie ihn jeder kleine Webserver implementiert. Die HashMap mappt einen Session-Token (kryptographisch zufällig) auf ein Tupel aus User-ID und Ablauf-Zeitpunkt. validieren macht den Lookup und prüft, ob die Session noch gültig ist; bei Ablauf wird kein Eintrag entfernt, sondern nur None zurückgegeben.

Das aufraeumen ist die periodische Wartung. retain(closure) ist eine in-place-Filter-Operation: alle Einträge, für die das Prädikat false liefert, werden entfernt; alle anderen bleiben stehen. Bei 1000 Sessions mit 50% abgelaufenen wäre die Alternative — alle Tokens sammeln, dann einzeln remove aufrufen — deutlich langsamer und mit zusätzlichem Speicher-Aufwand. retain ist die idiomatische Wahl.

Der _ als Key-Argument zeigt, dass wir den Token nicht zur Entscheidung brauchen, nur den Inhalt — die Closure schaut auf die Ablauf-Zeit und vergleicht mit jetzt.

HashMap als Mapping-Tabelle

use std::collections::HashMap;

pub fn status_message(code: u16) -> String {
    let mapping = HashMap::from([
        (200, "OK"),
        (404, "Not Found"),
        (500, "Internal Server Error"),
    ]);
    mapping.get(&code).copied().unwrap_or("Unknown").to_string()
}

Dieses Beispiel ist absichtlich grenzwertig — es zeigt, wann HashMap nicht die beste Wahl ist. Bei einer statischen Mapping-Tabelle mit drei Einträgen ist match semantisch klarer, schneller (der Compiler kann zu einem Jump-Table optimieren) und allokiert nichts. Die HashMap-Variante alloziert bei jedem Funktionsaufruf eine neue Map mit drei Einträgen — bei häufigen Aufrufen reine Verschwendung.

Die HashMap-Lösung wird erst dann sinnvoll, wenn die Mapping-Tabelle dynamisch ist (z. B. aus einer Konfigurationsdatei geladen, zur Laufzeit erweiterbar) oder groß (Hunderte von Einträgen, wo der Compiler beim match ineffizient wird). Bei der gezeigten Größe ist match code { 200 => "OK", 404 => "Not Found", 500 => "Internal Server Error", _ => "Unknown" } die richtige Wahl.

Weiterführende Ressourcen

Externe Quellen

• The Rust Book – HashMap
• std::collections::HashMap
• std::collections::hash_map::Entry
• ahash-Crate
• rustc-hash-Crate

Verwandte Artikel

• HashSet
• BTreeMap und BTreeSet
• Vec
• Collections – Übersicht