Dictionnaires et tables de hachage
Cours · NSI (terminale), chapitre 2 · terminale, spécialité numérique et sciences informatiques · le début du chapitre, la suite sur Adloun
Le type dictionnaire est l'une des structures de données les plus utilisées en informatique. Contrairement aux tableaux et aux listes, où l'on accède aux éléments par un indice entier, le dictionnaire permet d'associer à une clé arbitraire (chaîne de caractères, nombre, tuple, etc.) une valeur quelconque. Cette association clé valeur, appelée parfois tableau associatif ou map, est rendue remarquablement efficace grâce à une technique fondamentale : le hachage.
Dans ce chapitre, nous étudions d'abord l'interface du type dictionnaire et les opérations disponibles en Python. Nous expliquons ensuite le mécanisme interne qui permet ces performances : la table de hachage, la fonction de hachage et la gestion des collisions. Nous analysons enfin le coût des opérations et présentons plusieurs applications classiques : le comptage d'occurrences, la construction d'index et la mémoïsation.
2.1 Le type dictionnaire
2.1.1 Définition et vocabulaire
Un dictionnaire est une structure de données qui associe à chaque clé une unique valeur. L'ensemble des couples constitue le contenu du dictionnaire. Les clés sont deux à deux distinctes : une même clé ne peut apparaître qu'une seule fois.
En Python, le dictionnaire est un type intégré (dict). On le construit avec des accolades, en séparant chaque clé de sa valeur par le caractère deux-points.
# Un annuaire associant un nom a un numero de telephone
annuaire = {
"Alice": "06 12 34 56 78",
"Bob": "07 98 76 54 32",
"Chloe": "06 11 22 33 44"
}
# Un dictionnaire vide
vide = {}
print(type(vide)) # <class 'dict'>En Python, une clé de dictionnaire doit être un objet hachable, c'est-à-dire immuable et possédant une valeur de hachage stable : nombres, chaînes de caractères, booléens et tuples (composés d'éléments hachables) sont hachables. Les listes et les dictionnaires, qui sont modifiables, ne peuvent pas servir de clé.
2.1.2 Opérations fondamentales
Méthode : Accès, ajout et modification
On accède à la valeur associée à une clé avec la notation entre crochets d[cle]. La même notation permet d'ajouter un nouveau couple ou de modifier une valeur existante.
annuaire["Alice"] # lecture -> "06 12 34 56 78"
annuaire["David"] = "06 00 00 00 00" # ajout
annuaire["Bob"] = "07 00 00 00 00" # modificationL'accès à une clé absente provoque une erreur KeyError.
Méthode : Test d'appartenance et suppression
L'opérateur in teste la présence d'une clé. L'instruction del supprime un couple. La méthode get renvoie une valeur par défaut si la clé est absente, évitant ainsi l'erreur.
"Chloe" in annuaire # True
"Zoe" in annuaire # False
del annuaire["Chloe"] # suppression du couple
annuaire.get("Zoe", "inconnu") # "inconnu" (cle absente)Méthode : Parcours d'un dictionnaire
On peut parcourir les clés, les valeurs ou les couples au moyen des méthodes keys, values et items.
for cle in annuaire: # parcourt les cles
print(cle)
for cle, valeur in annuaire.items(): # parcourt les couples
print(cle, "->", valeur)
n = len(annuaire) # nombre de couplesExercices du chapitre
- Mot le plus fréquent corrigé
- Détecter un anagramme corrigé
- Premier élément non répété corrigé
- Problème — Cache de résultats générique corrigé
- Inverser un dictionnaire corrigé
- Fusionner deux dictionnaires corrigé