Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous

Identifiant
Mot de passe

Mot de passe oublié ?

Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

Apprendre comment faire une implémentation naïve d'une table de hachage en Python

Un billet blog de Denis Hulo

Le 25 avril 2023, par User

0PARTAGES

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Une erreur dans cette actualité ? Signalez-nous-la !

Votre nom : Votre e-mail :

Décrivez l'erreur que vous souhaitez porter à notre connaissance :

Commenter Signaler un problème