Hachage, Equals et GetHashCode …













Je pense que tout programmeur C# et Java qui se respecte, dois au minimum connaitre toute les méthodes de la classe Object et comprendre à quoi elles servent.
Pourtant assez fréquemment, quand je fais passer des entretiens, je me retrouve en face de candidats qui sont un peu court sur ce sujet.

Simulation d’entretien

C’est pourquoi aujourd’hui, je vais vous retranscrire la discution que j’attendrais sur les méthodes Equals et GetHashCode.

On commence donc soft avec une question générale:

Quelles sont les structures de donnée fournie par le framework?

Dans le flot de réponse, j’espère entendre une structure basée sur une table de hashage (HashSet, Dictionary en C#, HashMap, HashSet en Java).
Je passe sur les questions sur les temps d’accès.

Comment marche une table de Hashage?

Pour simplifier:
Elle se base sur un tableau simple (accessible par indice), lors d’une insertion d’un élément, on calcule son hashcode (la classe Object possède la méthode GetHashCode()), le hashcode modulo la taille du tableau (capacity) donnera l’indice a insérer.
Du coup quand on voudra accéder a cet objet, on récupérera seulement la valeur dans le tableau a l’indice du modulo de son hashCode.

Et si deux objects ont le même hashCode?

En pratique, On ne garde pas seulement l’objet dans chaque case du tableau. On garde une liste d’objets.
Du coup, pour retrouver notre objet, on récupère la liste stockée à l’indice du hashcode et on itère sur les éléments.
Pour retrouver le bon, on appelle la méthode Equals (la classe Object possède cette méthode) pour s’arrêter sur le bon élément de la liste.

Quelles sont du coup principales règles lorsqu’on redéfinit les deux méthode?

1 : un même objet doit toujours retourner le même HashCode (hashCode immuable)*.
2 : si deux objets sont égaux, alors ils doivent avoir le même hash code.
Corollaire : si deux objet ont un hashCode différent, alors ils ne sont pas égaux.

Merci vous êtes engages.

Je déconne bien sur, le point « structure de donnée » n’est qu’un point parmi une vingtaine à vérifier en entretien.

* Resharper vous donne d’ailleurs le hint suivant si vous tentez d’utiliser un champ qui n’est pas en lecture seule : « non-ReadOnly field referenced in GetHashCode ».

Pourquoi ces deux règles sont si importantes?

Example en cas de violation des regles 1 et 2:

 
using System.Collections.Generic;
using NUnit.Framework;
 
namespace MyNameSpace
{
    /// <summary>
    /// Je brise les regles!
    /// </summary>
    [TestFixture]
    public class MyTests
    {
        /// <summary>
        /// Tests lorsque je brise la regle 1
        /// </summary>
        [Test]
        public void BreakFirstRule()
        {
            ObjectWithHashCodeChanging a = new ObjectWithHashCodeChanging() { Id = 1 };
            ObjectWithHashCodeChanging b = new ObjectWithHashCodeChanging() { Id = 1 };
            HashSet<ObjectWithHashCodeChanging> h = new HashSet<ObjectWithHashCodeChanging>();
            h.Add(a);
            Assert.IsTrue(h.Contains(a));
            Assert.IsTrue(h.Contains(b));
            a.Id = 2;
            //Faux! car dans le bucket 1, le seul objet a comme Id 2 (c'est a).
            Assert.IsTrue(h.Contains(b));
            //Faux! car dans le bucket 2, Il n'y a rien!!!!!
            Assert.IsTrue(h.Contains(a));
        }
 
        /// <summary>
        /// Tests lorsque je brise la regle 2
        /// </summary>
        [Test]
        public void BreakSecondRule()
        {
            ObjectWithEquals a = new ObjectWithEquals() { Id = 1 };
            HashSet<ObjectWithEquals> h = new HashSet<ObjectWithEquals>();
            h.Add(a);
            Assert.IsTrue(h.Contains(a));
 
            //Je veux chercher dans ma structure si il y a un element avec un Id =1:
            //Je cree un objet pour la recherche:
            ObjectWithEquals b = new ObjectWithEquals() { Id = 1 };
            Assert.AreEqual(a, b);
            //Je ne trouve plus mon element, ou est-il!!!??
 
            Assert.IsTrue(h.Contains(b));
        }
    }
 
 
 
    /// <summary>
    /// Petit objet innocent qui est entierement defini par son Id.
    /// </summary>
    internal class ObjectWithHashCodeChanging
    {
        public int Id;
        public override bool Equals(object obj)
        {
            var objectWithHashCodeChangingObj = obj as ObjectWithHashCodeChanging;
            if (objectWithHashCodeChangingObj == null)
            {
                return false;
            }
            return objectWithHashCodeChangingObj.Id == this.Id;
        }
 
        public override int GetHashCode()
        {
            return Id;
        }
    }
 
    /// <summary>
    /// Petit objet innocent il est definit par sont Id et sa version.
    /// Je me fou un peu de la version alors j'ai retire du equals la version sans toucher au GetHashCode.
    /// (Pourquoi toucher cette fonction, je ne sais meme pas a quoi elle sert!)
    /// </summary>
    internal class ObjectWithEquals
    {
        public int Id;
 
        public override bool Equals(object obj)
        {
            var objectWithEquals = obj as ObjectWithEquals;
            if (objectWithEquals == null)
            {
                return false;
            }
            return objectWithEquals.Id == this.Id;
        }
    }
}

A lire pour aller plus loin : http://blogs.msdn.com/b/ericlippert/archive/2011/02/28/guidelines-and-rules-for-gethashcode.aspx

Comments are closed.