Fil d'Ariane
Mis à jour le mardi 25 juillet 2017
  • 40 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

Ce cours existe en livre papier.

Ce cours existe en eBook.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

Vous pouvez être accompagné et mentoré par un professeur particulier par visioconférence sur ce cours.

J'ai tout compris !

Les tables de hachage

Connectez-vous ou inscrivez-vous pour bénéficier de toutes les fonctionnalités de ce cours !

Les listes chaînées ont un gros défaut lorsqu'on souhaite lire ce qu'elles contiennent : il n'est pas possible d'accéder directement à un élément précis. Il faut parcourir la liste en avançant d'élément en élément jusqu'à trouver celui qu'on recherche. Cela pose des problèmes de performance dès que la liste chaînée devient volumineuse. Imaginez une liste chaînée de 1 000 éléments où celui que l'on recherche est tout à la fin !

Les tables de hachage représentent une autre façon de stocker des données. Elles sont basées sur les tableaux du langage C que vous connaissez bien, dorénavant. Leur gros avantage ? Elles permettent de retrouver instantanément un élément précis, que la table contienne 100, 1 000, 10 000 cases ou plus encore !

Pourquoi utiliser une table de hachage ?

Partons du problème que peuvent nous poser les listes chaînées. Celles-ci sont particulièrement souples, nous avons pu le constater : il est possible d'ajouter ou de supprimer des cases à tout moment, alors qu'un tableau est « figé » une fois qu'il a été créé.

Toutefois, comme je vous le disais en introduction, les listes chaînées ont quand même un gros défaut : si on cherche à récupérer un élément précis de la liste, il faut parcourir celle-ci en entier jusqu'à ce qu'on le retrouve !

Imaginons une liste chaînée qui contienne des informations sur des élèves : leur nom, leur âge et leur moyenne. Chaque élève sera représenté par une structureEleve

Si je veux retrouver les informations sur Luc Doncieux dans la fig. suivante, il va falloir parcourir toute la liste pour se rendre compte qu'il était à la fin !

Pour retrouver Luc Doncieux dans la liste, il faut la parcourir en entier en analysant chaque élément à partir du premier !

Dans cet exemple, notre liste chaînée ne contient que quatre éléments. L'ordinateur retrouvera Luc Doncieux très rapidement avant que vous n'ayez eu le temps de dire « ouf ». Mais imaginez maintenant que celui-ci se trouve à la fin d'une liste chaînée contenant 10  000 éléments ! Ce n'est pas acceptable de devoir parcourir jusqu'à 10 000 éléments pour retrouver une information. C'est là que les tables de hachage entrent en jeu.

Qu'est-ce qu'une table de hachage ?

Si vous vous souvenez bien, les tableaux ne connaissaient pas ce problème. Ainsi, pour accéder à l'élément d'indice 2 dans mon tableau, il me suffisait d'écrire ceci :

int tableau[4] = {12, 7, 14, 33};
printf("%d", tableau[2]);

Si on lui donnetableau[2], l'ordinateur va directement à la case mémoire où se trouve stocké le nombre 14. Il ne parcourt pas les cases du tableau une à une.

Tu es en train de dire que les tableaux ne sont « pas si mauvais », en fait ? Mais dans ce cas, on perd l'avantage des listes chaînées qui nous permettaient d'ajouter et de retirer des cases à tout moment !

En effet, les listes chaînées sont plus flexibles. Les tableaux, eux, permettent un accès plus rapide. Les tables de hachage constituent quelque part un compromis entre les deux.

Il y a un défaut important avec les tableaux dont on n'a pas beaucoup parlé jusqu'ici : les cases sont identifiées par des numéros qu'on appelle des indices. Il n'est pas possible de demander à l'ordinateur : « Dis-moi quelles sont les données qui se trouvent à la case "Luc Doncieux" ». Pour retrouver l'âge et la moyenne de Luc Doncieux, on ne peut donc pas écrire :

tableau["Luc Doncieux"];

Ce serait pourtant pratique de pouvoir accéder à une case du tableau rien qu'avec le nom ! Eh bien avec les tables de hachage, c'est possible.

Puisque notre tableau doit forcément être numéroté par des indices, comment fait-on pour retrouver le bon numéro de case si on connaît seulement le nom « Luc Doncieux » ?

