User

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 :

1. On transforme la clé en un nombre entier ;
2. 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