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.