Bonne remarque. En effet, un tableau reste un tableau et celui-ci ne fonctionne qu'avec des indices numérotés. Imaginez un tableau correspondant à la fig. suivante : chaque case a un indice et possède un pointeur vers une structure de typeEleve. Cela, vous savez déjà le faire.

Un simple tableau contenant des pointeurs vers des structures Eleve

Si on veut retrouver la case correspondant à Luc Doncieux, il faut pouvoir transformer son nom en indice du tableau. Ainsi, il faut pouvoir faire l'association entre chaque nom et un numéro de case de tableau :

  • Julien Lefebvre = 0 ;

  • Aurélie Bassoli = 1 ;

  • Yann Martinez = 2 ;

  • Luc Doncieux = 3.

On ne peut écriretableau["Luc Doncieux"]comme je l'ai fait précédemment. Ce n'est pas valide en C.

La question est : comment transformer une chaîne de caractères en numéro ? C'est toute la magie du hachage. Il faut écrire une fonction qui prend en entrée une chaîne de caractères, fait des calculs avec, puis retourne en sortie un numéro correspondant à cette chaîne. Ce numéro sera l'indice de la case dans notre tableau (fig. suivante).

La fonction de hachage génère un indice correspondant au nom envoyé en paramètre

Écrire une fonction de hachage

Toute la difficulté consiste à écrire une fonction de hachage correcte. Comment transformer une chaîne de caractères en un nombre unique ?

Tout d'abord, mettons les choses au clair : une table de hachage ne contient pas 4 cases comme sur mes exemples, mais plutôt 100, 1 000 ou même plus. Peu importe la taille du tableau, la recherche de l'élément sera aussi rapide.

Imaginons donc un tableau de 100 cases dans lequel on va stocker des pointeurs vers des structuresEleve.

Eleve* tableau[100];

Nous devons écrire une fonction qui, à partir d'un nom, génère un nombre compris entre 0 et 99 (les indices du tableau). C'est là qu'il faut être inventif. Il existe des méthodes mathématiques très complexes pour « hacher » des données, c'est-à-dire les transformer en nombres.

Vous pouvez inventer votre propre fonction de hachage. Ici, pour faire simple, je vous propose tout simplement d'additionner les valeurs ASCII de chaque lettre du nom, c'est-à-dire pour Luc Doncieux faire la somme suivante :

'L' + 'u' + 'c' + ' ' + 'D' + 'o' + 'n' + 'c' + 'i' + 'e' + 'u' + 'x'

On va toutefois avoir un problème : cette somme dépasse 100 ! Comme notre tableau ne fait que 100 cases, si on s'en tient à ça, on risque de sortir des limites du tableau.
Je vous rappelle que chaque lettre dans la table ASCII peut être numérotée jusqu'à 255. On a donc vite fait de dépasser 100.

Pour régler le problème, on peut utiliser l'opérateur modulo%. Vous vous souvenez de lui ? Il donne le reste de la division ! Si on fait le calcul :

sommeLettres % 100

… on obtiendra forcément un nombre compris entre 0 et 99. Par exemple, si la somme fait 4315, le reste de la division par 100 est 15. La fonction de hachage retournera donc 15.

Voici à quoi pourrait ressembler cette fameuse fonction :

int hachage(char *chaine)
{
    int i = 0, nombreHache = 0;

    for (i = 0 ; chaine[i] != '\0' ; i++)
    {
        nombreHache += chaine[i];
    }
    nombreHache %= 100;

    return nombreHache;
}

Si on lui envoiehachage("Luc Doncieux"), elle renvoie 55. Avechachage("Yann Martinez"), on obtient 80.

Grâce à cette fonction de hachage, vous savez donc dans quelle case de votre tableau vous devez placer vos données ! Lorsque vous voudrez y accéder plus tard pour en récupérer les données, il suffira de hacher à nouveau le nom de la personne pour retrouver l'indice de la case du tableau où sont stockées les informations !

Je vous recommande de créer une fonction de recherche qui se chargera de hacher la clé (le nom) et de vous renvoyer un pointeur vers les données que vous recherchiez. Cela donnerait par exemple :
infosSurLuc = rechercheTableHachage(tableau, "Luc Doncieux");

Gérer les collisions

Quand la fonction de hachage renvoie le même nombre pour deux clés différentes, on dit qu'il y a collision. Par exemple dans notre cas, si nous avions un anagramme de Luc Doncieux qui s'appelle Luc Doncueix, la somme des lettres est la même, donc le résultat de la fonction de hachage sera le même !

