Fortgeschrittene Collections: Architektur, CPU-Caches & Performance-Optimierung

Willkommen im Profi-Abschnitt von Kapitel 6. In der alltäglichen Rust-Programmierung greift man intuitiv zu Vec für Sequenzen und zu HashMap für Schlüssel-Wert-Paare. Für viele Anwendungsfälle ist das völlig ausreichend. Wenn Sie jedoch hochperformante Systeme, Spiele-Engines, Compiler oder speichersensitive Netzwerkdienste entwickeln, müssen Sie die Mechanik unter der Haube verstehen.

In diesem Abschnitt betrachten wir die Standard-Collections aus der Perspektive der Hardware, des Compilers und des API-Designs. Wir strukturieren diesen Abschnitt in konkrete, praxisrelevante Empfehlungen (Items), die Ihnen helfen, fundierte architektonische Entscheidungen zu treffen.

Item 11: Wähle die passende Datenstruktur basierend auf Komplexität und CPU-Cache-Verhalten

Ein weit verbreiteter Irrglaube in der Softwareentwicklung ist, dass die Wahl einer Datenstruktur ausschließlich anhand ihrer asymptotischen Laufzeitkomplexität (der O-Notation wie $O(1)$ oder $O(\log n)$) erfolgen sollte. In der Realität moderner Hardware-Architekturen spielt das CPU-Cache-Verhalten eine oft dominierende Rolle. Eine theoretisch langsame Operation auf einer cache-lokalen Datenstruktur kann eine theoretisch schnelle Operation auf einer cache-unfreundlichen Struktur um ein Vielfaches schlagen.

1. Didaktische Alltagsanalogie: Der geordnete Aktenordner vs. Die Zettelwirtschaft im Haus

Um den Unterschied zwischen cache-freundlichen und cache-unfreundlichen Strukturen zu verstehen, stellen wir uns folgendes Szenario vor: Sie müssen ein Rezept mit 10 Schritten kochen.

• Der Vektor (Vec\<T\>) – Der geordnete Aktenordner: Alle Schritte des Rezepts stehen direkt nacheinander auf einer einzigen Seite in einem Aktenordner, der vor Ihnen auf dem Küchentisch liegt. Da der Küchentisch Ihr CPU-Cache ist, haben Sie das gesamte Blatt sofort im Blickfeld. Um von Schritt 1 zu Schritt 2 zu gelangen, müssen Sie lediglich Ihren Blick um eine Zeile senken. Das geht extrem schnell, da keine physische Bewegung im Raum erforderlich ist.
• Die verkettete Liste (LinkedList\<T\>) – Die Zettelwirtschaft im Haus: Jeder einzelne Kochschritt steht auf einem separaten Zettel. Auf Zettel 1 (auf dem Küchentisch) steht: “Schneide die Zwiebeln. Der nächste Zettel befindet sich im Keller hinter der Waschmaschine.” Sie laufen in den Keller (Hauptspeicher-Zugriff / RAM). Auf Zettel 2 steht: “Bratsch die Zwiebeln an. Der nächste Zettel liegt auf dem Dachboden im alten Koffer.” Sie laufen auf den Dachboden. Das nennt man in der Informatik Zeigerjagen (Pointer Chasing). Obwohl Sie auch hier nur 10 Schritte ausführen, verbringen Sie 99 % Ihrer Zeit mit dem Laufen durch das Haus (Warten auf den RAM), anstatt mit dem Kochen (Rechnen der CPU).

2. Theorie & Konzepte: Cache-Lines und Speicherlokalität

Moderne CPUs arbeiten nicht direkt auf dem Hauptspeicher (RAM). Der Zugriff auf den RAM ist im Vergleich zur Taktfrequenz der CPU extrem langsam (ca. 50–100 Nanosekunden gegenüber weniger als 0,5 Nanosekunden für einen CPU-Zyklus). Um diese Lücke zu schließen, besitzen CPUs hierarchische Caches (L1, L2, L3).

Wenn die CPU ein bestimmtes Byte aus dem Hauptspeicher anfordert, lädt sie nicht nur dieses eine Byte, sondern einen ganzen Block von typischerweise 64 Bytes – eine sogenannte Cache-Line.

