Un dictionnaire est une structure de données permettant le stockage tout comme les tableaux et les listes chaînées. Mais contrairement aux tableaux, les éléments d’un dictionnaires ne sont pas identifiés à l’aide d’un indixe mais à l’aide d’une clé.

Un dictionnaire est donc un ensemble de {clé : valeur}.

I. Description

1. Interface

En tant que structure de stockage, le dictionnaire doit implémenter les opérations suivantes :

• ajouter : ajouter une nouvelle paire clé : valeurs au dictionnaire
• modifier : modifier la valeur associée à une clé. Il n’est pas possible de modifier la clé (on doit la supprimer et en créer une nouvelle)
• supprimer : supprimer la clé (et donc la valeur qui lui est associée)
• rechercher : rechercher une valeur à partir d’une clé

On retrouve les méthodes classiques déjà rencontrées dans les listes chaînées. La différence peut se faire sur la complexité :

• chercher une valeur dans une liste chaînée est en complexité linéaire \(O(n)\) : il faut lire toutes les valeurs jusqu’à trouver la bonne
• dans un tableau, on peut accéder directement à la cellule en connaissant son indice. On est en temps constant \(O(1)\)
• dans un dictionnaire on peut directement aller à la bonne cellule dans la mémoire. On est en là encore temps constant \(O(1)\)

Table de hachage

L’implémentation des dictionnaires se fait le plus souvent à l’aide de tables de hachage.

L’idée est d’utiliser une fonction de hachage. On ne décrira pas ici fonctionnement précis de cet outil mais retenons les points suivants. Une fonction de hachage :

• est une fonction prenant en argument la clé du dictionnaire et renvoyant un nombre de taille précise (ce nombre peut ensuite être transformé en un indice dans la table)
• essaie au maximum de faire en sorte que deux clés différentes ne soient pas associées au même indice

Il peut arriver (et il est même certain que cela arrivera !) que deux clés pointent vers deux indices identiques. On parle alors de collision. Dans ce cas, l’implémentation de la table de hachage cherche un autre indice disponble (en regardant par exemple si la cellule située juste après est vide).

Remarque : les fonctions de hachage sont très utilisées en informatique. On les retrouve par exemple pour vérifier l’intégrité d’un fichier après un téléchargement (le fichier téléchargé est-il bien celui qui était sur le serveur) ou pour stocker les mots de passe dans une base de données. En effet il est bien souvent compliqué connaisant le hash d’une donnée de retrouver celle-ci : si un pirate récupère la table des mots de passe hashés, il ne pourra pas remonter au mots de passe en clair

II. En python

Nous avons déjà rencontrés les dictionnaires en Python. Voici quelques rappels.

1. Création d’un dictionnaire

Un dictionnaire est identifié en python par des accolades {}.

On peut créer un dictionnaire de plusieurs façon :

# Création d'un dictionnaire vide de deux manières différentes

dico = {} # avec les accolades 

dico = dict() # en utilisant le constructeur

On peut aussi créer un dictionnaire en passant directement les couples clé : valeur séparés par des virgules , :

dico = {"Nicolas": "Première 1", "Claire": "Première 2", "Arnaud": "Première 3"}

donne {'Nicolas': 'Première 1', 'Claire': 'Première 2', 'Arnaud': 'Première 3'}

Les clés et valeurs d’un dictionnaire peuvent être de types différents et complexes :

dico = {1 : "Nicolas", "Claire " : 5, (1,3) : "tour blanche"}

Dans l’exemple ci-dessus la clé (1,3) est un couple de nombres (un tuple en python). Cela est pratique pour repérer des éléments dans une grille. Ici par exemple, le contenu de la case de coordonnées (1,3) est "tour blanche"

2. Manipulation des données

Une fois un dictionnaire créé, on peut afficher une valeur en utilisant la notation nom_du_dictionnaire[clé] :

dico = {"Nicolas": "Première 1", "Claire": "Première 2", "Arnaud": "Première 3"}

dico["Claire"]

Retourne : Première 2

Si une clé n’est pas encore créée, il suffit de l’attribuer :

dico = {"Nicolas": "Première 1", "Claire": "Première 2", "Arnaud": "Première 3"}

# Ajout de la clé "François"
dico["François"] = "Première 4"

Le dictionnaire vaut alors {'Nicolas': 'Première 1', 'Claire': 'Première 2', 'Arnaud': 'Première 3', 'François': 'Première 4'}

On peut de la même façon modifier une valeur :

dico = {"Nicolas": "Première 1", "Claire": "Première 2", "Arnaud": "Première 3"}

# Modification de la valeur associée à "Nicolas"
dico["Nicolas"] = "Première 6"

On obtient :{'Nicolas': 'Première 6', 'Claire': 'Première 2', 'Arnaud': 'Première 3'}

On peut retirer un couple clé : valeur en utilisant pop(clé) :

dico = {"Nicolas": "Première 1", "Claire": "Première 2", "Arnaud": "Première 3"}

# Suppression de l'entrée "Nicolas"
dico.pop("Nicolas")

qui donne : {'Claire': 'Première 2', 'Arnaud': 'Première 3'}

La taille d’un dictionnaire, le nombre de couples clé : valeur, est donné à l’aide de len(dico) :

On peut demander à Python si le dictionnaire comporte une entrée associée à une clé précise avec in:

dico = {"Nicolas": "Première 1", "Claire": "Première 2", "Arnaud": "Première 3"}

"Nicolas" in dico # y-a-t'il une clé valant "Nicolas" ? Oui

renverra True

3. Parcourir un dictionnaire

• L’ensemble des clés d’un dictionnaire est donné par nom_du_dictionnaire.keys(). Attention on obtient un objet particulier que l’on pourra ensuite convertir en liste.

dico = {"Nicolas": "Première 1", "Claire": "Première 2", "Arnaud": "Première 3"}

L’appel à dico.keys() renvoie en effet dict_keys(['Nicolas', 'Claire', 'Arnaud'])

• L’ensemble des valeurs d’un dictionnaire est donné par nom_du_dictionnaire.values().

Ainsi l’appel à dico.values() renvoie dict_values(['Première 1', 'Première 2', 'Première 3']). Là encore il peut être nécessaire de convertir le résultat en une liste.

• L’ensemble des couples clé, valeur d’un dictionnaire est donné par nom_du_dictionnaire.items().

dico.items() renvoie dict_items([('Nicolas', 'Première 1'), ('Claire', 'Première 2'), ('Arnaud', 'Première 3')])

• On peut itérer sur un dictionnaire de plusieurs façons :

# Sur les clés (1)
for cle in dico.keys() :
    print(">>", cle)

# Sur les clés (2), plus facile
for cle in dico :
    print(">>", cle)

# Sur les valeurs
for valeur in dico.values() :
    print(">>", valeur)
    
# Sur les deux à la fois      
for cle, valeur in dico.items() :
    print(">> clé :", cle)
    print(">> valeur :", valeur)