Au coeur des dictionnaires en .Net 2.0

Date de publication : 10/09/2007 , Date de mise à jour : 10/09/2007

Cet article présente une synthèse des dictionnaires du Framework .Net 2.0

Version PDF (Miroir) Version hors-ligne (Miroir)

I. Introduction
II. Présentation générale
III. La Complexité des algorithmes
IV. Les dictionnaires dans le Framework 2.0
IV-A. Introduction aux dictionnaires
IV-B. Dictionary
IV-C. SortedDictionary
IV-D. OrderedDictionary
IV-E. ListDictionary Vs Hashtable Vs HybridDictionary
IV-F. StringDictionary
IV-G. NameValueCollection
IV-H. KeyedCollection
V. Conclusion
Ressource
Remerciments

I. Introduction

Le Framework 2.0 compte parmi ses classes une grande panoplie de collections aussi diverses l'une de l'autre et conçues pour un besoin spécifique. Les développeurs .Net se trouvent fréquemment dans une situation où ils ne savent pas laquelle des collections choisir et se tournent généralement vers la plus basique d'entre elles pour arriver à leurs fins. Ce choix rapide et maladroit entraine souvent le ralentissement de l'algorithme à implémenter et aussi des effets de bords incompréhensibles et difficiles à cerner si on ne s'aperçoit pas que la collection choisie est en fait la cause des malheurs.

Le but de cet article, est d'assister le développeur à choisir le bon dictionnaire selon le cas de figure dans lequel il se trouve. Je vais traiter tout au long de cet article les avantages et les limites de chacun des dictionnaires du Framework tout en me focalisant sur les méthodes les plus intéressantes qu'offrent chacune des classes.

II. Présentation générale

Du point de vue organisationnel, les collections sont groupées en 3 namespaces :

System.Collections : ce namespace regroupe un ensemble de collections non typées permettant de stocker des données hétérogènes dans la même structure dynamique puisque la signature des méthodes accepte le type object.

System.Collections.Generics : La grande nouveauté du Framework 2.0, les generics reprennent essentiellement les collections du premier namespace en prenant en charge des données typées.

System.Collections.Specialized : comme son nom l'indique, ce namespace regroupe un ensemble de collections spécialisées qui répondent à un besoin spécifique pour un type de donnée spécifique. Contrairement aux collections du namespace System.Collections, celles du namespace Specialized sont fortement typées.

Les collections qui seront traitées dans cet article sont les suivantes :

Namespaces & Classes
System.Collections
Hashtable
System.Collections.Specialized
OrderedDictionary
StringDictionary
NameValueCollection
ListDictionary
HybridDictionary
System.Collections.Generics
Dictionnary
SortedDictionnay
System.Collection.ObjectModel
KeyedCollection

Du point de vue logique, je regrouperais les collections du Framework en 5 classes. Bien entendu une collection du Framework peut appartenir à plusieurs groupes.

Les collections basiques : Ce sont les collections à comportement basique. Elles permettent de stocker des données dynamiquement dans une structure de données en se limitant à des fonctionnalités de base telles que l'ajout, la suppression, l'énumération, etc.

Les listes séquentielles : Ces collections suivent une certaine logique d'ordre lors de l'insertion des données. Il existe deux sortes de collectons séquentielles dans le Framework 2.0 ; la pile (LIFO : Last In First Out) et la file (FIFO : First In First Out).

Les dictionnaires : Ce sont des structures dynamiques qui permettent d'emmagasiner des données sous forme de clé/valeur afin de rendre instantanée la récupération d'une valeur sachant sa clé.

Les collections spécialisées : Ce sont des structures spéciales qui représentent des comportements spécifiques applicables généralement à un type donné. Par exemple une structure qui représente une suite binaire ou une structure qui n'accepte que des types strings.

Les generics : C'est l'ensemble des collections fortement typées. Elles font parties systématiquement du namespace System.Collections.Generics.

III. La Complexité des algorithmes

Afin de comparer l'efficacité des différentes collections du Framework, nous aurons besoin d'une norme qui permettrait d'évaluer le coût d'exécution des opérations offertes par les collections. La théorie de la complexité algorithmique permet justement d'évaluer la rapidité d'exécution des tâches algorithmiques (méthodes de classes). Tout au long de cet article la complexité dans le pire des cas a été adoptée. Elle permet en fait d'évaluer les algorithmes dans le cas où les paramètres d'entrées engendrent le maximum d'itérations pour converger vers une solution.

