Numérique et sciences informatiques (spécialité) · TerminaleBac

Dictionnaires et tables de hachage : cours de Terminale NSI

Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur

L'essentiel

Un dictionnaire (tableau associatif) range des couples clé : valeur ; chaque clé est associée à une seule valeur au plus.³
Une table de hachage est une façon de l'implémenter : une fonction de hachage $h$ calcule, à partir de la clé, la position de la donnée dans un tableau.²
Deux clés différentes peuvent donner le même indice : c'est une collision, qu'il faut gérer (chaînage, adressage ouvert).
Recherche et insertion coûtent $O(1)$ en moyenne, mais peuvent coûter $O(n)$ dans le pire des cas ; l'ordre des clés n'est pas conservé.³
Face à un arbre équilibré : table de hachage plus rapide en moyenne, arbre meilleur dans le pire des cas et capable de parcourir les clés dans l'ordre.³

Pourquoi a-t-on besoin des dictionnaires ?

Imagine que tu gères les notes d'une classe. Avec une liste Python, tu peux ranger les notes dans l'ordre, mais pour retrouver celle de « Camille » tu dois parcourir la liste jusqu'à tomber sur le bon élève. Plus la classe est grande, plus la recherche est longue.

Ce que tu voudrais, c'est demander directement : « la note de Camille ? » et obtenir la réponse sans rien parcourir. C'est exactement le service que rend un dictionnaire. Dans ce chapitre, tu vas voir ce qu'est ce type de données, puis comment on arrive à le rendre très rapide grâce au hachage.

Tu as déjà rencontré des structures où l'on accède aux éléments par leur position (listes, listes chaînées) ou selon un ordre d'arrivée (piles, files). Ici, l'accès se fait par un nom, appelé clé, et non par un rang.

Les opérations sur un dictionnaire

Comme pour les piles et les files, on définit un dictionnaire par les opérations qu'il propose, sans parler de la mémoire. Les opérations de base sont les suivantes :

Opération	Effet
créer un dictionnaire vide	on obtient une structure sans aucun couple
ajouter / modifier un couple	si la clé existe, sa valeur est remplacée ; sinon le couple est ajouté
lire la valeur d'une clé	on obtient la valeur associée, ou une erreur si la clé est absente
tester la présence d'une clé	on obtient un booléen
supprimer un couple	la clé et sa valeur disparaissent
parcourir	on passe en revue les clés, les valeurs ou les couples

Le point important est que la clé joue le rôle d'identifiant unique : écrire deux fois avec la même clé ne crée pas deux couples, cela remplace la valeur précédente.³

ExempleUtiliser un dictionnaire en Python

notes = {}                 # dictionnaire vide
notes["Camille"] = 15      # ajout du couple ("Camille", 15)
notes["Yanis"] = 12
notes["Camille"] = 17      # la valeur de "Camille" est remplacée

print(notes["Camille"])    # 17
print("Lea" in notes)      # False
del notes["Yanis"]         # suppression du couple

for cle, valeur in notes.items():
    print(cle, valeur)

Après ces instructions, le dictionnaire ne contient plus qu'un seul couple : "Camille" associé à 17.

MéthodeCompter des occurrences avec un dictionnaire

Pour compter combien de fois chaque lettre apparaît dans un mot :

Crée un dictionnaire vide effectif.
Pour chaque lettre c du mot, regarde si c est déjà une clé.
Si oui, augmente sa valeur de 1 ; sinon, crée le couple c : 1.
À la fin, chaque clé est une lettre et chaque valeur son nombre d'apparitions.

def effectifs(mot):
    effectif = {}
    for c in mot:
        if c in effectif:
            effectif[c] = effectif[c] + 1
        else:
            effectif[c] = 1
    return effectif

print(effectifs("banane"))   # b:1, a:2, n:2, e:1

Le principe du hachage

Comment retrouver une valeur sans parcourir tout le dictionnaire ? L'idée est de calculer l'endroit où la donnée est rangée, au lieu de le chercher.

