Le trait Hash a été conçu pour supporter des collections basées sur des hachages comme HashMap et HashSet. La bibliothèque standard Rust exige que tout type implémentant Eq implémente également Hash de manière à ce que si k1 == k2, alors hash(k1) == hash(k2). Cette invariant garantit que les tables de hachage résolvent correctement les collisions.
Le problème survient lorsque deux instances distinctes se comparent comme égales (selon Eq) mais produisent des hachages différents. Dans ce scénario, un HashMap peut placer ces clés « égales » dans des seaux différents. Les recherches ultérieures peuvent alors échouer à trouver des entrées existantes, ou des insertions peuvent créer des doublons, violant le contrat sémantique de la carte d'unicité des clés.
La solution nécessite de maintenir une synchronisation bit à bit entre l'égalité et la logique de hachage. Lorsque vous personnalisez PartialEq et Eq pour ignorer certains champs (par exemple, des timestamps ou des hachages mis en cache), vous devez également exclure ces champs de l'implémentation Hash. Cela garantit que des valeurs logiques équivalentes correspondent toujours à des codes de hachage identiques, préservant l'intégrité de la collection.
Considérez un planificateur de tâches distribué où les structures Task servent de clés dans un HashMap suivant l'état d'achèvement. Chaque Task contient un id: Uuid, payload: Vec<u8> et timestamp: Instant. Au départ, à la fois Hash et Eq sont dérivés automatiquement. Cependant, les exigences changent : les tâches doivent être considérées comme égales si leur id correspond, indépendamment du payload ou du timestamp.
La première solution envisagée était de dériver les deux traits automatiquement via #[derive]. Cette approche maintenait la cohérence structurelle entre le hachage et l'égalité en incluant tous les champs, mais cela a entraîné des erreurs fonctionnelles dans la logique métier. Plus précisément, les tâches ayant des IDs identiques mais des timestamps différents étaient considérées comme des clés distinctes, empêchant les mises à jour d'état pour les tâches existantes et enflant la carte avec des entrées obsolètes.
La deuxième solution consistait à implémenter manuellement Eq pour ignorer timestamp tout en gardant le Hash dérivé. Cela semblait efficace mais a introduit un bogue critique. Deux tâches égales par ID hacheraient différemment si leurs timestamps divergeaient, provoquant un HashMap à les disperser dans des seaux non liés :
impl PartialEq for Task { fn eq(&self, other: &Self) -> bool { self.id == other.id // Ignore le timestamp } } // #[derive(Hash)] hache toujours tous les champs y compris le timestamp
Les recherches concernant l'état des tâches passeraient aléatoirement à côté des entrées existantes, conduisant à une exécution de tâches en double et à une épuisement de ressources.
La solution choisie a été l'implémentation manuelle des deux Hash et Eq, en s'assurant que les deux considéraient uniquement le champ id :
impl Hash for Task { fn hash<H: Hasher>(&self, state: &mut H) { self.id.hash(state); // Hache uniquement l'ID } }
Cela a garanti que des tâches logiquement équivalentes s'accumulaient toujours dans le même seau, permettant à HashMap d'identifier correctement les doublons par des vérifications d'égalité après une collision de hachage.
Le résultat a été un système stable où la déduplication des tâches fonctionnait correctement, éliminant l'exécution double et maintenant des temps de recherche moyens de O(1). Cette approche garantissait que le planificateur distribué pouvait suivre de manière fiable l'achèvement des tâches sans fuites de mémoire ou incohérences logiques. La correction a nécessité des tests minutieux pour vérifier que les collisions de hachage entre différents ID étaient gérées correctement par la vérification d'égalité, confirmant que la logique de partial-égalité s'intégrée parfaitement avec l'implémentation de la table de hachage de la bibliothèque standard.
Pourquoi Hash doit-il être cohérent avec Eq mais pas nécessairement avec Ord ?
La cohérence avec Eq est obligatoire car HashMap utilise le hachage pour localiser un seau et utilise ensuite l'égalité (==) pour résoudre les collisions dans ce seau. Si des éléments égaux hachent différemment, ils occupent des seaux différents, rendant la vérification de l'égalité irréelle lors de la recherche et rompant l'invariant d'unicité. Ord, cependant, définit un ordre total pour des collections triées comme BTreeMap, qui ne dépend pas du hachage mais des arbres de comparaison ; ainsi, Ord et Hash n'ont pas de relation contractuelle, et un type peut être ordonnable d'une manière incohérente avec son hachage sans compromettre la sécurité de la mémoire ou la sémantique de collection.
Que se passe-t-il si la méthode hash panique lors de l'insertion dans un HashMap ?
Si Hash panique, le HashMap se retrouve dans un état intermédiaire où la clé a été partiellement traitée mais pas complètement insérée. Contrairement à Mutex, HashMap n'implémente pas le poisoning. Cependant, l'allocation mémoire sous-jacente pour l'entrée pourrait avoir eu lieu sans que la valeur soit complètement initialisée ou liée à la chaîne de la table. Cela peut conduire à des fuites de mémoire ou, dans les cas extrêmes, à un comportement indéfini si la panique se produit lors d'une opération de ré-hachage où la table est redimensionnée. La bibliothèque standard atténue cela en utilisant des gardes de suppression et une gestion d'état soigneuse, mais le code utilisateur doit s'assurer que les implémentations Hash sont exemptes de panique pour garantir la cohérence de la collection.
Comment BuildHasher prévient-il les attaques HashDoS, et pourquoi SipHasher est-il le défaut ?
BuildHasher abstrait la création d'instances Hasher, permettant à HashMap d'instancier un nouveau hacheur avec des clés randomisées pour chaque instance de carte. L'état par défaut RandomState utilise SipHasher-1-3 (ou une variante similaire) avec des clés générées à partir de la source d'entropie du système d'exploitation. Cette randomisation empêche les attaques HashDoS où un attaquant fabrique des entrées qui hachent toutes au même seau, dégradant les recherches à O(n). En graissant chaque carte différemment, la surface d'attaque est éliminée car l'attaquant ne peut pas prédire quelles entrées vont entrer en collision. SipHasher a été choisi pour son équilibre entre la sécurité cryptographique (prévention de la récupération de clés) et la vitesse, contrairement à des algorithmes plus rapides mais vulnérables comme MurmurHash ou des hachages cryptographiques plus lents comme SHA-3.