6.4 Unter der Haube: Collections auf Hardware- und Systemebene

Willkommen im Maschinenraum! In den vorherigen Abschnitten haben wir gelernt, wie wir Vektoren, Slices und HashMaps in unseren Rust-Programmen nutzen. Für Anwendungsentwickler reicht dieses Wissen meist völlig aus. Doch du bist hier, weil du wissen willst, was wirklich unter der Haube passiert. Du willst wissen, wie sich die Elektronen im RAM bewegen, warum manche Operationen deine CPU zum Schnurren bringen, während andere sie in eine gähnende Warteschleife schicken.

In diesem Abschnitt legen wir die Abstraktionen beiseite. Wir nehmen das Skalpell und sezieren das Speicherlayout unserer Datenstrukturen auf Byte-Ebene. Wir schauen uns an, wie moderne CPUs mit Speicher interagieren und warum die Wahl der richtigen Collection den Unterschied zwischen einer trägen Schnecke und einer Rakete ausmachen kann.

1. Arrays: Die Formel 1 des Direktzugriffs

Fangen wir mit der fundamentalsten aller Collections an: dem Array (z. B. [T; N]). Arrays sind die reinsten und direktesten Datenstrukturen überhaupt. Sie spiegeln eins zu eins wider, wie physikalischer Arbeitsspeicher strukturiert ist.

Die Alltagsanalogie: Der Apothekerschrank

Stell dir einen Apothekerschrank mit 10 nebeneinander liegenden Schubladen vor. Jede Schublade ist exakt gleich breit – sagen wir 10 Zentimeter. Wenn du die 5. Schublade öffnen willst, musst du nicht bei Schublade 0 anfangen und dich mühsam vorwärtstasten. Da du weißt, dass jede Schublade 10 Zentimeter breit ist und der Schrank an einer festen Wand beginnt, kannst du im Bruchteil einer Sekunde ausrechnen, wo sich der Griff der 5. Schublade befindet: $5 \times 10\text{ cm} = 50\text{ cm}$ von der Wand entfernt. Du greifst direkt dorthin. Das ist der Direktzugriff.

Das Speicherlayout im Detail

In Rust hat ein Array [T; N] eine feste Länge N, die bereits zur Kompilierzeit feststehen muss. Das erlaubt es dem Compiler, das Array komplett auf dem Stack (oder als Teil einer größeren Struktur auf dem Heap) anzulegen. Die Elemente liegen lückenlos und fortlaufend hintereinander im Speicher.

Nehmen wir ein einfaches Array von fünf 32-Bit-Ganzzahlen (i32):

#![allow(unused)]
fn main() {
let zahlen: [i32; 5] = [10, 20, 30, 40, 50];
}

Da ein i32 genau 4 Bytes belegt, sieht das Layout im Speicher so aus:

Adresse:    0x1000      0x1004      0x1008      0x100C      0x1010
            +-----------+-----------+-----------+-----------+-----------+
Inhalt:     |    10     |    20     |    30     |    40     |    50     |
            +-----------+-----------+-----------+-----------+-----------+
Index:            0           1           2           3           4
Größe:      |< 4 Bytes >|< 4 Bytes >|< 4 Bytes >|< 4 Bytes >|< 4 Bytes >|

Der O(1)-Zugriff auf CPU-Ebene: Die Adressberechnung

Warum sagen Informatiker stolz, dass der Zugriff auf ein Array-Element eine $O(1)$-Operation ist – also unabhängig von der Größe des Arrays immer gleich schnell is? Weil die CPU die genaue Speicheradresse des gewünschten Elements mit einer einzigen mathematischen Formel berechnen kann:

$$\text{Adresse}(i) = \text{Basisadresse} + i \times \text{Größe eines Elements}$$

• Basisadresse: Der Startpunkt des Arrays im Speicher (im obigen Beispiel 0x1000).
• $i$: Der gewünschte Index (z. B. 3).
• Größe eines Elements: Die Bytegröße des Typs T (im Fall von i32 also 4).

