Dictionnaires

Vue d'ensemble

Une liste range ses éléments par position : le 0^e, le 1^er, etc. Mais souvent on ne veut pas retrouver une information par son numéro, on veut la retrouver par un nom : la note de « Bob », le prix du « pain », le nombre de fois où la lettre « a » apparaît. C'est exactement le rôle du dictionnaire (type dict) : il associe à une clé une valeur, comme un vrai dictionnaire associe à un mot sa définition. Mieux : cette recherche par clé est quasi instantanée, même sur des millions d'entrées. Cette fiche te fait écrire chaque opération, la décrypter ligne par ligne, la tracer sur un exemple, et maîtriser l'algorithme reine : compter des occurrences.

Au programme (tronc commun, 1^re année — BO 2021) — Type dictionnaire : association clé → valeur ; construction, accès, ajout, modification, suppression ; test d'appartenance d'une clé et parcours ; coût constant en moyenne des opérations grâce à la table de hachage (le mécanisme du hachage lui-même relève de la 2^e année).

Prérequis

Manipuler les listes et les chaînes : indexation, len, boucle for x in ... (fiche « listes et chaînes »)
Boucle for et boucle while, condition if
Savoir ce qu'est un coût en $O (1)$ , $O (n)$ , $O (n^{2})$ (fiche « complexité »)

🎯 Accompagnement Majorant

Tu sais coder une liste mais le dictionnaire te paraît « magique » ? Choisir la bonne structure de données est ce qui distingue une copie d'informatique moyenne d'une excellente. Nos mentors alumni X · Centrale · Mines t'apprennent à voir quand un dictionnaire divise ton programme par cent, et à dérouler ses opérations à la main jusqu'au réflexe.

Trouver un mentor →

1. Le dictionnaire : associer une clé à une valeur

Définition 1.1 — Dictionnaire

Un dictionnaire (type dict en Python) est une collection de couples (clé, valeur). À chaque clé correspond une seule valeur, et on retrouve la valeur en donnant sa clé — pas en donnant une position comme dans une liste. On dit qu'un dictionnaire réalise une association clé → valeur.

On écrit un dictionnaire entre accolades { }, chaque couple sous la forme clé: valeur, séparés par des virgules :

vide = {}                                    # un dictionnaire vide
notes = {"Alice": 15, "Bob": 12, "Chloe": 18}   # 3 couples cle -> valeur

print(notes["Bob"])                          # 12 : on lit la valeur associee a la cle "Bob"

🔍 Décryptage ligne par ligne

vide = {}Le dictionnaire vide. Deux accolades sans rien à l'intérieur. Attention : {} crée un dictionnaire vide, pas un ensemble — c'est le point de départ de presque tous les algorithmes de cette fiche.

notes = {"Alice": 15, ...}Trois associations. La clé "Alice" pointe vers la valeur 15, "Bob" vers 12, etc. Les clés sont ici des chaînes, les valeurs des entiers, mais rien n'oblige à ce qu'elles soient du même type.

notes["Bob"]L'accès par clé. On met la clé entre crochets (et non un indice comme notes[1]). Python renvoie la valeur associée : 12. C'est toute la puissance du dictionnaire : on interroge par nom, pas par position.

📝 Clés uniques, valeurs libres. Deux couples ne peuvent pas avoir la même clé : si tu écris {"a": 1, "a": 2}, seule la dernière compte et il reste {"a": 2}. En revanche deux clés différentes peuvent parfaitement partager la même valeur (deux élèves à 15).

2. Quelles valeurs peut-on utiliser comme clé ?

Définition 2.1 — Clé hashable (immuable)

Une clé de dictionnaire doit être hashable : concrètement, une valeur qu'on ne peut pas modifier en place, dite immuable. Les types int, float, str, bool et les tuple (de valeurs elles-mêmes immuables) conviennent. Une liste ne convient pas : on peut la modifier, elle n'est pas hashable.

position = {(0, 0): "depart", (2, 3): "tresor"}   # cles tuple : autorise
print(position[(2, 3)])                            # tresor

# La ligne suivante planterait :
# mauvais = {[0, 0]: "depart"}   # TypeError: unhashable type: 'list'

🔍 Décryptage ligne par ligne

