Dictionnaires et programmation orientée objet
Terminale · NSI · Structures de données
Structures de données
Le dictionnaire : associer des clés à des valeurs
Dans un tableau, on retrouve une donnée grâce à sa position : un entier, de 0 à n − 1. Le dictionnaire généralise cette idée : on retrouve une donnée grâce à une clé qui peut être n'importe quoi d'immuable — un mot, un couple de coordonnées, un numéro d'élève. C'est la structure la plus utile du langage, et celle qui rend tant de programmes courts et rapides.
Les opérations de base en Python
- d = {} ou d = dict() : crée un dictionnaire vide. Attention, {} donne bien un dictionnaire, pas un ensemble.
- d[cle] = valeur : ajoute le couple si la clé est absente, REMPLACE la valeur si la clé existe déjà.
- d[cle] : renvoie la valeur associée ; lève une erreur KeyError si la clé n'existe pas.
- d.get(cle, defaut) : renvoie la valeur si la clé existe, sinon la valeur par défaut — pratique pour compter sans planter.
- cle in d : renvoie True si la CLÉ est présente (jamais pour tester une valeur).
- del d[cle] : supprime le couple.
- len(d) : nombre de couples.
- for cle in d : parcourt les clés ; for cle, val in d.items() : parcourt les couples.
Pourquoi est-ce si rapide ? La table de hachage
Un dictionnaire Python est implémenté par une table de hachage. Le principe : une fonction de hachage transforme la clé en un entier, qui sert d'indice dans un grand tableau interne. Trouver une clé revient donc à un calcul suivi d'un accès direct — d'où un coût constant en moyenne, O(1), même avec des millions de couples.
Il arrive que deux clés différentes donnent le même indice : c'est une collision. Ce n'est pas une erreur, la table sait les gérer (par exemple en rangeant les clés concernées dans une petite liste, ou en cherchant une case libre voisine). Dans le pire des cas, très rare, le coût peut redevenir linéaire.
| Opération | Tableau (list Python) | Dictionnaire |
|---|---|---|
| Accès par indice / par clé | O(1) par indice entier | O(1) en moyenne, par clé quelconque |
| Rechercher une VALEUR | O(n) | O(n) : il faut tout parcourir |
| Ajouter un élément | O(1) en fin (append) | O(1) en moyenne |
| Supprimer un élément | O(n) en général (décalage) | O(1) en moyenne |
| Ordre des éléments | l'ordre des indices | l'ordre d'insertion (depuis Python 3.7) |
| Clés autorisées | entiers 0 à n − 1 uniquement | tout type immuable |
Structures de données
Programmation orientée objet : classes, objets, interfaces
La programmation orientée objet (POO) permet de définir ses propres types. Elle est au programme de Terminale pour une raison précise : c'est l'outil qui permet d'implémenter proprement les structures de données abstraites du chapitre précédent, en réunissant au même endroit les données et les opérations qui agissent dessus.
Le constructeur et le mot-clé self
En Python, le constructeur est la méthode spéciale __init__ (deux blancs soulignés de chaque côté). Elle est appelée automatiquement lors de la création d'un objet et sert à initialiser les attributs.
Le premier paramètre de toute méthode est self : il désigne l'objet sur lequel la méthode est appelée. Lorsqu'on écrit p.empiler(4), Python exécute en réalité empiler avec self valant p et x valant 4 — c'est pourquoi on n'écrit jamais self dans l'appel.
Encapsulation et interface
L'intérêt profond de la POO ici, c'est l'encapsulation : l'utilisateur d'une classe Pile manipule la structure uniquement par son interface (empiler, dépiler, est_vide) et n'a pas à savoir si le contenu est stocké dans une liste Python ou dans une liste chaînée.
Conséquence concrète : si tu remplaces l'implémentation interne par une liste chaînée, aucun programme utilisateur n'a besoin d'être modifié, tant que les méthodes gardent le même nom et le même comportement. C'est exactement la séparation interface / implémentation vue avec les types abstraits.
| Terme | Ce que c'est | Exemple |
|---|---|---|
| Classe | le modèle, écrit une seule fois | class Pile: |
| Objet / instance | un exemplaire créé à partir de la classe | p = Pile() |
| Attribut | une donnée propre à l'objet | self.contenu |
| Méthode | une fonction définie dans la classe | def empiler(self, x): |
| Constructeur | la méthode appelée à la création | def __init__(self): |
| self | l'objet sur lequel la méthode est appelée | self.contenu.append(x) |
Exercices corrigés
On a d = {"a": 1}. Que fait l'instruction d["b"] = 5 ?
- A.Elle lève une erreur, car la clé "b" n'existe pas encore
- B.Elle remplace la valeur associée à "a"
- C.Elle ajoute au dictionnaire le couple ("b", 5)Bonne réponse
- D.Elle crée une nouvelle variable nommée b
Réponse : C — Elle ajoute au dictionnaire le couple ("b", 5)
En écriture, d[cle] = valeur ajoute le couple si la clé est absente et remplace la valeur si la clé existe déjà. Ici "b" est absente, elle est donc créée : d vaut désormais {"a": 1, "b": 5}. L'erreur KeyError ne survient qu'en LECTURE d'une clé absente, par exemple d["c"]. C'est une dissymétrie importante à connaître.
Que parcourt la boucle « for k in d: » quand d est un dictionnaire ?
- A.Les clés du dictionnaireBonne réponse
- B.Les valeurs du dictionnaire
- C.Les couples (clé, valeur)
- D.Les indices entiers de 0 à len(d) − 1
Réponse : A — Les clés du dictionnaire
Par défaut, itérer sur un dictionnaire parcourt ses CLÉS. Pour obtenir les valeurs, il faut écrire for v in d.values() ; pour les couples, for k, v in d.items(). L'oubli le plus classique est d'écrire for k in d puis d'utiliser k comme s'il s'agissait de la valeur : pense à écrire d[k] pour récupérer la valeur associée.
On compte les occurrences des lettres du mot « banane » dans un dictionnaire. Quel résultat obtient-on ?
- A.{'b': 1, 'a': 2, 'n': 2, 'e': 1}Bonne réponse
- B.{'b': 1, 'a': 1, 'n': 1, 'e': 1}
- C.{'b': 1, 'a': 3, 'n': 2, 'e': 1}
- D.{'b': 2, 'a': 2, 'n': 2, 'e': 1}
Réponse : A — {'b': 1, 'a': 2, 'n': 2, 'e': 1}
Décomposons « banane » : b, a, n, a, n, e. On compte donc un b, deux a, deux n et un e. Vérification par la somme : 1 + 2 + 2 + 1 = 6, et le mot compte bien 6 lettres — c'est le contrôle à faire systématiquement. L'option 2 oublie que les clés déjà présentes doivent être incrémentées, et les options 3 et 4 donnent des totaux de 7, donc impossibles.
Que teste l'expression « k in d » lorsque d est un dictionnaire ?
- A.Si k est une valeur du dictionnaire
- B.Si le dictionnaire d est vide
- C.Si k est une clé du dictionnaireBonne réponse
- D.Si k est un entier valide
Réponse : C — Si k est une clé du dictionnaire
L'opérateur in appliqué à un dictionnaire porte sur les CLÉS, jamais sur les valeurs. Avec d = {"a": 1}, l'expression "a" in d vaut True mais 1 in d vaut False. Pour chercher une valeur, il faut écrire 1 in d.values() — et le coût passe alors à O(n), puisqu'il faut parcourir tous les couples au lieu de bénéficier du hachage.
Une classe Pile définit « def empiler(self, x): ... ». Comment appelle-t-on cette méthode sur une pile nommée p ?
- A.Pile.empiler(x)
- B.empiler(p, x)
- C.p.empiler(self, x)
- D.p.empiler(x)Bonne réponse
Réponse : D — p.empiler(x)
On appelle une méthode sur l'OBJET, avec la notation pointée, et sans jamais écrire self : Python le transmet automatiquement, en lui donnant la valeur p. L'option 1 appelle la méthode sur la classe sans lui fournir d'instance. L'option 2 correspond à une fonction ordinaire, pas à une méthode. L'option 3 est l'erreur la plus fréquente : passer self explicitement donnerait un argument de trop.
Dans une table de hachage, deux clés différentes produisent la même valeur de hachage. Comment appelle-t-on cette situation ?
- A.Une erreur d'exécution qui interrompt le programme
- B.Un doublon, l'une des deux clés étant supprimée
- C.Une collision, que la table de hachage sait gérerBonne réponse
- D.Un tri automatique des deux clés
Réponse : C — Une collision, que la table de hachage sait gérer
C'est une collision, et c'est inévitable : il y a infiniment plus de clés possibles que de cases dans la table. La structure prévoit donc un mécanisme de résolution — ranger les clés concernées dans une petite liste attachée à la case, ou chercher une case libre voisine. Rien n'est supprimé et le programme ne plante pas : les deux clés restent distinctes et gardent chacune leur valeur. Seule conséquence : trop de collisions dégradent le coût vers O(n).
Quel est le coût de la recherche d'une VALEUR donnée dans un dictionnaire de n couples ?
- A.O(1), comme la recherche par une clé
- B.O(log n), comme dans un arbre binaire équilibré
- C.C'est totalement impossible à faire en Python
- D.O(n) : il faut parcourir tous les couplesBonne réponse
Réponse : D — O(n) : il faut parcourir tous les couples
Le hachage porte sur les clés, et sur elles seules : c'est ce qui rend d[k] instantané. Rien n'indexe les valeurs, donc les retrouver impose de parcourir l'ensemble des couples, d'où un coût linéaire O(n). Si ton programme a besoin de chercher souvent dans les deux sens, la bonne réponse d'ingénieur est de maintenir un SECOND dictionnaire inversé, valeur vers clé — à condition que les valeurs soient uniques et immuables.
Que fait un dictionnaire Python ?
- A.Il associe obligatoirement des indices entiers à des valeurs
- B.Il associe des clés à des valeursBonne réponse
- C.Il range automatiquement les valeurs par ordre croissant
- D.Il stocke uniquement des fonctions
Réponse : B — Il associe des clés à des valeurs
Un dictionnaire est une table d'association : à chaque clé correspond une valeur, et la clé peut être bien autre chose qu'un entier (une chaîne, un tuple…). C'est justement ce qui le distingue d'un tableau, où l'unique moyen d'accès est l'indice entier. Et un dictionnaire ne trie rien : depuis Python 3.7 il conserve simplement l'ordre d'insertion.
Quelle écriture crée un dictionnaire vide en Python ?
- A.[]
- B.()
- C.set()
- D.{}Bonne réponse
Réponse : D — {}
Les accolades vides {} créent un dictionnaire vide (on peut aussi écrire dict()). [] crée une liste vide, () un tuple vide, et set() un ensemble vide. Petit point de vigilance : les accolades servent aussi aux ensembles, mais uniquement quand elles contiennent des éléments — {1, 2} est un ensemble, tandis que {} vide est bien un dictionnaire.
On pose d = {"a": 1, "b": 2}. Que vaut d["b"] ?
- A.2Bonne réponse
- B.1
- C."b"
- D.Une erreur, car "b" n'est pas un indice entier
Réponse : A — 2
d["b"] renvoie la VALEUR associée à la clé "b", c'est-à-dire 2. Répondre 1 serait donner la valeur associée à "a", ou raisonner comme si "b" désignait la position 1 — mais dans un dictionnaire il n'y a pas de position, seulement des clés. Et une chaîne est une clé parfaitement valide, il n'y a donc aucune erreur.
Quelle condition une clé de dictionnaire doit-elle respecter ?
- A.Être obligatoirement un entier
- B.Être obligatoirement une chaîne de caractères
- C.Être d'un type immuable : entier, flottant, chaîne, tuple d'immuables…Bonne réponse
- D.Être d'un type modifiable, pour pouvoir la mettre à jour
Réponse : C — Être d'un type immuable : entier, flottant, chaîne, tuple d'immuables…
La contrainte porte sur l'immuabilité, pas sur un type précis : entiers, flottants, booléens, chaînes et tuples d'immuables font tous de bonnes clés. La raison est technique : la table de hachage calcule un indice à partir de la clé, donc la clé ne doit jamais changer après insertion. L'option 4 est exactement l'inverse de la règle. Les VALEURS, en revanche, peuvent être de n'importe quel type.
En programmation orientée objet, qu'est-ce qu'une classe ?
- A.Un objet particulier, créé en premier
- B.Une fonction qui renvoie un dictionnaire
- C.Une variable globale accessible partout dans le programme
- D.Un modèle décrivant les attributs et les méthodes des objets qu'on pourra créerBonne réponse
Réponse : D — Un modèle décrivant les attributs et les méthodes des objets qu'on pourra créer
La classe est le plan, le modèle : elle décrit ce que sauront faire les objets (les méthodes) et quelles données ils porteront (les attributs). Les objets, ou instances, sont les exemplaires concrets créés à partir de ce modèle, par exemple p = Pile(). Confondre la classe et l'objet est l'erreur la plus fréquente en début de chapitre : la classe s'écrit une fois, les objets se créent autant de fois qu'on veut.
S'entraîner sur ce chapitre
Ce chapitre compte 37 exercices corrigés dans l'application, avec le suivi de ta progression.
Commencer les exercices