Für Index 3 rechnet die CPU: $$\text{Adresse}(3) = 0\text{x}1000 + 3 \times 4 = 0\text{x}1000 + 12 = 0\text{x}100\text{C}$$

Moderne CPUs (wie die x86_64-Architektur) sind für genau diese Berechnung im Silizium optimiert. Sie verfügen über spezielle Adressierungsmodi, die diese Multiplikation und Addition in einem einzigen Taktzyklus direkt im Befehlsdecoder ausführen. Ein Assembler-Befehl wie:

mov eax, [rbx + rcx * 4]

bedeutet: “Lade den Wert aus der Adresse Basisadresse (in rbx) + Index (in rcx) * Elementgröße (4) in das Register eax”. Schneller geht es physikalisch nicht.

Compiler-Sicherheitsnetz vs. nackte Hardware

In Sprachen wie C oder C++ wird bei dieser Adressberechnung blind vertraut. Wenn du dort auf Index 10 eines 5-Element-Arrays zugreifst, rechnet die CPU stur weiter, liest Speicher außerhalb des Arrays und dein Programm stürzt entweder mit einem Segfault ab oder – noch schlimmer – liest geheime Daten.

Rust schützt dich davor. Bei jedem Indexzugriff (z. B. zahlen[i]) fügt Rust zur Laufzeit einen kleinen Check ein (Bounds Check):

#![allow(unused)]
fn main() {
if i >= zahlen.len() {
    panic!("index out of bounds: the len is {} but the index is {}", zahlen.len(), i);
}
}

Dieser Check kostet minimale Performance, rettet dich aber vor schwerwiegenden Sicherheitslücken. Wenn der Compiler jedoch zur Kompilierzeit beweisen kann (z. B. in einer for-Schleife über die Range 0..5), dass der Index niemals außerhalb liegt, optimiert er diesen Check komplett weg!

2. Vec\<T\>: Der dynamische Vektor im Detail

Ein normales Array ist wunderbar, aber unelastisch. Was ist, wenn wir erst zur Laufzeit wissen, wie viele Elemente wir speichern müssen? Hier kommt der Vektor (Vec\<T\>) ins Spiel. Ein Vektor ist im Grunde ein dynamisch wachsendes Array, das seine Zelte auf dem Heap aufschlägt.

Die Alltagsanalogie: Der Koffer mit Anhänger

Stell dir vor, du gehst auf Reisen. Du hast einen Gepäckanhänger (den Stack), den du fest in der Hand hältst. Auf diesem Anhänger stehen drei wichtige Dinge:

1. Eine Adresse, wo dein eigentlicher Koffer im Frachtraum des Flugzeugs liegt.
2. Die maximale Größe (Kapazität) des Koffers (wie viele T-Shirts reinpassen).
3. Die aktuelle Anzahl an T-Shirts, die du bereits eingepackt hast.

Der eigentliche Koffer (mit den T-Shirts) reist im Frachtraum (dem Heap) und kann bei Bedarf gegen einen größeren Koffer ausgetauscht werden.

Das Speicherlayout von Vec\<T\>

Ein Vec\<T\> besteht aus zwei Teilen: einem festen Kontrollblock auf dem Stack und den eigentlichen Daten auf dem Heap.

Der Stack-Teil eines Vektors hat auf einer 64-Bit-CPU eine feste Größe von 24 Bytes (3 Feldern à 8 Bytes bzw. 1 “Word”):

1. Pointer (8 Bytes): Die Speicheradresse, die auf den Beginn des allokierten Heap-Speicherbereichs zeigt.
2. Capacity (8 Bytes): Die Anzahl der Elemente, die der aktuelle Heap-Speicherbereich maximal aufnehmen kann, ohne dass neuer Speicher angefordert werden muss.
3. Length (8 Bytes): Die Anzahl der Elemente, die sich aktuell tatsächlich im Vektor befinden.

