Rappels sur les dictionnaires en Python

Objectifs et prérequis

Prérequis : fonctions en Python , listes et tuples vus en première

À l’issue de ce chapitre, vous saurez :

  • créer un dictionnaire (littéral, à partir d’une liste de couples, par compréhension) ;
  • accéder, ajouter, modifier et supprimer des entrées ;
  • itérer sur les clés, les valeurs ou les couples (clé, valeur) ;
  • gérer l’absence d’une clé avec try/except ou la méthode get ;
  • comparer la complexité de la recherche dans une liste (O(n)) et dans un dictionnaire (O(1)).

Introduction

Plutôt qu’accéder à une valeur à partir de son indice (comme dans un tableau), on peut souhaiter y accéder à partir d’une clé.

Par exemple dans un annuaire téléphonique, on accède à un numéro de téléphone à partir d’un nom. Les noms sont donc les clés, les numéros de téléphone les valeurs. Dans un dictionnaire (au sens traditionnel), on recherche une définition à partir d’un mot. Les mots sont les clés et les définitions les valeurs.

L’accès à la valeur ainsi que la modification ou l’ajout d’une valeur doivent être possibles sans parcourir toute la structure. On parle aussi de tableaux associatifs.

Un dictionnaire est un ensemble de couples (clé, valeur) : on accède à une valeur par sa clé et non par sa position (l’ordre d’insertion est conservé, mais il ne joue aucun rôle). On peut ajouter des couples ; si la clé figure déjà dans le dictionnaire alors le couple est remplacé par le nouveau. Un dictionnaire Python est un objet mutable (comme les listes mais contrairement aux chaînes de caractères ou aux tuples).

Création de dictionnaires

Plusieurs méthodes permettent de créer un dictionnaire.

Dictionnaire vide

d = dict()

# ou

d = {}


print(d)

{}

À partir d’une liste de couples

boxoffice = {'Aladdin' : 569439,
             'Godzilla 2' : 342574,
             'Rocketman' : 277017}


print(boxoffice)

{'Aladdin': 569439, 'Godzilla 2': 342574, 'Rocketman': 277017}

Par compréhension

dict1 = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

double_dict1 = {k: v * 2 for (k, v) in dict1.items()}

print(double_dict1)

{'a': 2, 'b': 4, 'c': 6, 'd': 8, 'e': 10}

Accès aux valeurs, informations

Accès à une valeur par sa clé

print(boxoffice['Aladdin'])

569439

Nombre d’enregistrements (longueur)

print(len(boxoffice) == 3)

True

Test d’appartenance d’une clé

print('Rocketman' in boxoffice)

True

Ajout, modification, suppression de valeurs

Ajout d’une valeur

boxoffice['Avengers'] = 0

print(len(boxoffice) == 4)
print(boxoffice['Avengers'])

True
0

Unicité des clés

boxoffice['Avengers'] = 132260

print(len(boxoffice) == 4)
print(boxoffice['Avengers'])

True
132260

Les valeurs peuvent ne pas être uniques

boxoffice['Mon Film'] = 132260

print(len(boxoffice) == 5)
print(boxoffice['Avengers'])
print(boxoffice['Mon Film'])

True
132260
132260

Supprimer une valeur

del boxoffice['Mon Film']

print(len(boxoffice) == 4)
print('Mon Film' in boxoffice )

True
False

Itérations

Itération sur les clés

for film in boxoffice:
    print(f"{film} => {boxoffice[film]} spectateurs")

Aladdin => 569439 spectateurs
Godzilla 2 => 342574 spectateurs
Rocketman => 277017 spectateurs
Avengers => 132260 spectateurs

On obtient le même résultat avec le code ci-dessous :

for film in boxoffice.keys():
    print(f"{film} => {boxoffice[film]} spectateurs")

Aladdin => 569439 spectateurs
Godzilla 2 => 342574 spectateurs
Rocketman => 277017 spectateurs
Avengers => 132260 spectateurs

Itération sur les valeurs

for nbre_spectateurs in boxoffice.values():
    print(nbre_spectateurs)

569439
342574
277017
132260

Itération sur les paires (clé, valeur)

for film, nbre_spectateurs in boxoffice.items():
    print(f"{film} => {nbre_spectateurs} spectateurs")

Aladdin => 569439 spectateurs
Godzilla 2 => 342574 spectateurs
Rocketman => 277017 spectateurs
Avengers => 132260 spectateurs

Exceptions

Accès à une valeur inexistante

print(boxoffice['Mon Film'])

Traceback (most recent call last):
  File "main.py", line 1, in <module>
    print(boxoffice['Mon Film'])
KeyError: 'Mon Film'

Capture d’exceptions

def nombre_entrees(titre_film):
    '''
    renvoie le nombre d'entrées du film selon boxoffice, 0 si nombre non connnu
    (boxoffice considéré ici comme global)
    '''
    try:
        return boxoffice[titre_film]
    except KeyError:
        return 0

print(nombre_entrees('Avengers'))
print(nombre_entrees('Mon film'))

132260
0

La méthode get() permet d’accéder à la valeur d’une clef

print(boxoffice.get('Avengers'))

132260
  • boxoffice.get(key) est équivalent boxoffice[key] si key est une clef qui existe
  • boxoffice.get(key) renvoie None par défaut en cas de clef absente
print(boxoffice.get('Mon Film') == None)

