Retrouvez cet article dans : Linux Magazine 88

Après les listes chaînées et les chaînes de caractères, intéressons-nous aux tables de hachage, moyen convenant pour associer des clés à des données.

Introduction

Une table de hachage est, au même titre qu’un tableau ou qu’une liste chaînée, un moyen de stocker des données en mémoire et de les y retrouver. Mais contrairement à ceux-ci, où chaque donnée ne peut être identifiée que par sa position dans la structure de donnée, la table de hachage propose d’associer à chaque donnée ce qu’on appelle une clé. L’idée est qu’à partir d’une clé qui caractérise une donnée, vous puissiez retrouver la donnée, et ce, le plus vite possible. Mais où est le problème ? Il serait aisé de créer une structure de donnée contenant à la fois la donnée et la clé. Parcourez la liste en comparant la clé de chaque donnée avec celle de référence jusqu’à l’avoir trouvée. Pour de petites listes, ceci est faisable. Si vous passez à des listes un peu plus grandes, le temps de parcours ralentit sérieusement les choses.

Le principe d’une table de hachage

Le principe d’une table de hachage est fondamentalement différent. Mais c’est celui que, inconsciemment, vous connaissez le mieux. Quand vous devez ranger un objet chez vous, afin de le retrouver plus tard, où le rangez-vous ? Sur une pile d’objets ? Non, vous réfléchissez sans vous en apercevoir à l’endroit où vous iriez le chercher. C’est à cet endroit où vous le récupéreriez que vous allez le mettre. Les tables de hachage fonctionnent suivant ce même principe. A une table de hachage est associée une fonction qui, à partir d’une clé associée à une donnée, calcule une valeur. C’est elle qu’on appelle le hachage, ou hash en anglais. Cette valeur n’est rien d’autre qu’un index pour un tableau, dans lequel vous allez placer votre donnée. Plus tard, quand vous voudrez récupérer la donnée, indiquez votre clé, calculez sa valeur de hachage, et retrouvez votre donnée à l’endroit indiqué par le hachage. Prenons un exemple : vous souhaitez stocker les numéros de téléphone de vos amis dans une table de hachage. Vous prenez leur nom comme clé. Pour la fonction de hachage, vous choisissez le numéro de la première lettre du nom (A=0, B=1...). Votre table de hachage aura ainsi 26 entrées. Cet exemple nous montre deux choses :

• C’est la fonction de hachage, par son ensemble de sortie, qui définit la taille de la table de hachage ;
• Il est possible d’avoir une même valeur de hachage pour des données distinctes.

Lorsque deux données ont le même hachage, elles sont en général stockées sous forme de liste chaînée démarrant à l’endroit pointé par le hachage. Ainsi, à l’indice 15 (la lettre P de Pierre et Paul), si vous trouvez Pierre alors que vous cherchiez Paul, regardez derrière Pierre et vous devriez le trouver. Cette illustration montre d’ailleurs toute l’importance du choix d’une bonne table de hachage. En effet, la nôtre n’est pas géniale : vous allez surcharger la liste chaînée démarrant en position 15 avec Pierre, Paul, Pénélope, Philippe et Philomène, alors qu’à la lettre W, il n’y a personne dans votre entourage. Par ailleurs, la fonction de hachage définissant la taille de la table, il est bon de penser à l’avance au nombre de données que vous allez y stocker. Si votre carnet d’adresse n’est que de 20 personnes, vous pouvez avoir une table de taille entre 5 et 10. Si au contraire vous voulez concurrencer l’annuaire téléphonique, prévoyez une table bien plus grande. Le tout est d’avoir la liste chaînée la plus petite à parcourir une fois le hachage calculé. Dans la suite de l’article, nous utiliserons le terme nœud à la place du terme donnée pour mieux coller aux termes informatiques. Un nœud contient une valeur correspondant à votre donnée et une clé caractérisant le nœud.

 

Remarque :

Cet article est basé sur la version 2.12.4 de glib.

Les tables de hachage dans glib

Une table de hachage, dans glib, est associée au type GHashTable. Voici sa définition dans glib/ghash.h.

01 typedef struct _GHashTable  GHashTable;

Le véritable code se trouve dans glib/ghash.c :

01 struct _GHashTable
02 {
03   gint             size;
04   gint             nnodes;
05   GHashNode      **nodes;
06   GHashFunc        hash_func;
07   GEqualFunc       key_equal_func;
08   volatile guint   ref_count;
09   GDestroyNotify   key_destroy_func;
10   GDestroyNotify   value_destroy_func;
11 };

A part GHashNode que nous voyons ci-dessous, nous allons étudier cette structure plus loin, avec la fonction g_hash_table_new() qui permet de créer une table de hachage.

01 typedef struct _GHashNode      GHashNode;
02 
03 struct _GHashNode
04 {
05   gpointer   key;
06   gpointer   value;
07   GHashNode *next;
08 };

