Au programme de ce chapitre
- I. Le dictionnaire : une association clé-valeur
- II. Construire un index à partir de données
- III. Clés composées et dictionnaires imbriqués
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
- À retenir
La définition à retenir
Définition Un dictionnaire associe à chaque clé unique une valeur. Contrairement à une liste, l'accès ne se fait pas par un rang mais directement par la clé :
d[cle]. En Python, les dictionnaires reposent sur une table de hachage : une fonction de hachage transforme la clé en un indice dans un tableau interne, ce qui permet d'accéder à la valeur sans parcourir tout le dictionnaire.
🔒 Illustration du chapitre completIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
🔒 Infographie récapitulative du chapitreIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
Un exemple corrigé
Exemple Testé avec
python3 :
>>> documents = {
... 1: "le chat noir dort",
... 2: "le chien noir aboie",
... 3: "le chat dort sur le tapis",
... }
>>> index = {}
>>> for id_doc, texte in documents.items():
... for mot in texte.split():
... index.setdefault(mot, set()).add(id_doc)
...
>>> index["chat"]
{1, 3}
>>> index["chat"] & index["dort"]
{1, 3}setdefault(mot, set()) crée un ensemble vide la première fois qu'un mot est rencontré, puis y ajoute l'identifiant du document courant. L'intersection & des deux ensembles donne immédiatement les documents contenant à la fois « chat » et « dort », sans reparcourir les textes d'origine : c'est tout l'intérêt de l'index, construit une seule fois en O(N) (N étant le nombre total de mots), puis interrogé en O(1) par mot.Les erreurs fréquentes à éviter
Piège. Une clé doit être non modifiable (immuable) : liste interdite, tuple autorisé.
Attention Les clés d'un dictionnaire doivent être des objets non modifiables (chaîne, nombre, p-uplet), car la fonction de hachage doit toujours renvoyer la même valeur pour une même clé. Une liste, modifiable, ne peut donc pas être utilisée comme clé.
L'astuce du prof
Astuce. Dictionnaire = accès direct par clé, en temps constant moyen.
Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1
Comment accède-t-on à une valeur par sa clé, et en quelle complexité ?
Voir la correction
Avec d[cle], en O(1) en moyenne (table de hachage).
Exercice 2
Pourquoi les clés doivent-elles être non modifiables ?
Voir la correction
Pour que le hachage renvoie toujours la même valeur pour une même clé.