Numérique et sciences informatiques (spécialité) · TerminaleBac
Dictionnaires et tables de hachage : fiche de Terminale NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
- Un dictionnaire (ou tableau associatif) range des couples clé : valeur ; chaque clé est associée à une seule valeur au plus 3.
- On accède à une valeur à partir de sa clé, pas de sa position 1.
- Une fonction de hachage calcule, à partir d'une donnée, une valeur qui donne sa position dans une table 2.
- Une table de hachage a une recherche en en moyenne ; dans le pire des cas, le coût peut atteindre 3.
- Un arbre équilibré garde l'ordre des clés, pas une table de hachage 3.
L'essentiel sur les dictionnaires
Les opérations et leur coût
Tables de hachage
Table de hachage ou arbre équilibré
Hachage et sécurité
Les fonctions de hachage servent aussi en cryptographie. Pour vérifier qu'un document n'a pas été modifié, on lui associe une empreinte conservée séparément : une modification du document doit entraîner une modification de l'empreinte 2. Les fonctions MD5 et SHA-1 calculent des empreintes de 128 bits et de 160 bits 2.
Questions flash
5 questions · correction immédiate · ton score reste sur ton appareil.
-
On interroge un dictionnaire avec la clé, qui est associée à la valeur. La position n'a pas de sens ici : contrairement à une liste, les éléments ne sont pas repérés par un indice entier.
-
Chaque clé n'a qu'une seule valeur, au plus. Écrire de nouveau la même clé remplace l'ancienne valeur. Ce sont des clés différentes qui peuvent partager une même valeur.
-
En moyenne, la recherche dans une table de hachage est en . Le est le coût dans le pire des cas d'un arbre équilibré, et le celui du pire des cas de certaines tables de hachage.
-
On calcule , car . La case est donc la numéro 2. Répondre 5 revient à confondre le quotient et le reste.
-
Un arbre équilibré préserve l'ordre des clés. Une table de hachage ne le préserve pas : les clés sont dispersées selon leur adresse.
Les questions qu'on se pose
Pourquoi une table de hachage est-elle plus rapide qu'une liste pour chercher ?
Dans une liste, il faut parfois parcourir de nombreux éléments. Avec une table de hachage, on calcule l'adresse à partir de la clé et on va directement à l'endroit voulu. En moyenne, le temps de recherche ne dépend pas du nombre d'éléments 1.
Que se passe-t-il quand deux clés ont la même adresse ?
C'est une collision. La table doit prévoir un moyen de ranger les deux couples, par exemple dans une même case. Si les collisions sont nombreuses, la recherche ralentit et peut atteindre dans le pire des cas 3.
Une table de hachage garde-t-elle l'ordre des clés ?
Non : les tables de hachage ne préservent pas l'ordre des clés, alors que les arbres équilibrés le préservent 3. Ne compte donc pas sur un parcours des clés dans l'ordre croissant (en Python, un dict garde seulement l'ordre d'insertion).
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.