• Räumliche Lokalität (Spatial Locality): Wenn ein Programm auf eine Speicheradresse zugreift, ist die Wahrscheinlichkeit hoch, dass es bald auf benachbarte Speicheradressen zugreift.
• Vec<T>: Garantiert, dass alle Elemente in einem einzigen, kontinuierlichen Speicherbereich im Heap liegen. Greifen Sie auf vec[0] zu, lädt die CPU die gesamte Cache-Line (die je nach Elementgröße auch vec[1], vec[2] etc. enthält). Der Zugriff auf die Folgeelemente ist somit ein “Cache-Hit” (L1/L2-Zugriff) und geschieht nahezu verzögerungsfrei.
• LinkedList<T>: Jedes Element (Knoten) wird einzeln auf dem Heap allokiert. Diese Knoten können kreuz und quer im RAM verstreut sein. Jeder Schritt zum nächsten Element (node.next) erfordert das Verfolgen eines Zeigers auf eine neue, unvorhersehbare Speicheradresse. Dies führt fast immer zu einem Cache-Miss, wodurch die CPU untätig auf den RAM warten muss. Nutzen Sie LinkedList in Rust daher fast nie.

Die wichtigsten Standard-Collections im Vergleich:

3. Compilerfehler verstehen & reparieren

Ein häufiger Fehler bei Einsteigern beim Umgang mit sequentiellen Collections ist der Versuch, Elemente über einen Index direkt zu konsumieren (Ownership zu verschieben), während die Collection noch die Ownership hält.

Fehlerhafter Code:

struct Benutzer {
    name: String,
    aktiv: bool,
}

fn verarbeite_ersten_benutzer(benutzer_liste: Vec<Benutzer>) {
    // FEHLER: Wir versuchen, die Ownership aus dem Vektor herauszubewegen!
    let erster = benutzer_liste[0]; 
    println!("Verarbeite: {}", erster.name);
}

fn main() {
    let liste = vec![
        Benutzer { name: String::from("Anna"), aktiv: true },
        Benutzer { name: String::from("Ben"), aktiv: false },
    ];
    verarbeite_ersten_benutzer(liste);
}

Compiler-Fehlermeldung:

error[E0507]: cannot move out of index of `Vec<Benutzer>`
  --> src/main.rs:8:19
   |
8  |     let erster = benutzer_liste[0]; 
   |                  ^^^^^^^^^^^^^^^^^
   |                  |
   |                  move occurs because value has type `Benutzer`, which does not implement the `Copy` trait
   |                  help: consider borrowing here: `&benutzer_liste[0]`

Warum lehnt der Compiler das ab?

Der Vektor benutzer_liste besitzt seine Elemente. Wenn wir let erster = benutzer_liste[0] schreiben, versuchen wir, das Element an Index 0 aus dem Vektor herauszubewegen. Das würde den Vektor in einem ungültigen Zustand hinterlassen, da Rust verlangt, dass alle Plätze in einem Vektor mit gültigen Werten belegt sind. Da Benutzer einen String enthält, implementiert es nicht das Copy-Trait.

Die Reparatur:

Wir haben drei Möglichkeiten, je nachdem, was wir architektonisch erreichen wollen:

1. Ausleihen (Borrowing), wenn wir die Liste danach noch verwenden wollen: let erster = &benutzer_liste[0];
2. Entfernen (Entnehmen der Ownership), wenn wir das Element aus der Liste löschen wollen: let erster = benutzer_liste.remove(0); (Achtung: Verschiebt alle nachfolgenden Elemente, $O(n)$!).
3. Austauschen (Inplace Swap) für $O(1)$ Entnahme, wenn die Reihenfolge egal ist: let erster = benutzer_liste.swap_remove(0); (Ersetzt das erste Element mit dem letzten und gibt das erste zurück).

4. Vollständiges, kompilierbares Praxisbeispiel: Job-Queue mit VecDeque

Das folgende Beispiel demonstriert eine effiziente Implementierung einer Job-Warteschlange (FIFO). Wir nutzen VecDeque, um das ineffiziente Verschieben von Elementen zu vermeiden, das bei einem normalen Vec beim Entfernen am Anfang auftreten würde.

use std::collections::VecDeque;

#[derive(Debug)]
struct Job {
    id: u64,
    beschreibung: String,
}

struct JobQueue {
    jobs: VecDeque<Job>,
}

impl JobQueue {
    fn new() -> Self {
        JobQueue {
            jobs: VecDeque::new(),
        }
    }