Vous voyez dans cette structure GHashNode que nous avons bien d’une part l’association entre une clé (ligne 5) et une valeur (ligne 6), et un bon indice comme quoi nous aurons affaire à des listes chaînées simples (ligne 7 avec la présence du pointeur next).

Fig. 1 : Table de hachage

g_hash_table_new()

Étudions la structure _GHashNode à l’aide de la fonction g_hash_table_new() :

01 GHashTable*
02 g_hash_table_new (GHashFunc    hash_func,
03                   GEqualFunc   key_equal_func)
04 {
05   return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
06 }

Il s’agit en fait d’un appel à g_hash_table_new_full() simplifié, avec NULL pour la fonction de destruction des clés et pour celle des valeurs.

01 GHashTable*
02 g_hash_table_new_full (GHashFunc       hash_func,
03                        GEqualFunc      key_equal_func,
04                        GDestroyNotify  key_destroy_func,
05                        GDestroyNotify  value_destroy_func)
06 {
07   GHashTable *hash_table;
08   
09   hash_table = g_slice_new (GHashTable);
10   hash_table->size               = HASH_TABLE_MIN_SIZE;
11   hash_table->nnodes             = 0;
12   hash_table->hash_func          = hash_func ? hash_func : g_direct_hash;
13   hash_table->key_equal_func     = key_equal_func;
14   hash_table->ref_count          = 1;
15   hash_table->key_destroy_func   = key_destroy_func;
16   hash_table->value_destroy_func = value_destroy_func;
17   hash_table->nodes              = g_new0 (GHashNode*, hash_table->size);
18   
19   return hash_table;
20 }

En premier lieu, ligne 9, un petit espace mémoire est alloué pour stocker les informations relatives à la table de hachage. C’est tout l’intérêt de la structure GHashTable. La suite consiste à remplir cette structure avec des valeurs par défaut. Une table de hachage a, comme nous l’avons vu, une taille, qui est définie par l’ensemble de sortie de la fonction de hachage. Cependant, glib n’est pas en mesure de connaître cette taille. Aussi, plutôt que d’ennuyer le programmeur à calculer et indiquer cette taille, elle préfère choisir une taille minimale initiale, quitte à redimensionner l’ensemble plus tard. C’est pourquoi vous trouvez un champ size dans la structure GHashTable (ligne 10). Du coup, comme nous le verrons plus loin, la véritable fonction de hachage est celle indiquée en argument, modulo cette taille. Une table de hachage, lors de sa création, est vide (ligne 11). Une fonction de hachage lui est toujours associée, au point d’y faire figurer un pointeur dessus dans la structure GHashTable (ligne 12). Si le programmeur oublie d’indiquer cette fonction, la fonction g_direct_hash() est choisie par défaut. Nous allons revenir sur son code au paragraphe suivant. Il faut également fournir une fonction de test d’égalité entre deux clés (ligne 13). Par exemple, vous ne pouvez pas utiliser le même test pour un nombre et pour une chaîne de caractères. Ligne 14, vous voyez le nombre de références à la table de hachage. Cette valeur ne sert que pour la gestion des objets propres à glib. Lignes 15 et 16 apparaissent des fonctions de destruction des clés et valeurs. En effet, lors de la destruction d’une table de hachage, il faut également détruire les clés et valeurs. Si vous avez indiqué NULL pour ces valeurs (vous-même ou par l’intermédiaire de g_hash_table_new()), vous devrez faire le nettoyage vous-même auparavant. Enfin, ligne 17 est alloué l’espace mémoire nécessaire à chacun des premiers nœuds de chaque entrée de la table.

Fonctions de hachage

g_direct_hash()

Cette fonction est celle utilisée par défaut par les GHashTable. Comme les suivantes, elle se trouve dans le fichier glib/gutils.c.

01 guint
02 g_direct_hash (gconstpointer v)
03 {
04   return GPOINTER_TO_UINT (v);
05 }

Cette fonction ne fait pas autre chose que de convertir un pointeur en entier non signé. Quand vous ne disposez pas de plus d’informations, vous faites avec ce que vous avez...

g_int_hash()

Cette fonction est dédiée aux données se présentant sous forme d’entiers.

01 guint
02 g_int_hash (gconstpointer v)
03 {
04   return *(const gint*) v;
05 }

Cette fonction ressemble étrangement à la précédente. En effet, la seule information dont nous disposons est que nous avons affaire à des entiers. Comme nous ne disposons d’aucune information sur la distribution des clés par rapport aux valeurs possibles, le mieux est de supposer une distribution uniforme. Si ce n’est pas le cas, c’est à la charge du développeur de fournir sa propre fonction de hachage.

g_str_hash()

Cette fonction se trouve dans glib/gstring.c contrairement aux précédentes.