On range les données dans un tableau (une zone de mémoire où l'on accède à une case par son indice en un temps constant). Il suffit alors d'avoir un moyen de transformer une clé en indice de ce tableau. Ce moyen s'appelle une fonction de hachage.

Dans un dictionnaire, la donnée dont on calcule l'adresse est la clé. Pour une table de $m$ cases numérotées de $0$ à $m-1$ , on veut donc une fonction qui, à toute clé, associe un entier entre $0$ et $m-1$ .

Une construction très courante se fait en deux temps :

transformer la clé en un entier (pour une chaîne de caractères, on peut par exemple additionner les codes de ses caractères) ;
ramener cet entier dans l'intervalle des indices avec un reste de division : $h(k) = k \bmod m$ .

1. La cléOn part de la clé, par exemple 25.
2. CalculOn applique h(k) = k mod 7.
3. IndiceOn obtient 25 mod 7 = 4.
4. LectureOn lit directement la case 4.

Retrouver une clé grâce au hachage · Le chemin d'une clé vers sa valeur.

Les collisions et leur gestion

Il y a en général beaucoup plus de clés possibles que de cases dans la table. Par exemple, il existe une infinité de chaînes de caractères, mais la table n'a que $m$ cases. Il est donc impossible d'éviter que deux clés distinctes tombent sur la même case : on parle de collision.

Il existe deux grandes familles de solutions.

Le chaînage. Chaque case de la table ne contient pas une seule donnée mais une petite liste (souvent une liste chaînée, que tu connais) de tous les couples dont la clé tombe sur cette case. Pour chercher une clé, on calcule son indice puis on parcourt la petite liste de cette case.

L'adressage ouvert. Chaque case contient au plus un couple. Si la case visée est occupée, on essaie une autre case selon une règle fixée (par exemple la case suivante, en revenant au début à la fin du tableau). La recherche suit la même règle jusqu'à trouver la clé ou une case vide.

	Chaînage	Adressage ouvert
Contenu d'une case	une liste de couples	au plus un couple
Collision	on ajoute à la liste de la case	on cherche une autre case libre
Nombre d'éléments	peut dépasser le nombre de cases	au plus égal au nombre de cases
Suppression	simple : on retire de la liste	délicate : il faut marquer la case

Table de 7 cases avec chaînage
Indice	Contenu de la case
0	vide
1	vide
2	vide
3	31
4	25
5	12 puis 19 (collision)
6	vide

Table de 7 cases avec chaînage · Résultat de l'insertion des clés 12, 25, 31 puis 19 avec h(k) = k mod 7.

Complexité : pourquoi c'est rapide (et quand ça ne l'est plus)

Le grand intérêt de la table de hachage est la vitesse. Pour chercher un élément dans un dictionnaire, la complexité est en $O(1)$ : la durée ne dépend pas du nombre d'éléments présents.¹ Dans une liste non triée, au contraire, la recherche dans le pire des cas demande de regarder les $n$ éléments, soit $O(n)$ .

Pourquoi $O(1)$ ? Parce que les étapes sont : calculer $h(k)$ (durée constante pour une clé de taille raisonnable), lire la case d'indice $h(k)$ (accès direct dans un tableau), puis comparer avec très peu d'éléments si la répartition est bonne.

Le pire des cas arrive quand toutes les clés, ou presque, tombent sur la même case. Avec le chaînage, la table se réduit alors à une seule longue liste, qu'il faut parcourir en entier : on retrouve la recherche linéaire. Cette situation est improbable avec une bonne fonction de hachage, mais elle explique que $O(1)$ soit une garantie en moyenne et non absolue.

Table de hachage ou arbre équilibré ?

Il existe une seconde façon efficace de représenter un dictionnaire : l'arbre équilibré.³ Tu étudieras bientôt les arbres binaires de recherche ; retiens pour l'instant les différences de comportement entre les deux choix, en notant $n$ le nombre d'éléments.

Critère	Table de hachage	Arbre équilibré
Insertion et recherche en moyenne	$O(1)$	$O(\log n)$
Pire des cas	peut atteindre $O(n)$	$O(\log n)$
Ordre des clés	non conservé	conservé
Place en mémoire	souvent plus compacte	généralement moins compacte

