4. Le TAD hashtable_t

On suppose que les types key_t et value_t désignent respectivement le type des clés et le type des valeurs.

On suppose également que le type element_t est une structure avec les 2 champs contenant les valeurs et clés :

            typedef struct {
              key_t key;
              value_t value;
            } element_t;
          

5. Hachage par chaînage

La table de hachage est simplement une table de listes chaînées, chaque maillon contenant la clé et la valeur associée.

On utilise les fonctions de base sur les listes pour ajouter en tête, rechercher si une clé est déjà présente, obtenir la valeur associée à une clé, supprimer un couple [clé, valeur].

          typedef struct _link {
            element_t val;      // un élément de la liste
            struct _link *next; // l'adresse du maillon suivant
          } link_t, *list_t;    // les structures de maillon et de liste

          typedef struct {
            int size;     // nombre de listes de la table
            list_t* data; // tableau de listes d'éléments, devant être alloué dynamiquement
          } hashtable_t;  // la structure de la table de hachage

        

5.1 Création de la table

La fonction hashtable_t hashtable_new(int m) crée une structure et alloue dynamiquement le tableau de listes.

Le code de la fonction est simple :

          // Crée et retourne une nouvelle table de m listes vides ;
          // Retourne une table vide en cas d'erreur
          hashtable_t hashtable_new(int m) {
            hashtable_t t;
            t.size = 0;
            t.data = calloc(m, sizeof(list_t)) ; // allocation du tableau de m listes
            if(t.data == NULL) {
              return t ; // échec de l'allocation => retourne une table vide
            }
            t.size = m;
            return t;
          }
        

5.2 Insertion d'un couple [clé,valeur]

La fonction int hashtable_put(key_t k, value_t v, hashtable_t t) ajoute un couple [clé,valeur] par l'algorithme suivant :

            h = calculer l'indice de hachage de la clé k.
            element_t e = créer un élément contenant la clé k et la valeur v
            Ajouter e à la liste d'indice h, c'est à dire à la liste   t.data[h]
            si l'ajout à la liste a fonctionné
              retourner 1
            sinon
              retourner 0
          

Attention toutefois : une clé donnée ne doit apparaître qu'une seule fois dans la table ! Pour cela, les implémentations choisissent en général l'une des deux options suivantes :

1. Précondition : le contrat de la fonction hashtable_put() précise en précondition que la clé k ne doit pas être déjà présente dans la table. Dès lors, comme d'habitude avec les préconditions, le développeur doit le vérifier avant d'appeler la fonction hashtable_put().
2. Remplacement : si la clé existe déjà dans la table, alors la fonction hashtable_put() remplace la valeur associée par la nouvelle valeur.

Dans cette fiche, on choisit la première option (précondition). Vous verrez la seconde en TD/TP.

Voici alors le code C pour La fonction int hashtable_put(key_t k, value_t v, hashtable_t t) :

            /**
              Ajoute le couple k,v à la table de hachage t.
              retourne 1 si l'ajout est réussi, 0 sinon.
              PRECONDITION : k n'est pas une clé déjà existante dans la table
            */
            int hashtable_put(key_t k, value_t v, hashtable_t t)  {
              // Remarque : du fait de la précondition "k n'est pas une clé déjà existante dans la table",
              // pas la peine de tester si la clé k existe déjà dans la table.

              int h = hash(k, t.size); // calcul du code de hachage pour la clé k
              element_t e;
              e.key=k;
              e.value=v;

              /*
                Ajout du couple à la liste t.data[i]
                Rappel : si l'ajout dans la liste ne réussit pas, list_add_first() retourne l'ancien premier maillon.
                Donc il faut d'abord mettre de côté l'ancienne tête de liste.
              */
              // 1. On met de côté l'état courant de la liste
              list_t old_list=t.data[h];

              // 2. tentative d'ajout
              t.data[h]=list_add_first(e, t.data[h] );

              // 3. On vérifie que l'ajout à la liste s'est bien passé
              if (t.data[h] == old_list) {
                // Erreur lors de l'ajout
                return 0;
              }

              // Ajout réussi
              return 1;
            }
          

5.2 Recherche

La fonction int hashtable_contains(key_t k, hashtable_t t) recherche si la clé est présente par l'algorithme suivant :

            h =  calculer l'indice de hachage de la clé k
            ptr_maillon =  valeur de retour de la fonction de recherche de la clé k dans la liste située à l'indice h de la table
            si ptr_maillon vaut NULL
              retourner 0
            sinon
              retourner 1
          

La fonction int hashtable_getvalue(key_t k, value_t* pv, hashtable_t t) recherche si la valeur associée à la clé par l'algorithme suivant :

            h =  calculer l'indice de hachage de la clé k
            ptr_maillon =  valeur de retour de la fonction de recherche de la clé k dans la liste située à l'indice h de la table
            si ptr_maillon vaut NULL
              retourner 0
            sinon
              *pv = partie valeur du maillon pointée par pmaillon;
              retourner 1
          

