Type abstrait : Dictionnaire¶

Un dictionnaire est un type abstrait gardant en mémoire des informations de la forme (clé, valeur). Le but d’un dictionnaire est d’être capable d’accéder rapidement à une valeur à partir de sa clé, en moyenne cette opération se fera en \(O(1)\).

Interface d’un dictionnaire (aussi appelé tableau associatif)¶

nouveauDictionnaire() -> Dictionnaire : on crée un nouveau dictionnaire vide
ajouter(cle:Cle, valeur:Valeur, d:Dictionnaire) : rajoute une nouvelle clé en lui associant la valeur fournie.
modifier(cle:Cle, valeur:Valeur, d:Dictionnaire) : modifie la valeur associée à la clé.
rechercher(cle:Cle, d:Dictionnaire) -> Valeur : renvoie la valeur associée à une clé, si la clé existe.
supprimer(cle:Cle, d:Dictionnaire) : supprime la clé et la valeur associée du dictionnaire.

Avec des listes Python¶

On peu utiliser les listes Python pour mettre en oeuvre l'interface Dictionnaire.

contenu = [('a', 1), ('b', 99), ...]

Cette liste de tuples contient d'une part la clé ('a' dans le premier tuple) et la valeur (1 dans le premier tuple)

Question

Pourquoi cette solution n'est pas efficace si on cherche une valeur à partir de sa clé ?

Table de hachage¶

Une mise en oeuvre plus efficace consiste à utiliser une table de hachage.

Le fonctionnement d'une table de hachage est hors programme, donc vous pouvez passer cette partie si vous le souhaitez.

Soit \(U\) l’ensemble des valeurs possibles et soit \(K\) l’ensemble des valeurs effectivement utilisées. Une table de hachage est une table (tableau) dont :

Les éléments sont placés dans des cases.
Le choix de la case est effectuée en appliquant une fonction sur une valeur : c’est la fonction de hachage.

Fonction de hachage¶

Pour construire une table de hachage il faut donc commencer par définir une fonction de hachage. Cette fonction permet d'identifier la donnée contenue dans le dictionnaire pour pouvoir la récupérer rapidement.

Une fonction de hachage \(h\) etablit une relation entre \(U\) (univers des valeurs) et un sous-ensemble fini :
\(h : U → \{0, 1, ..., m − 1\}\)

Collisions¶

Plusieurs valeurs peuvent avoir une même valeur de hachage : c’est une collision. Plusieurs solutions existent pour résoudre ce problème. Citons notamment :

Le chaînage
L'adressage ouvert

Nous n'expliquerons pas ici l'adressage ouvert bien que ce soit la technique utilisée dans Python pour résoudre les collisions.

Chaînage¶

Avec cette technique, on place dans une liste chaînée tous les éléments ayant la même valeur de hachage :

Bonus

Vidéo du MIT (en anglais) :

Le type `dict`¶

En Python le type dict correspond à une table de hachage. Nous le reverrons (censé avoir été vu en Première) en salle informatique.

Exercices de révision (ou découverte).

Note

vehicules_vitesse = {"voiture": 100, "velo": 25, "train": 100}
vitesse = vehicules_vitesse['velo']

Quelle valeur sera présente dans la variable vitesse ?

mes_fruits = {"poire": 3, "pomme": 4, "orange": 2}
mes_fruits["pomme"] = mes_fruits["pomme"] - 1

Après l'exécution de ce programme qu'est ce qui aura changé dans le dictionnaire mes_fruits ?

mes_fruits = {"poire": 3, "pomme": 4, "orange": 2}

for fruit in mes_fruits.keys():
    print(fruit)

Que va afficher le code ci-dessus ?

lent = []
vehicules_vitesse = {"voiture": 100, "velo": 25, "train": 100}
for vitesse in vehicules_vitesse.values():
    if vitesse < 40 :
        lent.append(vitesse)

Que contiendra la liste lent ?

utilisateurs = [{'nom': 'toto', 'num': 2}, {'nom': 'titi', 'num': 5},  {'nom': 'tata', 'num': 4}, {'nom': 'tutu', 'num': 3}]
utilisateurs_nom =  []

for u in utilisateurs :
    if u['num'] >= 3:
        utilisateurs_nom.append(u['nom'])

Que contiendra la liste utilisateurs_nom ?