01 guint
02 g_str_hash (gconstpointer v)
03 {
04   /* 31 bit hash function */
05   const signed char *p = v;
06   guint32 h = *p;
07 
08   if (h)
09     for (p += 1; *p != ‘\0’; p++)
10       h = (h << 5) - h + *p;
11 
12   return h;
13 }

Ce code n’est pas simple à comprendre. Pourtant, vous le retrouverez souvent dans les fonctions de hachage des chaînes de caractères sans aucune indication sur la distribution. Dans ce code, nous travaillons avec p qui pointe sur le caractère courant, et avec h, le hachage, qui prend pour valeur initiale celle du premier caractère (lignes 5 et 6). Si ce caractère est nul, la chaîne est vide (ligne 8) et nous pouvons renvoyer 0 comme hachage. Sinon, déchiffrons la boucle lignes 9 et 10. La boucle, ligne 9, porte sur tous les caractères de la chaîne. Nous allons donc, ligne 10, modifier notre hachage h en fonction de chaque caractère. Pour chacun d’eux, nous modifions le hachage en l’état par une multiplication par 2^5 (le décalage à gauche avec l’opérateur <<) à laquelle nous ajoutons l’opposé du hachage, puis le caractère. Le hachage final est donc le n-ième terme de la série suivante :

h0 = p[0]
hi = hi-1 x 25 - hi-1 + p

Soit, en plus simple et avec a=25-1 :

h0 = p[0]
hi = hi-1 x a + p

Partons des polynômes Pn(C) suivants (C signifiant Chaîne de caractères bien entendu) :

Pn(C) = p0 + a.p1 + a2.p2 + ... + an.pn

Pour une chaînée C donnée, et sur le papier, nous avons bien h = Pn(C). L’intérêt d’une telle fonction polynomiale est que, avec des caractères de 0 à 255, Pn(C) est caractéristique d’une chaîne C si a est supérieur ou égal à 256. Les plus malins auront remarqué qu’avec a=256, nous sommes en base 256 et Pn(C) n’est autre que ce qui est pointé par la chaîne, encore faudrait-il afficher ce résultat en décimal et non en ASCII ! Mais voilà, ligne 6, vous lisez que le type de notre hachage h est guint32. Nous n’avons donc pas h = Pn(C) comme nous l’avions fièrement trouvé plus haut, mais peut-être h = Pn(C) mod 232, encore faudrait-il le prouver :

h0 = p[0]
hi = ( hi-1 x a + p ) mod 232

et donc, en utilisant la propriété (a mod b) mod b = a mod b, nous obtenons les polynômes suivants qui ne ressemblent presque plus aux polynômes Pn(C) :

( p0 + (a.p1) mod 232 + (a2.p2) mod 232 + ... + (an.pn) mod 232 ) mod 232

c’est-à-dire, avec la propriété (a + b) mod n = (a mod n + b mod n) mod n :

(p0 + a.p1 + a2.p2 + ... + an.pn) mod 232

Ouf, nous avons réussi à nous y retrouver : h = Pn(C) mod 232. Cet opérateur modulo nous cause bien des soucis. En effet, si nous choisissons a=256, soit a=28, nous nous privons de la valeur de certains caractères pour notre calcul de hachage. Typiquement, tous les caractères de position supérieure à 4 et multiples de 4 seraient ignorés à cause de leur caractère divisible par 232. Pire, vu notre façon de calculer à l’aide d’une suite, nous ne prendrions en compte que les 4 derniers caractères. Il nous faut donc une valeur de a qui soit à la fois supérieure à 256 et première avec 232, par exemple 257. Cependant, les développeurs ont fait un autre choix. Ils ont préféré la valeur 31 (25 - 1) qui affiche bien un caractère premier avec 232, mais qui est inférieure à 256. Leur choix peut s’expliquer par le fait que la fonction de hachage doit d’abord être rapide à calculer, mais aussi éviter les collisions (deux chaînes différentes ayant le même hachage). Or, 31 dispose de ces caractéristiques. Il est facile de calculer avec cette valeur comme vous le constatez dans le code (ligne 10). De plus, les caractères ASCII et en particulier les lettres sont des séries de 26 lettres, l’une commençant à 26+1 pour les majuscules, et l’autre à 27+1 pour les minuscules. Avec 31, les chances de collisions sont faibles.

Rechercher une clé

Lorsque vous lirez le code d’insertion d’un nœud dans la table, vous verrez que nous commençons par rechercher si elle n’y est pas déjà, et sinon à l’insérer là où nous l’aurions trouvée si elle y était. Par conséquent, nous allons d’abord nous intéresser à la recherche d’une clé.