STACK (24 Bytes)                               HEAP
+------------------+-----------+-----------+   +-----------+-----------+-----------+---
| Pointer (8 Byte) | Cap (8 B) | Len (8 B) |-->| Element 0 | Element 1 | Element 2 |...
+------------------+-----------+-----------+   +-----------+-----------+-----------+---
  |                  |           |
  |                  |           +-- Aktuelle Anzahl (z.B. 2)
  |                  +-- Reservierter Platz (z.B. 4)
  +-- Zeigt auf Heap-Adresse

Egal, ob dein Vektor leer ist oder eine Million Elemente enthält: Auf dem Stack belegt er immer exakt 24 Bytes!

Let’s verify this with code. Hier ist ein vollständig kompilierbares Beispiel, das uns die genauen Byte-Größen zeigt:

use std::mem::size_of;

fn main() {
    // Wir erstellen einen Vektor mit Elementen
    let mut v: Vec<i32> = Vec::with_capacity(4);
    v.push(10);
    v.push(20);

    // 1. Größe auf dem Stack ermitteln
    let stack_groesse = size_of::<Vec<i32>>();
    println!("Größe des Vec-Kontrollblocks auf dem Stack: {} Bytes", stack_groesse);

    // 2. Zustand des Vektors abfragen
    let laenge = v.len();
    let kapazitaet = v.capacity();
    let heap_adresse = v.as_ptr(); // Holt den rohen Zeiger auf den Heap

    println!("Länge: {}, Kapazität: {}", laenge, kapazitaet);
    println!("Startadresse auf dem Heap: {:p}", heap_adresse);

    // Jedes Element ist ein i32 (4 Bytes). Bei Kapazität 4
    // belegt der Heap-Bereich also 4 * 4 = 16 Bytes.
}

3. Slices &[T]: Die schlanken Fat Pointer

Ein Slice &[T] (gesprochen: “Slice von T”) ist eine Referenz auf ein zusammenhängendes Stück Speicher. Es besitzt die Daten nicht selbst, sondern borgt sie sich nur aus. Ein Slice kann auf ein Array auf dem Stack zeigen, auf einen Teil eines Vektors auf dem Heap oder auf statische Daten im Programmbereich.

Die Alltagsanalogie: Der Lichtkegel

Stell dir eine Theaterbühne vor, auf der 20 Schauspieler nebeneinander stehen. Ein Vektor besitzt die gesamte Bühne. Ein Slice ist wie ein Scheinwerfer: Er beleuchtet nur einen bestimmten Ausschnitt (z. B. Schauspieler 5 bis 12). Der Scheinwerfer muss wissen:

1. Wo beginnt der Lichtkegel (Startadresse)?
2. Wie breit ist der Lichtkegel (Anzahl der beleuchteten Schauspieler)? Er muss nicht wissen, wie groß die gesamte Bühne ist oder wie viele Leute maximal draufpassen.

Das Speicherlayout: Der Fat Pointer (16 Bytes)

Während eine normale Referenz auf ein einzelnes Element (z. B. &i32) ein einfacher Zeiger von 8 Bytes ist, ist ein Slice-Zeiger ein sogenannter Fat Pointer (breiter Zeiger). Er belegt auf dem Stack exakt 16 Bytes:

1. Pointer (8 Bytes): Zeiger auf das erste Element des Slices.
2. Length (8 Bytes): Die Anzahl der Elemente, die zum Slice gehören.

Da der Slice die Daten nicht besitzt, braucht er kein Capacity-Feld. Es gibt nichts zu vergrößern.