{(0, 0): "depart", ...}Un tuple comme clé. Un couple de coordonnées (0, 0) est immuable, donc utilisable comme clé. C'est très pratique pour repérer des cases d'une grille par leur position.

position[(2, 3)]On relit par la clé tuple. Même mécanisme qu'avec une chaîne : on donne la clé, on récupère la valeur "tresor".

# {[0, 0]: ...} -> TypeErrorPourquoi une liste est interdite. Une liste peut changer de contenu ; Python ne pourrait plus la retrouver de façon fiable. Il lève donc TypeError: unhashable type: 'list'. Retiens : clé = immuable.

⚠ « unhashable type: 'list' ». Si tu vois cette erreur, tu as presque sûrement essayé d'utiliser une liste comme clé (ou comme élément d'un ensemble). Remplace-la par un tuple : [0, 0] devient (0, 0). Les valeurs, elles, peuvent parfaitement être des listes — c'est seulement la clé qui doit être immuable.

3. Accéder à une valeur : d[k], get et l'erreur KeyError

L'accès d[k] est direct, mais il a un défaut : si la clé n'existe pas, le programme plante avec une KeyError. La méthode get permet d'éviter ce crash.

notes = {"Alice": 15, "Bob": 12}

print(notes["Alice"])         # 15 : la cle existe, tout va bien
print(notes.get("David"))     # None : cle absente, aucune erreur
print(notes.get("David", 0))  # 0 : valeur par defaut si la cle est absente

# print(notes["David"])       # KeyError: 'David' -> arrete le programme

🔍 Décryptage ligne par ligne

notes["Alice"]Accès direct, clé présente. "Alice" est bien une clé : on obtient 15. Rapide et lisible… tant que la clé existe.

notes.get("David")get sans défaut. La clé "David" est absente. Au lieu de planter, get renvoie None. On peut donc tester le résultat sans risque.

notes.get("David", 0)get avec valeur par défaut. Le second argument est la valeur renvoyée quand la clé manque : ici 0. C'est exactement le mécanisme qui rendra l'algorithme de comptage (§6) si compact.

notes["David"] # KeyErrorLe crash à éviter. Avec les crochets, une clé absente lève KeyError: 'David' et interrompt tout. Règle : si tu n'es pas sûr que la clé existe, utilise get ou teste k in d d'abord.

4. Ajouter, modifier, supprimer, tester, mesurer