01 gpointer
02 g_hash_table_lookup (GHashTable    *hash_table,
03                      gconstpointer key)
04 {
05   GHashNode *node;
06   
07   g_return_val_if_fail (hash_table != NULL, NULL);
08   
09   node = *g_hash_table_lookup_node (hash_table, key);
10   
11   return node ? node->value : NULL;
12 }

Cette fonction est, comme vous en avez pris l’habitude d’en voir dans glib, une interface à la véritable fonction que vous trouvez ligne 9. Nous pouvons déjà déduire, d’après la ligne 11, que g_hash_table_lookup_node() recherche un nœud par sa clé key et renvoie un GHashNode** qui est soit le nœud, soit NULL s’il n’a pas été trouvé. Contrairement à g_hash_table_lookup_node(), g_hash_table_lookup() renvoie la valeur et non un pointeur sur le GHashNode correspondant.

01 static inline GHashNode**
02 g_hash_table_lookup_node (GHashTable     *hash_table,
03                           gconstpointer  key)
04 {
05   GHashNode **node;
06   
07   node = &hash_table->nodes
08     [(* hash_table->hash_func) (key) % hash_table->size];
09   
10   /* Hash table lookup needs to be fast.
11    *  We therefore remove the extra conditional of testing
12    *  whether to call the key_equal_func or not from
13    *  the inner loop.
14    */
15   if (hash_table->key_equal_func)
16     while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
17       node = &(*node)->next;
18   else
19     while (*node && (*node)->key != key)
20       node = &(*node)->next;
21   
22   return node;
23 }

Nous voici dans le cœur du problème : la recherche d’une donnée à l’aide de la fonction de hachage dont nous nous servons dès la ligne 7. C’est sur cette même ligne que vous voyez que la véritable fonction de hachage est celle indiquée dans la structure GHashTable modulo la taille de la table, soit (* hash_table->hash_func) (key) % hash_table->size. Le résultat de cette fonction pour la clé key est le hachage, à savoir l’indice du tableau hash_table->nodes[] où se trouve le nœud ou l’endroit où l’insérer. Nous stockons un pointeur vers cet endroit dans *node. A partir de maintenant, nous nous intéressons à *node et à la liste chaînée qui se trouve derrière. Lignes 16 et 17, ou 19 et 20, nous allons la parcourir à la recherche du nœud. Deux cas se présentent : soit nous disposons d’une fonction de comparaison (hash_table->key_equal_func) et nous exécutons la boucle lignes 16 et 17, soit nous n’en disposons pas et disposons de la simple égalité de pointeurs ligne 19 (et 20 pour la boucle). Tant que *node pointe sur quelque chose et que la clé n’est pas celle que nous cherchons (lignes 16 ou 19), nous itérons en faisant pointer *node vers la cellule suivante (lignes 17 ou 20). Enfin, nous retournons node qui, en tant que GHashNode**, pointe forcément vers l’endroit où devrait se trouver la donnée, qu’elle y soit ou non. Si elle y est, *node pointe le nœud la contenant. Sinon, *node est NULL.

Insérer une donnée

La fonction précédente, g_hash_table_lookup_node(), a ceci d’intéressant que, dans tous les cas, elle retourne l’endroit où devrait se trouver la donnée. En l’utilisant, il ne reste ensuite qu’à insérer ou remplacer une cellule dans la liste chaînée sur laquelle elle pointe.

01 void
02 g_hash_table_insert (GHashTable *hash_table,
03                      gpointer         key,
04                      gpointer         value)
05 {
06   GHashNode **node;
07   
08   g_return_if_fail (hash_table != NULL);
09   g_return_if_fail (hash_table->ref_count > 0);
10   
11   node = g_hash_table_lookup_node (hash_table, key);
12   
13   if (*node)
14     {
15       /* do not reset node->key in this place, keeping
16        * the old key is the intended behaviour. 
17        * g_hash_table_replace() can be used instead.
18        */
19 
20       /* free the passed key */
21       if (hash_table->key_destroy_func)
22         hash_table->key_destroy_func (key);
23       
24       if (hash_table->value_destroy_func)
25         hash_table->value_destroy_func ((*node)->value);
26 
27       (*node)->value = value;
28     }
29   else
30     {
31       *node = g_hash_node_new (key, value);
32       hash_table->nnodes++;
33       G_HASH_TABLE_RESIZE (hash_table);
34     }
35 }

