Les dictionnaires (ou tableaux associatifs) ont déjà été abordé en première, il permettent de retrouver une données à partir d'une clef (et pas d'un index comme pour un tableau. Nous allons voir dans ce chapitre comment implémenter un dictionnaire et par là aborder la notion de table de Hachage.
Interface.
Les interfaces de base d'un tableau associatif sont :
La création
L'ajout d'une donnée associée à une clef.
La récupération d'une donnée via une clef.
La modification d'une donnée via une clef.
la suppression d'une donnée via une clef.
Implémentation
Nous allons créer un tableau associatif qui marchera avec des clefs de type chaîne de caractères, le principe étant le même avec les autres type de clef. (il n'y a pas besoin d'avoir des types identiques pour les clefs dans un dictionnaire Python)
Le principe est relativement simple, on part d'un tableau indexé (le tableau est la structure de base) de taille fixe (généralement grand , puis à chaque clef on associe un index et on place le coupe (clef, indexe dans la tableau).
fonction de Hachage
Une fonction de hachage a pour but de transformer un objet quelconque (ici une chaîne de caractère) en un nombre (qui servira d'index). Les fonctions de hachages sont importantes et utilisées notamment en cryptographie, donnons des exemples de table de hachage.
A une chaîne on associe sa longueur. f("bonjour") = 7.
A une chaîne on associe la somme des représentation ASCII des caractères. g("bonjour") = 767
Longueur : Somme des caractères :
Collisions
Prenons comme fonction de hachage la longueur d'un mot, notre dictionnaire est au départ un tableau indexé (de taille 10 pour se fixer les idées. Plaçons le couple clef = "lundi", valeur = "Monday", comme lundi a pour longueur 5 on va ranger le couple (comme un tuple ("lundi","Monday")) dans la case d'indice 5 du tableau. Plaçons maintenant le couple clef = "mardi", valeur = "Tuesday", comme mardi a aussi une longueur de 5 il faut le placer dans la case d'indice 5 mais il y a déjà un élément dans cette case ! On dit qu'il y a collision.
Pour éviter le plus possible les collisions on doit :
Avoir une bonne fonction de hachage qui va répartir équitablement les clefs dans les cases.
Avoir beaucoup de case dans le tableau de base.
Malheureusement en mathématiques il existe un résultat en combinatoire appelé paradoxe des anniversaires qui montre que même avec une fonction de hachage qui garantie la répartition équitable et un tableau de taille 356 il suffit de rentrer 23 clefs pour avoir plus d'une chance sur deux d'avoir une collision. Les collisions sont donc plus ou moins inévitables et on a deux façons d'en tenir compte.
Première façon.
On place le couple clef-valeur dans la case d'indice obtenue par la fonction de hachage et si elle est déjà occupée on passe à la case libre qui suit.
Indice :
0
1
2
3
4
5
6
7
8
9
clef :
valeur :
Deuxième façon.
On place le couple clef-valeur dans une liste elle même contenue dans la case d'indice obtenue dans la table de hachage.
Indice :
0
1
2
3
4
5
6
7
8
9
Implémentation.
Voici une des façons d'implémenter un dictionnaire en utilisant la deuxième façon, ici on surcharge les méthodes pour avoir la même utilisation qu'avec les dictionnaires de base de Python, on peut même itérer sur une instance de Dico !
On utilise un tableau self._tableau (de taille fixe mais comme Python n'a pas de "vrai" tableau on prend une liste), On utilise ensuite les listes de bases de python, mais généralement on utilise des listes chainées (voir cours précédent).