Dictionary<TKey, TValue> et IEquatable<TKey>

Aujourd’hui, un article pour expliquer un comportement un peu spécial dans les dictionnaires génériques de .NET. Imaginons que, pour une fonctionnalité particulière, vous ayez besoin d’un dictionnaire qui utilise une clé composite, dont la structure contient plusieurs chaînes.

Souvent, il est possible d’utiliser un séparateur et de revenir à une seule chaîne, mais ce n’est pas toujours le cas. On pourrait utiliser également un tuple, mais supposons pour notre étude que vous ayez besoin d’un nombre non déterminé à l’avance. Nous pourrions donc écrire le code de test suivant, avec dans l’exemple un dictionnaire avec la clé composite basée sur une liste de chaînes, et la valeur étant un decimal :

using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TestDicoIEquatable
{
    [TestClass]
    public class TestCleListe
    {
        private Dictionary<List<string>, decimal> Dico = new Dictionary<List<string>, decimal>();

        [TestInitialize]
        public void Initialisation()
        {
            List<string> Cle = new List<string>() { "2012", "A" };
            Dico.Add(Cle, 2501.56M);
        }

        [TestMethod]
        public void TestCleSimilaire()
        {
            List<string> Cle = new List<string>() { "2012", "A" };
            Assert.AreEqual(2501.56M, Dico[Cle]);
        }
    }
}

Ce code plante avec l’erreur suivante :

La méthode de test TestDicoIEquatable.TestCleListe.TestCleSimilaire a levé une exception :
System.Collections.Generic.KeyNotFoundException: La clé donnée était absente du dictionnaire.

Que se passe-t-il ? Il semblerait que le fait de reconstruire une clé, même si son contenu est similaire, ne suffise pas à ce que le dictionnaire soit capable de la localiser. Il n’y a pas égalité entre les deux versions de la clé de notre test. A supposer que nous transformions les List<string> en string[], le problème reste le même.

Un coup d’oeil dans la documentation nous apprend, je cite, que :

Dictionary<TKey, TValue> requiert l’implémentation d’une égalité pour déterminer si les clés sont égales.Vous pouvez spécifier une implémentation de l’interface générique IEqualityComparer<T> en utilisant un constructeur qui accepte un paramètre comparer ; si vous ne spécifiez pas d’implémentation, le comparateur générique d’égalité par défaut EqualityComparer<T>.Default est utilisé.Si le type TKey implémente l’interface générique System.IEquatable<T>, le comparateur d’égalité par défaut utilise cette implémentation.

Voilà a priori la raison de l’échec du test : les classes que nous utilisions n’implémentaient pas IEquatable<TKey>, et l’implémentation par défaut du EqualityComparer<T> ne devait pas faire l’affaire. Qu’à cela ne tienne, nous allons donc implémenter ce qu’il faut dans une classe dédiée pour TKey :

using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TestDicoIEquatable
{
    [TestClass]
    public class TestCleIEquatable
    {
        public class CleComposite : IEquatable<CleComposite>
        {
            private string[] _Valeurs;

            public CleComposite(string[] valeurs)
            {
                this._Valeurs = valeurs;
            }

            public bool Equals(CleComposite other)
            {
                if (other._Valeurs.Length != this._Valeurs.Length) return false;
                for (int i = 0; i < other._Valeurs.Length; i++)
                    if (other._Valeurs[i] != this._Valeurs[i]) return false;
                return true;
            }
        }

        private Dictionary<CleComposite, decimal> Dico = new Dictionary<CleComposite, decimal>();

        [TestInitialize]
        public void Initialisation()
        {
            CleComposite Cle = new CleComposite(new string[] { "2012", "A" });
            Dico.Add(Cle, 2501.56M);
        }

        [TestMethod]
        public void TestCleSimilaire()
        {
            CleComposite Cle = new CleComposite(new string[] { "2012", "A" });
            Assert.AreEqual(2501.56M, Dico[Cle]);
        }
    }
}

Surprise : ça ne marche toujours pas, et on a toujours la même erreur comme quoi la clé est absente du dictionnaire !

Après un peu de recherche (et en particulier, la lecture de cet excellent article de JaredPar), la solution est d’implémenter la surcharge Object.Equals ainsi bien sûr que celle de Object.GetHashCode. Dans cet exemple, je pointe simplement Object.Equals sur IEquatable<T>.Equals, et j’implémente Object.GetHashCode avec une méthode simplissime, à savoir prendre le hash de la concaténation de toutes les chaînes représentant les valeurs de la clé composite. Au final, le code suivant fonctionne :

using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TestDicoIEquatable
{
    [TestClass]
    public class TestCleIEquatable
    {
        public class CleComposite : IEquatable<CleComposite>
        {
            private string[] _Valeurs;

            public CleComposite(string[] valeurs)
            {
                this._Valeurs = valeurs;
            }

            public bool Equals(CleComposite other)
            {
                if (other._Valeurs.Length != this._Valeurs.Length) return false;
                for (int i = 0; i < other._Valeurs.Length; i++)
                    if (other._Valeurs[i] != this._Valeurs[i]) return false;
                return true;
            }

            public override bool Equals(object obj)
            {
                return this.Equals(obj as CleComposite);
            }

            public override int GetHashCode()
            {
                return string.Join(string.Empty, this._Valeurs).GetHashCode();
            }
        }

        private Dictionary<CleComposite, decimal> Dico = new Dictionary<CleComposite, decimal>();

        [TestInitialize]
        public void Initialisation()
        {
            CleComposite Cle = new CleComposite(new string[] { "2012", "A" });
            Dico.Add(Cle, 2501.56M);
        }

        [TestMethod]
        public void TestCleSimilaire()
        {
            CleComposite Cle = new CleComposite(new string[] { "2012", "A" });
            Assert.AreEqual(2501.56M, Dico[Cle]);
        }
    }
}

A noter que la documentation spécifie bien ce besoin d’implémentation, mais malheureusement pas dans la page de Dictionary<TKey, TValue>, ce qui est un peu gênant.

En espérant que ça serve à quelqu’un !