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).
637576
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 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 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 :
nombre_entier = ord(cle)*256**(n-1) + ord(cle)*256**(n-2) + ... + ord(cle[n-1])
n désignant le nombre de caractères de la clé.
On obtient ainsi la fonction Python :
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) # code ascii du caractère cle
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 :
# 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 :
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 :
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 :
637577
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 :
637578
On peut implémenter une liste chaînée en Python à l'aide de deux classes :
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 :
# 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 :
# 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.
637723
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 :
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(*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 :
# 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 :
637706
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 :
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 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
liste_chainee.queue.suivant = maillon
liste_chainee.queue = maillon
# copie de la liste dans le slot
self.table = liste_chainee
Pour tester la méthode, nous écrivons simplement ces lignes :
# 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 :
637775
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 :
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:
# on récupère la liste chaînée à l'emplacement donné par la valeur de hachage
liste_chainee = self.table
# 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==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 :
# 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 :
637776
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 :
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) # code ascii du caractère cle
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(*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 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
liste_chainee.queue.suivant = maillon
liste_chainee.queue = maillon
# copie de la liste dans le slot
self.table = 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:
# on récupère la liste chaînée à l'emplacement donné par la valeur de hachage
liste_chainee = self.table
# 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==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 = 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:
# on récupère la liste chaînée à l'emplacement donné par la valeur de hachage
liste_chainee = self.table
# 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==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
Vous avez lu gratuitement 92 articles depuis plus d'un an.
Soutenez le club developpez.com en souscrivant un abonnement pour que nous puissions continuer à vous proposer des publications.
Soutenez le club developpez.com en souscrivant un abonnement pour que nous puissions continuer à vous proposer des publications.