STACK (16 Bytes Fat Pointer)                   HEAP / STACK (Datenquelle)
+------------------+------------------+        +-----+-----+-----+-----+-----+
| Pointer (8 Byte) | Length (8 Bytes) |------->| 10  | 20  | 30  | 40  | 50  |
+------------------+------------------+        +-----+-----+-----+-----+-----+
  |                  |                           ^           ^
  |                  +-- Länge des Slices (3)    |           |
  +-- Zeigt auf das Start-Element ---------------+-----------+

Das folgende kompilierbare Code-Beispiel demonstriert den Größenunterschied im Speicher:

use std::mem::size_of;

fn main() {
    let daten: [i32; 5] = [10, 20, 30, 40, 50];

    // Wir erstellen ein Slice auf die mittleren drei Elemente
    let slice: &[i32] = &daten[1..4]; // Enthält [20, 30, 40]

    println!("Größe eines normalen Zeigers (&i32): {} Bytes", size_of::<&i32>());
    println!("Größe des Slices (&[i32]) auf dem Stack: {} Bytes", size_of::<&[i32]>());

    println!("Slice-Länge: {}", slice.len());
    println!("Adresse des ersten Slice-Elements: {:p}", &slice[0]);
    println!("Adresse des ersten Original-Elements: {:p}", &daten[0]);
}

4. Die Anatomie der Heap-Reallokation bei Vektoren

Was passiert eigentlich, wenn wir in einen Vektor schreiben und dieser seine maximale Kapazität erreicht? Nehmen wir an, wir haben einen Vektor mit Kapazität 4 und Länge 4. Wir rufen nun ein weiteres Mal push() auf.

Das Problem

Der Vektor muss wachsen. Da der Heap-Speicher jedoch von vielen verschiedenen Programmteilen genutzt wird, können wir nicht einfach hoffen, dass der Speicherbereich direkt hinter unserem Vektor noch frei ist. Der Speicher allokiert dort vielleicht schon ein anderes Objekt. Wir können den Vektor also nicht einfach “nach hinten verlängern”.

Die Wachstumsstrategie (Capacity Doubling)

Rusts Standardbibliothek verdoppelt bei einer Reallokation in der Regel die bisherige Kapazität. Das hat mathematische Gründe: Durch die Verdopplung müssen wir immer seltener neuen Speicher anfordern, je größer der Vektor wird. Die Zeitkomplexität für das Einfügen bleibt dadurch im Schnitt (amortisiert) bei $O(1)$.

Der 3-Schritte-Tanz der CPU

Wenn die Kapazität erschöpft ist, führt die Laufzeitumgebung drei hardwareintensive Schritte aus:

Schritt 1: Neuen, doppelt so großen Speicherbereich auf dem Heap finden & allokieren.
Alt (Kapazität 4):  [ A | B | C | D ]
Neu (Kapazität 8):  [   |   |   |   |   |   |   |   ]

Schritt 2: Daten per schnellem CPU-Befehl (memcpy) kopieren.
Neu (Kapazität 8):  [ A | B | C | D |   |   |   |   ]

Schritt 3: Alten Speicherbereich freigeben und Pointer im Stack-Kontrollblock aktualisieren.

Die Gefahren dieses Prozesses

1. Speicher-Fragmentierung: Häufige Reallokationen hinterlassen “Löcher” im Heap, da alte, kleinere Speicherblöcke freigegeben werden, die der Allokator erst mühsam wieder an andere, passende Daten vergeben muss.
2. Performance-Einbruch (Latenz-Spitzen): Das Kopieren von Daten per memcpy ist zwar extrem schnell, da die CPU ganze Speicherblöcke über breite Datenbusse verschiebt. Dennoch kostet es Zeit. Wenn dein Vektor eine Million Elemente enthält, bremst eine Reallokation dein Programm spürbar aus.
3. Spitzen-Speicherbedarf: Während des Kopiervorgangs belegt dein Vektor kurzzeitig das Dreifache der Kapazität im RAM: Der alte Block, der neue Block und das Element, das du gerade hineinkopieren willst.

Die Rettung: Vec::with_capacity

