Prepa Help
Prepa Help › Cours › Informatique, 2e année

Dictionnaires et principes du hachage : cours, méthodes et exercices corrigés

Type abstrait dictionnaire, syntaxe et parcours, table de hachage, fonction de hachage, collisions, résolution par paquets, coûts moyens et pire cas, redimensionnement, limites sur le domaine des clés, compter, regrouper, indexer, choisir sa collection.

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

Ce que tu sauras faire

Un dictionnaire retrouve une valeur à partir d'une clé, presque sans dépendre du nombre de données. On s'en sert depuis la première année sans regarder comment il fonctionne. Ce chapitre reprend tout l'usage du dictionnaire en Python, puis ouvre la boîte : pourquoi l'accès est-il si rapide, à quelles conditions, et pourquoi toutes les valeurs ne peuvent-elles pas servir de clé ?

L'essentiel : Vocabulaire Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

À retenir Définitions
  • Dictionnaire : ensemble d'associations (clé, valeur), avec une valeur au plus par clé.
  • Table de hachage : tableau de mm alvéoles ; la clé cc va dans l'alvéole f(c)=h(c) mod mf(c) = h(c) \bmod m, où hh est la fonction de hachage.
  • Haché : l'entier h(c)h(c). Deux clés égales ont le même haché ; la réciproque est fausse en général.
  • Collision : deux clés différentes dans la même alvéole. Dès qu'il y a plus de clés possibles que d'alvéoles, ff n'est pas injective : c'est le principe des tiroirs.
  • Résolution par paquets : chaque alvéole contient une liste de couples (clé, valeur) ; on compare la clé dans le paquet.
  • Facteur de remplissage : α=n/m\alpha = n / m.

Une méthode du chapitre Extrait gratuit

Méthode Choisir la bonne collection à partir des opérations demandées
Quand l’utiliser

L'énoncé demande une structure de données, ou bien tu dois en choisir une pour écrire une fonction. Le programme demande que ce choix soit un « choix éclairé ».

Rappel de cours

Une liste donne l'accès par indice en temps constant, et une recherche linéaire. Un dictionnaire donne l'accès par clé en temps constant en moyenne, mais il n'a pas d'indice et pèse plus lourd. Une liste triée donne une recherche en O(log⁡n)O(\log n) et une insertion en O(n)O(n) (cours, sections 2.3 et 10.1).

Démarche
  1. Écrire les opérations du programme : chercher, ajouter, parcourir dans l'ordre, lire le ii-ème.
  2. Repérer celle qui se répète le plus.
  3. Regarder les données : les clés sont-elles 0,…,n−10, \dots, n - 1 ? Y a-t-il des répétitions ?
  4. Choisir, et dire le coût de l'opération la plus fréquente.
  5. Citer le défaut accepté : mémoire, pas d'indice, pas de répétition de clé.
Rédaction type

« L'opération la plus fréquente est la recherche d'un adhérent par son numéro, en O(n)O(n) dans une liste de couples. Un dictionnaire de clés les numéros la ramène à un temps constant en moyenne, au prix d'une mémoire plus grande. Comme aucun accès par rang n'est demandé, ce choix ne coûte rien d'autre. »

Exemple traité

Trois besoins. Noter la température de chaque heure d'une journée : les indices 0 à 23 sont des clés naturelles, on prend une liste. Compter les mots d'un texte : les clés sont des chaînes inconnues d'avance, on prend un dictionnaire. Enregistrer les pesées d'un jour dans l'ordre d'arrivée, avec des valeurs répétées : on garde une liste, car un dictionnaire perdrait les répétitions.

Erreurs fréquentes
  • Choisir un dictionnaire pour des clés 0,…,n−10, \dots, n - 1 : plus lourd, sans gain.
  • Justifier par « c'est plus rapide » sans nommer l'opération.
  • Oublier qu'un dictionnaire n'accepte pas deux fois la même clé.
Pour s’entraîner

Exercices 10 et 32.

Un exercice corrigé Extrait gratuit

Exercice Lire et écrire dans un dictionnaire ★☆☆

On exécute le programme suivant, ligne après ligne.

