Il trait Hash è stato progettato per supportare collezioni basate su hash come HashMap e HashSet. La libreria standard di Rust impone che qualsiasi tipo che implementa Eq deve anche implementare Hash in modo tale che se k1 == k2, allora hash(k1) == hash(k2). Questa invariante assicura che le tabelle hash risolvano correttamente le collisioni.
Il problema sorge quando due istanze distinte vengono confrontate come uguali (in base a Eq) ma producono digest diversi. In questo scenario, un HashMap potrebbe posizionare queste chiavi "uguali" in cestini diversi. Le ricerche successive potrebbero quindi non trovare voci esistenti, oppure le inserzioni potrebbero creare duplicati, violando il contratto semantico della mappa di chiavi uniche.
La soluzione richiede di mantenere la sincronizzazione bitwise tra la logica di uguaglianza e quella di hashing. Quando si personalizzano PartialEq e Eq per ignorare determinati campi (ad esempio, timestamp o hash memorizzati), è necessario escludere corrispondentemente quei campi dall'implementazione di Hash. Questo garantisce che valori logici equivalenti mappino sempre a codici hash identici, preservando l'integrità della collezione.
Considera un scheduler di task distribuito in cui le strutture Task fungono da chiavi in un HashMap che tiene traccia dello stato di completamento. Ogni Task contiene un id: Uuid, payload: Vec<u8> e timestamp: Instant. Inizialmente, sia Hash che Eq sono derivati automaticamente. Tuttavia, i requisiti cambiano: i task devono essere considerati uguali se il loro id corrisponde, indipendentemente da payload o timestamp.
La prima soluzione considerata è stata derivare entrambi i trait automaticamente tramite #[derive]. Questo approccio manteneva la coerenza strutturale tra hashing e uguaglianza includendo tutti i campi, ma ha causato errori funzionali nella logica aziendale. In particolare, i task con ID identici ma timestamp differenti venivano trattati come chiavi distinte, impedendo aggiornamenti dello stato per task esistenti e gonfiando la mappa con voci obsolete.
La seconda soluzione prevedeva l'implementazione manuale di Eq per ignorare timestamp mantenendo il Hash derivato. Questo sembrava efficiente ma ha introdotto un bug critico. Due task uguali per ID avrebbero hashato in modo diverso se i loro timestamp differivano, causando la dispersione dei task nel HashMap in cestini non correlati:
impl PartialEq per Task { fn eq(&self, other: &Self) -> bool { self.id == other.id // Ignora timestamp } } // #[derive(Hash)] ancora hashava tutti i campi inclusi timestamp
Le ricerche sullo stato dei task avrebbero perso casualmente voci esistenti, portando a esecuzioni duplicate dei task e esaurimento delle risorse.
La soluzione scelta è stata l'implementazione manuale di sia Hash che Eq, garantendo che entrambi considerassero solo il campo id:
impl Hash per Task { fn hash<H: Hasher>(&self, state: &mut H) { self.id.hash(state); // Hasha solo ID } }
Questo garantiva che i task logicamente equivalenti collidessero sempre nello stesso cestino, consentendo al HashMap di identificare correttamente i duplicati tramite controlli di uguaglianza dopo le collisioni hash.
Il risultato è stato un sistema stabile in cui la deduplicazione dei task funzionava correttamente, eliminando l'esecuzione doppia e mantenendo tempi di ricerca medi di O(1). Questo approccio ha garantito che lo scheduler distribuito potesse monitorare affidabilmente il completamento dei task senza perdite di memoria o incoerenze logiche. La correzione ha richiesto test accurati per verificare che le collisioni hash tra ID diversi fossero gestite correttamente dal controllo di uguaglianza, confermando che la logica di uguaglianza parziale si integrasse senza problemi con l'implementazione della tabella hash della libreria standard.
Perché Hash deve essere coerente con Eq ma non necessariamente con Ord?
La coerenza con Eq è obbligatoria perché HashMap utilizza l'hash per localizzare un cestino e poi utilizza l'uguaglianza (==) per risolvere le collisioni all'interno di quel cestino. Se gli elementi uguali hashano in modo diverso, occupano cestini diversi, rendendo il controllo di uguaglianza irrilevante durante la ricerca e rompendo l'invariante di unicità. Ord, tuttavia, definisce un ordinamento totale per collezioni ordinate come BTreeMap, che non si basa sull'hashing ma su alberi di confronto; quindi, Ord e Hash non hanno una relazione contrattuale, e un tipo può essere ordinabile in un modo incoerente con il suo hash senza compromettere la sicurezza della memoria o la semantica della collezione.
Cosa succede se il metodo hash va in panico durante l'inserimento in un HashMap?
Se Hash va in panico, il HashMap rimane in uno stato intermedio in cui la chiave è stata parzialmente elaborata ma non completamente inserita. A differenza di Mutex, HashMap non implementa il poisoning. Tuttavia, l'allocazione di memoria sottostante per l'elemento potrebbe essere avvenuta senza che il valore fosse completamente inizializzato o collegato nella catena della tabella. Questo può portare a perdite di memoria o, nei casi estremi, a comportamenti indefiniti se il panico si verifica durante un'operazione di rehash in cui la tabella viene ridimensionata. La libreria standard mitiga questo utilizzando guardie di drop e gestione attenta dello stato, ma il codice degli utenti deve garantire che le implementazioni di Hash siano prive di panico per garantire la coerenza della collezione.
Come previene BuildHasher gli attacchi HashDoS, e perché SipHasher è il predefinito?
BuildHasher astrae la creazione di istanze di Hasher, consentendo a HashMap di istanziare un nuovo hasher con chiavi casualizzate per ogni istanza della mappa. Il predefinito RandomState utilizza SipHasher-1-3 (o una variante simile) con chiavi generate dalla sorgente di entropia del sistema operativo. Questa randomizzazione previene attacchi HashDoS in cui un attaccante crea input che hashano tutti allo stesso cestino, degradando la ricerca a O(n). Sembrando ogni mappa in modo diverso, la superficie di attacco è eliminata poiché l'attaccante non può prevedere quali input si scontreranno. SipHasher è stato scelto per il suo equilibrio tra sicurezza crittografica (per evitare il recupero della chiave) e velocità, a differenza di algoritmi più veloci ma vulnerabili come MurmurHash o hash crittografici più lenti come SHA-3.