    // Einen neuen Job hinten anfügen - O(1)
    fn job_hinzufuegen(&mut self, job: Job) {
        self.jobs.push_back(job);
    }

    // Den ältesten Job vorne entnehmen - O(1)
    fn naechsten_job_holen(&mut self) -> Option<Job> {
        self.jobs.pop_front()
    }

    fn verbleibende_jobs(&self) -> usize {
        self.jobs.len()
    }
}

fn main() {
    let mut warteschlange = JobQueue::new();

    // Jobs einreihen
    warteschlange.job_hinzufuegen(Job {
        id: 1,
        beschreibung: String::from("Datenbank-Backup erstellen"),
    });
    warteschlange.job_hinzufuegen(Job {
        id: 2,
        beschreibung: String::from("Cache leeren"),
    });

    println!("Warteschlange enthält {} Jobs.", warteschlange.verbleibende_jobs());

    // Jobs abarbeiten
    while let Some(job) = warteschlange.naechsten_job_holen() {
        println!("Verarbeite Job {}: {}", job.id, job.beschreibung);
    }

    println!("Warteschlange leer. Verbleibend: {}", warteschlange.verbleibende_jobs());
}

Item 12: Nutze die Entry-API zur Eliminierung redundanter Map-Lookups

Wenn Sie mit einer HashMap oder BTreeMap arbeiten, müssen Sie häufig prüfen, ob ein Schlüssel bereits existiert, um den Wert entweder zu aktualisieren oder einen neuen Standardwert einzufügen. Ein naiver Ansatz führt zu doppelten Suchoperationen im Baum oder in der Hash-Tabelle. Die Entry-API löst dieses Problem auf elegante und hocheffiziente Weise.

1. Didaktische Alltagsanalogie: Der Postbote und das Paketfach

Stell dir vor, ein Postbote möchte ein Paket in ein elektronisches Schließfach legen.

• Ohne Entry-API (Der umständliche Weg):
  1. Der Postbote geht zum Schließfach 42 und schaut nach, ob es belegt ist (1. Lookup).
  2. Er sieht: Das Schließfach ist leer.
  3. Er läuft zurück zu seinem Lieferwagen (Rückgabe der Kontrolle an den aufrufenden Code).
  4. Er holt das Paket, läuft wieder zu Schließfach 42, tippt die Nummer erneut ein, öffnet es und legt das Paket hinein (2. Lookup). Dieser doppelte Weg kostet unnötig viel Zeit.
• Mit Entry-API (Der effiziente Weg):
  1. Der Postbote geht direkt zu Schließfach 42 (Einziger Lookup).
  2. Er öffnet die Tür. Ist das Fach leer (Vacant), legt er das Paket hinein. Ist es belegt (Occupied), klebt er einen Hinweiszettel auf das vorhandene Paket. Er muss den Weg kein zweites Mal laufen.

2. Theorie & Konzepte: Das Entry-Enum

Die Methode map.entry(key) gibt ein Enum namens std::collections::hash_map::Entry zurück. Dieses repräsentiert eine Stelle in der Map, die entweder belegt oder frei ist:

