[Actualité] Implémentation naïve d'une table de hachage en Python
par
, 25/04/2023 à 11h26 (5857 Affichages)
I. Introduction
Une table de hachage est une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif :
Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1).
Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie.
Il s'agit d'un tableau ne comportant pas d'ordre. On accède à chaque valeur ou élément par sa clé, qui transformée par une fonction de hachage en une valeur de hachage (un nombre) indexe les éléments de la table, ces derniers étant appelés alvéoles (en anglais, buckets ou slots).
Pour mieux comprendre le fonctionnement et aussi l'intérêt de ces tables de hachage on présentera dans ce billet un exemple d'implémentation naïve en Python.
A noter qu'en python les tables de hachage sont appelées dictionnaires. Dans un dictionnaire, on associe une valeur à une clé.
II. Fonction de hachage
Elle permet de transformer la clé en une valeur de hachage, donnant ainsi la position d'une alvéole dans le tableau. Le but étant bien sûr de minimiser le nombre de collisions, c'est-à-dire le nombre de clés ayant la même valeur d'index.
Le calcul de la valeur de hachage se fait dans notre cas en deux étapes :
- On transforme la clé en un nombre entier ;
- Ce nombre entier est converti en une position possible dans la table en calculant le reste modulo la taille de la table.
On convertit ainsi une clé composée d'une séquence de caractères ASCII en un nombre entier, puis on utilise la méthode de division modulo pour obtenir la valeur d'index de la table.
II-A. Fonction de conversion de la clé en nombre entier
Elle transforme la clé constituée d'une séquence de caractères ASCII en un nombre entier.
On utilise pour cela la fonction Python ord() qui va renvoyer la valeur ASCII de chaque caractère cle[i] de la chaîne cle. Il existe en fait 128 caractères de ce type et 256 en ASCII étendu.
Ensuite, on attribue un poids qui est une puissance de 256 à chaque code ASCII, le poids fort étant logiquement affecté au code du premier caractère de la chaîne.
On calcule enfin la somme pondérée des codes ASCII comme pour un changement de base :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part nombre_entier = ord(cle[0])*256**(n-1) + ord(cle[1])*256**(n-2) + ... + ord(cle[n-1])
n désignant le nombre de caractères de la clé.
On obtient ainsi la fonction Python :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 def convertir_cle(cle): # transforme la clé en nombre entier # conversion de la chaîne de caractères en nombre entier : "ABCD" -> 65*256^3 + 66*256^2 + .. # initialisation de la somme : nombre entier nombre_entier = 0 # nombre de caractères de la clé n = len(cle) # parcours des indices des caractères : 0 -> (nombre_caracteres - 1) for i in range(n): code_asc = ord(cle[i]) # code ascii du caractère cle[i] nombre_entier += code_asc*(256**(n-1-i)) # nombre_entier = nombre_entier + code_ascii.256^(n-1-i) return nombre_entier # retourne le nombre entier résultat de la conversion de la chaîne de caractères
Note : il existe bien sûr des librairies Python qui proposent des fonctions de hachage bien meilleures.
II-B. Fonction de hachage
On transforme la clé en valeur entière à l'aide de la fonction précédente :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 # conversion de la clé en nombre entier nombre_entier = convertir_cle(cle)
Ensuite, la valeur de hachage est obtenue en calculant le reste de la division du nombre entier par la taille de la table :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part valeur_hachage = nombre_entier % taille_table
En réalité, on divise généralement le nombre entier par un nombre premier proche de la taille de la table, et en prenant une table de dimension suffisamment grande on évite ainsi au maximum les collisions.
On peut alors écrire la fonction complète en Python :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 def fonction_hachage(cle, taille_table): # transforme la clé en valeur de hachage. # conversion de la clé en nombre entier nombre_entier = convertir_cle(cle) return (nombre_entier % taille_table) # retourne la valeur de hachage : reste modulo la taille de la table
Il s'agit ici d'un exemple très simple de fonction de hachage, si vous souhaitez avoir plus de détail sur le sujet je vous invite à consulter cette page.
III. Chaînage
Dans notre cas, chaque alvéole de la table de hachage est une liste chaînée des paires clé–valeur qui ont la même valeur de hachage. Une fois l'alvéole trouvée, la recherche est alors linéaire en la taille de la liste chaînée :
Le principe de la liste simplement chaînée est que chaque maillon possède, en plus de la donnée, un pointeur vers le maillon suivant dans la liste.
Une liste simplement chaînée, composée de trois éléments ayant respectivement les valeurs : 12, 99 et 37 :
On peut implémenter une liste chaînée en Python à l'aide de deux classes :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9 class Maillon: def __init__(self, Valeur=None): self.valeur = valeur # valeur transmise au moment de la création de l'objet Maillon self.suivant = None # pas d'élément suivant au moment de la création de l'objet class ListeChainee: def __init__(self): self.tete = None # tête de la liste chaînée initialisée à None self.queue = None # queue de la liste chaînée initialisée à None
Exemple de mise en œuvre :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 # création d'un objet ListeChainee liste_chainee = ListeChainee() # création d'un premier maillon contenant 12 maillon1 = Maillon(12) # ajout de ce maillon à la tête et à la queue de la liste chaînée liste_chainee.tete = maillon1 liste_chainee.queue = maillon1 # création d'un second maillon contenant 99 maillon2 = Maillon(99) # ajout du second maillon à la queue de la liste chaînée liste_chainee.queue.suivant = maillon2 liste_chainee.queue = maillon2
Dans notre cas, on souhaite ajouter des paires clé-valeur à notre liste chaînée :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 # création d'un objet ListeChainee liste_chainee = ListeChainee() # création d'un premier maillon contenant la paire ('Bonnaventure Sébastien', '01 01 01 01 12') maillon1 = Maillon(('Bonnaventure Sébastien', '01 01 01 01 12')) # ajout de ce maillon à la tête et à la queue de la liste chaînée liste_chainee.tete = maillon1 liste_chainee.queue = maillon1 # création d'un second maillon contenant la paire ('Amat Laurent', '07 01 01 01 77') maillon2 = Maillon(('Amat Laurent', '07 01 01 01 77')) # ajout du second maillon à la queue de la liste chaînée liste_chainee.queue.suivant = maillon2 liste_chainee.queue = maillon2
Si vous souhaitez avoir plus d'information sur les listes chaînées, je vous invite à consulter cette page wikipedia.
IV. Implémentation naïve de la table de hachage
Comme on l'a vu précédemment, une table de hachage est une structure de données qui permet une association clé–valeur.
Mais si on souhaite pouvoir ajouter, supprimer ou rechercher une paire clé-valeur dans cette table, il nous faut donc créer une classe Python.
Notre classe comportera un constructeur, c'est-à-dire une méthode particulière __init__() dont le code est exécuté quand la classe est instanciée.
Elle va nous permettre d'initialiser le tableau dont la taille est passée en argument au moment de la création de l'objet :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 class TableHachage: def __init__(self, taille_table): # initialisation de la table de hachage avec toutes les cellules du tableau à None: self.tableau = Array([None, None, ...]) self.table = array([None]*taille_table) def __str__(self): # permet d'afficher le contenu de la table de hachage # initialisation de la variable d'index index=0 contenu_table = "Table de hachage :\n" contenu_table = contenu_table + '-----------------------------------------------------\n' # parcours des slots de la table de hachage : chaque slot est une liste chaînée for slot in self.table: # ajoute à la chaîne de caractères contenu_table l'index de la table contenu_table = contenu_table + 'index: ' + str(index) + "\n" if slot: # si le slot n'est pas vide # ajoute à la chaîne de caractères contenu_table les paires contenues dans la liste chaînées maillon=slot.tete # tant qu'il y a un maillon ou un élément dans la liste while maillon: # ajoute la paire clé-valeur à la chaîne contenu_table = contenu_table + str(maillon.valeur) + '\n' # passe à l'élément suivant de la liste chaînée maillon = maillon.suivant index+=1 return contenu_table # retourne le contenu de la table sous forme de chaîne de caractères #...
La méthode __str__ permet d'afficher le contenu de la table de hachage.
Pour tester ces méthodes, nous ajoutons ces lignes au module :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 # création de l'objet TableHachage : table comportant 13 slots (13 étant un nombre premier) table_hachage = TableHachage(13) # affiche le contenu de la table de hachage print(table_hachage)
Le code affiche :
On a choisit une table comportant 13 slots pour l'exemple, mais en réalité compte tenu du nombre d'entrées possibles dans la table, sa taille devrait être beaucoup plus importante.
IV-A. Ajouter des entrées à la table
On souhaiterait maintenant insérer des entrées clé-valeur dans la table de hachage, on doit donc ajouter une méthode à notre classe :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class TableHachage: .... def ajouter(self, cle, valeur): # évaluation de la valeur de hachage à partir de la clé valeur_hachage = fonction_hachage(cle, self.taille_table()) # création du maillon contenant la paire cle-valeur maillon = Maillon((cle, valeur)) # si pas d'élément à cet emplacement dans le tableau if self.table[valeur_hachage] is None: # création de la liste chaînée avec un seul maillon ou élément liste_chainee = ListeChainee() liste_chainee.tete = maillon liste_chainee.queue = maillon else: # sinon # ajout de l'élément à la liste chaînée liste_chainee = self.table[valeur_hachage] liste_chainee.queue.suivant = maillon liste_chainee.queue = maillon # copie de la liste dans le slot self.table[valeur_hachage] = liste_chainee
Pour tester la méthode, nous écrivons simplement ces lignes :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14 # liste d'entrées à ajouter à la table de hachage liste_entrees = [{'clé': 'Bonnaventure Sébastien', 'valeur': '01 01 01 01 12'}, {'clé': 'Amat Laurent', 'valeur': '07 01 01 01 77'}, {'clé': 'Le Breton Tiphaine', 'valeur': '06 01 01 01 35'}, {'clé': 'Cardin Anthony', 'valeur': '09 01 01 01 44'}, {'clé': 'Soudain Cyril', 'valeur': '04 01 01 01 32'}, {'clé': 'Valdes Lucien', 'valeur': '07 01 01 01 21'}, {'clé': 'Harry John', 'valeur': '03 01 01 01 23'}, {'clé': 'Thiel Xavier', 'valeur': '05 01 01 01 17'}, {'clé': 'Gillet Mélanie', 'valeur': '02 01 01 01 15'}, {'clé': 'Richard Océane', 'valeur': '03 01 01 01 25'}, {'clé': 'Dias Pauline', 'valeur': '06 01 01 01 27'}, {'clé': 'Moulin Olivier', 'valeur': '04 01 01 01 11'}] # ajout d'une liste d'entrées aux bons emplacements dans la table de hachage for entree in liste_entrees: table_hachage.ajouter(entree['clé'], entree['valeur']) # affiche le contenu de la table de hachage après l'ajout de ces entrées print(table_hachage)
Le code affiche :
Note : on voit qu'il y a en tout seulement 2 collisions et que dans le pire des cas on peut par exemple accéder à la valeur de la clé Thiel Xavier en seulement 2 comparaisons.
IV-B. Rechercher une paire clé-valeur dans la table
Si on souhaite en plus rechercher une paire clé-valeur dans la table de hachage, on doit alors ajouter une méthode rechercher à notre classe :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class TableHachage: .... def rechercher(self, cle): # détermination de la valeur de hachage pour la valeur de clé à rechercher valeur_hachage = fonction_hachage(cle, self.taille_table()) # si au moins une entrée est présente à cet emplacement dans le tableau if self.table[valeur_hachage]: # on récupère la liste chaînée à l'emplacement donné par la valeur de hachage liste_chainee = self.table[valeur_hachage] # premier maillon de la liste chaînée maillon = liste_chainee.tete # tant qu'il y a un maillon ou un élément dans la liste chaînée while maillon: # si la clé de la paire est égale à la clé recherchée if maillon.valeur[0]==cle: return maillon.valeur # retourne la paire correspondante maillon = maillon.suivant return None
Pour tester la méthode, nous avons juste besoin de quelques lignes de code :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 # recherche d'une paire dans la table à l'aide de sa clé paire = table_hachage.rechercher('Thiel Xavier') if paire: # si une paire a été trouvée print(paire) # affiche la paire else: # sinon print("Pas de résultat !")
Le code affiche :
V. Module complet
On donne ici le code complet pour effectuer les tests avec en plus une méthode pour supprimer une paire clé-valeur de la table :
Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197 from numpy import * # librairie utilisée pour créer un tableau Array([...]) def convertir_cle(cle): # transforme la clé en nombre entier # conversion de la chaîne de caractères en nombre entier : "ABCD" -> 65*256^3 + 66*256^2 + .. # initialisation de la somme : nombre entier nombre_entier = 0 # nombre de caractères de la clé n = len(cle) # parcours des indices des caractères : 0 -> (nombre_caracteres - 1) for i in range(n): code_asc = ord(cle[i]) # code ascii du caractère cle[i] nombre_entier += code_asc*(256**(n-1-i)) # nombre_entier = nombre_entier + code_ascii.256^(n-1-i) return nombre_entier # retourne le nombre entier résultat de la conversion de la chaîne de caractères def fonction_hachage(cle, taille_table): # transforme la clé en valeur de hachage. # conversion de la clé en nombre entier nombre_entier = convertir_cle(cle) return (nombre_entier % taille_table) # retourne la valeur de hachage : reste modulo la taille de la table # liste chaînée composée d'éléments ou de maillons : chaque maillon contient une valeur et un pointeur sur le maillon suivant class Maillon: def __init__(self, valeur=None): self.valeur = valeur # on transmet la valeur self.suivant = None # pas d'élément suivant : création d'un seul maillon au début class ListeChainee: def __init__(self): self.tete = None # tête de la liste chaînée initialisée à None self.queue = None # queue de la liste chaînée initialisée à None class TableHachage: def __init__(self, taille_table): # initialisation de la table de hachage avec toutes les cellules du tableau à None: self.tableau = Array([None, None, ...]) self.table = array([None]*taille_table) def __str__(self): # permet d'afficher le contenu de la table de hachage # initialisation de la variable d'index index=0 contenu_table = "Table de hachage :\n" contenu_table = contenu_table + '-----------------------------------------------------\n' # parcours des slots de la table de hachage : chaque slot est une liste chaînée for slot in self.table: # ajoute à la chaîne de caractères contenu_table l'index de la table contenu_table = contenu_table + 'index: ' + str(index) + "\n" if slot: # si le slot n'est pas vide # ajoute à la chaîne de caractères contenu_table les paires contenues dans la liste chaînées maillon=slot.tete # tant qu'il y a un maillon ou un élément dans la liste while maillon: # ajoute la paire clé-valeur à la chaîne contenu_table = contenu_table + str(maillon.valeur) + '\n' # passe à l'élément suivant de la liste chaînée maillon = maillon.suivant index+=1 return contenu_table # retourne le contenu de la table sous forme de chaîne de caractères def taille_table(self): # retourne la taille de la table de hachage : nombre de slots return len(self.table) def ajouter(self, cle, valeur): # évaluation de la valeur de hachage à partir de la clé valeur_hachage = fonction_hachage(cle, self.taille_table()) # création du maillon contenant la paire cle-valeur maillon = Maillon((cle, valeur)) # si pas d'élément à cet emplacement dans le tableau if self.table[valeur_hachage] is None: # création de la liste chaînée avec un seul maillon ou élément liste_chainee = ListeChainee() liste_chainee.tete = maillon liste_chainee.queue = maillon else: # sinon # ajout de l'élément à la liste chaînée liste_chainee = self.table[valeur_hachage] liste_chainee.queue.suivant = maillon liste_chainee.queue = maillon # copie de la liste dans le slot self.table[valeur_hachage] = liste_chainee def supprimer(self, cle): # détermination de la valeur de hachage pour la valeur de clé à rechercher valeur_hachage = fonction_hachage(cle, self.taille_table()) # si au moins un élément est présent à cet emplacement dans le tableau if self.table[valeur_hachage]: # on récupère la liste chaînée à l'emplacement donné par la valeur de hachage liste_chainee = self.table[valeur_hachage] # premier maillon de la liste chaînée maillon = liste_chainee.tete maillon_prec = None # tant qu'il y a un maillon ou un élement dans la liste chaînée while maillon: # si la valeur de la clé de la paire est égale à la clé recherchée if maillon.valeur[0]==cle: if maillon_prec: # s'il y a un maillon précédent # suppression du maillon : le maillon préc. pointe désormais sur le maillon suivant maillon_prec.suivant = maillon.suivant if maillon.suivant is None: liste_chainee.queue = maillon_prec else: # sinon liste_chainee.tete = liste_chainee.tete.suivant if liste_chainee.tete is None: self.table[valeur_hachage] = None # plus de maillon on vide le slot return True # renvoie True pour indiquer que la suppression a bien été effectuée maillon_prec = maillon maillon = maillon.suivant return False # renvoie False pour indiquer qu'on a pas trouvé l'élément def rechercher(self, cle): # détermination de la valeur de hachage pour la valeur de clé à rechercher valeur_hachage = fonction_hachage(cle, self.taille_table()) # si au moins un élément est présent à cet emplacement dans le tableau if self.table[valeur_hachage]: # on récupère la liste chaînée à l'emplacement donné par la valeur de hachage liste_chainee = self.table[valeur_hachage] # premier maillon de la liste chaînée maillon = liste_chainee.tete # tant qu'il y a un maillon ou un élément dans la liste chaînée while maillon: # si la valeur de la clé de la paire est égale à la clé recherchée if maillon.valeur[0]==cle: return maillon.valeur # retourne la paire correspondante maillon = maillon.suivant return None print("I. Création de la table de hachage :\n") # création de l'objet TableHachage : table comportant 13 slots (13 étant un nombre premier) table_hachage = TableHachage(13) # affiche le contenu de la table de hachage print(table_hachage) print() print("II. Ajout d'entrées à la table de hachage :\n") # liste d'entrées à ajouter à la table de hachage liste_entrees = [{'clé': 'Bonnaventure Sébastien', 'valeur': '01 01 01 01 12'}, {'clé': 'Amat Laurent', 'valeur': '07 01 01 01 77'}, {'clé': 'Le Breton Tiphaine', 'valeur': '06 01 01 01 35'}, {'clé': 'Cardin Anthony', 'valeur': '09 01 01 01 44'}, {'clé': 'Soudain Cyril', 'valeur': '04 01 01 01 32'}, {'clé': 'Valdes Lucien', 'valeur': '07 01 01 01 21'}, {'clé': 'Harry John', 'valeur': '03 01 01 01 23'}, {'clé': 'Thiel Xavier', 'valeur': '05 01 01 01 17'}, {'clé': 'Gillet Mélanie', 'valeur': '02 01 01 01 15'}, {'clé': 'Richard Océane', 'valeur': '03 01 01 01 25'}, {'clé': 'Dias Pauline', 'valeur': '06 01 01 01 27'}, {'clé': 'Moulin Olivier', 'valeur': '04 01 01 01 11'}] # ajout d'une liste d'entrées aux bons emplacements dans la table de hachage for entree in liste_entrees: table_hachage.ajouter(entree['clé'], entree['valeur']) # affiche le contenu de la table de hachage après l'ajout de ces entrées print(table_hachage) print() print("III. Recherche d'une paire clé-valeur dans la table de hachage :\n") # recherche d'une paire dans la table à l'aide de sa clé paire = table_hachage.rechercher('Thiel Xavier') if paire: # si une paire a été trouvée print(paire) # affiche la paire else: # sinon print("Pas de résultat !")
VI. Conclusion
Cet implémentation naïve nous aura notamment permis de mieux comprendre comment ajouter une entrée ou rechercher une clé dans une table de hachage.
Libre à chacun ensuite d'améliorer le code proposé en choisissant par exemple une meilleure fonction de hachage.
Sources :
https://fr.wikipedia.org/wiki/Table_de_hachage
https://fr.wikipedia.org/wiki/Fonction_de_hachage
https://fr.wikipedia.org/wiki/Liste_cha%C3%AEn%C3%A9e