stock = {'dattes': 12, 'figues': 7}
stock['amandes'] = 3
stock['dattes'] = stock['dattes'] + 1
print(len(stock))
print('figues' in stock, 7 in stock)
print(stock['dattes'])
print(stock)
print(stock['noix'])
print('fin')
  1. Donner sur papier l'état de stock après chacune des trois premières lignes.
  2. Prédire chaque ligne affichée, et dire où le programme s'arrête.
  3. Corriger la dernière lecture pour que le programme affiche absent au lieu de s'arrêter, puis fin.
Indications
  • Méthode 2 : d[c] = v crée la clé si elle manque et remplace sa valeur si elle existe.
  • Méthode 3 : x in d ne regarde que les clés, jamais les valeurs.
  • Lire une clé absente lève une erreur et arrête le programme.
Analyse : comment trouver l’idée

Pour chaque ligne, demande-toi d'abord si la clé existe déjà. Écris ensuite ce que le test d'appartenance compare à quoi. Pour la question 3, cherche le test à faire avant de lire.

Correction détaillée

Question 1. Après la première ligne, stock contient deux associations. La deuxième ligne crée la clé 'amandes'. La troisième remplace la valeur de 'dattes', qui passe de 12 à 13 : aucune clé n'est créée.

Question 2. Le dictionnaire a trois clés. 'figues' est une clé, mais 7 n'en est pas une : c'est une valeur, et in ne regarde pas les valeurs. L'ordre d'affichage est l'ordre d'insertion. La lecture de 'noix' arrête le programme, et fin n'est jamais affiché.

Le programme affiche :

3
True False
13
{'dattes': 13, 'figues': 7, 'amandes': 3}
KeyError: 'noix'

Question 3.

On teste la clé avant de lire. Le test coûte peu et évite l'arrêt du programme.

if 'noix' in stock:
    print(stock['noix'])
else:
    print('absent')
print('fin')

Le programme affiche :

absent
fin
Méthodes à retenir

Écrire crée ou remplace, lire exige que la clé existe, et in ne voit que les clés. Voir les méthodes 2 et 3.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 16 méthodes, 24 pièges corrigés, la carte mentale, 35 exercices corrigés, 3 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Ce chapitre est offert : il s’ouvre en entier avec un compte d’essai gratuit.

Ouvrir l'essai gratuit

Plan du cours

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

  1. Choisir la bonne collection à partir des opérations demandées
  2. Créer et remplir un dictionnaire
  3. Lire sans erreur : tester une clé avant d'y accéder
  4. Compter des occurrences en une seule passe
  5. Regrouper : un dictionnaire de listes
  6. Indexer et inverser, gérer les valeurs répétées
  7. Parcourir et chercher la clé de valeur maximale
  8. Tester l'appartenance avec un dictionnaire
  9. Choisir une clé hachable, composer une clé par un tuple
  10. Représenter un enregistrement ou un graphe par un dictionnaire
  11. Copier sans alias
  12. Calculer un haché à la main et ranger des clés dans une table
  13. Justifier une complexité avec dictionnaire
  14. Expliquer le principe du hachage en quatre phrases
  15. Écrire une table de hachage par paquets
  16. Se souvenir d'un résultat déjà calculé

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (14)

Entraînement (16)

Approfondissement (5)

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Sujets de concours sur ce chapitre

9 sujets à télécharger gratuitement en PDF, sans corrigé. Tous les sujets de concours.

Comment y accéder

Ce chapitre fait partie des chapitres offerts : il s'ouvre en entier avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet, les tarifs ou une question, écris-nous sur WhatsApp.

Toute ta prépa au même endroit

Pour chaque chapitre : le cours, l'essentiel, les méthodes, les pièges, les exercices corrigés, les problèmes de concours, et un assistant qui répond à tes questions. Programmes du Maroc et de France. Avec la plateforme vidéo YOUNESS SCHOOL offerte, dès 600 DH (60 $) par mois, sans engagement.

Prépas scientifiques : voir l'offrePrépas ECS et ECT : voir l'offreTu hésites encore ? Essaie gratuitement Prepa Help.

← Algorithmes gloutons