# On peut préciser, en second paramètre, la valeur que l'on veut avoir pour une clef absente
print(boxoffice.get('Mon Film', 0))
print(boxoffice.get('Avengers', 0))

True
0
132260

Recherche dans une liste et dans un dictionnaire

Lorsqu’on cherche une valeur dans une liste, il faut, dans le pire cas, parcourir tous les éléments un par un. La complexité est donc en \(O(n)\) où \(n\) est la taille de la liste.

def recherche_liste(element, liste):
    for e in liste:
        if e == element:
            return True
    return False

animaux = ['chat', 'chien', 'poule', 'vache', 'cochon']
print(recherche_liste('vache', animaux))
print(recherche_liste('tigre', animaux))

True
False

Lorsqu’on cherche une clé dans un dictionnaire, Python utilise une table de hachage. Le principe est le suivant : une fonction de hachage transforme la clé en un indice de tableau, ce qui permet d’accéder directement à la valeur associée, sans parcourir toute la structure. La complexité est donc en \(O(1)\) en moyenne.

ages = {'Alice': 17, 'Bob': 16, 'Charlie': 18}
print('Bob' in ages)
print('Diana' in ages)

True
False

Le test d’appartenance in effectue une recherche en \(O(n)\) sur une liste et en \(O(1)\) sur un dictionnaire. Cela se vérifie expérimentalement :

import time

n = 10_000_000
grande_liste = list(range(n))
grand_dict = {i: None for i in range(n)}

t0 = time.time()
print(n - 1 in grande_liste)
t1 = time.time()
print(f"Liste : {t1 - t0:.4f} s")

t0 = time.time()
print(n - 1 in grand_dict)
t1 = time.time()
print(f"Dictionnaire : {t1 - t0:.6f} s")

La différence est spectaculaire : la recherche dans la liste prend quelques centièmes de seconde tandis que celle dans le dictionnaire prend environ une microseconde, soit un facteur de l’ordre de 10 000, quelle que soit la taille de la structure.

À retenir. Le choix entre une liste et un dictionnaire a un impact majeur sur les performances d’un programme. Si l’on a besoin de tester fréquemment l’appartenance d’un élément, un dictionnaire (ou un ensemble set) est bien plus adapté qu’une liste.

Type des clés et valeurs

Les clés peuvent être de différents types (mais non mutables)

chiffres_arabes_vers_romains = {1: 'I', 10: 'X', 100: 'C'}
print(chiffres_arabes_vers_romains[10])

X

grille = {(0,0): 'T', (0,1): 'S', (1,0): ' ', (1,1): 'T'}
print(grille[(0,0)] == 'T')

True

Ce code provoque une erreur :

d1 = {'s': 3, 8: 'chat', [1, 'chien']: (2, 7)}
print(d1)

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    d1 = {'s': 3, 8: 'chat', [1, 'chien']: (2, 7)}
TypeError: unhashable type: 'list'

Pas celui-ci :

d2 = {'s': 3, 8: 'chat', (1, 'chien'): (2, 7)}
print(d2)

{'s': 3, 8: 'chat', (1, 'chien'): (2, 7)}

Les valeurs aussi peuvent être de différents types

thon = {'espece': 'T', 'gestation': 3}
requin = {'espece': 'S', 'gestation': 2, 'energie': 2}
mer = {(0, 0): thon, (0, 1): None, (1, 0): None, (1, 1): requin}

print(mer[(0, 0)]['espece'])
print(mer[(1, 1)]['energie'])

T
2
Vérifiez votre compréhension
  1. Pourquoi une liste ne peut-elle pas servir de clé dans un dictionnaire, alors qu’un tuple le peut ?
    RéponseLes clés d'un dictionnaire doivent être hachables, c'est-à-dire non mutables. Une liste est mutable (on peut modifier ses éléments), donc non hachable. Un tuple est immutable, donc hachable et utilisable comme clé.
  2. Quelle est la différence entre boxoffice['Mon Film'] et boxoffice.get('Mon Film', 0) quand la clé n’existe pas ?
    Réponseboxoffice['Mon Film'] lève une exception KeyError qui interrompt le programme. boxoffice.get('Mon Film', 0) renvoie la valeur par défaut 0 sans erreur. La méthode get est plus sûre quand on n'est pas certain que la clé existe.
  3. Pourquoi la recherche d’une clé dans un dictionnaire est-elle en O(1) alors qu’elle est en O(n) dans une liste ?
    RéponseUn dictionnaire utilise une table de hachage : une fonction transforme la clé en un indice de tableau, permettant un accès direct sans parcourir la structure. Dans une liste, il faut potentiellement examiner tous les éléments un par un.
L'essentiel à retenir
  • Un dictionnaire est un ensemble de couples (clé, valeur), accessibles par clé et non par position ; l’accès à une valeur par sa clé est en O(1) grâce au hachage.
  • Les clés doivent être non mutables (chaînes, entiers, tuples) ; les valeurs peuvent être de n’importe quel type.
  • On itère avec .keys(), .values() ou .items() ; l’absence d’une clé se gère avec try/except KeyError ou la méthode .get().
  • Le choix entre liste et dictionnaire a un impact majeur sur les performances : O(n) vs O(1) pour la recherche.
  • Les dictionnaires servent de base aux représentations de graphes et à de nombreuses structures en Python.
Chapitres liés