5.3 Suppression d'une clé

La fonction int hashtable_deletekey(key_t k, hashtable_t t) supprime la clé (si elle est présente) par l'algorithme suivant

            h =  calculer l'indice de hachage de la clé k
            ptr_maillon =  valeur de retour de la recherche de la clé k dans la liste située à l'indice h de la table
            si ptr_maillon vaut NULL
              retourner 0
            sinon
              Supprimer le maillon de la liste située à l'indice h de la table;
              retourner 1
          

5.4 Destruction de la table complète

La fonction hashtable_t hashtable_delete(hashtable_t t) supprime tous les éléments et la table par l'algorithme suivant

            Pour toutes les listes l de la table t
              destruction de la liste l
            libérer la mémoire allouée pour le tableau de listes
            mettre la taille à 0
            retourner t;
          

6. Hachage ouvert

Le hachage ouvert est une alternative dans laquelle tous les éléments sont stockés dans un tableau, sans listes chaînées.

Il ne peut fonctionner que si le nombre d'éléments de la table est inférieur à la taille de la table.

6.1 Principes du Hachage ouvert et sondage

Il existe plusieurs stratégies de sondage :

• sondage linéaire :

  à partir de l'indice j=hash(k), on regarde si la case d'indice j est vide, puis la case j+1, puis j+2, etc jusqu'à trouver une case vide. La fonction de hachage totale s'écrit donc j=hash(k)+i où i est le nombre d'essais.

• sondage quadratique :

  à partir de l'indice j=hash(k), on regarde si la case d'indice j est vide, puis la case j+1, puis j+4, puis j+9 etc jusqu'à trouver une case vide. La fonction de hachage totale s'écrit donc j=hash(k)+c1*i+c2*i*i où j est le nombre d'essais et c1,c2 sont des constantes.

• sondage double hachage :

  on utilise une deuxième fonction de hachage g. A partir de l'indice j=hash(k), on regarde si la case d'indice j est vide, puis la case j+g(k), puis j+2*g(k), etc... jusqu'à trouver une case vide. La fonction de hachage totale s'écrit donc j=hash(k)+i*g(k) où i est le nombre d'essais.

Dans la suite, pour simplifier, les explications s'appuient sur le principe du sondage linéaire.

6.2 Insertion et hachage ouvert

Prenons pour exemple notre fonction de hachage basique (somme des lettres). Voici un exemple d'insertion avec cette fonction et le sondage linéaire.

Insertion par sondage dans une table d'association

                // On veut ajouter ajouter les clés k=
                //      lame, male,  mela, puis mena
                // dans la table. L'algorithme d'insertion est :
                i=0
                répéter
                  h = hash(k) + i
                  si la case h est libre
                  alors
                    remplir cette case avec la clé et sa valeur
                  sinon
                    incrementer i
                jusqu'à atteindre la fin de la table
                Erreur car table pleine
              

Ajout de la la clé lame.
Rappel : hash("lame")=31

i=0, j=31

La case d'indice 31 est vide

on remplit la case d'indice 31 de la table avec la clé k=lame et sa définition

Ajout de la la clé male.
Rappel : hash("male")=31

i=0, j=31

La case d'indice 31 est deja remplie

i=1

i=1, j=32

La case d'indice 32 est vide

on remplit la case d'indice 32 de la table avec la clé male et sa définition

Ajout de la la clé mela.
Rappel : hash("mela")=31

i=0, j=31

La case d'indice 31 est deja remplie

i=1

i=1, j=32

La case d'indice 32 est deja remplie

i=2

i=2, j=33

La case d'indice 33 est vide

on remplit la case d'indice 33 de la table avec la clé mela et sa définition

pour la clé mena, hash("mena")=33

i=0, j=33

La case d'indice 33 est deja remplie

i=1

i=1, j=34

La case d'indice 34 est vide

on remplit la case d'indice 34 de la table avec la clé mena et sa définition

6.3. Recherche et hachage ouvert

La recherche d'une clé et/ou d'une valeur s'effectue de manière identique. L'algorithme s'écrit de la manière suivante :

            i=0
            l = calculer l'indice de hachage de la clé k
            répéter
              h = l + i
              si la case h n'est pas vide ET si la clé k est égale à la clé stockée dans la table
              alors
                retourner la valeur associée à la clé dans la case h
              sinon
                incrementer i
            jusqu'à atteidre une case VIDE ou la fin de la table
            retourner "PAS TROUVE"
          

6.4. Suppression et hachage ouvert

La suppression d'une clé (et de la valeur associée) est un peu plus compliquée. On ne peut pas simplement marquer à VIDE la case du tableau qui contenait la clé.

En effet, si on se contente de vider la case contenant la clé, alors l'algorithme d'insertion et l'algorithme de recherche ne fonctionnent plus. Pour l'expliquer, dans le slide qui suit :

• on ajoute les entrées lame, male, mela, mena dans la table. Les cases d'indice 31 à 34 sont donc remplies.
• puis on supprime l'entrée male avec l'algorithme de suppression erroné qui se contente de vider la case (la case d'incice 32).

L'état de la table est donc à ce moment :

A partir de cet état, dans le slide qui suit, on recherche le mot mela, avec notre algorithme de recherche :

Que devient l'algorithme de recherche
si l'algorithme de suppression est erroné ?

                i=0
                répéter
                  h = hash(k) + i
                  si la case h n'est pas vide ET si la clé k est égale à la clé stockée dans la table
                  alors
                    retourner la valeur associée à la clé dans la case h
                  sinon
                    incrementer i
                jusqu'à la case h est VIDE ou la fin de la table est atteinte
                retourner PAS TROUVE
              

pour la clé mela, hash("mela")=31

i=0, j=31

La case d'indice 31 n'est pas vide, mais la clé de la table lame n'est pas la bonne clé.

i=1

i=1, j=32

La case d'indice 32 est vide

i=2

La case h est VIDE, on quitte la recherche

En conséquence, l'algorithme indique que la clé mela n'est pas dans la table.

Cette erreur est due à l'arrêt de la boucle sur la case qui vient d'être vidée par l'algorithme de suppression de male !

Une solution à ce problème est, dans l'algorithme de suppression, de ne pas vider la case qui contenait la clé supprimée, mais d'indiquer que cette case contenait une clé qui a été supprimée.

Si on implante ainsi l'algorithme de suppression, les deux encarts qui suivent montrent comment il faut modifier les algorithmes d'insertion et de recherche :

Nouvel algorithme d'insertion lorsque l'algorithme de suppression est correct

              // Algorithme corrigé pour linsertion de la la clé k et de sa valeur 
              i=0
              répéter
                h = hash(k) + g(k,i)
                si la case h est VIDE ou SUPPRIME
                alors
                  remplir cette case avec la clé et sa valeur
                sinon
                incrementer i
              jusqu'à atteidre la fin de la table
              Erreur car table pleine
            

Nouvel algorithme de recherche lorsque l'algorithme de suppression est correct

            // Algorithme corrigé pour la recherche de la la clé k
            i=0
            répéter
              h = hash(k) + g(k,i)
              si la case h n'est pas VIDE
                si la case h est SUPPRIME OU si la clé k n'est pas égale à la clé à l'indice h
                alors
                  incrementer i
                sinon
                  retourner la valeur à cet indice h
            jusqu'à la case h est VIDE ou la fin de la table est atteinte
            retourner PAS TROUVE
          

Dans ces 2 algorithmes, la fonction g(k,i) est la fonction suivante :

• sondage linéraire : g(k,i) = i
• sondage quadratique : g(k,i) = c1*i+c2*i*i c1 et c2 constantes non nulles
• double hachage : g(k,i) : i*h2(k) où h2 est une deuxième fonction de hachage

7. Comparaison et conclusion

7.1 Complexité moyenne

Les performances dépendent de 2 paramètres :

• la taille de la table M
• le nombre de clés utilisées N

On définit aussi le facteur de charge par α=N/M

7.2 Remarques et comparaison qualitative

Le hachage ouvert par sondage linéaire a l'inconvénient de provoquer des regroupements des clés les unes derrière les autres, provoquant ainsi de nouvelles collisions. C'est le phénomène de grappe.

Exemple avec la fonction de hachage basique (somme des lettres) et le sondage linéaire.

• Ajout de lame, hash=31, indice 31 (car cette case est libre)
• Ajout de male, hash=31, indice 32 (car la case 31 est occupée) : collision classique
• Ajout de mela, hash=31, indice 33 (car les cases 31,32 sont occupées): collision classique
• Ajout de mena, hash=33, indice 34 (car le case 33 est occupée) : collision supplémentaire et grappe

Dans cet exemple, le sondage linéaire introduit une collision inexistante avec la fonction de hachage, puisque le mot mela prend la place du mot mena. Il n'est pas très uniforme.

Le sondage quadratique présente plus rarement ce phénomène de grappe, si les valeurs des constantes c1 et c2 sont bien choisies.

Le sondage par double hachage est plus difficile à implémenter, car la deuxième fonction de hachage devrait être première avec la taille de la table. Il est proche d'une distribution uniforme et meilleur que les 2 précédents.

Le chaînage présente l'inconvénient des listes chaînées. Le coût CPU de l'allocation n'est pas négligeable lors de l'insertion. Les pointeurs pour gérer le chaînage augmentent la taille mémoire nécessaire. De plus, la mémoire tend à être segmentée du fait des listes chaînées, ce qui implique un coût dans la manipulation de la table (parcours par exemple).

7.3 Quel type de hachage choisir ?