#![allow(unused)]
fn main() {
pub enum Entry<'a, K: 'a, V: 'a> {
    Occupied(OccupiedEntry<'a, K, V>),
    Vacant(VacantEntry<'a, K, V>),
}
}

Da die Methode entry eine exklusive Referenz (&mut) auf die Map benötigt, sichert sie den Speicherplatz intern ab. Der Compiler weiß nach dem Aufruf von entry genau, an welcher Speicheradresse der Schlüssel liegt. Wenn wir nun eine Modifikation vornehmen, muss die Map nicht erneut nach dem Schlüssel suchen.

Die wichtigsten Methoden auf Entry:

• .or_insert(default): Fügt den Standardwert ein, falls der Eintrag leer ist, und gibt eine veränderbare Referenz (&mut V) auf den Wert zurück.
• .or_insert_with(|| default): Wie or_insert, wertet den Standardwert aber träge (lazy) über ein Closure aus. Perfekt, wenn die Erstellung des Standardwerts teuer ist (z.B. bei Heap-Allokationen).
• .and_modify(|val| *val += 1): Erlaubt das direkte Modifizieren des Werts, falls der Eintrag existiert.

3. Code-Vergleich: Wortzähler (Naiv vs. Entry-API)

Der naive (ineffiziente) Ansatz:

#![allow(unused)]
fn main() {
use std::collections::HashMap;

fn wort_zaehler_naiv(text: &str) -> HashMap<&str, usize> {
    let mut stats = HashMap::new();

    for wort in text.split_whitespace() {
        // 1. Lookup: contains_key berechnet den Hash und sucht das Bucket
        if stats.contains_key(wort) {
            // 2. Lookup: get_mut berechnet den Hash erneut und sucht das Bucket
            if let Some(counter) = stats.get_mut(wort) {
                *counter += 1;
            }
        } else {
            // 2. Lookup: insert berechnet den Hash erneut und sucht das Bucket
            stats.insert(wort, 1);
        }
    }
    stats
}
}

Problem: Für jedes Wort in einem Text führen wir mindestens zwei vollständige Suchoperationen in der Hash-Tabelle durch. Bei großen Maps und langen Keys (wie Strings) führt das zu spürbaren Performance-Einbußen.

Der professionelle (idiomatische) Ansatz mit Entry-API:

#![allow(unused)]
fn main() {
use std::collections::HashMap;

fn wort_zaehler_entry(text: &str) -> HashMap<&str, usize> {
    let mut stats = HashMap::new();

    for wort in text.split_whitespace() {
        // Ein einziger Lookup!
        // or_insert gibt eine veränderbare Referenz &mut usize auf den Wert zurück.
        // Diese dereferenzieren wir mit '*', um den Wert zu erhöhen.
        *stats.entry(wort).or_insert(0) += 1;
    }
    stats
}
}

Erklärung: stats.entry(wort) sucht das Wort genau einmal in der Map. Ist das Wort nicht vorhanden, wird 0 eingefügt. In beiden Fällen erhalten wir ein &mut usize auf den Zähler im Speicher, den wir über den Dereferenzierungs-Operator * direkt im Speicher inkrementieren können. Das ist nicht nur kürzer, sondern auch maximal effizient.

Item 13: Eigene Typen als Map-Schlüssel: Implementierung von Hash, Eq und PartialEq

Um einen eigenen Typen als Schlüssel (Key) in einer HashMap zu verwenden, verlangt Rust, dass der Typ drei Traits implementiert: PartialEq, Eq und Hash. Während dies meist einfach über #[derive(PartialEq, Eq, Hash)] gelöst werden kann, erfordern komplexere Architekturen oft eine manuelle Implementierung dieser Schnittstellen.

1. Didaktische Alltagsanalogie: Das Aktenarchiv nach PLZ und Nachnamen

Stell dir vor, du sortierst Kundenakten in einem großen Hängeregister.

1. Der Hashwert (Der Postleitzahlen-Karton): Du nimmst die Adresse des Kunden und berechnest eine Kennzahl – zum Beispiel die Postleitzahl. Du legst die Akte in den Karton für diese PLZ. Das ist die Hash-Funktion. Sie sagt dir grob, in welchem “Eimer” (Bucket) die Akte liegt.
2. Die Gleichheit (Der Ausweisabgleich): Wenn du nach einem Kunden suchst, gehst du direkt zum Karton für seine PLZ (Hash-Lookup). Im Karton liegen aber 50 verschiedene Akten. Jetzt nimmst du jede Akte in die Hand und vergleichst den exakten Vor- und Nachnamen mit deinem Suchauftrag. Das ist die Gleichheitsprüfung (Eq).

Die goldene Regel der Konsistenz: Zwei Akten von Personen, die laut Ausweis absolut identisch sind (Eq), müssen zwingend dieselbe PLZ aufweisen (denselben Hashwert haben). Wenn Person A und Person B identisch sind, aber du A in den Karton 10000 und B in den Karton 20000 legst, wirst du Person B niemals finden, wenn du im Karton 10000 suchst.

2. Theorie & Konzepte: Das Zusammenspiel der Traits

• PartialEq<Rhs>: Definiert die partielle Äquivalenzrelation. Sie erfordert Symmetrie (wenn a == b, dann b == a) und Transitivität (wenn a == b und b == c, dann a == c).
• Eq: Ein reines Marker-Trait, das die mathematische Reflexivität zusichert (a == a muss immer wahr sein). Gleitkommazahlen (f32/f64) implementieren beispielsweise PartialEq, aber nicht Eq, da in der IEEE-754 Spezifikation definiert ist, dass NaN != NaN (Not a Number) gilt.
• Hash: Nimmt eine Instanz eines Hasher-Typs entgegen und speist die relevanten Daten des Structs in diesen ein.

Kritische Entwickler-Regel:

Important

Wenn Sie PartialEq manuell implementieren, müssen Sie auch Hash manuell implementieren. Es muss ausnahmslos gelten: if a == b { hash(a) == hash(b) } Ist diese Bedingung verletzt, verhält sich die HashMap fehlerhaft (Elemente können trotz Vorhandenseins nicht gefunden werden).

3. Compilerfehler verstehen & reparieren

Versuchen wir, ein Struct ohne diese Traits als Schlüssel zu verwenden, blockiert uns der Compiler sofort schützend.

Fehlerhafter Code:

use std::collections::HashMap;

struct BenutzerId {
    abteilung: String,
    personal_nummer: u32,
}

fn main() {
    let mut daten = HashMap::new();
    let key = BenutzerId {
        abteilung: String::from("IT"),
        personal_nummer: 1024,
    };
    
    // FEHLER: BenutzerId erfüllt die Anforderungen für Keys nicht!
    daten.insert(key, String::from("Thorsten"));
}

Compiler-Fehlermeldung:

error[E0277]: the trait bound `BenutzerId: Eq` is not satisfied
   --> src/main.rs:15:18
    |
15  |     daten.insert(key, String::from("Thorsten"));
    |           ------ ^^^ the trait `Eq` is not implemented for `BenutzerId`
    |           |
    |           required by a bound introduced by this call

Der Compiler fordert uns auf, Eq (und implizit Hash und PartialEq) zu implementieren.

4. Vollständiges, kompilierbares Praxisbeispiel (Manuelle Implementierung)

Wir implementieren nun einen Schlüssel ProjektSchluessel, bei dem wir die Gleichheit und das Hashing manuell definieren. Im echten Leben könnte das nötig sein, wenn wir beim Vergleich der Abteilung Groß- und Kleinschreibung ignorieren wollen (Case-Insensitivity).

use std::collections::HashMap;
use std::hash::{Hash, Hasher};

#[derive(Debug)]
struct ProjektSchluessel {
    abteilung: String,
    projekt_id: u32,
}

// Manuelle Implementierung von PartialEq: Case-Insensitiver Vergleich für abteilung
impl PartialEq for ProjektSchluessel {
    fn eq(&self, other: &Self) -> bool {
        self.projekt_id == other.projekt_id
            && self.abteilung.to_lowercase() == other.abteilung.to_lowercase()
    }
}

// Eq zusichern, da unsere eq-Implementierung reflexiv ist
impl Eq for ProjektSchluessel {}

// Manuelle Implementierung von Hash: 
// WICHTIG: Da wir in eq() die Abteilung zu Kleinbuchstaben konvertieren, 
// müssen wir das auch im Hasher tun, um die Konsistenz zu wahren!
impl Hash for ProjektSchluessel {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.projekt_id.hash(state);
        self.abteilung.to_lowercase().hash(state);
    }
}

fn main() {
    let mut projekte = HashMap::new();

    let key1 = ProjektSchluessel {
        abteilung: String::from("Marketing"),
        projekt_id: 42,
    };

    let key2 = ProjektSchluessel {
        abteilung: String::from("marketing"), // Unterschiedliche Schreibweise
        projekt_id: 42,
    };

    projekte.insert(key1, "Kampagne Sommer 2026");

    // Da key1 == key2 (dank case-insentivem PartialEq und konsistentem Hash),
    // liefert das Auslesen mit key2 den Wert von key1!
    if let Some(projektname) = projekte.get(&key2) {
        println!("Projekt gefunden: {}", projektname);
    } else {
        println!("Projekt wurde nicht gefunden!");
    }
}

Item 14: Optimiere Hashing-Performance mit nicht-kryptografischen Hashern

Standardmäßig verwendet Rusts HashMap einen Hashing-Algorithmus namens SipHash 1-3. Dieser Algorithmus wurde gezielt gewählt, weil er hochgradig resistent gegen sogenannte Hash-Flooding-DDoS-Angriffe (Denial of Service) ist. Für Webserver, die unbereinigte Benutzereingaben als Schlüssel in einer Map speichern, ist dies überlebenswichtig. In geschlossenen Systemen jedoch bremst SipHash die CPU unnötig aus.

1. Didaktische Alltagsanalogie: Das Panzerschloss am Küchenschrank

Stell dir vor, du möchtest deine Gewürze in der Küche sortieren.

• SipHash (Das Panzerschloss): Jedes Mal, wenn du Salz aus dem Schrank nehmen willst, musst du ein 10-stelliges Zahlenschloss an der Schranktür öffnen. Das Schloss ist absolut sicher gegen Profi-Einbrecher. Für deine Küche ist es jedoch massiver Overhead und bremst das Kochen extrem aus.
• FxHash / FnvHash (Der Magnetschnapper): Ein einfacher Magnetverschluss hält die Schranktür zu. Jeder kann sie mit einem leichten Ruck in Millisekunden öffnen. In deiner privaten Wohnung (ein geschlossenes System ohne bösartige Angreifer von außen) ist das die perfekte Wahl, weil es maximal schnell ist.

2. Theorie & Konzepte: DDoS-Sicherheit vs. Rohgeschwindigkeit

• Hash-Flooding: Wenn ein Angreifer weiß, dass eine HashMap einen simplen, deterministischen Hashing-Algorithmus nutzt, kann er tausende Schlüssel generieren, die alle exakt denselben Hashwert erzeugen. Dies führt in der Map zu maximalen Kollisionen, wodurch die Zugriffszeit von $O(1)$ auf $O(n)$ ansteigt. Die CPU-Last steigt auf 100 %, und der Server stürzt ab. SipHash verhindert dies durch die Verwendung eines kryptografisch sicheren Schlüssels, der bei jedem Programmstart zufällig generiert wird.
• Nicht-kryptografische Hasher: Algorithmen wie FNV-1a oder FxHash (welches intern im Rust-Compiler rustc genutzt wird) verzichten auf diese mathematischen Schutzbarrieren. Sie bestehen oft nur aus einer Handvoll einfacher CPU-Instruktionen (Multiplikation und XOR). Für interne Caches, Spiele, Compiler oder Datenanalyse-Tools sind sie der Schlüssel zu massiven Geschwindigkeitsvorteilen (oft 2- bis 5-mal schneller als SipHash).

3. Implementierung eines eigenen FNV-1a Hashers in Rust

Um zu verstehen, wie Hasher in Rust auf Systemebene integriert werden, implementieren wir einen eigenen FNV-1a (Fowler-Noll-Vo) Hasher für 64-Bit-Ganzzahlen komplett selbst. So vermeiden wir externe Abhängigkeiten und verstehen die Hasher- und BuildHasher-Traits der Standardbibliothek im Detail.

use std::collections::HashMap;
use std::hash::{BuildHasher, Hasher};

// 1. Der Hasher-Typ: Hält den aktuellen Hash-Zustand
struct Fnv64Hasher {
    state: u64,
}

impl Fnv64Hasher {
    // FNV-1a Konstanten für 64-Bit
    const FNV_PRIME: u64 = 0x00000100000001B3;
    const FNV_OFFSET_BASIS: u64 = 0xcbf29ce484222325;

    fn new() -> Self {
        Fnv64Hasher {
            state: Self::FNV_OFFSET_BASIS,
        }
    }
}

// Implementierung des Hasher-Traits: Beschreibt, wie Bytes verarbeitet werden
impl Hasher for Fnv64Hasher {
    // Gibt das Endergebnis des Hashings zurück
    fn finish(&self) -> u64 {
        self.state
    }

    // Kernmethode: Verarbeitet einen rohen Byte-Slice
    fn write(&mut self, bytes: &[u8]) {
        for &byte in bytes {
            // FNV-1a Algorithmus: Erst XOR, dann Multiplikation
            self.state ^= byte as u64;
            self.state = self.state.wrapping_mul(Self::FNV_PRIME);
        }
    }
}

// 2. Der BuildHasher-Typ: Erzeugt Instanzen unseres Hashers.
// Dies ist notwendig, da die HashMap für jede Operation einen frischen Hasher benötigt.
#[derive(Default)]
struct BuildFnvHasher;

impl BuildHasher for BuildFnvHasher {
    type Hasher = Fnv64Hasher;

    fn build_hasher(&self) -> Self::Hasher {
        Fnv64Hasher::new()
    }
}

