Dictionnaires
Les dictionnaires ont déjà été étudiés en classe de première. Pour rappel, ce type de données, aussi appelé tableau associatif, permet de stocker des valeurs et d'y accéder au moyen d'une clé, contrairement au tableau qui permet d'accéder à une donnée au moyen d'un indice.
Exemple
Voici ce à quoi ressemble l'utilisation d'un dictionaire en python :
dico = dict() dico["Nom"] = "Aldébaran" dico["Prenom"] = "Andjekel" print( dico["Prenom"] + " " + dico["Nom"])
Dans cet exemple, les clés sont les chaînes "Nom" et "Prenom". On affiche ensuite leurs valeurs.
Opérations classiques sur les dictionnaires
Les opérations classiques que l'on peut effectuer sur un dictionnaire sont :
- Ajouter une nouvelle entrée au dictionnaire en créant une nouvelle clé
- Modifier la valeur associée à une clé existante
- Suprimer une entrée dans un dictionnaire (méthode
.pop()) - Rechercher la présence d'une clé dans un dictionnaire.
La recherche dans un dictionnaire est optimisée pour s'effectuer sur les clés et non sur les valeurs. Par exemple
avec le dictionnaire que nous avons créé précédemment, la commande "Nom" in dico renverra True alors que "Aldébaran" in dico renverra False.
Dans un dictionnaire, les clés et les valeurs ne jouent donc pas du tout le même rôle et ne sont pas interchangeables.
Les clés
Une clé peut être d'un autre type que chaîne de caractère, du moment que c'est un objet non mutable,
c'est à dire qui ne peut pas être modifié. Une clé ne peut pas être une liste par exemple car une liste
est un objet mutable que l'on peut modifier, par exemple au travers de la méthode .append().
Regardons ce qui se passe si on essaye de définir une clé de type list pour un dicitonnaire :
dico[[2,1]] = "..." --------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-4-d463baccae6e> in <module>() ----> 1 dico[[2,1]] TypeError: unhashable type: 'list'
Le type list n'est pas pas hashable. Mais qu'est-ce que le hachage ?
Hachage
La notion de Hachage est omiprésente en informatique et est au coeur du fonctionnement des dictionnaires. Le hachage est un mécanisme permettant de transformer la clé en un nombre unique permettant l'accès à la donnée, un peu à la manière d'un indice dans un tableau.
Définition d'une fonction de hachage
Une fonction de hachage est une fonction qui va calculer une empreinte unique à partir de la donnée fournie en entrée. Elle doit respecter les règles suivantes :
- La longueur de l'empreinte (valeur retournée par la fonction de hachage) doit être toujours la même, indépendamment de la donnée fournie en entrée.
- Conaissant l'empreinte, il ne doit pas être possible de reconstituer la donnée d'origine
- des données différentes doivent donner dans la mesure du possible des empreintes différentes.
- des données identiques doivent donner des empreintes identiques.
Quelques utilisations du hachage
L'utilisation la plus courante est le stockage des mots de passe dans un système informatique un peu sécurisé.
En effet, lorsqu'on crée un compte sur un service en ligne, le mot de passe ne doit pas être stocké en clair, une empreinte est générée
afin que si le service est piraté et que les comptes sont dérobés, il ne soit pas possible de reconstituer le mot de passe
à partir de l'empreinte. Voici un exemple de fonctionnement d'une fonction de hachage.
Nous utiliserons le hachage
accessible sous Python au travers de la fonction hash() :
>>> hash("Aldébaran") 7932194494807972993
>>> hash("Aldebaran") -2778791670536604289
>>> hash("Andjekel Aldébaran") -8861304277632426640
On constate bien sur cet exemple que :
- toutes les empreintes ont la même longueur
- un petit changement dans la valeur d'entrée fournit une empreinte totalement différentes
Une autre utilisation du hachage est la détection de la modification d'un fichier.
Ainsi la fonction de hachage peut mettre en évidence des différences qui seraient invisibles à l'oeil nu.
Table de Hachage
Regardez la vidéo ci-dessous sur les tables de hachage.
Ce qui est important à retenir c'est que la recherche dans une table de hachage est indépendante du nombre d'éléments dans cette table.
Dans un tableau ou une liste chaînée au contraire, la recherche d'un élément prend un temps proportionnel au nombre d'éléments dans la structure.
Dans un dictionnaire, les clés sont stockées dans une table de hachage, ce qui explique le fait que le dictionnaire est optimisé pour la recherche sur les clés.
Nous allons vérifier cela en pratique dans un TP.
La version du Tp en NOTEBOOK à télécharger
utilisation des dictionnaires en Python
Vous pouvez à présent regarder la vidéo suivante afin de reviser la manipulation des dictionnaires en python.