Interfejs Hash został zaprojektowany, aby wspierać kolekcje oparte na haszach, takie jak HashMap i HashSet. Standardowa biblioteka Rustu wymaga, aby każdy typ implementujący Eq również implementował Hash, tak aby jeśli k1 == k2, to hash(k1) == hash(k2). Ta inwariantna zasada zapewnia, że tabele haszujące poprawnie rozwiązują kolizje.
Problem powstaje, gdy dwie różne instancje porównują się jako równe (zgodnie z Eq), ale generują różne skróty haszujące. W tym scenariuszu HashMap może umieścić te "równe" klucze w różnych kubełkach. Następne wyszukiwania mogą nie znaleźć istniejących wpisów, lub wstawienia mogą tworzyć duplikaty, naruszając semantyczny kontrakt mapy dotyczący unikalnych kluczy.
Rozwiązanie wymaga utrzymania synchronizacji bitowej pomiędzy logiką równości a logiką haszowania. Przy dostosowywaniu PartialEq i Eq do ignorowania niektórych pól (np. znaczników czasu lub zbuforowanych skrótów), musisz odpowiednio wyłączyć te pola z implementacji Hash. Zapewnia to, że równoważne wartości logiczne zawsze mapują do identycznych kodów haszujących, co utrzymuje integralność kolekcji.
Rozważ rozproszony harmonogram zadań, gdzie struktury Task służą jako klucze w HashMap śledzącym status wykonania. Każde Task zawiera id: Uuid, payload: Vec<u8> i timestamp: Instant. Początkowo zarówno Hash, jak i Eq są automatycznie wyprowadzane. Jednak wymagania się zmieniają: zadania powinny być uważane za równe, jeśli ich id się zgadza, niezależnie od payload lub timestamp.
Pierwszym rozważanym rozwiązaniem było automatyczne wyprowadzanie obu interfejsów za pomocą #[derive]. To podejście utrzymywało strukturalną spójność pomiędzy haszowaniem a równością poprzez uwzględnienie wszystkich pól, ale spowodowało błędy funkcjonalne w logice biznesowej. Konkretne zadania z identycznymi identyfikatorami, ale różnymi znacznikami czasu były traktowane jako różne klucze, uniemożliwiając aktualizacje statusów istniejących zadań i powiększając mapę o nieaktualne wpisy.
Drugim rozwiązaniem było ręczne zaimplementowanie Eq, aby ignorować timestamp, zachowując jednocześnie wyprowadzony Hash. To wydawało się wydajne, ale wprowadziło krytyczny błąd. Dwa zadania równe według ID mogą haszować różnie, jeśli ich znaczniki czasu się różnią, co powoduje, że HashMap rozrzuca je po niezwiązanych kubełkach:
impl PartialEq for Task { fn eq(&self, other: &Self) -> bool { self.id == other.id // Ignoruje znacznik czasu } } // #[derive(Hash)] nadal haszuje wszystkie pola, w tym znacznik czasu
Wyszukiwania statusu zadania losowo pomijały istniejące wpisy, prowadząc do duplikacji wykonania zadań i wyczerpania zasobów.
Wybrane rozwiązanie to ręczna implementacja zarówno Hash, jak i Eq, zapewniając, że oba uwzględniają tylko pole id:
impl Hash for Task { fn hash<H: Hasher>(&self, state: &mut H) { self.id.hash(state); // Haszuj tylko ID } }
To zagwarantowało, że logicznie równoważne zadania zawsze kolidują w tym samym kubełku, pozwalając HashMap prawidłowo identyfikować duplikaty poprzez sprawdzenia równości po kolizji haszowej.
Rezultatem był stabilny system, w którym deduplikacja zadań działała poprawnie, eliminując podwójne wykonania i utrzymując średni czas wyszukiwania O(1). To podejście zapewniło, że rozproszony harmonogram mógł niezawodnie śledzić zakończenie zadań bez wycieków pamięci lub niespójności logicznych. Naprawa wymagała starannego testowania, aby upewnić się, że kolizje haszowe pomiędzy różnymi ID są poprawnie obsługiwane przez sprawdzenie równości, potwierdzając, że logika częściowej równości zintegrowała się płynnie z implementacją tablicy haszującej standardowej biblioteki.
Dlaczego Hash musi być spójny z Eq, ale niekoniecznie z Ord?
Spójność z Eq jest obowiązkowa, ponieważ HashMap używa hasha do lokalizacji kubełka, a następnie wykorzystuje równość (==) do rozwiązywania kolizji w tym kubełku. Jeśli równe elementy haszują różnie, zajmują różne kubełki, czyniąc sprawdzenie równości nieistotnym podczas wyszukiwania i łamiąc inwariant unikalności. Ord, natomiast, definiuje całkowite uporządkowanie dla posortowanych kolekcji, takich jak BTreeMap, które nie opierają się na haszowaniu, ale na drzewach porównawczych; zatem Ord i Hash nie mają relacji umownej, a typ może być porównywalny w sposób niespójny z jego hashem bez kompromisów w bezpieczeństwie pamięci czy semantyce kolekcji.
Co się stanie, jeśli metoda hash panikuje podczas wstawiania do HashMap?
Jeśli Hash panikuje, HashMap pozostaje w stanie pośrednim, w którym klucz został częściowo przetworzony, ale nie został w pełni wstawiony. W przeciwieństwie do Mutex, HashMap nie implementuje zatrucia. Jednak alokacja pamięci dla wpisu mogła się już zdarzyć, mimo że wartość nie została w pełni zainicjowana ani połączona z łańcuchiem w tabeli. Może to prowadzić do wycieków pamięci lub, w skrajnych przypadkach, nieokreślonego zachowania, jeśli panika wystąpi podczas operacji ponownego haszowania, gdy tabela jest rozmiarowana. Standardowa biblioteka łagodzi to poprzez stosowanie strażników spadku i staranne zarządzanie stanem, ale kod użytkownika musi zapewnić, że implementacje Hash są wolne od paniki, aby zagwarantować spójność kolekcji.
Jak BuildHasher zapobiega atakom HashDoS i dlaczego SipHasher jest domyślny?
BuildHasher abstrahuje proces tworzenia instancji Hasher, umożliwiając HashMap instancjonowanie nowego hashera z losowymi kluczami dla każdej instancji mapy. Domyślny RandomState używa SipHasher-1-3 (lub podobnej wersji) z kluczami generowanymi z źródła entropii systemu operacyjnego. Ta losowość zapobiega atakom HashDoS, w których atakujący tworzy dane wejściowe, które wszystkie haszują do tego samego kubełka, degradując wyszukiwanie do O(n). Poprzez nasianie każdej mapy inaczej, eliminowany jest powierzchnia ataku, ponieważ atakujący nie może przewidzieć, które dane wejściowe będą kolidować. SipHasher został wybrany ze względu na równowagę pomiędzy bezpieczeństwem kryptograficznym (zapobiegającym odzyskiwaniu kluczy) a szybkością, w przeciwieństwie do szybszych, ale podatnych algorytmów, takich jak MurmurHash czy wolniejszych skrótów kryptograficznych, takich jak SHA-3.