C’est effectivement ce qu’ont fait les développeurs de glib. L’emplacement prévu du nœud est calculé ligne 11 avec le pointeur node. Si son contenu est plein, (ligne 13), nous remplaçons sa valeur (ligne 27), après avoir détruit (ligne 25) celle existant avec la fonction hash_table->value_destroy_func si celle-ci a été fournie (test ligne 24). Par contre, la clé est laissée en place et c’est celle fournie en argument de g_hash_table_insert() qui est détruite (ligne 22), avec hash_table->key_destroy_func si (test ligne 21), comme pour la valeur, cette fonction a été fournie. Si au contraire *node est NULL, il faut créer un nouveau GHashNode, dont le pointeur est directement mis au bon endroit (ligne 31), dans le pointeur *node, vu que node est un pointeur de pointeur ! Ce genre d’écriture n’est pas très courant en C, aussi n’hésitez pas à passer un peu de temps pour bien comprendre cette mécanique de double pointeurs. Le nombre de nœuds est incrémenté ligne 32. Enfin, la table est redimensionnée si nécessaire avec la macro G_HASH_TABLE_RESIZE(). Intéressons-nous à cette macro. En effet, une particularité de glib est de proposer une implémentation de tables de hachage de taille ajustable en fonction des données !

01 #define G_HASH_TABLE_RESIZE(hash_table)                      \
02    G_STMT_START {                                            \
03      if ((hash_table->size >= 3 * hash_table->nnodes &&      \
04        hash_table->size > HASH_TABLE_MIN_SIZE) ||            \
05       (3 * hash_table->size <= hash_table->nnodes &&         \
06        hash_table->size < HASH_TABLE_MAX_SIZE))              \
07         g_hash_table_resize (hash_table);                    \
08    } G_STMT_END

Passons sur G_STMT_START et G_STMT_END qui ne servent qu’à ajouter un do et while(0) ou équivalent en fonction du compilateur, ce qui est une ruse classique pour éviter tout problème de syntaxe à l’utilisation de la macro. Si vous voulez en savoir plus, reportez-vous au fichier glib/gmacros.h qui définit ces deux macros. Cette macro est en fait juste un test pour déterminer s’il faut appeler la fonction g_hash_table_resize() (ligne 7). Le test est positif dans deux cas. Soit la taille de la table est trois fois plus grande que le nombre de nœuds (ligne 3) et nous n’avons pas atteint la taille minimale (ligne 4). Dans ce cas, vous vous doutez que g_hash_table_resize() diminuera la taille de la table. Soit nous sommes dans le cas inverse, avec le nombre de nœuds qui dépasse un tiers de la taille de la table (ligne 5). Si nous n’avons pas encore atteint la taille maximale (ligne 6), nous imaginons que dans ce cas g_hash_table_resize() augmentera la taille de la table. Voyons maintenant g_hash_table_resize() :

01 static void
02 g_hash_table_resize (GHashTable *hash_table)
03 {
04   GHashNode **new_nodes;
05   GHashNode *node;
06   GHashNode *next;
07   guint hash_val;
08   gint new_size;
09   gint i;
10 
11   new_size = g_spaced_primes_closest (hash_table->nnodes);
12   new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
13  
14   new_nodes = g_new0 (GHashNode*, new_size);
15   
16   for (i = 0; i < hash_table->size; i++)
17     for (node = hash_table->nodes[i]; node; node = next)
18       {
19         next = node->next;
20 
21         hash_val = (* hash_table->hash_func) (node->key) % new_size;
22 
23         node->next = new_nodes[hash_val];
24         new_nodes[hash_val] = node;
25       }
26   
27   g_free (hash_table->nodes);
28   hash_table->nodes = new_nodes;
29   hash_table->size = new_size;
30 }

Ce code est à lire en deux fois. La première partie consiste en les lignes de 11 à 14 où la taille de la nouvelle table est calculée, puis allouée. Attention ! Nous avons affaire à une nouvelle table (ligne 14). Ce n’est pas la table actuelle qui est redimensionnée. Nous reviendrons sur le calcul de la taille plus loin. La seconde partie consiste à déplacer tous les nœuds. En effet, comme nous changeons la taille de la table, nous changeons par la même occasion la fonction de hachage. C’est comme quand vous déménagez dans une maison plus grande ou plus petite : vous devez tout réorganiser en fonction de la nouvelle place dont vous disposez. Ligne 16, nous parcourons toutes les entrées de la table. Ligne 17, pour chaque entrée, nous parcourons tous les nœuds chaînés à celui de l’entrée. La nouvelle valeur du hachage est calculée ligne 21. Le nœud est déplacé dans la nouvelle table lignes 23 et 24. Attention ! du coup, node->next ne pointe plus vers le bon endroit, puisque nous le modifions ligne 23. C’est tout l’intérêt d’en garder une copie ligne 19. Enfin, l’ancienne table est détruite ligne 27 (d’autres choisissent de louer leur ancienne maison – c’est le rôle du gestionnaire de mémoire de décider si la mémoire est libérée ou rendue disponible pour une autre demande d’allocation mémoire). Les champs nodes et size prennent leur nouvelle valeur lignes 28 et 29. Revenons sur le calcul de la taille de la table de hachage. Nous faisons d’abord appel à g_spaced_primes_closest() (le code se trouve dans glib/gprimes.c) :

