Comment réaliser une table de hachage (ou hash table) ?
Une table de hachage (aussi appelée hash table ou hash map) est une structure de données, permettant des opérations d'ajout et de vérification d'existence extrêmement rapides. Ces structures sont très utilisées lorsqu'il est nécessaire de vérifier la présence d'un élément donné parmi une grande quantité d'informations, tel un mot dans un dictionnaire. Ses capacités d'accès rapide en font aussi un allier précieux pour retrouver un élément sur base d'une clé donnée, qu'il s'agisse d'un ListItem contenu dans une ListView, d'un Node contenu dans un TreeView, ou de n'importe quel objet présent dans une Collection. Structure d'une table de hachageUne table de hachage est un simple vecteur (tableau unidimensionnel), de taille fixe. Chaque élément est ajouté à une position correspondant à son "hachage". Le hachage est obtenu par une fonction de hachage, associant à un élément un indice dans le tableau. La table de hachage étant de taille limitée, on se rend compte que des collisions pourraient survenir si deux éléments obtenaient le même hachage. Il est donc important de conserver non seulement la présence du hachage dans la table, mais aussi la valeur à laquelle celui-ci est associé. Dans le cas contraire il serait impossible de distinguer la présence ou l'absence de deux éléments distincts disposant du même hachage. Afin de conserver plusieurs éléments distincts ayant le même hachage, on emploiera une structure de données appropriée, telle qu'une liste liée. Il est à remarquer que le parcours de cette liste de collisions sera moins rapide que l'accès au hachage dans la table. Il est donc important de choisir le fonction de hachage correctement pour limiter le nombre de collisions, malgré le nombre fini d'indices du tableau. VariantesIl est éventuellement possible d'associer aux éléments de la table de hachage une donnée significative pour le programme. C'est notamment le cas de l'objet collection où chaque clé est associée à un Variant. Certaines tables de hachage peuvent être basées sur des tableaux dynamiques. Lorsque trop d'éléments sont ajoutés et que par conséquent de nombreuses collisions sont présentes, pour éviter les pertes de performances, le tableau est agrandi. Les hachages de chaque clé doivent être recalculés en raison du nouvel espace et les éléments redistribués dans la table de hachage. Cette opération a un coût non négligeable, qui n'est compensé que sous certaines conditions. Plus d'informations à ce sujet sont disponibles dans la rubrique pour aller plus loin. Les variations les plus fréquentes concernent la résolution de collision et la fonction de hachage. Différentes structures de données autres qu'une liste liée peuvent présenter de nets avantages pour réaliser cette résolution. La technique dite de l'adressage ouvert est une variante très souvent employée. D'autres structures proposent des accès plus rapide ou des coûts en mémoire moindres. Concernant la fonction de hachage, celle-ci peut être optimisée par rapport aux éléments qui seront ajoutés. La construction d'une fonction de hachage efficace dépasse le cadre de cet article, mais d'autres ressources ne sont pas à négliger. RéalisationSous Visual Basic, la manière la plus courante d'utiliser une hashtable est l'utilisation de collections en tous genres, et plus particulièrement de leur clés. Nous vous proposons une implémentation simpliste où les clés, qui seront des chaînes de caractères, seront les seules données stockées. Les collisions seront gérées à l'aide de l'objet Collection. Puisque cet objet implémente déjà une table de hachage, son utilisation peut paraître redondante. Il faut cependant garder à l'esprit que l'exemple d'implémentation vise à montrer le principe plutôt qu'à être l'ultime manière efficace d'implémenter ce type de structure. Les méthodes implémentées seront les suivantes : - Exists(Key) : Détermine si une clé (Key) est présente dans la table
- Add(Key) : Ajoute une clé (Key) à la table
- Remove(Key) : Supprime une clé (Key) de la table
- Count : Détermine le nombre de clés stockées
Les points importants de l'implémentation sont les suivants : - Chacune des opérations se base sur la fonction Hash, permettant de calculer le hachage, donc la position, de l'élément demandé.
- Lorsqu'une clé doit être retrouvée dans la table, l'ensemble des clés ajoutées correspondant au hachage sont parcourues dans un For Each. On peut déduire intuitivement que ce parcours de chacune des clés une par une est plus lent que l'accès direct à l'élément de tableau correspondant au hachage.
Option Explicit
Private Const N_HASH As Long = 400093 Private Const B_HASH As Long = 256
Private arrHashTable(N_HASH) As Collection
Public Function Exists(Key As String) As Boolean Dim lngHash As Long Dim Result As Boolean Dim TableKey As Variant Exists = False
lngHash = Hash(Key) If Not arrHashTable(lngHash) Is Nothing Then For Each TableKey In arrHashTable(lngHash) If TableKey = Key Then Exists = True Exit For End If Next TableKey End If End Function
Public Sub Add(Key As String) Dim lngHash As Long
lngHash = Hash(Key) If arrHashTable(lngHash) Is Nothing Then Set arrHashTable(lngHash) = New Collection End If arrHashTable(lngHash).Add Key End Sub
Public Sub Remove(Key As String) Dim lngHash As Long Dim i As Long
lngHash = Hash(Key) If Not arrHashTable(lngHash) Is Nothing Then For i = 1 To arrHashTable(lngHash).Count If arrHashTable(lngHash)(i) = Key Then arrHashTable(lngHash).Remove i Exit For End If Next
If (arrHashTable(lngHash).Count = 0) Then Set arrHashTable(lngHash) = Nothing End If End If End Sub
Private Function Hash(s As String) As Long Dim v As Long Dim i As Long For i = 1 To Len(s) v = (v * B_HASH + Asc(Mid$(s, i, 1))) Mod N_HASH Next i Hash = v End Function La fonction suivante présente un exemple d'utilisation : Public Sub Test() Dim a As HashTable Dim FileNumber As Integer Dim Word As String Set a = New HashTable FileNumber = FreeFile Open "C:\...\Dictionnaire.txt" For Input As FileNumber While Not EOF(FileNumber) Line Input #FileNumber, Word a.Add Word Wend Close FileNumber Debug.Print a.Exists("implémenter") Debug.Print a.Exists("implémmenter") End Sub
Aller plus loin : Voir aussi : |