Dot.Blog

C#, XAML, Xamarin, UWP/Android/iOS

De l'intérêt d'overrider GetHashCode()

Les utilisateurs de Resharper ont la possibilité en quelques clics de générer un GetHashCode() et d'autres méthodes comme les opérateurs de comparaison pour toute classe en cours d'édition. Cela est extrêment pratique et utile à plus d'un titre. Encore faut-il avoir essayer la fonction de Resharper et s'en servir à bon escient... Mais pour les autres, rien ne vient vous rappeler l'importance de telles fonctions. Pourtant elles sont essentielles au bon fonctionnement de votre code !

GetHashCode()

Cette méthode est héritée de object et retourne une valeur numérique sensée être unique pour une instance. Cette unicité est toute relative et surtout sa répartition dans le champ des valeurs possibles est inconnue si vous ne surchargez pas GetHashCode() dans vos classes et structures ! Il est en effet essentiel que le code retourné soit en rapport direct avec le contenu de la classe / structure. Deux instances ayant des valeurs différentes doivent retourner un hash code différent. Mieux, ce hash code doit être représentatif et générer le minimum de collisions...

Si vous utilsez un structure comme clé d'une Hashtable par exemple, vous risquez de rencontrer des problèmes de performances que vous aurez du mal à vous expliquer si vous n'avez pas conscience de ce que j'expose ici...
Je ne vous expliquerais pas ce qu'est un hash code ni une table Hashtable, mais pour résumer disons qu'il s'agit de créer des clés représentant des objets, clés qui doivent être "harmonieusement" réparties dans l'espace de la table pour éviter les collisions. Car en face des codes de hash, il y a la table qui en interne ne gère que quelques entrées réelles. S'il y a collision, elle chaîne les valeurs.
Moralité, au lieu d'avoir un accès 1->1 (une code hash correspond à une case du tableau réellement géré en mémoire) on obtient plutôt n -> 1, c'est à dire plusieurs valeurs de hash se partageant une même entrée, donc obligation de les chaîner, ce que fait la Hashtable de façon transparente mais pas sans conséquences !

Il découle de cette situation que lorsque vous programmez un accès à la table de hash, au lieu que l'algorithme (dans le cas idéal 1->1) tombe directement sur la cellule du tableau qui correspond à la clé (hash code), il est obligé de parcourir par chaînage avant toutes les entrées correspondantes... De là une dégration nette des performances alors qu'on a généralement choisi une Hashtable pour améliorer les performances (au lieu d'une simple liste qu'il faut balayer à chaque recherche). On a donc, sans trop le savoir, recréé une liste qui est balayée là où on devrait avoir des accès directs...

La solution : surcharger GetHashCode()

Il existe plusieurs stratégies pour générer un "bon" hash code. L'idée étant de répartir le plus harmonieusement les valeurs de sorties dans l'espace de la table pour éviter, justement, les collisions de clés. Ressortez vos cours d'informatique du placard, vous avez forcément traité le sujet à un moment ou un autre ! Pour les paresseux et ceux qui n'ont pas eu de tels cours, je ne me lancerais pas dans la théorie mais voici quelques exemples d'implémentations de GetHashCode() pour vous donner des idées :

La méthode "bourrin"

Quand on ne comprends pas forcément les justifications et raisonnements mathématiques d'un algorithme, le mieux est de faire simple, on risque tout autant de se tromper qu'en faisant compliqué, mais au moins c'est facile à mettre en oeuvre et c'est facile à maintenir :-)

Imaginons une structure simple du genre :

public struct MyStruct
{
   
public int Entier { get; set; }
   
public string Chaine { get; set; }
   
public DateTime LaDate { get; set; }
}

Ce qui différencie une instance d'une autre ce sont les valeurs des champs. Le plus simple est alors de construire une "clé" constituée de toutes les valeurs concaténées et séparées par un séparateur à choisir puis de laisser le framework calculer le hash code de cette chaîne. Toute différence dans l'une des valeurs formera une chaine-clé différente et par conséquence un hash code différent. Ce n'est pas super subtile, mais ça fonctionne. Regardons le code :

public string getKey()
{
return Entier + "|" + Chaine + "|" + LaDate.ToString("yyyyMMMddHHmmss"); } public override int GetHashCode() {return getKey().GetHashCode(); }

J'ai volontairement séparé la chose en deux parties en créant une méthode getKey pour pouvoir l'afficher.

La sortie (dans un foreach) de la clé d'un exemple de 5 valeurs avec leur hash code donne :

1|toto|2008juil.11171952 Code: -236695174
10|toto|2008juil.11171952 Code: -785275536
100|zaza|2008juil.01171952 Code: -684875783
0|kiki|2008sept.11171952 Code: 888726335
0|jojo|2008sept.11171952 Code: 1173518366 

La méthode Resharper

Ce merveilleux outil se propose de générer pour vous la gestion des égalités et du GetHashCode, laissons-le faire et regardons le code qu'il propose (la structure a été au passage réécrite, les propriétés sont les mêmes mais elles utilisent des champs privés) :

D'abord le code de hachage :

public override int GetHashCode()
{
   unchecked
   {
      int result = entier;
      result = (result*397) ^ (chaine !=
null ? chaine.GetHashCode() : 0);
      result = (result*397) ^ laDate.GetHashCode();
      return result;
   }
}

On voit ici que les choix algorithmiques pour générer la valeur sont un peu plus subtiles et qu'ils ne dépendent pas de la construction d'une chaîne pour la clé (ce qui est consommateur de temps et de ressource).

Profitons-en pour regarder comment le code gérant l'équalité a été généré (ainsi que le support de l'interface IEquatable<MyStruct> qui a été ajouté à la définition de la structure)  - A noter, la génération de ce code est optionnel - :

public static bool operator ==(MyStruct left, MyStruct right)
{
return left.Equals(right); }

public static bool operator !=(MyStruct left, MyStruct right)
{
return !left.Equals(right); }

public bool Equals(MyStruct obj)
{ return obj.entier == entier && Equals(obj.chaine, chaine) && obj.laDate.Equals(laDate); }

public override bool Equals(object obj)
{
   
if (obj.GetType() != typeof(MyStruct)) return false;
    return Equals((MyStruct)obj);
}

Bien que cela soit optionel et n'ait pas de rapport direct avec GethashCode, on notera l'intérêt de la redéfinition de l'égalité et des opérateurs la gérant ainsi que le support de IEquatable. Une classe et encore plus une structure se doivent d'implémenter ce "minimum syndical" pour être sérieusement utilisables. Sinon gare aux bugs difficiles à découvrir (en cas d'utilisation d'une égalité même de façon indirecte) !

De même tout code correct se doit de surcharger ToString(), ici on pourrait simplement retourner le champ LaChaine en supposant qu'il s'agit d'un nom de personne ou de chose, d'une description. Tout autre retour est possible du moment que cela donne un résultat lisible. Ce qui est très pratique si vous créez une liste d'instances et que vous assignez cette liste à la propriété DataSource d'un listbox ou d'une combo... Pensez-y !

Conclusion

Créer des classes ou des structures, si on programme sous C# on en a l'habitude puisque aucun code ne peut exister hors de telles constructions. Mais "bien" construire ces classes et structures est une autre affaire. Le framework propose notamment beaucoup d'interfaces qui peuvent largement améliorer le comportement de votre code. Nous avons vu ici comment surcharger des méthodes héritées de object et leur importance, nous avons vu aussi l'interface IEquatable. IDisposable, INotityPropertyChanged, ISupportInitialize, et bien d'autres sont autant d'outils que vous pouvez (devez ?) implémenter pour obtenir un code qui s'intègre logiquement au framework et en tire tous les bénéfices.

Bon dev, et Stay Tuned !

blog comments powered by Disqus