Einführung
Willkommen bei Storing Keys With Associated Values in Hash Maps (Speichern von Schlüsseln mit zugehörigen Werten in Hash-Tabellen). Dieser Lab-Abschnitt ist Teil des Rust Book. Sie können Ihre Rust-Fähigkeiten in LabEx üben.
In diesem Lab werden wir das Konzept von Hash-Tabellen (Hash Maps) untersuchen und erfahren, wie sie verwendet werden können, um Schlüssel mit zugehörigen Werten zu speichern.
Speichern von Schlüsseln mit zugehörigen Werten in Hash-Tabellen (Hash Maps)
Die letzte unserer gängigen Sammlungen (Collections) ist die Hash-Tabelle (Hash Map). Der Typ HashMap<K, V> speichert eine Zuordnung von Schlüsseln des Typs K zu Werten des Typs V mithilfe einer Hash-Funktion, die bestimmt, wie diese Schlüssel und Werte im Speicher platziert werden. Viele Programmiersprachen unterstützen diese Art von Datenstruktur, verwenden aber oft einen anderen Namen, wie z. B. Hash, Map, Objekt, Hash-Tabelle, Wörterbuch oder assoziatives Array, um nur einige zu nennen.
Hash-Tabellen sind nützlich, wenn Sie Daten nicht wie bei Vektoren anhand eines Index, sondern anhand eines Schlüssels, der von jedem Typ sein kann, abrufen möchten. Beispielsweise könnten Sie in einem Spiel die Punktzahl jeder Mannschaft in einer Hash-Tabelle verfolgen, in der jeder Schlüssel der Name einer Mannschaft ist und die Werte die Punktzahl jeder Mannschaft darstellen. Bei Angabe eines Mannschaftsnamens können Sie seine Punktzahl abrufen.
In diesem Abschnitt werden wir uns die grundlegende API von Hash-Tabellen ansehen, aber viele weitere nützliche Funktionen verstecken sich in den Funktionen, die von der Standardbibliothek für HashMap<K, V> definiert werden. Wie immer, überprüfen Sie die Dokumentation der Standardbibliothek für weitere Informationen.
Erstellen einer neuen Hash-Tabelle (Hash Map)
Eine Möglichkeit, eine leere Hash-Tabelle zu erstellen, besteht darin, new zu verwenden und Elemente mit insert hinzuzufügen. In Listing 8-20 verfolgen wir die Punktzahlen von zwei Mannschaften, deren Namen Blue und Yellow sind. Die Blue-Mannschaft beginnt mit 10 Punkten, und die Yellow-Mannschaft beginnt mit 50 Punkten.
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
Listing 8-20: Erstellen einer neuen Hash-Tabelle und Einfügen einiger Schlüssel und Werte
Beachten Sie, dass wir zunächst HashMap aus dem Abschnitt der Sammlungen (Collections) der Standardbibliothek use müssen. Von unseren drei gängigen Sammlungen wird diese am wenigsten verwendet, daher ist sie nicht in den Funktionen enthalten, die automatisch im Präambel in den Geltungsbereich gebracht werden. Hash-Tabellen werden auch von der Standardbibliothek weniger unterstützt; es gibt beispielsweise keine integrierte Makro, um sie zu konstruieren.
Genau wie Vektoren speichern Hash-Tabellen ihre Daten auf dem Heap. Diese HashMap hat Schlüssel vom Typ String und Werte vom Typ i32. Wie Vektoren sind Hash-Tabellen homogen: Alle Schlüssel müssen denselben Typ haben, und alle Werte müssen denselben Typ haben.
Zugreifen auf Werte in einer Hash-Tabelle (Hash Map)
Wir können einen Wert aus der Hash-Tabelle abrufen, indem wir seinen Schlüssel an die get-Methode übergeben, wie in Listing 8-21 gezeigt.
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
let team_name = String::from("Blue");
let score = scores.get(&team_name).copied().unwrap_or(0);
Listing 8-21: Zugreifen auf die Punktzahl der Blue-Mannschaft, die in der Hash-Tabelle gespeichert ist
Hier wird score den Wert haben, der mit der Blue-Mannschaft verknüpft ist, und das Ergebnis wird 10 sein. Die get-Methode gibt ein Option<&V> zurück; wenn es in der Hash-Tabelle keinen Wert für diesen Schlüssel gibt, gibt get None zurück. Dieses Programm behandelt das Option-Objekt, indem es copied aufruft, um ein Option<i32> anstelle eines Option<&i32> zu erhalten, und dann unwrap_or, um score auf Null zu setzen, wenn scores keinen Eintrag für den Schlüssel hat.
Wir können über jedes Schlüssel-Wert-Paar in einer Hash-Tabelle auf ähnliche Weise wie bei Vektoren mithilfe einer for-Schleife iterieren:
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
for (key, value) in &scores {
println!("{key}: {value}");
}
Dieser Code wird jedes Paar in beliebiger Reihenfolge ausgeben:
Yellow: 50
Blue: 10
Hash-Tabellen (Hash Maps) und Besitz (Ownership)
Für Typen, die das Copy-Trait implementieren, wie i32, werden die Werte in die Hash-Tabelle kopiert. Bei eigenen Werten wie String werden die Werte verschoben, und die Hash-Tabelle wird der Besitzer dieser Werte sein, wie in Listing 8-22 gezeigt.
use std::collections::HashMap;
let field_name = String::from("Favorite color");
let field_value = String::from("Blue");
let mut map = HashMap::new();
map.insert(field_name, field_value);
// field_name and field_value are invalid at this point, try
// using them and see what compiler error you get!
Listing 8-22: Zeigt, dass Schlüssel und Werte von der Hash-Tabelle besessen werden, sobald sie eingefügt wurden
Wir können die Variablen field_name und field_value nicht mehr verwenden, nachdem sie mit dem Aufruf von insert in die Hash-Tabelle verschoben wurden.
Wenn wir Referenzen auf Werte in die Hash-Tabelle einfügen, werden die Werte nicht in die Hash-Tabelle verschoben. Die Werte, auf die die Referenzen verweisen, müssen mindestens so lange gültig sein wie die Hash-Tabelle. Wir werden uns diese Probleme ausführlicher in "Validating References with Lifetimes" (Überprüfen von Referenzen mit Lebensdauern) ansehen.
Aktualisieren einer Hash-Tabelle (Hash Map)
Obwohl die Anzahl der Schlüssel-Wert-Paare wachsen kann, kann jeder eindeutige Schlüssel zu einem bestimmten Zeitpunkt nur einen Wert zugeordnet haben (aber nicht umgekehrt: Beispielsweise könnten sowohl die Blue-Mannschaft als auch die Yellow-Mannschaft den Wert 10 in der scores-Hash-Tabelle gespeichert haben).
Wenn Sie die Daten in einer Hash-Tabelle ändern möchten, müssen Sie entscheiden, wie Sie den Fall behandeln möchten, wenn einem Schlüssel bereits ein Wert zugewiesen ist. Sie könnten den alten Wert durch den neuen Wert ersetzen und dabei den alten Wert völlig ignorieren. Sie könnten den alten Wert beibehalten und den neuen Wert ignorieren und den neuen Wert nur hinzufügen, wenn der Schlüssel noch nicht einen Wert hat. Oder Sie könnten den alten Wert und den neuen Wert kombinieren. Schauen wir uns an, wie man dies jeweils macht!
Überschreiben eines Werts
Wenn wir einen Schlüssel und einen Wert in eine Hash-Tabelle einfügen und dann denselben Schlüssel mit einem anderen Wert einfügen, wird der mit diesem Schlüssel verknüpfte Wert ersetzt. Auch wenn der Code in Listing 8-23 zweimal insert aufruft, enthält die Hash-Tabelle nur ein Schlüssel-Wert-Paar, da wir beide Male den Wert für den Schlüssel der Blue-Mannschaft einfügen.
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Blue"), 25);
println!("{:?}", scores);
Listing 8-23: Ersetzen eines mit einem bestimmten Schlüssel gespeicherten Werts
Dieser Code wird {"Blue": 25} ausgeben. Der ursprüngliche Wert von 10 wurde überschrieben.
Hinzufügen eines Schlüssels und Werts nur, wenn der Schlüssel noch nicht vorhanden ist
Es ist üblich, zu prüfen, ob ein bestimmter Schlüssel bereits in der Hash-Tabelle mit einem Wert existiert, und dann folgende Aktionen auszuführen: Wenn der Schlüssel in der Hash-Tabelle existiert, sollte der vorhandene Wert unverändert bleiben; wenn der Schlüssel nicht existiert, soll er und ein zugehöriger Wert eingefügt werden.
Hash-Tabellen haben für diesen Zweck eine spezielle API namens entry, die den Schlüssel, den Sie prüfen möchten, als Parameter nimmt. Der Rückgabewert der entry-Methode ist ein Enum namens Entry, das einen Wert darstellt, der existieren kann oder auch nicht. Nehmen wir an, wir möchten prüfen, ob der Schlüssel für die Yellow-Mannschaft einen zugehörigen Wert hat. Wenn nicht, möchten wir den Wert 50 einfügen, und dasselbe für die Blue-Mannschaft. Mit der entry-API sieht der Code wie in Listing 8-24 aus.
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.entry(String::from("Yellow")).or_insert(50);
scores.entry(String::from("Blue")).or_insert(50);
println!("{:?}", scores);
Listing 8-24: Verwenden der entry-Methode, um nur einzufügen, wenn der Schlüssel noch keinen Wert hat
Die or_insert-Methode auf Entry ist so definiert, dass sie eine veränderliche Referenz auf den Wert für den entsprechenden Entry-Schlüssel zurückgibt, wenn dieser Schlüssel existiert. Wenn nicht, wird der Parameter als neuer Wert für diesen Schlüssel eingefügt, und es wird eine veränderliche Referenz auf den neuen Wert zurückgegeben. Diese Technik ist viel sauberer als das Schreiben der Logik selbst und spielt außerdem besser mit dem Borrow-Checker zusammen.
Das Ausführen des Codes in Listing 8-24 wird {"Yellow": 50, "Blue": 10} ausgeben. Der erste Aufruf von entry wird den Schlüssel für die Yellow-Mannschaft mit dem Wert 50 einfügen, da die Yellow-Mannschaft noch keinen Wert hat. Der zweite Aufruf von entry wird die Hash-Tabelle nicht ändern, da die Blue-Mannschaft bereits den Wert 10 hat.
Aktualisieren eines Werts basierend auf dem alten Wert
Ein weiterer häufiger Anwendungsfall für Hash-Tabellen (Hash Maps) besteht darin, den Wert eines Schlüssels zu suchen und ihn dann basierend auf dem alten Wert zu aktualisieren. Beispielsweise zeigt Listing 8-25 Code, der zählt, wie oft jedes Wort in einem Text vorkommt. Wir verwenden eine Hash-Tabelle mit den Wörtern als Schlüsseln und erhöhen den Wert, um zu verfolgen, wie oft wir ein Wort gesehen haben. Wenn es das erste Mal ist, dass wir ein Wort sehen, fügen wir zunächst den Wert 0 ein.
use std::collections::HashMap;
let text = "hello world wonderful world";
let mut map = HashMap::new();
for word in text.split_whitespace() {
let count = map.entry(word).or_insert(0);
*count += 1;
}
println!("{:?}", map);
Listing 8-25: Zählen der Vorkommen von Wörtern mit einer Hash-Tabelle, die Wörter und Zählungen speichert
Dieser Code wird {"world": 2, "hello": 1, "wonderful": 1} ausgeben. Möglicherweise werden die gleichen Schlüssel-Wert-Paare in einer anderen Reihenfolge ausgegeben: Denken Sie an "Accessing Values in a Hash Map" (Zugreifen auf Werte in einer Hash-Tabelle), dass das Iterieren über eine Hash-Tabelle in beliebiger Reihenfolge erfolgt.
Die split_whitespace-Methode gibt einen Iterator über Teilschnitte zurück, die durch Leerzeichen getrennt sind, des Werts in text. Die or_insert-Methode gibt eine veränderliche Referenz (&mut V) auf den Wert für den angegebenen Schlüssel zurück. Hier speichern wir diese veränderliche Referenz in der Variablen count, daher müssen wir, um diesem Wert zuzuweisen, zunächst count mit dem Sternchen (*) dereferenzieren. Die veränderliche Referenz verlässt den Gültigkeitsbereich am Ende der for-Schleife, sodass alle diese Änderungen sicher sind und von den Borrowing-Regeln erlaubt werden.
Hash-Funktionen (Hashing Functions)
Standardmäßig verwendet HashMap eine Hash-Funktion namens SipHash, die einen Schutz gegen Denial-of-Service (DoS)-Angriffe bieten kann, die Hash-Tabellen betreffen. Dies ist nicht der schnellste verfügbare Hash-Algorithmus, aber der Kompromiss zwischen besserer Sicherheit und der damit verbundenen Leistungseinbuße lohnt sich. Wenn Sie Ihr Code profilieren und feststellen, dass die Standard-Hash-Funktion für Ihre Zwecke zu langsam ist, können Sie durch Angabe eines anderen Hashers (Hash-Funktionsevaluators) zu einer anderen Funktion wechseln. Ein Hasher ist ein Typ, der das BuildHasher-Trait implementiert. Wir werden in Kapitel 10 über Traits und deren Implementierung sprechen. Sie müssen nicht unbedingt Ihren eigenen Hasher von Grund auf neu implementieren; https://crates.io hat Bibliotheken, die von anderen Rust-Nutzern geteilt werden und Hashers bereitstellen, die viele gängige Hash-Algorithmen implementieren.
Zusammenfassung
Herzlichen Glückwunsch! Sie haben das Labor "Storing Keys With Associated Values in Hash Maps" (Speichern von Schlüsseln mit zugehörigen Werten in Hash-Tabellen) abgeschlossen. Sie können in LabEx weitere Labs üben, um Ihre Fähigkeiten zu verbessern.