Les tables de hachage gagnent en moyenne sur l'insertion et la recherche, alors que les arbres équilibrés l'emportent dans le pire des cas.³ La représentation en mémoire d'une table de hachage est en général plus compacte.³

La différence qui compte le plus dans la pratique est celle de l'ordre. Les arbres équilibrés préservent l'ordre des clés : on peut parcourir les clés dans l'ordre ou repérer rapidement une clé proche d'une valeur donnée. Les tables de hachage ne gardent pas cet ordre.³

Erreurs fréquentes et méthode pour le bac

Exercices corrigés

Exercice 1 Calculer des indices dans une table

★☆☆Environ 8 min

Une table de hachage contient $m = 7$ cases (indices de $0$ à $6$ ). La fonction de hachage est $h(k) = k \bmod 7$ . On insère dans l'ordre les clés $12$ , $25$ , $31$ et $19$ , avec un chaînage pour les collisions.

Calcule l'indice de la clé $25$ .
Y a-t-il une collision ? Entre quelles clés ?

Indice 1

Fais la division euclidienne de 25 par 7 et garde le reste.

Indice 2

Calcule l'indice des quatre clés et cherche celles qui partagent le même.

Voir la correction pas à pas

Pour $25$ : $25 = 3 \times 7 + 4$ , donc $h(25) = 4$ .
Les autres indices : $h(12) = 5$ car $12 = 1 \times 7 + 5$ ; $h(31) = 3$ car $31 = 4 \times 7 + 3$ ; $h(19) = 5$ car $19 = 2 \times 7 + 5$ .
Les clés $12$ et $19$ ont le même indice $5$ : c'est une collision.
Avec le chaînage, la case $5$ contient la liste des couples de clés $12$ puis $19$ .

La clé $25$ est rangée à l'indice $4$ . La collision concerne $12$ et $19$ , qui partagent la case $5$ .

Exercice 2 Hachage d'une chaîne de caractères

★★☆Environ 10 min

On définit le hachage d'un mot de la façon suivante : on additionne les codes ASCII de ses lettres, puis on prend le reste de la division par $m = 10$ . Les codes sont : N = 78, S = 83, I = 73.

Calcule l'indice de la clé "NSI" dans la table de 10 cases.

Indice 1

Additionne d'abord les trois codes.

Indice 2

Le reste de la division par 10 est le chiffre des unités.

Voir la correction pas à pas

On additionne les codes : $78 + 83 + 73 = 234$ .
On calcule le reste de la division par $10$ : $234 = 23 \times 10 + 4$ .
L'indice est donc $4$ , bien compris entre $0$ et $9$ .

La clé "NSI" est rangée à l'indice $4$ . Tout mot dont la somme des codes se termine par 4 tombe aussi sur cette case, ce qui montre pourquoi les collisions sont inévitables.

Exercice 3 Facteur de remplissage

★★☆Environ 6 min

Une table de hachage possède $m = 20$ cases et contient $n = 15$ couples. On décide d'agrandir la table dès que le facteur de remplissage $\alpha = n/m$ atteint ou dépasse $0{,}75$ .

Calcule $\alpha$ . La table doit-elle être agrandie ?

Indice 1

Divise le nombre de couples par le nombre de cases.

Indice 2

Compare le résultat au seuil de 0,75.

Voir la correction pas à pas

On applique la définition : $\alpha = \dfrac{15}{20}$ .
On simplifie : $\alpha = \dfrac{3}{4} = 0{,}75$ .
Le seuil est atteint ( $0{,}75 \geq 0{,}75$ ) : il faut agrandir la table.

Le facteur de remplissage vaut $0{,}75$ , donc la table doit être agrandie, puis toutes les clés sont replacées avec la nouvelle taille.

Exercice 4 Première lettre répétée

★★★Environ 12 min