fn main() {
    // 3. Einbinden in die HashMap über den dritten Typparameter.
    // Standardmäßig ist dies `RandomState` (SipHash). Wir setzen unseren `BuildFnvHasher` ein.
    let mut schnelle_map: HashMap<u32, String, BuildFnvHasher> = 
        HashMap::with_hasher(BuildFnvHasher);

    schnelle_map.insert(1, String::from("Hochleistungs-Daten"));
    schnelle_map.insert(2, String::from("Optimierter Speicher"));

    if let Some(wert) = schnelle_map.get(&1) {
        println!("Wert gelesen: {}", wert);
    }
}

Item 15: Heterogene Datensammlungen: Enums vs. Trait-Objekte

Rust-Collections wie Vec\<T\> sind homogen – sie können nur Elemente eines einzigen Typs T aufnehmen. In der Praxis benötigt man jedoch oft Sammlungen unterschiedlicher Typen (heterogene Collections), beispielsweise eine Liste von UI-Elementen (Buttons, Textfelder, Bilder). Rust bietet hierfür zwei grundlegende Lösungswege mit unterschiedlichen Trade-offs: Statische Polymorphie über Enums und Dynamische Polymorphie über Trait-Objekte.

1. Didaktische Alltagsanalogie: Der geformte Besteckkasten vs. Die Werkzeugtasche

• Das Enum – Der Besteckkasten (Statisch): Ein Besteckkasten hat vordefinierte Aussparungen für Messer, Gabeln und Löffel. Sie wissen im Voraus genau, welche drei Arten von Besteck es geben kann. Es passt kein Schraubenzieher hinein. Der Zugriff ist extrem schnell: Sie greifen blind in das Fach und haben sofort das richtige Besteckteil in der Hand. Der Speicherplatz ist starr, passt sich aber dem größten Besteckteil an.
• Das Trait-Objekt – Die Werkzeugtasche (Dynamisch): Eine Tasche, in die Sie alles hineinwerfen können, was das Label “Werkzeug” (das Trait) trägt. Sie können heute einen Hammer hineintun und morgen eine Bohrmaschine, die bei der Herstellung der Tasche noch gar nicht erfunden war. Wenn Sie jedoch hineingreifen, wissen Sie nicht blind, wie schwer oder groß das Werkzeug ist. Sie müssen es herausholen und die Bedienungsanleitung (Virtuelle Methodentabelle / vtable) lesen, um zu wissen, wie man es benutzt. Das ist flexibler, aber durch das Nachschlagen langsamer.

2. Theorie & Konzepte: Statische vs. Dynamische Polymorphie

Variante A: Statische Polymorphie (Enums)

• Funktionsweise: Alle möglichen Typen werden als Varianten in einem einzigen Enum gekapselt.
• Speicherlayout: Die Größe des Enums im Speicher entspricht der Größe seiner größten Variante plus einem kleinen Tag (Discriminant, meist 1 Byte), das angibt, welche Variante gerade aktiv ist.
• Vorteile:
  • Kein Speicherzugriff über Zeiger (keine Indirektion).
  • Exzellente CPU-Cache-Lokalität: Alle Elemente liegen direkt hintereinander im kontinuierlichen Speicher des Vektors.
  • Der Compiler kann den Code vollständig inlinen und optimieren (kein Laufzeit-Overhead).
• Nachteile:
  • Unflexibel: Das Enum ist geschlossen. Möchte eine externe Bibliothek einen neuen Typ hinzufügen, muss das Enum im Quellcode geändert werden.
  • Speicherverschwendung, wenn eine Variante extrem groß und alle anderen winzig sind, da jedes Element die Größe der größten Variante beansprucht.

Variante B: Dynamische Polymorphie (Trait-Objekte)

• Funktionsweise: Die Elemente implementieren ein gemeinsames Trait. Im Vektor speichern wir Zeiger auf diese Elemente, verpackt in Box<dyn Trait> oder &dyn Trait.
• Speicherlayout: Ein Trait-Objekt ist ein Fat Pointer. Er besteht aus zwei Zeigern: Einem Zeiger auf die eigentlichen Daten im Heap und einem Zeiger auf die vtable (virtuelle Methodentabelle), die die Funktionszeiger der konkreten Implementierung enthält.
• Vorteile:
  • Offenes System: Jeder beliebige Typ (auch aus Drittanbieter-Crates) kann in die Collection eingefügt werden, solange er das Trait implementiert.
  • Speichereffizient im Vektor selbst, da dort nur Zeiger gleicher Größe liegen.
• Nachteile:
  • Heap-Allokation pro Element erforderlich (Box).
  • Schlechte Cache-Lokalität durch Pointer-Chasing.
  • Dynamic Dispatch: Bei jedem Methodenaufruf muss die CPU über die vtable nachschlagen, welche Funktion aufgerufen werden soll. Dies verhindert Inlining und erschwert CPU-Branch-Prediction-Optimierungen.

3. Vollständiges, kompilierbares Praxisbeispiel: GUI-Rendering

Das folgende Beispiel zeigt beide Ansätze zur Speicherung einer Liste von GUI-Komponenten.

// Das Trait, das die gemeinsame Funktionalität definiert
trait Renderable {
    fn zeichnen(&self);
}

// Konkrete GUI-Komponente A
struct Button {
    text: String,
}

impl Renderable for Button {
    fn zeichnen(&self) {
        println!("[Button] Zeichne mit Text: {}", self.text);
    }
}

// Konkrete GUI-Komponente B
struct TextFeld {
    inhalt: String,
    breite: u32,
}

impl Renderable for TextFeld {
    fn zeichnen(&self) {
        println!("[TextFeld] Breite: {}, Inhalt: {}", self.breite, self.inhalt);
    }
}

// =========================================================================
// ANSATZ 1: Statische Polymorphie via Enum (Geschlossenes System, schnell)
// =========================================================================
enum GuiKomponenteEnum {
    Knopf(Button),
    Eingabe(TextFeld),
}

// Wir implementieren Renderable für das Enum, um das Zeichnen zu delegieren
impl Renderable for GuiKomponenteEnum {
    fn zeichnen(&self) {
        match self {
            GuiKomponenteEnum::Knopf(btn) => btn.zeichnen(),
            GuiKomponenteEnum::Eingabe(tf) => tf.zeichnen(),
        }
    }
}

// =========================================================================
// HIER FÜHREN WIR BEIDE ANSÄTZE ZUSAMMEN
// =========================================================================
fn main() {
    // --- Test von Ansatz 1 (Enum) ---
    // Speicherlayout: Ein kontinuierliches Array im Heap.
    // Keine Zeiger-Indirektionen beim Iterieren. Maximal performant.
    println!("--- Ansatz 1: Statische Polymorphie (Enum) ---");
    let mut enum_liste: Vec<GuiKomponenteEnum> = Vec::new();
    
    enum_liste.push(GuiKomponenteEnum::Knopf(Button {
        text: String::from("Senden"),
    }));
    enum_liste.push(GuiKomponenteEnum::Eingabe(TextFeld {
        inhalt: String::from("Thorsten"),
        breite: 250,
    }));

    for komponente in &enum_liste {
        // Aufruf über statischen Dispatch (wird vom Compiler optimiert)
        komponente.zeichnen();
    }

    // --- Test von Ansatz 2 (Trait-Objekt) ---
    // Speicherlayout: Ein Vektor von Fat Pointern im Heap.
    // Jedes Element liegt an einer anderen Heap-Stelle.
    println!("\n--- Ansatz 2: Dynamische Polymorphie (Trait-Objekt) ---");
    let mut trait_liste: Vec<Box<dyn Renderable>> = Vec::new();

    trait_liste.push(Box::new(Button {
        text: String::from("Abbrechen"),
    }));
    trait_liste.push(Box::new(TextFeld {
        inhalt: String::from("Suche..."),
        breite: 150,
    }));

    for komponente in &trait_liste {
        // Aufruf über Dynamic Dispatch (Nachschlagen in der vtable zur Laufzeit)
        komponente.zeichnen();
    }
}

Zusammenfassung für die Praxis:

• Wählen Sie Enums, wenn Sie die Menge der Typen kontrollieren können und die maximale Performance auf CPU-Ebene benötigen (Spiele, Parser, mathematische Berechnungen).
• Wählen Sie Trait-Objekte, wenn Sie ein Plugin-System bauen, bei dem andere Entwickler eigene Typen hinzufügen sollen, oder wenn die Größenunterschiede der Typen so groß sind, dass ein Enum zu viel Speicher verschwenden würde.