Question 161

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 hachage

Une 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.

Variantes

Il 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éalisation

Sous 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

' Ces 2 constantes peuvent être changées mais pour que l'algorithme de hachage reste efficace, il faut que:
Private Const N_HASH As Long = 400093       ' N_HASH soit un nombre premier
Private Const B_HASH As Long = 256          ' B_HASH soit une puissance de 2

Private arrHashTable(N_HASH) As Collection  ' la table de hachage

Public Function Exists(Key As String) As Boolean
    Dim lngHash As Long
    Dim Result As Boolean
    Dim TableKey As Variant
    
    Exists = False

    ' on calcule le hash de la chaine
    lngHash = Hash(Key)
    
    ' si une ou plusieurs valeurs sont présentes à cette position
    If Not arrHashTable(lngHash) Is Nothing Then
        'Parcours la liste de collisions pour déterminer si notre valeur existe
        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)
    
    'Crée la collection, si aucun élément n'a été ajouté pour ce hachage
    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
        'Parcours tous les éléments correspondant au hachage
        'et supprime celui demandé
        
        For i = 1 To arrHashTable(lngHash).Count
            If arrHashTable(lngHash)(i) = Key Then
                arrHashTable(lngHash).Remove i
                Exit For
            End If
        Next

        'Détruit la collection si celle-ci ne contient plus d'éléments
        If (arrHashTable(lngHash).Count = 0) Then
            Set arrHashTable(lngHash) = Nothing
        End If
    End If
End Sub

'La fonction de hachage proprement dite
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
    
    'Lit chacun des mots d'un dictionnaire, et les ajoute à la table
    Open "C:\...\Dictionnaire.txt" For Input As FileNumber
    
    While Not EOF(FileNumber)
        Line Input #FileNumber, Word
        a.Add Word
    Wend
        
    Close FileNumber
    
    'Détermine si un mot existe
    Debug.Print a.Exists("implémenter")
    Debug.Print a.Exists("implémmenter")
End Sub

Aller plus loin :

• Hashtable sur Wikipedia (en)
• Table de hachage sur Wikipédia (fr)
• Fonction de hachage sur Wikipédia (fr)
• General Purpose Hash Function Algorithms (en)

Voir aussi :

• Comment implémenter et utiliser les structures de données classiques ?
• Comment utiliser l'objet Collection ?