Écris une fonction premiere_repetee(mot) qui renvoie la première lettre qui apparaît pour la deuxième fois en lisant le mot de gauche à droite, ou None si toutes les lettres sont différentes. Utilise un dictionnaire et ne parcours le mot qu'une seule fois. Donne la complexité en moyenne, puis le résultat pour "informatique".

Indice 1

Utilise un dictionnaire des lettres déjà vues, et teste la présence avant d'ajouter.

Indice 2

Chaque test de présence et chaque ajout coûtent $O(1)$ en moyenne.

Voir la correction pas à pas

On crée un dictionnaire vide vues.
On parcourt le mot lettre par lettre. Si la lettre est déjà une clé de vues, on la renvoie immédiatement.
Sinon, on l'ajoute : vues[c] = True.
Si la boucle se termine sans retour, on renvoie None.
Le mot est parcouru une fois et chaque opération sur vues est en $O(1)$ en moyenne : la complexité est en $O(n)$ pour un mot de $n$ lettres.
Pour "informatique" : i, n, f, o, r, m, a, t sont nouvelles ; la lettre i, lue ensuite, est déjà dans vues, donc la fonction renvoie "i".

def premiere_repetee(mot):
    vues = {}
    for c in mot:
        if c in vues:
            return c
        vues[c] = True
    return None

La fonction est en $O(n)$ en moyenne et renvoie "i" pour "informatique".

Les questions qu'on se pose

Pourquoi une recherche dans un dictionnaire est-elle plus rapide que dans une liste ?

Dans une liste, il faut comparer l'élément cherché aux éléments un par un, ce qui coûte $O(n)$ dans le pire des cas. Dans une table de hachage, on calcule l'adresse de la clé et on va directement à la bonne case, d'où une durée qui ne dépend pas du nombre d'éléments.¹

Peut-on avoir deux fois la même clé dans un dictionnaire ?

Non. Chaque clé est associée à une seule valeur au plus.³ Si tu écris une seconde fois avec la même clé, la nouvelle valeur remplace l'ancienne. Si tu as besoin de plusieurs valeurs pour une même clé, mets une liste comme valeur.

Pourquoi les collisions sont-elles inévitables ?

Il y a beaucoup plus de clés possibles que de cases. Quand on range plus de clés que de cases, au moins deux clés partagent forcément une case. Même avec moins de clés que de cases, une fonction de hachage peut envoyer deux clés vers le même indice par hasard. L'important est de les gérer (chaînage, adressage ouvert) et de bien répartir les clés.

Que faut-il savoir pour le bac ?

Il faut savoir définir un dictionnaire, utiliser les opérations de base en Python, expliquer le rôle d'une fonction de hachage, remplir à la main une table avec gestion des collisions, et justifier la complexité moyenne en $O(1)$ . Il faut aussi savoir comparer avec une autre structure, en particulier sur l'ordre des clés.

Quand préférer un arbre équilibré à une table de hachage ?

Quand tu as besoin de parcourir les clés dans l'ordre ou de trouver une clé proche d'une valeur donnée, car l'arbre garde l'ordre.³ Il est aussi plus sûr si tu veux éviter un pire des cas en $O(n)$ , puisque sa complexité reste logarithmique.³

Sources

Fiche NSI Terminale : Dictionnaire, Pixees (INRIA). Consulté le 7 novembre 2026.
Hachage (encyclopédie technique), Universalis. Consulté le 7 novembre 2026.
Tableau associatif, Wikipédia. Consulté le 7 novembre 2026.

Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.

Signaler une erreur sur cette page

Dictionnaires et tables de hachage : cours de Terminale NSI

L'essentiel

Pourquoi a-t-on besoin des dictionnaires ?

Les opérations sur un dictionnaire

Le principe du hachage

Les collisions et leur gestion

Complexité : pourquoi c'est rapide (et quand ça ne l'est plus)

Table de hachage ou arbre équilibré ?

Erreurs fréquentes et méthode pour le bac

Exercices corrigés

Exercice 1 Calculer des indices dans une table

Exercice 2 Hachage d'une chaîne de caractères

Exercice 3 Facteur de remplissage

Exercice 4 Première lettre répétée

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur