GetHashCode et Equals : pourquoi leur redéfinition est cruciale en C#

Introduction : cette erreur qui ralentit votre code

Quiconque a déjà écrit en C# et rencontré Dictionary ou HashSet est tôt ou tard tombé sur cette question sur Stack Overflow. Des milliers de vues, des dizaines de réponses, mais le fond est le même : si vous avez redéfini Equals dans votre classe sans penser à GetHashCode, votre code peut fonctionner incorrectement ou être terriblement lent. Pourquoi ? Analysons cela avec des exemples concrets.

Imaginez que vous développez un système de réservation de billets d'avion. Vous avez une classe Flight avec un numéro de vol unique et une date. Vous souhaitez utiliser cette classe comme clé dans un Dictionary. Cela semble simple. Mais sans un GetHashCode correct, votre dictionnaire peut se transformer en une liste dégénérée avec une vitesse de recherche en O(n) au lieu de O(1).

La magie des tables de hachage : comment fonctionne Dictionary en C#

Pour comprendre le problème, il faut regarder sous le capot de Dictionary. En interne, il s'agit d'un tableau de "seaux" (buckets). Lorsque vous ajoutez un élément, C# appelle la méthode GetHashCode() sur la clé pour déterminer le numéro du seau. Si le seau contient déjà des éléments, Equals() est appelé pour comparer avec chacun d'eux. C'est ce tandem qui assure une recherche fulgurante.

Le contrat à ne pas violer

En C#, il existe un contrat tacite mais strict :

\n
• Si Equals() retourne true pour deux objets, leurs codes de hachage doivent être égaux.
\n
• Si les codes de hachage sont différents, Equals() ne sera jamais appelé (c'est une optimisation).
\n
• L'inverse n'est pas obligatoire : des objets différents peuvent avoir le même code de hachage (collision).
\n

Lorsque vous redéfinissez uniquement Equals sans GetHashCode, vous héritez de l'implémentation de System.Object, qui est basée sur la référence mémoire. Deux objets "égaux" selon votre logique auront des codes de hachage différents. Et c'est là que l'enfer commence.

Exemple du problème : des vols perdus dans le dictionnaire

Regardez ce code. Il semble devoir fonctionner, mais il ne fonctionne pas :

public class Flight\n{\n    public string FlightNumber { get; }\n    public DateTime Date { get; }\n\n    public Flight(string flightNumber, DateTime date)\n    {\n        FlightNumber = flightNumber;\n        Date = date;\n    }\n\n    public override bool Equals(object obj)\n    {\n        if (obj is Flight other)\n            return FlightNumber == other.FlightNumber && Date == other.Date;\n        return false;\n    }\n    \n    // GetHashCode n'est PAS redéfini !\n}\n\n// Utilisation\nvar flights = new Dictionary<Flight, string>();\nvar f1 = new Flight("SU100", new DateTime(2024, 12, 25));\nvar f2 = new Flight("SU100", new DateTime(2024, 12, 25));\n\nflights[f1] = "Moscou - Paris";\n\n// Erreur ! f2 n'est pas trouvé, bien que f1.Equals(f2) == true\nConsole.WriteLine(flights.ContainsKey(f2)); // False

Pourquoi cela ? f1 et f2 sont des objets différents en mémoire. Ils ont des codes de hachage différents provenant de Object.GetHashCode(). Le dictionnaire place f1 dans le seau n°123 et cherche f2 dans le seau n°456. Equals n'est même pas appelé ! Résultat : l'élément n'est pas trouvé.

Problème de performance : quand tout fonctionne, mais lentement

Le pire est une solution partielle. Supposons que vous ayez redéfini GetHashCode, mais mal fait, par exemple en retournant une constante :

public override int GetHashCode() => 42; // Tous les objets dans le même seau

Formellement, le contrat est respecté (les objets égaux ont le même hachage). Mais les performances s'effondrent : tous les objets tombent dans le même seau, et le Dictionary dégénère en liste. L'insertion et la recherche deviennent O(n). Pour un dictionnaire de 10 000 éléments, c'est une catastrophe.

Comment redéfinir correctement GetHashCode ?