01 guint
02 g_spaced_primes_closest (guint num)
03 {
04   gint i;
05 
06   for (i = 0; i < g_nprimes; i++)
07     if (g_primes[i] > num)
08       return g_primes[i];
09 
10   return g_primes[g_nprimes - 1];
11 }

Cette fonction parcourt un tableau g_primes[] (boucle ligne 6) à la recherche du premier élément supérieur à num fourni en argument (test ligne 7). S’il n’est pas trouvé, la fonction renvoie le dernier élément du tableau. En voici le contenu (pour ceux qui s’intéressent aux nombres premiers) :

01 static const guint g_primes[] =
02 {
03   11,
04   19,
05   37,
06   73,
07   109,
08   163,
09   251,
10   367,
11   557,
12   823,
13   1237,
14   1861,
15   2777,
16   4177,
17   6247,
18   9371,
19   14057,
20   21089,
21   31627,
22   47431,
23   71143,
24   106721,
25   160073,
26   240101,
27   360163,
28   540217,
29   810343,
30   1215497,
31   1823231,
32   2734867,
33   4102283,
34   6153409,
35   9230113,
36   13845163,
37 };
38 
39 static const guint g_nprimes = sizeof (g_primes) / sizeof (g_primes[0]);

Vous remarquez que les nombres premiers de ce tableau sont espacés. L’intérêt est d’agrandir la table de hachage de façon significative lorsque cela s’avère nécessaire. Pas question d’augmenter la taille un petit peu, et encore un petit peu... Par ailleurs, c’est également ici que g_nprimes est défini comme le nombre d’éléments de ce tableau. Après avoir fait appel à g_spaced_primes_closest(), g_hash_table_resize() utilise la macro CLAMP :

01 #define CLAMP(x, low, high)  (((x) > (high)) ? (high) : (((x) < (low)) ? (low) : (x)))

Cette fonction se contente de renvoyer la valeur fournie en premier argument ou, en cas de dépassement, la borne dépassée définie en argument deux ou trois. Nous n’aborderons pas le remplacement d’une donnée par une autre pour une même clé. La seule différence de code entre g_hash_table_replace() et g_hash_table_insert() est que l’ancienne clé est détruite et remplacée par la nouvelle au lieu de détruire la clé fournie en argument.

Supprimer une donnée

Pour supprimer une donnée, utilisez g_hash_table_remove() :

01 gboolean
02 g_hash_table_remove (GHashTable           *hash_table,
03                      gconstpointer  key)
04 {
05   GHashNode **node, *dest;
06   
07   g_return_val_if_fail (hash_table != NULL, FALSE);
08   
09   node = g_hash_table_lookup_node (hash_table, key);
10   if (*node)
11     {
12       dest = *node;
13       (*node) = dest->next;
14       g_hash_node_destroy (dest, 
15                            hash_table->key_destroy_func,
16                            hash_table->value_destroy_func);
17       hash_table->nnodes--;
18   
19       G_HASH_TABLE_RESIZE (hash_table);
20 
21       return TRUE;
22     }
23 
24   return FALSE;
25 }

Avant de supprimer un nœud, il faut savoir où il se trouve. C’est la raison de l’appel à g_hash_table_lookup_node() ligne 9. Puis, s’il existe, il est retiré de la liste chaînée (lignes 12 et 13), puis est détruit avec g_hash_node_destroy() ligne 14. Le nombre de nœuds s’en trouve décrémenté (ligne 17). Enfin, comme à chaque opération d’ajout ou de retrait d’une donnée, une vérification a lieu sur la taille de la table. Faut-il la réduire (ligne 19) ? Pour détruire un nœud, nous avons appelé g_hash_node_destroy() :

01 static void
02 g_hash_node_destroy (GHashNode      *hash_node,
03                      GDestroyNotify  key_destroy_func,
04                      GDestroyNotify  value_destroy_func)
05 {
06   if (key_destroy_func)
07     key_destroy_func (hash_node->key);
08   if (value_destroy_func)
09     value_destroy_func (hash_node->value);
10   g_slice_free (GHashNode, hash_node);
11 }

Cette fonction appelle les fonctions de destruction pour la clé et la valeur si elles existent. Puis un appel au gestionnaire de mémoire avec g_slice_free() libère la zone allouée au nœud.

Supprimer une table

Pour supprimer une table de hachage, appelez g_hash_table_destroy() :

01 void
02 g_hash_table_destroy (GHashTable *hash_table)
03 {
04   g_return_if_fail (hash_table != NULL);
05   g_return_if_fail (hash_table->ref_count > 0);
06   
07   g_hash_table_remove_all (hash_table);
08   g_hash_table_unref (hash_table);
09 }

Cette fonction, après avoir vérifié entre autres que la table est encore référencée (ligne 5), se charge de tout supprimer avec g_hash_table_remove_all() (ligne 6). Le nombre de références est alors décrémenté (ligne 8). Intéressons-nous à g_hash_table_remove_all() :

