Przechowywanie kluczy z powiązanymi wartościami w mapach haszujących
Ostatnią z naszych wspólnych kolekcji jest mapa haszująca. Typ HashMap<K, V> przechowuje mapowanie kluczy typu K na wartości typu V za pomocą funkcji haszującej, która określa, w jaki sposób umieszcza te klucze i wartości w pamięci. Wiele języków programowania obsługuje tego rodzaju strukturę danych, ale często używają innej nazwy, takiej jak hash, map, object, hash table, dictionary lub associative array, by wymienić tylko kilka.
Mapy haszujące są przydatne, gdy chcesz wyszukiwać dane nie za pomocą indeksu, jak w przypadku wektorów, ale za pomocą klucza, który może być dowolnego typu. Na przykład w grze możesz śledzić wyniki każdej drużyny w mapie haszującej, w której każdy klucz to nazwa drużyny, a wartości to wyniki każdej drużyny. Mając nazwę drużyny, możesz pobrać jej wynik.
W tej sekcji omówimy podstawowe API map haszujących, ale wiele innych dobrodziejstw kryje się w funkcjach zdefiniowanych dla HashMap<K, V> przez standardową bibliotekę. Jak zawsze, sprawdź dokumentację standardowej biblioteki, aby uzyskać więcej informacji.
Tworzenie nowej mapy haszującej
Jednym ze sposobów utworzenia pustej mapy haszującej jest użycie new i dodanie elementów za pomocą insert. W Listing 8-20 śledzimy wyniki dwóch drużyn, których nazwy to Niebiescy i Żółci. Drużyna Niebieskich zaczyna z 10 punktami, a drużyna Żółtych z 50.
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Niebiescy"), 10);
scores.insert(String::from("Żółci"), 50);
}Zauważ, że musimy najpierw use HashMap z części kolekcji standardowej biblioteki. Spośród naszych trzech wspólnych kolekcji, ta jest najrzadziej używana, więc nie jest ona domyślnie dołączana do zasięgu w preludium. Mapy haszujące mają również mniejsze wsparcie ze strony standardowej biblioteki; nie ma na przykład wbudowanego makra do ich konstruowania.
Podobnie jak wektory, mapy haszujące przechowują swoje dane na stercie. Ta HashMap ma klucze typu String i wartości typu i32. Podobnie jak wektory, mapy haszujące są jednorodne: wszystkie klucze muszą mieć ten sam typ, a wszystkie wartości muszą mieć ten sam typ.
Dostęp do wartości w mapie haszującej
Możemy pobrać wartość z mapy haszującej, podając jej klucz do metody get, jak pokazano w Listing 8-21.
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Niebiescy"), 10);
scores.insert(String::from("Żółci"), 50);
let team_name = String::from("Niebiescy");
let score = scores.get(&team_name).copied().unwrap_or(0);
}Tutaj score będzie miało wartość powiązaną z drużyną Niebieskich, a wynik będzie wynosił 10. Metoda get zwraca Option<&V>; jeśli dla tego klucza nie ma wartości w mapie haszującej, get zwróci None. Ten program obsługuje Option wywołując copied, aby uzyskać Option<i32> zamiast Option<&i32>, a następnie unwrap_or, aby ustawić score na zero, jeśli scores nie ma wpisu dla klucza.
Możemy iterować po każdej parze klucz-wartość w mapie haszującej w podobny sposób, jak to robimy z wektorami, używając pętli for:
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Niebiescy"), 10);
scores.insert(String::from("Żółci"), 50);
for (key, value) in &scores {
println!("{key}: {value}");
}
}Ten kod wydrukuje każdą parę w dowolnej kolejności:
Żółci: 50
Niebiescy: 10
Zarządzanie własnością w mapach haszujących
W przypadku typów implementujących cechę Copy, takich jak i32, wartości są kopiowane do mapy haszującej. W przypadku wartości posiadanych, takich jak String, wartości zostaną przeniesione, a mapa haszująca będzie właścicielem tych wartości, jak pokazano w Listing 8-22.
fn main() {
use std::collections::HashMap;
let field_name = String::from("Ulubiony kolor");
let field_value = String::from("Niebieski");
let mut map = HashMap::new();
map.insert(field_name, field_value);
// field_name i field_value są w tym momencie nieprawidłowe, spróbuj ich użyć i
// zobacz, jaki błąd kompilacji otrzymasz!
}Nie możemy używać zmiennych field_name i field_value po ich przeniesieniu do mapy haszującej za pomocą wywołania insert.
Jeśli wstawimy referencje do wartości do mapy haszującej, wartości nie zostaną przeniesione do mapy haszującej. Wartości, na które wskazują referencje, muszą być ważne przynajmniej tak długo, jak długo ważna jest mapa haszująca. Więcej o tych problemach omówimy w sekcji „Walidacja referencji za pomocą czasów życia” w Rozdziale 10.
Aktualizowanie mapy haszującej
Chociaż liczba par klucz-wartość może rosnąć, każdy unikalny klucz może mieć w danym momencie tylko jedną powiązaną wartość (ale nie na odwrót: na przykład, zarówno drużyna Niebieskich, jak i drużyna Żółtych mogłyby mieć wartość 10 przechowywaną w mapie haszującej scores).
Kiedy chcesz zmienić dane w mapie haszującej, musisz zdecydować, jak postąpić w przypadku, gdy klucz już ma przypisaną wartość. Możesz zastąpić starą wartość nową, całkowicie ignorując starą wartość. Możesz zachować starą wartość i zignorować nową wartość, dodając nową wartość tylko wtedy, gdy klucz nie ma jeszcze wartości. Lub możesz połączyć starą wartość i nową wartość. Przyjrzyjmy się, jak wykonać każdą z tych czynności!
Nadpisywanie wartości
Jeśli wstawimy klucz i wartość do mapy haszującej, a następnie wstawimy ten sam klucz z inną wartością, wartość powiązana z tym kluczem zostanie zastąpiona. Mimo że kod w Listing 8-23 wywołuje insert dwukrotnie, mapa haszująca będzie zawierać tylko jedną parę klucz-wartość, ponieważ dwukrotnie wstawiamy wartość dla klucza drużyny Niebieskich.
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Niebiescy"), 10);
scores.insert(String::from("Niebiescy"), 25);
println!("{scores:?}");
}Ten kod wydrukuje {"Niebiescy": 25}. Pierwotna wartość 10 została nadpisana.
Dodawanie klucza i wartości tylko wtedy, gdy klucz nie jest obecny
Często sprawdza się, czy dany klucz już istnieje w mapie haszującej z wartością, a następnie wykonuje następujące działania: Jeśli klucz istnieje w mapie haszującej, istniejąca wartość powinna pozostać taka, jaka jest; jeśli klucz nie istnieje, wstawia się go i wartość dla niego.
Mapy haszujące posiadają specjalne API do tego celu, zwane entry, które jako parametr przyjmuje klucz, który chcesz sprawdzić. Wartością zwracaną przez metodę entry jest enum o nazwie Entry, który reprezentuje wartość, która może istnieć lub nie. Załóżmy, że chcemy sprawdzić, czy klucz dla drużyny Żółtych ma przypisaną wartość. Jeśli nie, chcemy wstawić wartość 50, i to samo dla drużyny Niebieskich. Używając API entry, kod wygląda jak w Listing 8-24.
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Niebiescy"), 10);
scores.entry(String::from("Żółci")).or_insert(50);
scores.entry(String::from("Niebiescy")).or_insert(50);
println!("{scores:?}");
}Metoda or_insert w Entry jest zdefiniowana tak, aby zwracać mutowalną referencję do wartości dla odpowiadającego klucza Entry, jeśli ten klucz istnieje, a jeśli nie, wstawia parametr jako nową wartość dla tego klucza i zwraca mutowalną referencję do nowej wartości. Ta technika jest znacznie czystsza niż samodzielne pisanie logiki i, co więcej, lepiej współpracuje z mechanizmem sprawdzania pożyczek.
Uruchomienie kodu w Listing 8-24 wydrukuje {"Żółci": 50, "Niebiescy": 10}. Pierwsze wywołanie entry wstawi klucz dla drużyny Żółtych z wartością 50, ponieważ drużyna Żółtych nie ma jeszcze wartości. Drugie wywołanie entry nie zmieni mapy haszującej, ponieważ drużyna Niebieskich ma już wartość 10.
Aktualizowanie wartości na podstawie starej wartości
Innym częstym przypadkiem użycia map haszujących jest wyszukiwanie wartości klucza, a następnie aktualizowanie jej na podstawie starej wartości. Na przykład, Listing 8-25 pokazuje kod, który zlicza, ile razy każde słowo pojawia się w tekście. Używamy mapy haszującej ze słowami jako kluczami i inkrementujemy wartość, aby śledzić, ile razy widzieliśmy to słowo. Jeśli jest to pierwszy raz, kiedy widzieliśmy słowo, najpierw wstawimy wartość 0.
fn main() {
use std::collections::HashMap;
let text = "cześć świat cudowny świat";
let mut map = HashMap::new();
for word in text.split_whitespace() {
let count = map.entry(word).or_insert(0);
*count += 1;
}
println!("{map:?}");
}Ten kod wydrukuje {"świat": 2, "cześć": 1, "cudowny": 1}. Możesz zobaczyć te same pary klucz-wartość wydrukowane w innej kolejności: przypomnij sobie z sekcji „Dostęp do wartości w mapie haszującej”, że iteracja po mapie haszującej odbywa się w dowolnej kolejności.
Metoda split_whitespace zwraca iterator po podsekcjach, rozdzielonych spacjami, wartości w text. Metoda or_insert zwraca mutowalną referencję (&mut V) do wartości dla określonego klucza. Tutaj przechowujemy tę mutowalną referencję w zmiennej count, więc aby przypisać do tej wartości, musimy najpierw dereferencjować count za pomocą gwiazdki (*). Mutowalna referencja wychodzi poza zasięg na końcu pętli for, więc wszystkie te zmiany są bezpieczne i dozwolone przez zasady pożyczania.
Funkcje haszujące
Domyślnie HashMap używa funkcji haszującej zwanej SipHash, która może zapewnić odporność na ataki typu denial-of-service (DoS) związane z tabelami haszującymi1. Nie jest to najszybszy dostępny algorytm haszujący, ale kompromis między lepszym bezpieczeństwem a spadkiem wydajności jest tego wart. Jeśli profilujesz swój kod i stwierdzisz, że domyślna funkcja haszująca jest zbyt wolna dla Twoich celów, możesz przełączyć się na inną funkcję, określając inny haszer. Haszer to typ, który implementuje cechę BuildHasher. O cechach i sposobie ich implementacji omówimy w Rozdziale 10. Nie musisz koniecznie implementować własnego haszera od podstaw; crates.io posiada biblioteki udostępnione przez innych użytkowników Rusta, które dostarczają haszerów implementujących wiele popularnych algorytmów haszujących.
Podsumowanie
Wektory, ciągi znaków i mapy haszujące zapewnią dużą funkcjonalność niezbędną w programach, gdy trzeba przechowywać, uzyskiwać dostęp i modyfikować dane. Oto kilka ćwiczeń, które powinieneś być teraz w stanie rozwiązać:
- Mając listę liczb całkowitych, użyj wektora i zwróć medianę (po posortowaniu, wartość na środkowej pozycji) i dominantę (wartość, która występuje najczęściej; tutaj pomocna będzie mapa haszująca) listy.
- Przekształć ciągi znaków na języka Pig Latin. Pierwsza spółgłoska każdego słowa jest przenoszona na koniec słowa i dodawane jest ay, więc first staje się irst-fay. Słowa, które zaczynają się samogłoską, mają dodane hay na końcu (apple staje się apple-hay). Pamiętaj o szczegółach kodowania UTF-8!
- Korzystając z mapy haszującej i wektorów, stwórz interfejs tekstowy, aby umożliwić użytkownikowi dodawanie nazw pracowników do działu w firmie; na przykład „Dodaj Sally do Inżynierii” lub „Dodaj Amira do Sprzedaży”. Następnie pozwól użytkownikowi pobrać listę wszystkich osób w dziale lub wszystkich osób w firmie według działu, posortowanych alfabetycznie.
Dokumentacja API standardowej biblioteki opisuje metody, które mają wektory, ciągi znaków i mapy haszujące, które będą pomocne w tych ćwiczeniach!
Przechodzimy do bardziej złożonych programów, w których operacje mogą zakończyć się niepowodzeniem, więc to idealny czas, aby omówić obsługę błędów. Zrobimy to w następnej kolejności!