Ch. 3 - Partie 5 - Dictionnaires

1. Du point de vue utilisateur : Interface

Nous allons maintenant étudier un autre type abstrait de données : les dictionnaires aussi appelés tableaux associatifs.

AstuceDéfinition

Un dictionnaire est une structure de données permettant d’indexer des objets par leur nom plutôt que par un nombre.

On retrouve une structure qui ressemble, à première vue, beaucoup à un tableau (à chaque élément on associe un indice de position). Mais au lieu d’associer chaque élément à un indice de position, dans un dictionnaire, on associe chaque élément (on parle de valeur dans un dictionnaire) à une clé, on dit qu’un dictionnaire contient des couples clé:valeur (chaque clé est associée à une valeur).

Un dictionnaire associe une clé à une valeur. On peut voir les tableaux comme un dictionnaire où les clés sont des entiers allant de 0 à la longueur de la liste moins 1.

Mais cela peut être bien plus général :

• les clés peuvent être des mots et les valeurs un nombre. Cela permet par exemple de compter le nombre de fois où chaque mot d’un texte apparaît ;
• associer un numéro de téléphone (valeur) à un nom (clé) sans avoir besoin d’une liste allant de 0 à numéro max de téléphone.

Les clés ne doivent pas changer une fois créées : la position d’une clé dans le dictionnaire est calculée à partir de sa valeur (par une fonction de hachage). Si la clé changeait, cette position ne serait plus valable et la clé deviendrait introuvable. On ne doit donc utiliser que des objets non modifiables (immuables) pour créer des clés d’un dictionnaire Python, comme :

• des entiers ;
• des réels ;
• des chaînes de caractères ;
• des tuples (à condition que tous leurs éléments soient eux-mêmes immuables).

Mise en gardeExemple

Exemples de couples clé:valeur :

• prenom:Kevin, nom:Durand, naissance:17-05-2005.
• prenom, nom et naissance sont des clés ; Kevin, Durand et 17-05-2005 sont des valeurs.

Les méthodes primitives permettant de définir l’interface de la structure de dictionnaire peuvent être les suivantes :

• creer() : création d’un nouveau dictionnaire vide ;
• ajouter(dict, clé, valeur) : on associe une nouvelle valeur à une nouvelle clé ;
• modifier(dict, clé, valeur) : on modifie un couple clé:valeur en remplaçant la valeur courante par une autre valeur (la clé restant identique) ;
• supprimer(dict, clé) : on supprime une clé (et donc la valeur qui lui est associée) ;
• rechercher(dict, clé) : on recherche une valeur à l’aide de la clé associée à cette valeur.

NoteCorrespondance avec le type dict de Python

Primitive du TAD	Opération Python
creer()	d = {}
ajouter(d, clé, valeur)	d[clé] = valeur
modifier(d, clé, valeur)	d[clé] = valeur
supprimer(d, clé)	del d[clé]
rechercher(d, clé)	d[clé] (ou d.get(clé))

On remarque que Python fusionne les primitives ajouter et modifier : la même instruction d[clé] = valeur crée le couple s’il n’existe pas, ou remplace la valeur sinon.

Autres opérations utiles : clé in d (test d’appartenance), d.keys(), d.values(), d.items().

Mise en gardeExemple

Soit le dictionnaire D composé des couples clé:valeur suivants : prenom:Kevin, nom:Durand, naissance:17-05-2005. Pour chaque exemple ci-dessous on repart du dictionnaire d’origine :

ajouter(D, "tel", "06060606")
modifier(D, "nom", "Dupont")
supprimer(D, "naissance")
rechercher(D, "prenom")

• Ligne 1 : le dictionnaire D est maintenant composé des couples suivants : prenom:Kevin, nom:Durand, naissance:17-05-2005, tel:06060606 ;
• Ligne 2 : le dictionnaire D est maintenant composé des couples suivants : prenom:Kevin, nom:Dupont, naissance:17-05-2005 ;
• Ligne 3 : le dictionnaire D est maintenant composé des couples suivants : prenom:Kevin, nom:Durand ;
• Ligne 4 : la fonction renvoie Kevin.

L’utilisation de la structure dictionnaire en Python a été étudiée en première. Il faut donc revoir le cours correspondant.

2. Du point de vue concepteur : Implémentation

L’implémentation du type abstrait dictionnaire est complexe et dépasse le cadre du programme de NSI. Cette implémentation utilise des fonctions de hachage.

L’utilisation des tables et des fonctions de hachage est omniprésente en informatique, il est donc utile pour votre “culture générale informatique”, de connaître le principe des fonctions de hachage. Pour avoir quelques idées sur le principe des tables de hachage, je vous recommande le visionnage de cette vidéo : les tables de hachage.

NotePrincipe d’une table de hachage

Une table de hachage repose sur une fonction de hachage h qui transforme une clé en un indice de case :

h(\text{clé}) \longrightarrow \text{indice}

Exemple très simple. On dispose d’un tableau de 10 cases et on choisit h(\text{clé}) = \text{clé} \bmod 10 (le reste de la division par 10).

Clé	h(\text{clé})	Case
42	2	2
17	7	7
25	5	5

Pour retrouver la valeur associée à la clé 42, on calcule directement h(42) = 2 et on lit la case 2 : on n’a pas parcouru tout le tableau.

Collision. Deux clés différentes peuvent donner le même indice (par exemple 42 et 12 donnent tous deux 2). On parle alors de collision. Les tables de hachage réelles gèrent ces collisions (par exemple en stockant plusieurs éléments par case).

On peut retenir que

ImportantÀ retenir

La complexité de recherche, d’ajout et de suppression d’un élément dans un dictionnaire est en \mathcal{O}(1) en moyenne : elle ne dépend pas du nombre d’éléments présents dans le dictionnaire.

Attention toutefois : dans le pire cas (nombreuses collisions), cette complexité peut dégénérer en \mathcal{O}(n).

En comparaison, la complexité de l’algorithme de recherche dans un tableau non trié est \mathcal{O}(n).

La structure de dictionnaire est donc une structure très efficace ! N’hésitez pas à l’utiliser car son temps moyen d’exécution est très rapide.