01 void
02 g_hash_table_remove_all (GHashTable *hash_table)
03 {
04   guint i;
05 
06   g_return_if_fail (hash_table != NULL);
07 
08   for (i = 0; i < hash_table->size; i++)
09     {
10       g_hash_nodes_destroy (hash_table->nodes[i],
11                             hash_table->key_destroy_func,
12                             hash_table->value_destroy_func);
13       hash_table->nodes[i] = NULL;
14     }
15   hash_table->nnodes = 0;
16   
17   G_HASH_TABLE_RESIZE (hash_table);
18 }

Cette fonction parcourt tous les nœuds de la table (boucle ligne 8) pour les détruire avec g_hash_nodes_destroy(). L’entrée vers le nœud est mise à NULL (ligne 13). Pourquoi faire cela ? Pourquoi indiquer un nombre de nœuds nul ligne 15 et redimensionner la table ligne 17 ? Relisez le nom de la fonction : il s’agit ici de supprimer toutes les données, mais pas la table. Comme le coût de redimensionnement d’une table de hachage vide est plutôt faible, il est tout à fait acceptable que ces opérations soit effectuées bien qu’elles soient inutiles dans notre cas. Remarquez que nodes est au pluriel : ce n’est pas la fonction que nous avons vue plus haut.

01 static void
02 g_hash_nodes_destroy (GHashNode *hash_node,
03                       GFreeFunc  key_destroy_func,
04                       GFreeFunc  value_destroy_func)
05 {
06   while (hash_node)
07     {
08       GHashNode *next = hash_node->next;
09       if (key_destroy_func)
10         key_destroy_func (hash_node->key);
11       if (value_destroy_func)
12         value_destroy_func (hash_node->value);
13       g_slice_free (GHashNode, hash_node);
14       hash_node = next;
15     }
16 }

Cette fonction supprime tous les nœuds d’une entrée. Tant qu’il y a des nœuds (ligne 6), nous itérons ligne 14 (avec une préparation ligne 8 pour garder trace de hash_node->next), puis exécutons le même code que nous avions vu dans g_hash_node_destroy() : suppression de la clé, de la valeur et libération de l’espace mémoire consacré au nœud.

Parcourir tous les nœuds de la table de hachage

Maintenant que vous avez vu comment glib parcourt tous les nœuds pour les supprimer, peut-être souhaitez-vous les parcourir aussi, mais pour exécuter une autre action dessus ? Dans ce cas, munissez-vous d’une fonction correspondant à cette action, et fournissez-la en argument à g_hash_table_foreach() :

01 void
02 g_hash_table_foreach (GHashTable *hash_table,
03                       GHFunc          func,
04                       gpointer          user_data)
05 {
06   GHashNode *node;
07   gint i;
08   
09   g_return_if_fail (hash_table != NULL);
10   g_return_if_fail (func != NULL);
11   
12   for (i = 0; i < hash_table->size; i++)
13     for (node = hash_table->nodes[i]; node; node = node->next)
14       (* func) (node->key, node->value, user_data);
15 }

Comme vous pouviez vous en douter, une première boucle parcourt les entrées de la table (ligne 12) et pour chaque entrée, une deuxième boucle se charge des listes chaînées liées aux entrées (ligne 13). A l’intérieur de cette double boucle est appelée votre fonction (ligne 14). Simple, non ? Pourtant, si vous voulez supprimer des nœuds de la table en fonction d’un critère, cette fonction est inadaptée. En effet, vous risqueriez de perturber les boucles ! Pour cela, utilisez plutôt g_hash_table_foreach_remove() :

01 guint
02 g_hash_table_foreach_remove (GHashTable        *hash_table,
03                              GHRFunc         func,
04                              gpointer         user_data)
05 {
06   g_return_val_if_fail (hash_table != NULL, 0);
07   g_return_val_if_fail (func != NULL, 0);
08   
09   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
10 }

Nous avons encore affaire à une fonction qui en appelle une autre, g_hash_table_foreach_remove_or_steal(), qui parcourt réellement la table et, en fonction du dernier argument, dans notre cas à TRUE, supprime (ou sinon détache sans supprimer) le nœud.