Deux raisons peuvent expliquer une collision.

  • La fonction de hachage n'est pas très performante. C'est notre cas. Nous avons écrit une fonction très simple (mais néanmoins suffisante) pour nos exemples. Les fonctions MD5 et SHA1 mentionnées plus tôt sont de bonne qualité car elles produisent très peu de collisions. Notez que SHA1 est aujourd'hui préférée à MD5 car c'est celle des deux qui en produit le moins.

  • Le tableau dans lequel on stocke nos données est trop petit. Si on crée un tableau de 4 cases et qu'on souhaite stocker 5 personnes, on aura à coup sûr une collision, c'est-à-dire que notre fonction de hachage donnera le même indice pour deux noms différents.

Si une collision survient, pas de panique ! Deux solutions s'offrent à vous au choix : l'adressage ouvert et le chaînage.

L'adressage ouvert

S'il reste de la place dans votre tableau, vous pouvez utiliser la technique dite du hachage linéaire. Le principe est simple. La case est occupée ? Pas de problème, allez à la case suivante. Ah, elle est occupée aussi ? Allez à la suivante !

Ainsi de suite, continuez jusqu'à trouver la prochaine case libre dans le tableau. Si vous arrivez à la fin du tableau, retournez à la première case et continuez.

Cette méthode est très simple à mettre en place, mais si vous avez beaucoup de collisions, vous allez passer beaucoup de temps à chercher la prochaine case libre.

Il existe des variantes (hachage double, hachage quadratique…) qui consistent à hacher à nouveau selon une autre fonction en cas de collision. Elles sont plus efficaces mais plus complexes à mettre en place.

Le chaînage

Une autre solution consiste à créer une liste chaînée à l'emplacement de la collision. Vous avez deux données (ou plus) à stocker dans la même case ? Utilisez une liste chaînée et créez un pointeur vers cette liste depuis le tableau (fig. suivante).

Si deux éléments doivent être stockés au même endroit, créez une liste chaînée !

Bien entendu, on en revient au défaut des listes chaînées : s'il y a 300 éléments à cet emplacement du tableau, il va falloir parcourir la liste chaînée jusqu'à trouver le bon.

Ici, comme vous le voyez, tout est affaire de compromis. Les listes chaînées ne sont pas toujours idéales, mais les tables de hachage ont aussi leurs limites. On peut combiner les deux pour tenter de tirer le meilleur de chacune de ces structures de données.

Quoi qu'il en soit, le point critique dans une table de hachage est la fonction de hachage. Moins elle produit de collisions, mieux c'est. À vous de trouver la fonction de hachage qui convient le mieux à votre cas !

En résumé

  • Les listes chaînées sont flexibles, mais il peut être long de retrouver un élément précis à l'intérieur car il faut les parcourir case par case.

  • Les tables de hachage sont des tableaux. On y stocke des données à un emplacement déterminé par une fonction de hachage.

  • La fonction de hachage prend en entrée une clé (ex. : une chaîne de caractères) et retourne en sortie un nombre.

  • Ce nombre est utilisé pour déterminer à quel indice du tableau sont stockées les données.

  • Une bonne fonction de hachage doit produire peu de collisions, c'est-à-dire qu'elle doit éviter de renvoyer le même nombre pour deux clés différentes.

  • En cas de collision, on peut utiliser l'adressage ouvert (recherche d'une autre case libre dans le tableau) ou bien le chaînage (combinaison avec une liste chaînée).

Vous en voulez encore ?

Pourquoi ne pas apprendre le C++ ? C'est un autre cours que j'ai écrit sur ce langage cousin du C. Si vous connaissez le C, vous ne serez pas dépaysés et vous comprendrez rapidement les premiers chapitres !
Notez que j'ai aussi rédigé un petit cours intitulé "Du C au C++" qui reprend une partie des différences entre le C et le C++.

Avec le C++, vous pourrez faire de la programmation orientée objet (POO). C'est un petit peu complexe au premier abord, mais cette façon de programmer vous permet ensuite d'être très efficace ! Vous y découvrirez notamment la bibliothèque Qt qui permet de réaliser des interfaces graphiques très complètes. :)

Un grand merci à Taurre et Pouet_forever qui ont été d'une aide précieuse en apportant au cours ses dernières révisions.

Exemple de certificat de réussite
Exemple de certificat de réussite