Dictionnaires, index et clé

Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel

L'essentiel

Un dictionnaire (ou tableau associatif) stocke des couples clé:valeur. Contrairement à une liste où l'on accède par une position (indice entier), on accède ici par une clé, qui peut être une chaîne, un entier, un tuple, etc.

Chaque clé est unique dans un dictionnaire et doit être immuable (hachable) : on peut utiliser str, int, tuple, mais pas list ni dict.

L'intérêt majeur est la rapidité d'accès : retrouver une valeur par sa clé se fait en temps constant en moyenne, O(1), grâce à une table de hachage. Une fonction de hachage transforme la clé en indice de case du tableau interne.

Formules et schémas clés

Opérations de base en Python :

d = {} # dictionnaire vide d["Ada"] = 1815 # ajout / modification x = d["Ada"] # lecture, KeyError si absente "Ada" in d # test de présence -> booléen del d["Ada"] # suppression d.get("Zoe", 0) # lecture avec valeur par défaut for cle in d: ... # itération sur les clés

Comparaison des accès :

| Structure | Accès par identifiant | Recherche par valeur | |---|---|---| | Liste (non triée) | O(1) par indice | O(n) | | Dictionnaire | O(1) moyen par clé | O(n) |

Méthode type bac

1. Repérer ce qui sert de clé (identifiant unique) et ce qui sert de valeur. 2. Utiliser d[cle] = valeur pour construire ; cle in d pour tester. 3. Pour compter/regrouper, utiliser d.get(cle, defaut). 4. Pour ne pas modifier un dictionnaire en entrée, en faire une copie (dict(d)).

Pièges

  • Accéder à une clé absente avec d[k] lève KeyError : utiliser k in d ou d.get(k, defaut).
  • Une clé mutable (liste) est interdite : TypeError: unhashable type.
  • Le dictionnaire n'a pas de notion d'ordre par position : on n'accède pas par indice numérique.
  • Modifier un dictionnaire passé en paramètre modifie l'original (passage par référence) : copier si besoin.

Pour l'épreuve

Le dictionnaire est l'outil de prédilection pour compter des occurrences, indexer des données ou réaliser une recherche rapide par clé. Justifiez la complexité O(1) moyenne par le hachage, en signalant que le pire cas théorique est O(n) en cas de collisions, rare en pratique. À l'épreuve pratique, on manipule très souvent des dictionnaires pour représenter des graphes (listes d'adjacence) ou des comptages : maîtrisez get, in, del et l'itération sur les clés ou sur les couples avec items(). Savoir comparer dictionnaire et liste sur le critère de la recherche (accès par clé en O(1) contre parcours en O(n)) est une justification fréquemment demandée à l'écrit.