01 static guint
02 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
03                                       GHRFunc          func,
04                                       gpointer          user_data,
05                                       gboolean    notify)
06 {
07   GHashNode *node, *prev;
08   gint i;
09   guint deleted = 0;
10   
11   for (i = 0; i < hash_table->size; i++)
12     {
13     restart:
14       
15       prev = NULL;
16       
17       for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
18         {
19           if ((* func) (node->key, node->value, user_data))
20             {
21               deleted += 1;
22               
23               hash_table->nnodes -= 1;
24               
25               if (prev)
26                 {
27                   prev->next = node->next;
28                   g_hash_node_destroy (node,
29                              notify ? hash_table->key_destroy_func : NULL,
30                              notify ? hash_table->value_destroy_func : NULL);
31                   node = prev;
32                 }
33               else
34                 {
35                   hash_table->nodes[i] = node->next;
36                   g_hash_node_destroy (node,
37                              notify ? hash_table->key_destroy_func : NULL,
38                              notify ? hash_table->value_destroy_func : NULL);
39                   goto restart;
40                 }
41             }
42         }
43     }
44   
45   G_HASH_TABLE_RESIZE (hash_table);
46   
47   return deleted;
48 }

Cette fonction présente, comme g_hash_table_foreach(), une boucle sur les entrées de la table (ligne 11) et une boucle imbriquée (ligne 17). Cependant, vous voyez un label ligne 13. Cela sent le goto ! En effet, si le test effectué sur le nœud courant par la fonction utilisateur (ligne 19) est positif, il faut supprimer le nœud. Si, de plus, ce nœud était le premier de l’entrée, donc le premier de la liste, il est plus rapide de sortir de la boucle et de recommencer avec un goto tel que ligne 39 que de modifier les variables node et prev dans un sens puis, via l’itération ligne 17 dans l’autre. Ceci est un exemple de goto utilisé à bon escient. Remarquez par ailleurs que le nombre de nœuds dans la table est décrémenté à chaque suppression ligne 23. Deux lignes auparavant, nous comptons le nombre de nœuds supprimés afin de le renvoyer ligne 47, et par ailleurs par g_hash_table_foreach_remove(). Enfin, ligne 45, comme après chaque modification de la taille de la table de hachage, elle est revue et modifiée si nécessaire.

Quelle est la taille de votre table ?

Vous pouvez la connaître via votre_table->nnodes. Cependant, mieux vaut utiliser la fonction adéquate g_hash_table_size() :

01 guint
02 g_hash_table_size (GHashTable *hash_table)
03 {
04   g_return_val_if_fail (hash_table != NULL, 0);
05   
06   return hash_table->nnodes;
07 }

Pas de surprise, c’est bien de cela qu’il s’agit (ligne 6). Mais cette fonction vous offre un test de l’existence de la table en prime. De plus, si le champ nnodes venait à changer, vous devriez modifier toutes vos sources, alors qu’avec un appel à g_hash_table_size(), glib vous garantit le résultat.

Chercher une donnée en fonction d’un prédicat

Vous savez parcourir une table avec g_hash_table_foreach(). Mais vous ne savez pas arrêter le parcours en fonction d’un prédicat autre que l’égalité avec une clé (g_hash_table_lookup()). Pour cela, fournissez votre prédicat sous forme de fonction à g_hash_table_find() :

01 gpointer
02 g_hash_table_find (GHashTable           *hash_table,
03                    GHRFunc            predicate,
04                    gpointer            user_data)
05 {
06   GHashNode *node;
07   gint i;
08   
09   g_return_val_if_fail (hash_table != NULL, NULL);
10   g_return_val_if_fail (predicate != NULL, NULL);
11   
12   for (i = 0; i < hash_table->size; i++)
13     for (node = hash_table->nodes[i]; node; node = node->next)
14       if (predicate (node->key, node->value, user_data))
15         return node->value;       
16   return NULL;
17 }

Cette fonction, comme les nombreuses autres que nous avons vues, effectue une double boucle, l’une sur les entrées (ligne 12), et l’autre sur les nœuds de chaque entrée (ligne 13). Ainsi, pour chaque nœud, votre fonction fournie en argument est évaluée sur sa clé et sa valeur (ligne 14). Si le test est positif, nous sortons des boucles et de la fonction en renvoyant la valeur du nœud (ligne 15). Sinon, c’est ce bon vieux NULL qui est retourné (ligne 16).

 Conclusion

Les tables de hachage, au contraire des listes chaînées et des tableaux, sont une structure complexe qu’il n’est finalement pas difficile d’implémenter. Cependant, comme nous venons de le voir, le code à écrire est long, parfois fastidieux, parfois très technique. Il vaut mieux s’en remettre à des bibliothèques l’ayant déjà implémenté et se délecter de la lecture de ce code plutôt que de s’arracher les cheveux à le réécrire. Les tables de hachage sont par ailleurs une structure très utilisée. N’hésitez pas à en faire bon usage, au moins autant que les programmeurs en Perl qui utilisent les tableaux associatifs : ce sont des tables de hachage ! Mais Perl n’est pas le seul à proposer cela, et avec glib, C n’est pas en reste. Le mois prochain : les arbres binaires balancés de type GTree... Remerciements à Yann Guidon pour ses précieuses remarques sur les fonctions de hachage.

Retrouvez cet article dans : Linux Magazine 88