Un dictionnaire est modifiable. La même syntaxe d[k] = v sert à ajouter une clé (si elle n'existe pas) ou à modifier sa valeur (si elle existe déjà). On supprime avec del, on teste l'appartenance d'une clé avec in, on compte les couples avec len.

notes = {"Alice": 15, "Bob": 12}

notes["David"] = 9      # cle absente -> AJOUT du couple ("David", 9)
notes["Bob"] = 14       # cle presente -> MODIFICATION : 12 devient 14
del notes["Alice"]      # SUPPRESSION du couple de cle "Alice"

print("Bob" in notes)   # True  : "Bob" est une CLE du dictionnaire
print("Alice" in notes) # False : on l'a supprimee
print(len(notes))       # 2 : il reste 2 couples -> {"Bob": 14, "David": 9}

🔍 Décryptage ligne par ligne

notes["David"] = 9Ajout. La clé "David" n'existait pas : Python crée le couple. Une seule syntaxe pour créer une entrée.

notes["Bob"] = 14Modification. Même syntaxe, mais "Bob" existe déjà : sa valeur 12 est écrasée par 14. Créer et modifier, c'est le même geste — d'où l'importance de savoir si la clé est déjà là.

del notes["Alice"]Suppression. del retire complètement le couple de clé "Alice". (Si la clé n'existe pas, del lève lui aussi une KeyError.)

"Bob" in notesLe test porte sur les CLÉS. Point capital : in regarde si "Bob" est une clé, pas une valeur. 14 in notes vaudrait False même si 14 est une valeur présente.

len(notes)Nombre de couples. len compte les couples (clé, valeur), ici 2 après un ajout et une suppression.

⚠ in teste les clés, jamais les valeurs. Sur notes = {"Bob": 14}, l'expression 14 in notes vaut False : 14 est une valeur, pas une clé. Pour chercher parmi les valeurs il faut écrire 14 in notes.values() — et ce test-là coûte

O (n)

, pas

O (1)

(voir §7).

5. Parcourir un dictionnaire : clés, valeurs, couples

Une boucle for sur un dictionnaire parcourt ses clés. Trois méthodes précisent ce qu'on veut : keys() (les clés), values() (les valeurs), items() (les couples clé-valeur).

notes = {"Alice": 15, "Bob": 12, "Chloe": 18}

for cle in notes:              # par defaut, on parcourt les CLES
    print(cle, notes[cle])     # on affiche la cle et sa valeur

for cle, valeur in notes.items():   # on recupere les DEUX d'un coup
    print(cle, "->", valeur)

print(list(notes.keys()))      # ['Alice', 'Bob', 'Chloe']
print(list(notes.values()))    # [15, 12, 18]

🔍 Décryptage ligne par ligne

for cle in notes:Itérer = parcourir les clés. Sans rien préciser, la variable de boucle prend successivement chaque clé. On accède ensuite à la valeur avec notes[cle].

for cle, valeur in notes.items():Clé et valeur ensemble. items() fournit chaque couple ; le double nom cle, valeur les récupère d'un coup. C'est la façon la plus lisible de tout parcourir.

list(notes.keys()) / .values()Extraire une des deux colonnes. keys() donne toutes les clés, values() toutes les valeurs. On les transforme en liste pour les afficher ou les traiter.

📝 Ordre de parcours. Depuis Python 3.7, le parcours suit l'ordre d'insertion des clés (ici Alice, Bob, Chloé). Ne compte pas dessus pour ta logique : historiquement le dictionnaire n'était pas ordonné, et un jury attend un algorithme qui marche quel que soit l'ordre. Un dictionnaire sert à retrouver par clé, pas à ranger.

6. Algorithme central — compter les occurrences

Voici l'algorithme à connaître par cœur. On veut, pour un mot (ou une liste), savoir combien de fois apparaît chaque élément : un histogramme de fréquences. Le dictionnaire est parfait : la clé est l'élément, la valeur est son compteur.

📐 Méthode — l'idiome d[x] = d.get(x, 0) + 1.

Partir d'un dictionnaire vide compte = {}.
Parcourir chaque élément x.
Lire le compteur actuel de x avec compte.get(x, 0) : 0 si x est nouveau, sa valeur sinon.
Lui ajouter 1 et ranger le résultat dans compte[x].

def occurrences(mot):
    compte = {}                             # histogramme vide
    for lettre in mot:                      # on lit chaque lettre
        compte[lettre] = compte.get(lettre, 0) + 1   # +1 (0 si lettre nouvelle)
    return compte

print(occurrences("banane"))   # {'b': 1, 'a': 2, 'n': 2, 'e': 1}

🔍 Décryptage ligne par ligne

compte = {}On part de vide. Aucune lettre n'a encore été vue : le dictionnaire est vide.

for lettre in mot:On lit le mot lettre par lettre. Itérer sur une chaîne donne ses caractères un à un.

compte.get(lettre, 0)Le compteur actuel, ou 0. Si la lettre a déjà été vue, on récupère son compteur ; si c'est la première fois, get renvoie la valeur par défaut 0. C'est ce défaut qui évite la KeyError et supprime tout if.

compte[lettre] = ... + 1On incrémente. On ajoute 1 au compteur récupéré et on le range à la clé lettre : première apparition → 1, suivantes → 2, 3, …

Exécution pas à pas — occurrences("banane")
Lettre lue	`get(lettre, 0)`	Nouvelle valeur	Dictionnaire `compte` après
b	0 (nouvelle)	1	{'b': 1}
a	0 (nouvelle)	1	{'b': 1, 'a': 1}
n	0 (nouvelle)	1	{'b': 1, 'a': 1, 'n': 1}
a	1	2	{'b': 1, 'a': 2, 'n': 1}
n	1	2	{'b': 1, 'a': 2, 'n': 2}
e	0 (nouvelle)	1	{'b': 1, 'a': 2, 'n': 2, 'e': 1} ✓

💡 Le même idiome marche sur n'importe quoi. Remplace mot par une liste de votes ["oui", "non", "oui"] ou de nombres [3, 1, 3] : le code ne change pas d'une lettre. Compter des occurrences, c'est toujours d[x] = d.get(x, 0) + 1.

🎯 Accompagnement Majorant

Cet idiome tombe chaque année aux concours (Mines, Centrale, CCINP). Nos mentors alumni X · Centrale · Mines te font écrire ses variantes (mot le plus fréquent, anagrammes, doublons) jusqu'à ce que ta main l'écrive seule sous le stress de l'oral.

Trouver un mentor →

7. Le coût des opérations : dictionnaire contre liste

Propriété 7.1 — Coût constant en moyenne

Sur un dictionnaire de $n$ couples, l'accès d[k], l'insertion d[k] = v et le test d'appartenance d'une clé k in d coûtent $O (1)$ en moyenne. Cette rapidité vient d'une table de hachage : Python calcule à partir de la clé une adresse où ranger la valeur, sans parcourir les autres couples. Le fonctionnement précis du hachage est au programme de 2^e année ; en Sup, retiens seulement le résultat.

C'est la différence décisive avec une liste. Chercher un élément dans une liste de $n$ éléments oblige à la parcourir : $O (n)$ . Tester une clé dans un dictionnaire est $O (1)$ .

noms_liste = ["Alice", "Bob", "Chloe"]      # une liste
print("Bob" in noms_liste)   # True, mais Python compare element par element : O(n)

noms_dict = {"Alice": 15, "Bob": 12, "Chloe": 18}   # un dictionnaire
print("Bob" in noms_dict)    # True, retrouve directement par hachage : O(1) en moyenne

🔍 Décryptage ligne par ligne

"Bob" in noms_listeRecherche linéaire. Pour une liste, in compare "Bob" à chaque élément jusqu'à le trouver. Sur

n

éléments, ça peut demander

n

comparaisons :

O (n)

"Bob" in noms_dictRecherche par clé. Pour un dictionnaire, in teste si "Bob" est une clé, en une seule étape via la table de hachage :

O (1)

en moyenne, même sur des millions de clés.

Coût d'une recherche selon la structure (n éléments)
Opération	Liste	Dictionnaire (sur les clés)
tester la présence (`x in ...`)	$O (n)$	$O (1)$ en moyenne
lire par clé / par indice	$O (1)$ par indice	$O (1)$ par clé
ajouter un élément	`append` : $O (1)$	`d[k]=v` : $O (1)$ en moyenne
chercher parmi les valeurs	—	`x in d.values()` : $O (n)$

📝 Le réflexe à prendre. Dès que ton programme fait beaucoup de tests « est-ce que tel élément est présent ? » ou « quelle info est associée à tel nom ? », un dictionnaire remplace une liste et fait passer de

O (n)

O (1)

par recherche. Sur

n

recherches, c'est

O (n^{2})

qui devient

O (n)

8. Pièges classiques en copie

⚠ Accéder à une clé absente avec les crochets. d[k] sur une clé qui n'existe pas lève KeyError et stoppe le programme. Dans une boucle de comptage, utilise d.get(k, 0) ; ailleurs, teste if k in d: avant.

⚠ Croire que in teste les valeurs. k in d porte sur les clés. Pour les valeurs, c'est v in d.values(), et ce test coûte

O (n)

⚠ Utiliser une liste comme clé. {[1, 2]: "x"} lève TypeError: unhashable type: 'list'. Une clé doit être immuable : passe au tuple (1, 2).

⚠ Se fier à l'ordre du dictionnaire. L'ordre d'insertion est conservé depuis Python 3.7, mais un dictionnaire reste conceptuellement non ordonné : n'écris jamais un algorithme qui suppose « la première clé » ou « la plus petite clé » sans trier explicitement.

9. Exercices d'application

Fais-les sur papier avant d'ouvrir le corrigé, puis passe au quiz en bas de fiche.

Exo 1Ajout ou modification ?Facile

d = {"a": 1, "b": 2}
d["c"] = 3
d["a"] = 10
print(d)

Voir la correction détaillée

d["c"] = 3 : la clé "c" n'existe pas, c'est un ajout. Le dictionnaire vaut {"a": 1, "b": 2, "c": 3}.

d["a"] = 10 : la clé "a" existe déjà, c'est une modification : sa valeur 1 devient 10.

Affichage : {'a': 10, 'b': 2, 'c': 3}. La même syntaxe d[k]=v a servi une fois à ajouter, une fois à modifier.

Exo 2L'élément le plus fréquentIntermédiaire

Écris plus_frequent(liste) qui renvoie l'élément apparaissant le plus souvent dans liste (on suppose la liste non vide).

Voir la correction détaillée

On construit d'abord l'histogramme avec l'idiome du §6, puis on cherche la clé de plus grand compteur.

def plus_frequent(liste):
    compte = {}
    for x in liste:
        compte[x] = compte.get(x, 0) + 1   # histogramme
    gagnant = None
    best = 0
    for x in compte:              # on parcourt les cles
        if compte[x] > best:
            best = compte[x]
            gagnant = x
    return gagnant

print(plus_frequent(["a", "b", "a", "c", "a", "b"]))   # 'a'

L'histogramme est {'a': 3, 'b': 2, 'c': 1} ; le plus grand compteur est 3, obtenu pour 'a'. La fonction renvoie 'a'.

Exo 3Deux mots sont-ils anagrammes ?Difficile

Deux mots sont anagrammes s'ils contiennent exactement les mêmes lettres, avec les mêmes multiplicités (comme « chien » et « niche »). Écris anagrammes(m1, m2) qui renvoie un booléen. Indice : deux histogrammes.

Voir la correction détaillée

Deux mots sont anagrammes si et seulement si leurs histogrammes de lettres sont égaux. Or Python compare deux dictionnaires couple par couple, sans se soucier de l'ordre : c'est exactement ce qu'il nous faut.

def occurrences(mot):
    compte = {}
    for lettre in mot:
        compte[lettre] = compte.get(lettre, 0) + 1
    return compte

def anagrammes(m1, m2):
    return occurrences(m1) == occurrences(m2)

print(anagrammes("chien", "niche"))   # True
print(anagrammes("chat", "chien"))    # False

occurrences("chien") et occurrences("niche") donnent le même dictionnaire (c,h,i,e,n chacune une fois) : l'égalité vaut True. Pour "chat" et "chien", les histogrammes diffèrent : False. Élégant : aucun tri, juste une comparaison de dictionnaires.

Récap final — Ce qu'il faut absolument retenir

À la veille d'une khôlle ou d'un DS, parcours cette checklist : tu dois pouvoir répondre « oui, sans hésiter » à chaque question.

Sais-tu qu'un dictionnaire associe une clé à une valeur et se crée avec {clé: valeur} (et {} pour le vide) ?
Sais-tu qu'une clé doit être immuable/hashable (str, int, tuple) et qu'une liste comme clé lève TypeError ?
Sais-tu que d[k] sur une clé absente lève KeyError, et que d.get(k, defaut) l'évite ?
Sais-tu qu'une seule syntaxe d[k] = v sert à ajouter ou modifier, et que del d[k] supprime ?
Sais-tu que k in d et len(d) portent sur les clés / le nombre de couples ?
Sais-tu parcourir un dictionnaire avec for k in d, d.keys(), d.values(), d.items() ?
Sais-tu écrire de tête l'histogramme d'occurrences avec d[x] = d.get(x, 0) + 1 et le dérouler sur un exemple ?
Sais-tu pourquoi tester une clé dans un dict est $O (1)$ en moyenne alors que chercher dans une liste est $O (n)$ ?

Vue d'ensemble

Prérequis

1. Le dictionnaire : associer une clé à une valeur

2. Quelles valeurs peut-on utiliser comme clé ?

3. Accéder à une valeur : d[k], get et l'erreur KeyError

4. Ajouter, modifier, supprimer, tester, mesurer

5. Parcourir un dictionnaire : clés, valeurs, couples

6. Algorithme central — compter les occurrences

7. Le coût des opérations : dictionnaire contre liste

8. Pièges classiques en copie

9. Exercices d'application

Récap final — Ce qu'il faut absolument retenir

Débloque la fiche complète

Quiz — Dictionnaires

Fiches associées

Recherche par dichotomie

Variables, types et affectations

Conditions et booléens

Boucles for et while

Fonctions : paramètres et valeurs de retour

Listes et chaînes de caractères

Tu veux aller plus loin sur ce chapitre ?