Prenons l'exemple d'une liste chainée représentée par la structure suivante :

5	4	42	2	8	36	9	47

Dans le meilleur des cas, l'algorithme de la méthode GetAt, qui permet de récupérer une valeur à partir de son index, converge en 1 itération. Ce cas est représenté par l'appel GetAt(0). On dit que le l'algorithme dans le meilleur des cas est en O(1).

Dans le pire des cas, l'algorithme de la méthode GetAt converge en 8 itérations. Ce cas est représenté par l'appel GetAt(7). Pour généraliser, on dit que l'algorithme dans le pire des cas est en O(n), n représente la taille des entrées (taille du tableau dans notre cas).

La théorie de la complexité algorithmique utilise la notation Landau (O : grand o) pour représenter l'efficacité. En faisant abstraction des explications mathématiques, voici les différents types de complexités que l'on va rencontrer dans cet article classés du plus rapide au plus lent :

O(1) : complexité constante indépendante des paramètres d'entrées.

O(log(n)) : complexité logarithmique, le temps d'exécution croit légèrement par rapport à la taille des entrées.

O(n) : complexité proportionnelle à la longueur de l'entrée.

IV. Les dictionnaires dans le Framework 2.0

IV-A. Introduction aux dictionnaires

Les dictionnaires représentent des structures de données particulières qui permettent d'associer chaque valeur à une clé. La particularité de ce mapping est que la recherche d'une valeur par sa clé est presque instantanée et converge vers une complexité en O(1) même si dans certains cas elle peut monter jusqu'en O(n) si la fonction de hachage est mal implémentée. Cette rapidité de recherche est possible grâce aux tables de hachages sur lesquelles reposent les dictionnaires. La question qui se pose donc est : comment cette structure permet de retrouver les valeurs quasi instantanément.

En fait, une table de hachages permet d'associer à chaque clé, quelque soit son type, un entier calculé grâce à une fonction. La valeur entière représente généralement l'index de la clé dans la table et la fonction en question est appelée la fonction de hachage.

Concrètement, dans le Framework 2.0, la méthode GetHashCode représente la fonction de hachage. Le Framework dispose de l'implémentation de cette fonction pour quelques types comme le string. L'utilisation de string comme clé assure donc la performance de recherche dans la table de hachage puisque le Framework assure l'unicité de la valeur de hachage pour chaque combinaison de caractères stockée dans un string. Cette unicité empêche le cas où deux clés retournent le même code de hachage de se produire. Ce phénomène est appelé collision et est responsable de la perte de performance de la table de hachage. La méthode GetHashCode n'est pas tout le temps implémentée au niveau du Framework, certainement pas dans le cas où on veut utiliser des classes personnalisées comme clé. Dans ce cas, le développeur prend en charge l'implémentation de la fonction de hachage en surchargeant la méthode GetHashCode et en implémentant l'interface IEquatable. Ce sujet sera traité plus en détail dans la suite de l'article.

note msdn : Par exemple, l'implémentation de la méthode GetHashCode fournie par la classe String retourne des codes de hachage uniques pour des valeurs de chaîne uniques. Par conséquent, deux objets String retournent le même code de hachage s'ils représentent la même valeur de chaîne.

Prenons l'exemple du cas où on veut stocker dans un dictionnaire les noms des pilotes de formule 1 à qui on veut associer leurs totaux de points au cours de la saison.


Dictionary<string, int> lesPilotes = new Dictionary<string, int>(2);

lesPilotes.Add("Lewis Hamilton", 70);
lesPilotes.Add("Fernando Alonso", 68);

foreach (string piloteKey in lesPilotes.Keys)
{
    //afficher les clés et leurs codes de hachage
    Console.WriteLine("Clé = {0}, HashCode = {1}",
    piloteKey, piloteKey.GetHashCode());
}

//Clé = Lewis Hamilton,  HashCode = 710750954
//Clé = Fernando Alonso, HashCode = 477124616

Nous remarquons que les deux clés retournent des codes de hachages différents qui serviront à retrouver directement le score correspondant au nom du pilote.

IV-B. Dictionary

La classe Dictionary et la plus basique des génériques dans le contexte des structures en clé/valeur. Elle correspond à la classe hashtable (table de hachage) des collections de base. Nous allons voir dans ce qui suit les possibilités d'insertion et de suppression dans la classe Dictionary et son comportement après ces opérations.

Quand faut-il choisir la classe Dictionary ?
Collection typée qui stocke des listes de clé/valeur ; l'identification des clés similaires se fait en implémentant, la classe qui représente la clé, l'interface IEquatable. Il est possible aussi de passer une classe qui implémente IEqualityComparer lors de la construction de la collection. N'autorise pas les clés doublons. Rapide : accès et suppression en O(1)

Manipulation d'un dictionnaire


//Initialiser la taille pour gagner en performance.
Dictionary<string, string> lesPilotes = new Dictionary<string, string>(10);

//Initialiser le dictionnaire
lesPilotes.Add("L. Hamilton", " McLaren Mercedes");
lesPilotes.Add("F. Alonso", " McLaren Mercedes");
lesPilotes.Add("F. Massa", "Ferrari");
lesPilotes.Add("K. Räikkönen", "Ferrari");
lesPilotes.Add("N. Heidfeld", "BMW Sauber");
lesPilotes.Add("R. Kubica", "BMW Sauber");
lesPilotes.Add("G. Fisichella", "Renault");
lesPilotes.Add("H. Kovalainen", "Renault");
lesPilotes.Add("A. Wurz", "Williams");
lesPilotes.Add("M. Webber", "Red Bull");

//lesPilotes.

Afficher(lesPilotes);
// 1 - Pilote : L. Hamilton , Ecurie :  McLaren Mercedes
// 2 - Pilote : F. Alonso , Ecurie :  McLaren Mercedes
// 3 - Pilote : F. Massa , Ecurie : Ferrari
// 4 - Pilote : K. Räikkönen , Ecurie : Ferrari
// 5 - Pilote : N. Heidfeld , Ecurie : BMW Sauber
// 6 - Pilote : R. Kubica , Ecurie : BMW Sauber
// 7 - Pilote : G. Fisichella , Ecurie : Renault
// 8 - Pilote : H. Kovalainen , Ecurie : Renault
// 9 - Pilote : A. Wurz , Ecurie : Williams
// 10 - Pilote : M. Webber , Ecurie : Red Bull

//Exception "ArgumentNullException" levée lors de l'ajout d'une clé nulle
try
{
   lesPilotes.Add(null, "Ferrari");
}
catch (ArgumentNullException ex)
{
   Console.WriteLine(System.Environment.NewLine + ex.Message);
   //Value cannot be null.
   //Parameter name: key
}

//l'ajout d'une valeur null autorisé
lesPilotes.Add("M. Fekih", null);

//Exception "ArgumentException" levée lors de l'ajout d'une clé existante
try
{
   lesPilotes.Add("L. Hamilton", " McLaren Mercedes");
}
catch (ArgumentException ex)
{

   Console.WriteLine(System.Environment.NewLine + ex.Message + System.Environment.NewLine);
   //An item with the same key has already been added.
}

//Supprimer des entrées
lesPilotes.Remove("K. Räikkönen");
lesPilotes.Remove("G. Fisichella");

//Afficher des pilotes
Afficher(lesPilotes);

// 1 - Pilote : L. Hamilton , Ecurie :  McLaren Mercedes
// 2 - Pilote : F. Alonso , Ecurie :  McLaren Mercedes
// 3 - Pilote : F. Massa , Ecurie : Ferrari
// 4 - Pilote : N. Heidfeld , Ecurie : BMW Sauber
// 5 - Pilote : R. Kubica , Ecurie : BMW Sauber
// 6 - Pilote : H. Kovalainen , Ecurie : Renault
// 7 - Pilote : A. Wurz , Ecurie : Williams
// 8 - Pilote : M. Webber , Ecurie : Red Bull
// 9 - Pilote : M. Fekih , Ecurie :

Dans l'exemple précédent, des strings ont été utilisé comme clé. Le Framework reconnait deux strings identiques grâce à l'implémentation de GetHashCode. Dans ce qui suit nous allons voir comment utiliser une classe personnalisée ( custom class ) comme clé.

Tout d'abord, il faut comprendre comment le dictionnaire du Framework .Net fonctionne pour reconnaitre deux clés identiques. Le principe reste le même, le dictionnaire va calculer la valeur de hachage de la classe et va essayer de retrouver la même valeur dans les clés déjà utilisées dans la table de hachage. Si le dictionnaire ne trouve aucune clé alors il va pourvoir insérer la valeur sans se soucier de la redondance. Dans l'autre cas où le dictionnaire retrouve la même valeur de hachage. Il va vérifier si les deux instances de la classe qui représente la clé sont égaux. Pour cela, il va donc utiliser la méthode Equals.

On va donc dans le code suivant changer la définition de notre classe Pilote en implémentant la classe générique IEquatable et en surchargeant la méthode GetHashCode.

L'interface IEquatable


public class Pilote
{
    private string nom;

    public string Nom
    {
        get { return nom; }
        set { nom = value; }
    }

    private string prenom;

    public string Prenom
    {
        get { return prenom; }
        set { prenom = value; }
    }

    public Pilote(string prenom, string nom)
    {
        this.Nom = nom;
        this.Prenom = prenom;
    }

    public override string ToString()
    {
        return string.Concat(this.Prenom, " ", this.Nom);
    }
}
    
public class PiloteEquatable : Pilote, IEquatable<PiloteEquatable>
{

    public PiloteEquatable(string prenom, string nom)
        : base(prenom, nom)
    {

    }

    public override int GetHashCode()
    {
        Trace.WriteLine(" GetHashCode appelé ");
        return string.Concat(this.Prenom, " ", this.Nom).GetHashCode();
    }

    public bool Equals(PiloteEquatable other)
    {
        Trace.WriteLine(" Equals Appelé");
        return this.Nom.Equals(other.Nom) && this.Prenom.Equals(other.Prenom);
    }

    public override bool Equals(object obj)
    {
        return Equals((PiloteEquatable)obj);
    }
}
    
public static class DictionaryDemo
{
    public static void ExecuteIEquatable()
    {
        Dictionary<Pilote, string> lesPilotes = new Dictionary<Pilote, string>(3);

        //Essayer d'inserer deux pilotes identiques sans l'implementation de IEquatable
        lesPilotes.Add(new Pilote("Lewis", "Hamilton"), " McLaren Mercedes");
        lesPilotes.Add(new Pilote("Fernando", "Alonso"), " McLaren Mercedes");
        lesPilotes.Add(new Pilote("Lewis", "Hamilton"), " McLaren Mercedes");

        //1 - Pilote : Lewis Hamilton , Ecurie :  McLaren Mercedes
        //2 - Pilote : Fernando Alonso , Ecurie :  McLaren Mercedes
        //3 - Pilote : Lewis Hamilton , Ecurie :  McLaren Mercedes

        //ça fonctionne ; le dictionnaire ne detecte pas le même pilote
        Afficher(lesPilotes);

        Dictionary<PiloteEquatable, string> lesPilotesEquatable = new Dictionary<PiloteEquatable, string>(5);

        lesPilotesEquatable.Add(new PiloteEquatable("Lewis", "Hamilton"), " McLaren Mercedes");
        lesPilotesEquatable.Add(new PiloteEquatable("Fernando", "Alonso"), " McLaren Mercedes");

        try
        {
            lesPilotesEquatable.Add(new PiloteEquatable("Lewis", "Hamilton"), " McLaren Mercedes");
        }
        catch (ArgumentException ex)
        {
            Console.WriteLine(System.Environment.NewLine + ex.Message);

            //Ajouter une nouvelle fois Lewis Hamilton :
            //GetHashCode appelé
        	//Equals Appelé 

            //Le dictionnaire detecte deux hashcode identitiques => GetHashCode appelé
            //Il va donc comparer les instaces grâce à Equals => Equals appelé

            //An item with the same key has already been added.
        }


        Console.WriteLine(lesPilotesEquatable.ContainsKey(new PiloteEquatable("Fernando", "Alonso"))); // True

        lesPilotesEquatable.Remove(new PiloteEquatable("Fernando", "Alonso"));
    }
}

IV-C. SortedDictionary

La SortedDictionary est une implémentation particulière de la classe Dictionary précédente. Elle a la particularité d'ordonner les clés de sa table selon une logique définie par l'utilisateur. Cette prise en charge de l'ordonnancement influe sur les performances de la collection.

Quand faut-il choisir la classe SortedDictionary ?

Collection typée qui stocke des listes de clé/valeur ordonnées par les clés ; la classe représentant la clé doit implémenter l'interface IComparable. Dans le cas échéant, l'utilisateur peut passer une classe qui implémente IComparer lors de la construction de la collection.
N'autorise pas les clés doublons.
Plus lente que la Dictionary : Insertion et suppression en O(log(n))

Pour la détection des clés similaires, la SortedDictionary se base sur la méthode CompareTo, membre de l'interface IComparable. Cette méthode est appelée systématiquement lors de l'ajout, suppression et recherche de clés, d'où la perte de performance constatée par rapport à la classe Dictionary.

Par exemple, si on utilise un type primitif du Framework tel que le string, la collection va automatiquement ordonner les éléments selon l'ordre alphabétique.

Manipulation simple d'une SortedDictionary


SortedDictionary<string,string> lesPilotes=new SortedDictionary<string,string>();

lesPilotes.Add("L. Hamilton", "McLaren Mercedes");
lesPilotes.Add("F. Alonso", "McLaren Mercedes");
lesPilotes.Add("F. Massa", "Ferrari");
lesPilotes.Add("K. Räikkönen", "Ferrari");
lesPilotes.Add("N. Heidfeld", "BMW Sauber");
lesPilotes.Add("R. Kubica", "BMW Sauber");
lesPilotes.Add("G. Fisichella", "Renault");
lesPilotes.Add("H. Kovalainen", "Renault");
lesPilotes.Add("A. Wurz", "Williams");
lesPilotes.Add("M. Webber", "Red Bull");

Afficher(lesPilotes);
 //1 - Pilote : A. Wurz , Ecurie : Williams
 //2 - Pilote : F. Alonso , Ecurie : McLaren Mercedes
 //3 - Pilote : F. Massa , Ecurie : Ferrari
 //4 - Pilote : G. Fisichella , Ecurie : Renault
 //5 - Pilote : H. Kovalainen , Ecurie : Renault
 //6 - Pilote : K. Räikkönen , Ecurie : Ferrari
 //7 - Pilote : L. Hamilton , Ecurie : McLaren Mercedes
 //8 - Pilote : M. Webber , Ecurie : Red Bull
 //9 - Pilote : N. Heidfeld , Ecurie : BMW Sauber
 //10 - Pilote : R. Kubica , Ecurie : BMW Sauber
}

public static void ExecuteIEquatable()
{
SortedDictionary<PiloteComparable, string> lesPilotes = new SortedDictionary<PiloteComparable, string>();

//Dans le cas d'une classe personnalisée, il faut impérativement implementer IComparable
lesPilotes.Add(new PiloteComparable("Lewis", "Hamilton"), "McLaren Mercedes");


//la duplication est detectée par CompareTo et non pas par Equals et GetHashCode
try
{
    lesPilotes.Add(new PiloteComparable("Lewis", "Hamilton"), "McLaren Mercedes");
}
catch (ArgumentException ex)
{

    Console.WriteLine(System.Environment.NewLine + ex.Message + System.Environment.NewLine);
    //An entry with the same key already exists.
}

lesPilotes.Add(new PiloteComparable("Fernando", "Alonso"), "McLaren Mercedes");
lesPilotes.Add(new PiloteComparable("Felipe", "Massa"), "Ferrari");
lesPilotes.Add(new PiloteComparable("Kimi", "Räikkönen"), "Ferrari");
lesPilotes.Add(new PiloteComparable("Nick", "Heidfeld"), "BMW Sauber");
lesPilotes.Add(new PiloteComparable("Robert", "Kubica"), "BMW Sauber");
lesPilotes.Add(new PiloteComparable("Giancarlo", "Fisichella"), "Renault");
lesPilotes.Add(new PiloteComparable("Heikki", "Kovalainen"), "Renault");
lesPilotes.Add(new PiloteComparable("Alexander", "Wurz"), "Williams");
lesPilotes.Add(new PiloteComparable("Mark", "Webber"), "Red Bull");

Afficher(lesPilotes);
//1 - Pilote : Alexander Wurz , Ecurie : Williams
//2 - Pilote : Felipe Massa , Ecurie : Ferrari
//3 - Pilote : Fernando Alonso , Ecurie : McLaren Mercedes
//4 - Pilote : Giancarlo Fisichella , Ecurie : Renault
//5 - Pilote : Heikki Kovalainen , Ecurie : Renault
//6 - Pilote : Kimi Räikkönen , Ecurie : Ferrari
//7 - Pilote : Lewis Hamilton , Ecurie : McLaren Mercedes
//8 - Pilote : Mark Webber , Ecurie : Red Bull
//9 - Pilote : Nick Heidfeld , Ecurie : BMW Sauber
//10 - Pilote : Robert Kubica , Ecurie : BMW Sauber


//ContainsKey utilise que CompareTo 
Console.WriteLine(lesPilotes.ContainsKey(new PiloteComparable("Robert", "Kubica")));
//True

//Remove utilise que CompareTo
lesPilotes.Remove(new PiloteComparable("Giancarlo