Odpowiedź

Aby używać struktur użytkownika w kolekcjach typu HashMap lub HashSet, należy zaimplementować traty Eq i Hash (często również PartialEq). Implementacja tych traitów określa, jak obiekty są ze sobą porównywane i jak obliczany jest ich hasz.

Ważne: jeśli dwa obiekty są równe (a == b), to ich wartości haszowe muszą być zgodne (hash(a) == hash(b)). W przeciwnym razie kontenery, które polegają na haszach, będą działać niepoprawnie (niemożliwe będzie znalezienie lub usunięcie elementu).

Przykład implementacji:

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

#[derive(Eq, PartialEq)]
struct Point {
    x: i32,
    y: i32,
}

impl Hash for Point {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.x.hash(state);
        self.y.hash(state);
    }
}

Pytanie z podtekstem

Czy można zaimplementować Hash dla struktury, w której niektóre pola biorą udział w porównywaniu równości (Eq/PartialEq), a inne tylko w haszowaniu?

Odpowiedź: Nie, to prowadzi do naruszenia inwariantu: jeśli dwa elementy są uważane za równe, ich hasz musi być taki sam. Wszystkie pola biorące udział w PartialEq/Eq powinny być również uwzględniane w Hash. Ignorowanie "niesporównywanych" pól jest bezpieczne tylko wtedy, gdy nie biorą one udziału w logice porównywania.

impl Hash for MyType {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.x.hash(state); // jeśli tylko self.x jest używane także w Eq
    }
}

Przykłady rzeczywistych błędów z powodu niewiedzy na ten temat

---

Historia

W dużym projekcie serwerowym struktura klucza była używana w HashMap, ale w haszowaniu zapomniano o jednym polu, które uczestniczyło w PartialEq. W rezultacie niemożność znalezienia odpowiedniego klucza doprowadziła do "wycieku" użytkowników z cache: elementy były uważane za identyczne, chociaż były różne.

---

Historia

W open source bibliotece dla obiektów geometrycznych w Hash i Eq używano porównania zmiennoprzecinkowego (f64). W rezultacie z powodu szczególnych cech porównania NaN i -0.0/+0.0 standardowe kontenery działały z błędami, czasami nie znajdując istniejącego obiektu w kolekcji.

---

Historia

W jednym projekcie fintech przy refaktoryzacji używano auto-derywacji #[derive(Hash, Eq, PartialEq)] dla struktury z prywatnymi polami, zmieniając kolejność ich deklaracji. W rezultacie zmienił się ostateczny hasz, co zepsuło działanie cache i spowodowało utratę danych po restarcie.