Logo de kxs.frCours d'informatique pour le lycée et la prépa

Dictionnaires

Présentation

Le nom générique pour un dictionnaire en informatique est tableau associatif. Un dictionnaire est composé d'un ensemble de couples clé:valeur. On peut accéder à une valeur en utilisant sa clé. Par exemple pour stocker les coordonnées d'une personne il sera possible d'utiliser un dictionnaire. Si on utilise un dictionnaire Python :

individu = {"nom": "McFly", "prenom": "Marty", "date": "09/06/1968"}

Interface

Définition

L'interface d'un tableua associatif possède habituellemnt les méthodes suivantes :

ajoute(cle, valeur)
ajoute un couple clé:valeur ;

modifie(cle, valeur)
modifie la valeur correspondant à cle ;

supprime(cle)
supprime le couple correspondant à cle ;

recherche(cle)
renvoie la valeur associé à cle ;

Exemple

1) Considérant la suite d'instructions suivante, donnez ce que renvoie l'instruction ou le contenu du dictionnaire à chaque ligne repérée par un numéro en commentaire. mon_dico est initialement un dictionnaire vide. On représentera le dictionnaire par des couples clé:valeur séparés par de virgules entre acolades comme en Python.

mon_dico.ajoute("Maurice", "051245")
mon_dico.ajoute("Ginette", "250168")
mon_dico.ajoute("Emile", "140842") #1
mon_dico.modifie("Maurice", "061245") #2
mon_dico.recherche("Ginette") #3
mon_dico.supprime("Emile")
mon_dico.ajoute("Marcel", "280136") #4

Implémentation

2) Pour ne pas, encore un fois, créer une classe en Python, décrivez simplement comment Python permet d'effectuer les quatre opérations ci-dessus.

Bilan

Un avantage des dictionaires en Python est qu'ils permettent d'accéder rapidement à un élément grâce à sa clé. Pour cela Python utilise une table de hashage. Pour comprendre le fonctionnement d'une table de hashage, regardez la vidéo ci-dessous :

3) Implémentez la fonction de hashage proposée dans la vidéo et testez-la sur plusieurs chaînes de caractère.