Wenn du im Vorhinein weißt (oder gut schätzen kannst), wie viele Elemente in deinem Vektor landen werden, nutze immer Vec::with_capacity. Damit reservierst du den Speicher einmalig und verhinderst teure Reallokationen.

Hier ist ein Experiment, das die Reallokation live im Speicher sichtbar macht:

fn main() {
    let mut v = Vec::new();
    let mut letzte_adresse = std::ptr::null();

    for i in 0..10 {
        v.push(i);
        let aktuelle_adresse = v.as_ptr();

        // Wenn sich die Heap-Adresse ändert, gab es eine Reallokation!
        if aktuelle_adresse != letzte_adresse {
            println!(
                "Element {}: Reallokation! Kapazität: {} -> Heap-Adresse: {:p}",
                i,
                v.capacity(),
                aktuelle_adresse
            );
            letzte_adresse = aktuelle_adresse;
        }
    }
}

Wenn du dieses Programm ausführst, wirst du sehen, wie die Kapazität sprunghaft ansteigt ($0 \rightarrow 4 \rightarrow 8 \rightarrow 16$) und sich dabei jedes Mal die Hexadezimal-Adresse des Heap-Zeigers ändert.

5. CPU-Caching, Datenlokalität und Hardware Prefetching

Nun kommen wir zum absoluten Königsthema der Systemprogrammierung. Warum ist ein Vektor in der Praxis fast immer dramatisch schneller als eine verkettete Liste (LinkedList), obwohl beide theoretisch die gleichen Komplexitätsklassen für viele Operationen haben?

Die Antwort liegt nicht in der Software, sondern im Silizium deiner CPU: Datenlokalität und Caches.

Die Alltagsanalogie: Der Schreibtisch und das Außenlager

Stell dir vor, du bist ein Handwerker in einer Werkstatt:

• Die CPU-Register sind die Werkzeuge, die du direkt in deiner Hand hältst.
• Der L1/L2/L3-Cache ist deine Werkbank direkt vor dir. Hier liegen Werkzeuge griffbereit. Der Zugriff dauert 1 Sekunde.
• Der Hauptspeicher (RAM) ist ein Außenlager am anderen Ende der Stadt. Jedes Mal, wenn du ein Werkzeug von dort holen musst, musst du ins Auto steigen und hinfahren. Das dauert 2 Stunden.

Wenn du nun ein Projekt bearbeitest, bei dem du nacheinander 10 Schrauben eindrehen musst, schickt dich dein Lehrling (der Hardware Prefetcher) nicht für jede einzelne Schraube einzeln zum Außenlager. Wenn du nach der ersten Schraube greifst, fährt er zum Lager und bringt dir eine ganze Kiste mit 64 Schrauben mit (eine Cache Line). Da die Schrauben im Lager alle nebeneinander in einer Schachtel lagen, konnte er sie auf einmal mitnehmen.

Was ist Hardware Cache Line Prefetching?

Wenn die CPU Daten aus dem langsamen RAM anfordert, liest sie niemals nur das einzelne angeforderte Byte. Sie lädt immer einen zusammenhängenden Block von meist 64 Bytes (eine sogenannte Cache-Zeile oder Cache Line) in den schnellen L1-Cache.

Der Hardware Prefetcher ist eine spezialisierte Schaltung in der CPU. Er analysiert die Speicherzugriffsmuster deines Programms. Erkennt er, dass dein Programm sequenziell auf den Speicher zugreift (z. B. Adresse 0x1000, 0x1004, 0x1008…), lädt er die nächsten Cache-Zeilen bereits präventiv in den Cache, bevor dein Code den nächsten Befehl ausführt. Der Zugriff erfolgt dann direkt aus dem L1-Cache (ein sogenannter Cache Hit). Das dauert oft weniger als einen Taktzyklus!

Das Duell: Vec\<T\> vs. LinkedList\<T\>

Der Vektor: Der Traum der CPU

Da im Vektor alle Elemente lückenlos nebeneinander im Speicher liegen, ist er der beste Freund des Prefetchers.

Speicher:   [ Elem 0 ][ Elem 1 ][ Elem 2 ][ Elem 3 ][ Elem 4 ]
            |================== Cache Line 1 ==================|

Beim Zugriff auf Elem 0 lädt die CPU die gesamte Cache Line. Die Elemente 1 bis 3 landen gratis und ohne Verzögerung im L1-Cache. Der Prefetcher sieht den Trend und lädt bereits die nächste Cache Line für die Elemente 4 und folgende. Die CPU läuft unter Volldampf, ohne jemals auf den RAM warten zu müssen.

Die LinkedList: Der Albtraum der CPU

Eine verkettete Liste besteht aus einzelnen Knoten, die wild verstreut auf dem Heap liegen. Jeder Knoten enthält neben den Nutzdaten einen Zeiger auf die Adresse des nächsten Knotens.

Heap:      [ Elem 0 | Pointer ] --------> (irgendwo im Heap) --------> [ Elem 1 | Pointer ]
           |== Cache Line A ==|                                      |== Cache Line B ==|

Wenn du die Liste durchläufst, greifst du auf Elem 0 zu. Die CPU lädt Cache Line A. Nun liest du den Zeiger auf den nächsten Knoten. Dieser zeigt auf eine Adresse weit entfernt im Heap. Die CPU muss die aktuelle Cache Line verwerfen, eine neue Anfrage an den RAM schicken und warten (ein schwerer Cache Miss bzw. Pointer Chasing). Während dieser Hunderte von Taktzyklen langen Wartezeit (der sogenannten Memory Wall) tut die CPU absolut nichts – sie heizt nur den Raum. Der Prefetcher ist völlig blind, da er kein sequenzielles Muster erkennen kann.

Important

Bevorzuge in Rust fast immer Vec\<T\> gegenüber LinkedList\<T\>, selbst wenn du Elemente am Anfang oder in der Mitte einfügen musst. Die CPU-Cache-Effizienz des kontinuierlichen Speichers macht das Kopieren von Elementen im Vektor bei fast allen praxisrelevanten Größen (bis zu zehntausenden Elementen) wett!

6. HashMaps unter der Lupe: SwissTable und Robin Hood

Eine HashMap\<K, V\> erlaubt es uns, Werte über einen Schlüssel in $O(1)$-Zeit zu suchen. Doch wie schafft sie das auf Systemebene, und wie löst sie das Problem, wenn zwei unterschiedliche Schlüssel denselben Hash-Wert erzeugen (eine Kollision)?

Das Prinzip der Hash-Tabelle

Eine HashMap besitzt intern ein flaches Array von “Buckets” (Speicherzellen). Die Hash-Funktion nimmt den Schlüssel (z. B. "Thorsten") und berechnet daraus eine scheinbar zufällige Zahl. Diese Zahl wird per Modulo-Operation auf die Größe des internen Arrays abgebildet. Das Ergebnis ist der Index, an dem wir nachschauen müssen.

Kollisionsauflösung mit Robin-Hood-Hashing

Wenn zwei Schlüssel (z. B. "Apfel" und "Birne") nach dem Hashen auf denselben Index zeigen, haben wir eine Kollision. Rust verwendet ein hocheffizientes Verfahren zur Kollisionsauflösung: Robin-Hood-Hashing kombiniert mit offener Adressierung (Linear Probing).

Die Alltagsanalogie: Der reiche und der arme Gast

Stell dir ein Hotel vor, in dem die Zimmernummern nach dem Namen der Gäste vergeben werden.

• Gast A reist an und erhält sein Wunschzimmer 10. Seine “Distanz zum Wunschzimmer” ist 0. Er ist “reich” (an Bequemlichkeit).
• Gast B reist an. Sein Wunschzimmer ist ebenfalls Zimmer 10. Da es besetzt ist, geht er ein Zimmer weiter zu Zimmer 11. Seine Distanz zum Wunschzimmer ist 1. Er ist “ärmer” als Gast A.
• Gast C reist an. Sein Wunschzimmer ist Zimmer 10. Da Zimmer 10 und 11 besetzt sind, müsste er eigentlich zu Zimmer 12 gehen. Seine Distanz wäre dann 2.

Nun kommt das “Robin-Hood-Prinzip”: Wir bestehlen die Reichen und geben es den Armen!

Wenn Gast C (Distanz 0 an Wunschzimmer 10) anreist und Zimmer 10 besetzt vorfindet, geht er zu Zimmer 11. Dort wohnt Gast B (dessen Distanz aktuell 1 ist). Gast C stellt fest: “Wenn ich hier einziehe, ist meine Distanz 1. Die von Gast B ist auch 1. Keine Verbesserung.” Er geht weiter zu Zimmer 12.

Was aber, wenn Gast D (Wunschzimmer 10, also an Zimmer 11 bereits Distanz 1) ankommt und in Zimmer 11 wohnt jemand, der dort sein absolutes Wunschzimmer hat (Gast X mit Distanz 0)? Gast D verdrängt den “reichen” Gast X einfach aus dem Zimmer! Gast X muss nun ausziehen und ein Zimmer weiter wandern (womit Gast X zum “Armen” wird mit Distanz 1).

Durch dieses ständige Verdrängen und Weiterreichen wird die Varianz der Distanzen extrem gering gehalten. Niemand ist extrem weit von seinem Wunschzimmer entfernt. Das sorgt dafür, dass die Suche nach einem Schlüssel im Worst-Case extrem schnell abgebrochen werden kann.

Das SwissTable-Design (Hashbrown)

Rusts Standard-HashMap basiert auf der hashbrown-Crate, einer Implementierung von Googles revolutionärem SwissTable-Design.

SwissTable optimiert die Suche im Speicher durch die Trennung von Kontroll- und Nutzdaten:

1. Nutzdaten-Array: Ein großes Array, das die eigentlichen Schlüssel und Werte enthält.
2. Metadaten-Array (Control Bytes): Ein paralleles Array, bei dem jedes Byte den Status eines Buckets beschreibt (z. B. ob es leer ist, gelöscht wurde oder die untersten 7 Bits des Hash-Werts des dort liegenden Elements enthält).

Metadaten:  [ 0x7F ][ 0x1A ][ 0xFF ][ 0x7F ] ... (1 Byte pro Bucket)
            |--------- SIMD Register --------|
Daten:      [ Key A | Val A ][ Key B | Val B ] ...

SIMD-Beschleunigung

Wenn wir nach einem Schlüssel suchen, berechnen wir dessen Hash. Die CPU lädt nun eine Gruppe von 16 Metadaten-Bytes auf einmal in ein spezielles SIMD-Register (Single Instruction, Multiple Data). Mit einem einzigen CPU-Befehl vergleicht die CPU diese 16 Bytes gleichzeitig mit den gesuchten Hash-Bits. Wir durchsuchen also 16 Buckets in einem einzigen Taktzyklus! Erst wenn wir in den Metadaten einen Treffer finden, greifen wir auf das teurere Nutzdaten-Array zu, um den eigentlichen Schlüssel auf Gleichheit zu prüfen.

Das macht Rusts HashMap zu einer der schnellsten Implementierungen in der gesamten Programmierwelt.

Zusammenfassung der Hardware-Regeln

Wenn du das nächste Mal eine Datenstruktur auswählst, denke nicht nur an die theoretische $O$-Komplexität. Denke an den Heap-Allokator, den L1-Cache und den fleißigen Hardware-Prefetcher. In 95 % aller Fälle lautet die richtige Antwort auf Hardware-Ebene: Nimm einen Vektor.